CSC 17 Lab: Trie and Trie again Download and study the Trie.java program for Tries that use Strings as keys. 1. Implement a "binary trie" data structure, in which the key is a non-negative binary number, of size up to 64 bits (type long/Long). Each node in the trie has exactly two branches, corresponding to 0 or 1. Because the way the numbers work, it's better to start with the least significant (rightmost) bit of the number: Given non-negative long n, while n>0 n%2 gives value of last bit (0 or 1) n=n/2 shifts bits to the right, remove previous least significant bit. n = n>>1; // right shift 1, same as n=n/2. n<<1 is same as n*=2; However, unlike a String, a long is ALWAYS 64 bits long! But only a certain number of bits at the end is really the key, thus to identify a long, you will need a another number to say how many bits of the number is to be treated as the key. To help you do this I've written a class for you: class BinKey { protected long key; protected int length; //number of rightmost bits that make up the actual key. public int length() { return length;} public long key() { return key; } public BinKey(long k, int l) { key=k; length=l; } public BinKey() { key=0; length=0; } // root key public BinKey(long k) // length set depending on leftmost 1 bit { key = k; length =0; while (k>0) { length++; k = k/2; // same as k >> 1 } }// constructor public int nthbit(int n) // nth bit from the right, last bit is bit 0 { if (n<0 || n>63) throw new RuntimeException("bad n in nthbit"); return (int)((key>>n)%2); // shift right then divide } // non-destructive addbit; add bit to left, bit should be 0 or 1 public BinKey addbit(int bit) { if (bit<0 || bit>1 || length>=64) throw new RuntimeException("addbit failed"); long k2=key; int l2=length+1; long power = bit << (l2-1); k2 += power; return new BinKey(k2,l2); } public String toString() { return "("+key+","+length+")"; } public boolean equals(Object x) // equality between keys { BinKey k2 = (BinKey)x; return key==k2.key && length==k2.length; } }//BinKey Each Binkey is defined by a numerical key and a length, in number of bits counted from the right. The root node of the trie should have key 0,0. Your data structure class should support all the public functions implemented by my Trie class. In particular, implement the following interface: interface BinMap { int size(); // returns number of non-null items stored in structure VT set(BinKey key, VT val); // insert key:val pair, return previous val VT get(BinKey key); // return value associated with key, null if none VT remove(BinKey key); // return and delete value associated with key } write in BinTrie.java: public class BinTrie implements BinMap {... and devise a main to test your program (add more to example) public static void main(String[] av) { BinTrie Major = new BinTrie(); Major.set(new BinKey(4),"cs"); Major.set(new BinKey(6),"cse"); Major.set(new BinKey(14),"math"); System.out.println(Major.get(new BinKey(6))); System.out.println(Major.remove(new BinKey(4))); System.out.println(Major); // should work after part 2 completed. } (part 1. OPTION). Instead of a binary trie, implement a "quad-trie" (not to be confused with a quad tree). In a quad trie the binary number is processed two digits at a time and each node has 4 branches/children. Use n%4 and n/4 to extract/shift the least significant two bits of n. /////////////////////////////////////////////////// 2. Add the following methods to your BinTrie class: a. public String toString() // prints all key:value pairs in trie b. ArrayList> prefixsearch(BinKey prefkey) Here, kvpair encapsulates a key:value pair as follows: class kvpair { public final KT key; public final VT val; public kvpair(KT k, VT v) { key=k; val=v;} public String toString() { return key+":"+val; } }//kvpair The prefixsearch function should return a collection of key:value pairs where prefkey is a "prefix" of each key. For example, key (0110,4) is a prefix of key(10110,5) and key(00110,5). Read bits from right. If keys were strings, "Alex" would be a prefix of "Alexander" and if I did a prefixsearch on "Alex", I would get an ArrayList containing the values for both "Alex" and "Alexander", as well as for all values with keys for which "Alex" is a prefix of. You are just implementing this feature for BinTries with BinKeys instead of Strings. For both toString and prefixsearch, you should emulate my node.collect(key) function. Be sure to import java.util.ArrayList; at the top. CHALLENGE: It gets a little complicated if the binary key can be negative. In the two's complement representation of integers, negative numbers are prefixed by 1, not 0. In particular, -1 is represented by 11111111 (in 8 bits), or 0xffffffff in 64 bits. -1/2 gives -1, not 0! -1%2 gives 1 (because -1 = -1*2+1), so at least that works. You will have to figure out how to adjust the algorithms to account for negative longs. For example, the BinKey.addbit function would need to subtract instead of add to the key if the bit to be added is zero. Java has no unsigned numerical types. Modify your binary (or quad) trie to allow negative integers to be used as keys.