// 3/27/01
// Mark Llewellyn & Arup Guha
// Class Description: This class provides the tools to manage a simple
//                    singly linked list.
// Main program: Uses Singly_Linked_List class to build a hash table.
import java.io.*;
import java.util.Random;

public class Hash_Table {	

    final int HASH_SIZE = 2*3*5*7*11 + 1;
    Singly_Linked_List[] hash_table;
    int[] freq;
    Random gen;

    public Hash_Table() {
	hash_table = new Singly_Linked_List[HASH_SIZE];
	freq = new int[HASH_SIZE];
	for (int i=0; i < HASH_SIZE; i++) {
	    hash_table[i] = new Singly_Linked_List();
	    freq[i] = 0;
	}
	gen = new Random();
    }

    public Math_Vector Get_Rand_Vec() {
	int x = (Math.abs(gen.nextInt()))%HASH_SIZE;
	int y = (Math.abs(gen.nextInt()))%HASH_SIZE;
	return new Math_Vector(x, y);
    }

    private int Get_Hash_Value(Math_Vector vec) {
	return (int)(Math.floor(vec.getMagnitude()))%HASH_SIZE;
    }

    public void Add(Math_Vector vec) {
	int hash_value = Get_Hash_Value(vec);
	hash_table[hash_value].insert(vec);
	freq[hash_value]++;
    }

    private void Print_List(int index) {
	hash_table[index].gotoHeader();
	while (hash_table[index].canWalk()) {
	    hash_table[index].walkForward();
	    Math_Vector cur = (Math_Vector)(hash_table[index].get_current());
	    cur.print();
	    System.out.println();   
	}
    }

    public void Print_All() {
	for (int i=0;i<HASH_SIZE; i++) {
	    Print_List(i);
	}
    }

    private boolean Find(Math_Vector vec, int hash_value) {
	hash_table[hash_value].gotoHeader();
	while (hash_table[hash_value].canWalk()) {
	    hash_table[hash_value].walkForward();
	    if (vec.equals((Math_Vector)(hash_table[hash_value].get_current())))
		return true;
	}
	return false;
    }

    public boolean Find(Math_Vector vec) {
	int hash_value = Get_Hash_Value(vec);
	return Find(vec, hash_value);
    }

    public static int menu() throws IOException {
	
	BufferedReader stdin = new BufferedReader(new InputStreamReader
						  (System.in));

	System.out.println("Choose an option.");
	System.out.println("1. Find a vector.");
	System.out.println("2. Print out all vectors.");
	System.out.println("3. Quit.");
	int choice = Integer.parseInt(stdin.readLine());
	return choice;
    }

    public static void main(String[] args) throws IOException {

	BufferedReader stdin = new BufferedReader(new InputStreamReader
						  (System.in));

	Hash_Table vectors = new Hash_Table();
	System.out.println("How many random vectors would you like to add?");
	int num = Integer.parseInt(stdin.readLine());

	for (int i=0; i < num; i++)
	    vectors.Add(vectors.Get_Rand_Vec());

	boolean done = false;
	while (!done) {
	    int choice = menu();
	    if (choice == 1) {
		System.out.println("Enter the vector you are searching for.");
		int x = Integer.parseInt(stdin.readLine());
		int y = Integer.parseInt(stdin.readLine());
		if (vectors.Find(new Math_Vector(x,y)))
		    System.out.println("It is stored.");
		else
		    System.out.println("It is not in the hash table.");
	    }
	    else if (choice == 2) {
		vectors.Print_All();
	    }
	    else if (choice == 3)
		done = true;
	    else
		System.out.println("Not a valid menu choice. Try again.");
	}
    }
} // end Hash_Table