The Trie class is to have methods insert(Lexicographical), traverse(), and a constructor that builds an empty trie. The constructor should take an integer argument representing the number of subtrees of a nonleaf node.

The LexUtils class is to have static void methods radixSort(Lexicographical[], int) and bucketSort(Lexicographical[]) that respectively implement bottom-up and top-down bucket sort (bin sort). Both methods should leave the sorted sequence in the input array. The extra parameter for radixsort specifies the number of passes that the algorithm should perform. Note that if this number is small enough, the radixsort algorithm will not completely sort the input sequence.

The sorting algorithms needn't treat small input sequences specially (except for size 0 and perhaps size 1).

Attempts at duplicate insertions into a trie should be ignored -- but make sure that you can insert proper prefixes and suffixes of items already in the tree. However all copies of duplicate elements should appear in the result of both radixsort and bucketsort. Note that the Lexicographical interface does not specify an equals? method, so you shouldn't assume that a useful equals? method exists when you are checking for duplicate trie insertion.

Definitions of the lexicographical classes TrieString, TrieInteger, and TrieIntegerString, and TriColor may be found on the class web site.

Do not turn in any files, either on the disk or on the hard copy, that are identical to those that I gave you.

to do?? more realistic TriColor constructor? javadoc it, if so in any case test javadoc, after all classes defined does interface documentation automatically appear? what if the implementation has its own documentation?

hints: represent empty trie as empty root have class TrieLeaf & TrieInternalNode inheriting from TrieNode class whose insert methods explicitly return a node how to avoid duplicate insertions into trie?? use the LinkedList addAll method to append use debuggger and/or test with smaller input sizes