OrderedSet<Eextends Comparable<E>
Develop class OrderedSet<E extends Comparable<E> as a generic collection that stores nodes in a binary search tree data structure. Each node has a reference to data, a left binary search tree, and a right binary search tree. The type to be stored must be limited to those that implement the Comparable interface or any interface that extends Comparable.
publicclassOrderedSet<E extends Comparable<E>
The required method headings are provided below with their behavior listed as comments to help you complete all 11 methods. The following test method illustrates how to construct an OrderedSet object and how to send three different messages to it.
@Test
publicvoidtestInsertSizeAndTostringinorder() {
OrderedSet<String> bst = newOrderedSet<String>();
assertEquals("", bst.toStringInorder());
assertTrue(bst.insert("d"));
assertTrue(bst.insert("b"));
assertTrue(bst.insert("e"));
assertFalse(bst.insert("e"));
assertTrue(bst.insert("a"));
assertEquals(4, bst.size());
assertEquals("a b d e", bst.toStringInorder());
}
// 1) Add element to this OrderedSet and return true keeping this aOrderedSet.
// If element is found to already exist, do not change this OrderedSet, return false.
publicboolean insert(E element)
// 2) The number of elements in this OrderedSet, which should be 0 when first constructed.
// This may run O(n) or O(1)--your choice.
publicint size()
// 3) Return one string that concatenates all elements in this OrderedSet as they are
// visited inorder. Elements are separated by spaces as in "1 4 9" from this OrderedSet:
// 4
// / \
// 1 9
public String toStringInorder()
// 4) Return true is search equals an element in this OrderedSet.
publicboolean contains(E search)
// 5) Return the element in this OrderedSet that is greater than all other elements.
// If this OrderedSet is empty, return null.
public E max()
//6) Return how many nodes are at the given level. If level > the height of the tree,
// return 0. Remember that an empty tree has a height of -1 (see page 252).
//
// 4 There is 1 node on level 0
// / \
// 3 9 There are 2 nodes on level 1
// / / \
// 1 5 11 There are 3 nodes in level 2 (and 0 nodes on levels >= 3)
publicint nodesAtLevel(int level)
// 7) Return the intersection of this OrderedSet and the other OrderedSet as
// a new OrderedSet. Do not modify this OrderedSet or the other OrderedSet.
// The intersection of two sets is the set of elements that are in both sets.
// The intersection of {2, 4, 5, 6} and {2, 5, 6, 9} is {2, 5, 6}
publicOrderedSet<E> intersection(OrderedSet<E> other)
// 8) Return the union of this OrderedSet and the other OrderedSet as
// a new OrderedSet. Do not modify this OrderedSet or the other OrderedSet.
// The union of two sets is the set all distinct elements in the collection.[
// The union of {2, 4, 6} and {2, 5, 9} is {2, 4, 5, 6, 9}
publicOrderedSet<E> union(OrderedSet<E> other)
// 9) Return an OrderedSet that contains all elements that are greater than or equal to
// the first parameter (inclusive) and strictly less than the second parameter (exclusive).
publicOrderedSet<E> subset(E inclusive, E exclusive)
// These assertions should pass
@TestpublicvoidtestSubSet() {
OrderedSet<Integer> bst = newOrderedSet<Integer>();
bst.insert(50);
bst.insert(25);
bst.insert(12);
bst.insert(75);
bst.insert(65);
bst.insert(90);
assertEquals("12 25 50 65 75 90", bst.toStringInorder());
assertEquals("12 25", bst.subset(1, 49).toStringInorder());
assertEquals("25 50 65", bst.subset(25, 75).toStringInorder());
assertEquals("", bst.subset(12, 12).toStringInorder()); // 12 < 12 is false
}
// 10)Return true if two different OrderedSet objects have the same exact structure.
// Each node must have the same number of nodes on every level, the same height,
//the same size, the same number of leaves, and the same number of internal nodes.
// Each corresponding node must also have the same number of children (0, 1, or 2)
// in the same place. The data need NOT be the same. Do not compare corresponding
// elements. Each of these pairs of OrderedSetshave the sameStructure:
//
// M P | Lmn Rts | 5 55 | 3 999
// / \ / \ | / / | \ \ | / /
// B R F Q | Abc Lmn | 10 89 | 2 888
// \ \ \ \ | | / \ / \ | / /
// F Z J R | | 8 77 79 99 | 1 777
//
// Empty trees also have the same structure.
//
// Each pair of these OrderedSets do NOT have the sameStucture (elements may be "equals")
//
// M M | M M | 5 5 | 3 2
// / \ / \ | / / | \ \ | / / \
// B R B Z | L A | 10 12 | 2 1 3
// \ \ \ / | / \ | / \ / | /
// F Z F R | A L | 8 12 10 | 1
// | | / |
// | | 8 |
//
// Precondition: E is the same for bothOrderedSets
publicbooleansameStructure(OrderedSet<E> other)
// 11) If element equals an element in this OrderedSet, remove it and return true.
// Return falsewhenever element is not found. In all cases, this OrderedSet must
// remain a true OrderedSet. Here is one recommended algorithm
//
publicboolean remove(E element)
Grading Criteria 100pts
100 pts for WebCat Problem Coverage and Code Coverage