/*       CSC 17 Lab: Implementing Variations on Hash Maps

Study my CHMap.java (and HMap.java) classes to understand how they work.
The objective of this lab is to USE these classes as much as possible to
create your own variations of the hash table data structure, some of which
is not included in Java or in the standard libraries of most languages.  

1. Similar to a hash map is a "Hash Set".  Create a

public class HSet<T>  

to represent sets of values of type T.  A set contains exactly one copy
of each value.  The value can be any object.  Unlike a hash map, however,
the key and the value are the same.  The following code should work:

HSet<String> S = new HSet<String>();
S.add("abc"); S.add("bac"); S.add("cba"); S.add("bac"); S.add("cab");
System.out.println(S.contains("cba")); // true
S.remove("cba");
System.out.println(S.contains("cba"));	//false
System.out.println(S.size());  // should print 3

In other words, your HSet class should implement the following interface:
*/
interface FiniteSet<D>  // finite set of elements of type D
{
    boolean add(D x); // add x to set, returns true if not a duplicate
                      // i.e. if x is a duplicate, return false with no changes
    boolean contains(D x); // search for x in set
    boolean remove(D x); // remove x, returns true if something was removed
    int size();  // returns cardinality of set
}
/*
If you find yourself repeating a lot of code in my CHMap implementation, 
you're NOT DOING THIS THE RIGHT WAY.  You should figure out a way to use
a hash map to implement a hashset without redoing the details of hashing
and rehashing.

HINT 1: first create a subclass of CHMap (follow example of Idmap):

class boolmap<T> extends CHMap<T,Boolean>

(or just create an instance of  new HMap<T,Boolean>).

A Boolean is different from a boolean in that a Boolean can be null, and
we can also call .equals on a Boolean, but not a boolean.

Now think about how you can use this map to implement a hash set like above.

HINT 2: just when you think you've figured out how easy this is, there are
a few points to be careful about.  The size of your hash set is not the
same as a boolmap, because a boolmap can map a key to the boolean value
'false'.  You have to maintain your own size variable carefully.

YOU MAY NOT USE ANY java.util OR ANY OTHER PRE-DEFINED DATA STRUCTURES 
IN YOUR PROGRAM, EXCEPT AS AUTHORIZED.


======================================================================
2.  This time we are going to create a data structure that doesn't
even have an equivalent in Java (though third party libraries may have
it, which you may not use).  A bijective map, or "Bimap" is a hash map
that associates a pair of values, but one in which either value can be
used as the "key" to lookup the other.  For example, suppose we want
to create an association between letter grades and their numerical
values:

Bimap<String,Double> Gradepoint = new Bimap<String,Double>(16);
Gradepoint.set("A-", 3.7);  // map between grades and numerical values
Gradepoint.set("B+", 3.3);

Double gp = Gradepoint.get("A-"); // returns 3.7
String gr = Gradepoint.revget(3.7);  // reverse-get returns "A-"

This structure assumes that each value uniquely identifies the pair.
That is, "A-" cannot be mapped to a different value than 3.7, AND vice
versa (but the association can change).  In other words, there needs to
be a one-to-one correspondence between keys and values.  If multiple
keys can map to the same value, you should not be using this
structure. For example, if we are mapping student names to their GPAs then
we can't use a bimap because two students can certainly have the same GPA.

The idea is to create, internally, a pair of ONE-DIRECTIONAL maps. In
the case of the Gradepoint example, you need a map from Strings to
Doubles AND one from Doubles to Strings.  You also need to make sure
that the two maps are consistent.  If you change "A-" to map to 3.8
for example, in the other map you must also delete the other map's
entry for 3.7 and insert a key-value pair mapping 3.8 to "A-".

Your class should implement the following interface:
*/
interface twowaymap<TA,TB> // bijective map between values of types TA and TB
{
   void set(TA x, TB y);  // insert or change pair, x,y must be non-null
   TB get(TA x);   // (or getA) get corresponding TB value given TA value x
   TA reverse_get(TB x); // (or getB) get TA value given TB value
   void removeA(TA x); // remove pair associated with TA x
   void removeB(TB y); // remove pair associated with TB y
   int size();       // number of pairs in map.
}
/*
Here's a test function that works with my program, and you can use it
to test yours.  

    public static void test()
    {
	// bijective map between letter grades and grade point values
	Bimap<String,Double> GP = new Bimap<String,Double>(16);
	String[] Grades = {"A","A-","B+","B","B-","C+","C","C-","D+","D","F"};
	Double[] Points = {4.0,3.7,3.3,3.0,2.7,2.3,2.0,1.7,1.3,1.0,0.0};
	for(int i=0;i<Grades.length;i++) GP.set(Grades[i],Points[i]);
	for(String g:Grades) System.out.println(GP.get(g));
	for(Double p:Points) System.out.println(GP.reverse_get(p));	

	GP.set("A-",3.75); // CHANGE value of A- from 3.7 to 3.75
	GP.set("B+",3.25); // change another key/value
	GP.removeB(1.3); // remove the D+ grade

	System.out.println(GP.get("A-")); // should print 3.75
	System.out.println(GP.reverse_get(3.75)); // should print A-
	System.out.println(GP.get("D+")); // should print null

	/// THIS ONE COULD TRIP YOU UP: BE CAREFUL:
	System.out.println(GP.reverse_get(3.7)); // should print null****
	// because you already changed A- to correspond to 3.75, there
	// should be no value associated with 3.7.

	//GP.set("A+",4.0); // this will also erase value for "A". why?
	System.out.println(GP.size());  // should print 10

	// Pay special attention to case marked with **** above
    }//test
    
   For the Bimap, you can use my CHMap, HMap, or even java.util.HashMap,
   BUT YOU MAY NOT USE ANY PRE-DEFINED DATA STRUCTURE WITHOUT PERMISSION.
*/


/*
=========================
Part 3 (Challenge)

Write a version of bi-directional hash map that only requires the
first key to be unique, which means that lookup using the value (other
key) must return a set of values.  For example:
GP.set("A",4.0); GP.set("A+",4.0); // both A and A+ are worth 4.0

For this part of the assignment, reuse your own HSet class from part 1.
The hint here is to again use two one-way maps underneath, except
one of the maps should be from ValueType to HSet<Keytype>. 

Then GP.reverse_get(4.0) should return a hash set containing both "A" and
"A+".  The first key (grade in this case), however, should still only
map to a single value (the map is functional in one direction).

You should add a toarray() function to the HSet class. However
(java quirk here), when calling the function, call it like this:
Object[] A = yourmap.toarray();  // otherwise you'll get weird errors.
for(Object x:A) System.out.println(x); 
There's a way to get around this using reflection but it's too quirky
to mention.

For the optional challenge you may also use java.util.HashSet and
java.util.HashMap.  These classess implement Iterable, so you can use
a for-each loop on them.


==========================
Part 4 (Mega Challenge)

This, time you can edit the CHMap class to implement the following
enhancement to the basic closed-hashing algorithm.  In the current
implementation, in order to determine that a key is not in the table,
we have to keep rehashing until we find a null key slot.  This means
that we have to keep keys in the table even when they're no longer
associated with any values.  We can try to improve on this by
recording the *maximum* number of rehashes needed to find an open
slot.  Using the Mary-Larz-Narx example, where all three strings
hashes to the same value, suppose we inserted Mary then deleted Larz,
our table would look like this currently (under 'linear probing' rehash
function):

index    key     value
 
 i       Mary    702123456
 i+1     Larz    null
 i+2     null    null

Suppose now we look for "Narx".  We can't stop at i+1 but must
continue rehashing to at least i+2 before concluding that Narx is not
in the table.  However, if we recorded that the hash value i required
AT MOST ONE REHASH STARTING FROM i, then we can stop at i+1 (after
just one rehash) and conclude that Narx is not in the table.  As the
table gets fuller, this enhancement should improve the worst-time
performance of lookups.  We would also no longer need to keep keys
with null values (so Larz can be removed completely), which means the
slot occupied by Larz can be reused to insert another value, thus
making more efficient use of the table.  To do this, you should keep a
third array, parallel to Keys and Vals, that records the maximum
number of rehashes needed at each index.  This value should *only
increase* and never increase, except when the table is recreated
during increase-capacity.  In other words your table will now look
like this (after Mary and Larz are inserted and Larz deleted):

index    key     value         max_rehash
 
 i       Mary    702123456       1
 i+1     null    null            0

When we look up Narx, what now tells us that Narx is not in the table is
not the null key, but that we've reached the maximum number of rehashes needed
as determined by max_rehash[i].  Now suppose we inserted Mary, Larz and Narx,
and deleted Larz, our table will now look like:

index    key     value         max_rehash
 
 i       Mary    702123456       2
 i+1     null    null            0
 i+2     Narx    702123456       0

Because inserting Narx took two rehashes to find a slot, max_rehash[i]
is now 2.  We will know to keep looking for Narx by rehashing at most
twice, even though Keys[i+1] is now null.

Be careful though: now if you .set("Narx",702000111) to change the value
associated with Narx, you must not mistakenly insert a new entry into the
null slot.  The null slot can be reused if for some other string x,
hash(x)==i+1.

Implement an alternative version of CHMap.java with this enhancement.
*/