Implement a Countdown Tree , in the file CountdownTree.java. This is a balanced
ID: 3701631 • Letter: I
Question
Implement a Countdown Tree, in the file CountdownTree.java. This is a balanced search tree that uses partial rebuilding in a manner similar to scapegoat trees (see OpenDataStructures.org: Scapegoat Trees).
Every countdown tree has a float parameter d, defined when it is created. We call this the tree's countdown delay factor.
Each node u in a countdown tree has an int countdown timer, u.timer. When a new node is created, it's timer is set to Math.ceil(d).
When a node u's timer reaches 0, the node explodes, and the entire subtree rooted at u is rebuilt into a perfectly balanced binary search tree (note that u is probably not the root of this new subtree). Every node v in the rebuilt subtree has it's timer reset to Math.ceil(d*size(v)) where size(v) denotes the number of nodes in the subtree rooted at v.
The add(x) operation in a countdown tree works just like adding in a normal (unbalanced) Binary Search Tree. A new node u containing the value x is added as a leaf in the tree, but in addition u.timer is set to Math.ceil(d). Next, every node on the path from u to the root of the tree has its timer decremented and, if any of these nodes' timers drop to 0, then their subtree 'explodes'.
The remove(x) operation works just like in a normal (unbalanced) Binary Search Tree. We first find the node w that contains x. Now, it might not be easy to remove w because it has two children so we try to find a node u that is easy to delete. If w has no right child, then we set u=w. Otherwise, we pick u to be the leftmost (smallest value) node in w's right subtree. Next we swap u.x and w.x and splice u out of the tree.
Finally, we walk back up the path from (the now removed) u to the root and decrement the timer of every node along the way. If any of these nodes' timers drop to 0, then their subtree explodes.
You don't need to do anything to implement the find(x) operation, it's inherited from the BinarySearchTree class and works unmodified.
__________________________________________________________________
________________________________________________________
____________________________________________
________________________________________________________________________
__________________________________________________________________________
__________________________________________________________________
________________________________________________
Explanation / Answer
Below is your code: -
Testnum.java
/**
* A utility class with some static methods for testing List implementations
*
* @author morin
*/
public class Testum {
protected static void myassert(boolean b) throws AssertionError {
if (!b) {
throw new AssertionError();
}
}
protected static String s(Object c) {
return c.getClass().getName();
}
public static void sortedSetSanityTests(SortedSet<Integer> ss, int n) {
SortedSet<Integer> ts = new TreeSet<Integer>();
ss.clear();
Random r = new Random();
for (int i = 0; i < n; i++) {
Integer x = r.nextInt(2 * n);
if (ts.add(x) != ss.add(x))
throw new RuntimeException("add(x) returned wrong value");
if (!compareSortedSets(ts, ss))
throw new RuntimeException("sorted sets differ!");
}
for (int i = 0; i < n; i++) {
Integer x = r.nextInt(2 * n);
if (ts.remove(x) != ss.remove(x))
throw new RuntimeException("remove(x) returned wrong value");
if (!compareSortedSets(ts, ss))
throw new RuntimeException("sorted sets differ!");
}
ss.clear();
ts.clear();
compareSortedSets(ts, ss);
}
public static void sortedSetSpeedTests(Collection<SortedSet<Integer>> css, int n) {
long start, stop;
for (SortedSet<Integer> ss : css) {
ss.clear();
myassert(ss.size() == 0);
}
for (SortedSet<Integer> ss : css) {
System.out.print("random insertions (" + s(ss) + ")...");
start = System.nanoTime();
Random r = new Random();
for (int i = 0; i < n; i++)
ss.add(r.nextInt(2 * n));
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
myassert(ss.size() >= n / 2);
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("random contains (" + s(ss) + ")...");
start = System.nanoTime();
Random r = new Random();
for (int i = 0; i < 2 * n; i++)
ss.contains(r.nextInt(2 * n));
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("random removals (" + s(ss) + ")...");
start = System.nanoTime();
Random r = new Random();
for (int i = 0; i < 2 * n; i++)
ss.remove(r.nextInt(2 * n));
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("random headSets (" + s(ss) + ")...");
start = System.nanoTime();
Random r = new Random();
for (int i = 0; i < n; i++) {
ss.headSet(r.nextInt(2 * n));
Iterator<Integer> it = ss.iterator();
if (it.hasNext())
it.next();
}
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("iteration (" + s(ss) + ")...");
start = System.nanoTime();
for (Integer i : ss) {
i = i + 1;
}
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("clear (" + s(ss) + ")...");
start = System.nanoTime();
ss.clear();
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("sequential insertions (" + s(ss) + ")...");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
myassert(ss.size() == i);
ss.add(i * 2);
}
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
myassert(ss.size() == n);
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("sequential contains (" + s(ss) + ")...");
start = System.nanoTime();
for (int i = 0; i < 2 * n; i++)
ss.contains(i);
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("sequential headSets (" + s(ss) + ")...");
start = System.nanoTime();
for (int i = 0; i < 2 * n; i++)
ss.headSet(i);
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
for (SortedSet<Integer> ss : css) {
System.out.print("iteration over subSets (" + s(ss) + ")...");
start = System.nanoTime();
for (Integer i : ss.subSet(n / 2, 3 * n / 4)) {
i = i + 1;
}
stop = System.nanoTime();
System.out.println(" " + (1e-9 * (stop - start)) + " seconds");
}
System.out.println();
}
protected static <T> boolean compareSortedSets(Collection<T> a, Collection<T> b) {
if (a.size() != b.size())
return false;
for (T x : a) {
if (!b.contains(x))
return false;
}
for (T x : b) {
if (!a.contains(x))
return false;
}
Iterator<T> ita = a.iterator();
Iterator<T> itb = b.iterator();
while (ita.hasNext()) {
if (!ita.next().equals(itb.next()))
return false;
}
return true;
}
}
SortedSSet.java
/**
* This class is a wrapper that allows any class that implements SSet<T> to
* allow it to also implement SortedSet<T>.
*
* @author morin
*
* @param <T>
*/
public class SortedSSet<T> extends AbstractSet<T> implements SortedSet<T> {
protected SSet<T> s;
public SortedSSet(SSet<T> s) {
this.s = s;
}
public Comparator<? super T> comparator() {
return s.comparator();
}
public T first() {
return s.findGE(null);
}
public T last() {
return s.findLT(null);
}
public SortedSet<T> headSet(T b) {
return new RangeSSet<T>(s, null, b);
}
public SortedSet<T> subSet(T a, T b) {
return new RangeSSet<T>(s, a, b);
}
public SortedSet<T> tailSet(T a) {
return new RangeSSet<T>(s, a, null);
}
public boolean add(T x) {
return s.add(x);
}
public void clear() {
s.clear();
}
@SuppressWarnings("unchecked")
public boolean contains(Object o) {
T y = s.findGE((T) o);
return y != null && y.equals(o);
}
public Iterator<T> iterator() {
return s.iterator();
}
@SuppressWarnings("unchecked")
public boolean remove(Object x) {
return s.remove((T) x);
}
public int size() {
return s.size();
}
public boolean isEmpty() {
return !s.iterator().hasNext();
}
}
DefaultComparator.java
class DefaultComparator<T> implements Comparator<T> {
@SuppressWarnings("unchecked")
public int compare(T a, T b) {
return ((Comparable<T>) a).compareTo(b);
}
}
SSet.java
/**
* The SSet<T> interface is a simple interface that allows a class to implement
* all the functionality of the (more complicated) SortedSet<T> interface. Any
* class that implements SSet<T> can be wrapped in a SortedSSet<T> to obtain an
* implementation of SortedSet<T>
*
* @author morin
*
* @param <T>
* @see SortedSSet<T>
*/
public interface SSet<T> extends Iterable<T> {
/**
* @return the comparator used by this SSet
*/
public Comparator<? super T> comparator();
/**
* @return the number of elements in this SSet
*/
public int size();
/**
* Find the smallest element in the SSet that is greater than or equal to x.
* If x is null, return the smallest element in the SSet
*
* @param x
* @return the smallest element in the SSet that is greater than or equal to
* x. If x is null then the smallest element in the SSet
*/
public T findGE(T x);
/**
* Find the largest element in the SSet that is greater than to x. If x is
* null, return the largest element in the SSet
*
* @param x
* @return the largest element in the SSet that is less than x. If x is null
* then the smallest element in the SSet
*/
public T findLT(T x);
/**
* Add the element x to the SSet
*
* @param x
* @return true if the element was added or false if x was already in the
* set
*/
public boolean add(T x);
/**
* Remove the element x from the SSet
*
* @param x
* @return true if x was removed and false if x was not removed (because x
* was not present)
*/
public boolean remove(T x);
/**
* Clear the SSet, removing all elements from the set
*/
public void clear();
/**
* Return an iterator that iterates over the elements in sorted order,
* starting at the first element that is greater than or equal to x.
*/
public Iterator<T> iterator(T x);
}
BinaryTree.java
class BinaryTreeNode<Node extends BinaryTreeNode<Node>> {
public Node left;
public Node right;
public Node parent;
}
public class BinaryTree<Node extends BinaryTreeNode<Node>> {
/**
* Used to make a mini-factory
*/
public Node sampleNode;
/**
* The root of this tree
*/
public Node r;
/**
* This tree's null node
*/
public Node nil;
/**
* Create a new instance of this class
*
* @param isampleNode
*/
public BinaryTree(Node nil) {
sampleNode = nil;
this.nil = null;
}
/**
* Create a new instance of this class
*
* @warning child must set sampleNode before anything that might make calls
* to newNode()
*/
public BinaryTree() {
}
/**
* Allocate a new node for use in this tree
*
* @return
*/
@SuppressWarnings({ "unchecked" })
public Node newNode() {
try {
Node u = (Node) sampleNode.getClass().newInstance();
u.parent = u.left = u.right = nil;
return u;
} catch (Exception e) {
return null;
}
}
public int depth(Node u) {
int d = 0;
while (u != r) {
u = u.parent;
d++;
}
return d;
}
/**
* Compute the size (number of nodes) of this tree
*
* @return the number of nodes in this tree
*/
public int size() {
return size(r);
}
/**
* @return the size of the subtree rooted at u
*/
public int size(Node u) {
if (u == nil)
return 0;
return 1 + size(u.left) + size(u.right);
}
public int height() {
return height(r);
}
/**
* @return the size of the subtree rooted at u
*/
public int height(Node u) {
if (u == nil)
return -1;
return 1 + Math.max(height(u.left), height(u.right));
}
/**
* @return
*/
public boolean isEmpty() {
return r == nil;
}
/**
* Make this tree into the empty tree
*/
public void clear() {
r = nil;
}
public void traverse(Node u) {
if (u == nil)
return;
traverse(u.left);
traverse(u.right);
}
public void traverse2() {
Node u = r, prev = nil, next;
while (u != nil) {
if (prev == u.parent) {
if (u.left != nil)
next = u.left;
else if (u.right != nil)
next = u.right;
else
next = u.parent;
} else if (prev == u.left) {
if (u.right != nil)
next = u.right;
else
next = u.parent;
} else {
next = u.parent;
}
prev = u;
u = next;
}
}
public int size2() {
Node u = r, prev = nil, next;
int n = 0;
while (u != nil) {
if (prev == u.parent) {
n++;
if (u.left != nil)
next = u.left;
else if (u.right != nil)
next = u.right;
else
next = u.parent;
} else if (prev == u.left) {
if (u.right != nil)
next = u.right;
else
next = u.parent;
} else {
next = u.parent;
}
prev = u;
u = next;
}
return n;
}
public void bfTraverse() {
Queue<Node> q = new LinkedList<Node>();
q.add(r);
while (!q.isEmpty()) {
Node u = q.remove();
if (u.left != nil)
q.add(u.left);
if (u.right != nil)
q.add(u.right);
}
}
/**
* Find the first node in an in-order traversal
*
* @return
*/
public Node firstNode() {
Node w = r;
if (w == nil)
return nil;
while (w.left != nil)
w = w.left;
return w;
}
/**
* Find the node that follows u in an in-order traversal
*
* @param w
* @return
*/
public Node nextNode(Node w) {
if (w.right != nil) {
w = w.right;
while (w.left != nil)
w = w.left;
} else {
while (w.parent != nil && w.parent.left != w)
w = w.parent;
w = w.parent;
}
return w;
}
public static <Node extends BinaryTreeNode<Node>> void completeBinaryTree(BinaryTree<Node> t, int n) {
Queue<Node> q = new LinkedList<Node>();
t.clear();
if (n == 0)
return;
t.r = t.newNode();
q.add(t.r);
while (--n > 0) {
Node u = q.remove();
u.left = t.newNode();
u.left.parent = u;
q.add(u.left);
if (--n > 0) {
u.right = t.newNode();
u.right.parent = u;
q.add(u.right);
}
}
}
/**
* Create a new full binary tree whose expected number of nodes is n
*
* @param <Node>
* @param t
* @param n
*/
public static <Node extends BinaryTreeNode<Node>> void galtonWatsonFullTree(BinaryTree<Node> t, int n) {
Random r = new Random();
Queue<Node> q = new LinkedList<Node>();
t.clear();
t.r = t.newNode();
q.add(t.r);
double p = ((double) 0.5 - ((double) 1) / (n + n));
while (!q.isEmpty()) {
Node u = q.remove();
if (r.nextDouble() < p) {
u.left = t.newNode();
u.left.parent = u;
q.add(u.left);
u.right = t.newNode();
u.right.parent = u;
q.add(u.right);
}
}
}
static <Node extends BinaryTreeNode<Node>> void galtonWatsonTree(BinaryTree<Node> t, int n) {
Random r = new Random();
Queue<Node> q = new LinkedList<Node>();
t.clear();
t.r = t.newNode();
q.add(t.r);
double p = ((double) 0.5 - ((double) 1) / (n + n));
while (!q.isEmpty()) {
Node u = q.remove();
if (r.nextDouble() < p) {
u.left = t.newNode();
u.left.parent = u;
q.add(u.left);
}
if (r.nextDouble() < p) {
u.right = t.newNode();
u.right.parent = u;
q.add(u.right);
}
}
}
}
BSTNode.java
public class BSTNode<Node extends BSTNode<Node, T>, T> extends BinaryTreeNode<Node> {
/**
* The key stored at this node
*/
T x;
}
BinarySearchTree.java
public class BinarySearchTree<Node extends BSTNode<Node,T>, T> extends
BinaryTree<Node> implements SSet<T> {
public Comparator<T> c;
/**
* The number of nodes (elements) currently in the tree
*/
public int n;
public Node newNode(T x) {
Node u = super.newNode();
u.x = x;
return u;
}
public BinarySearchTree(Node is, Comparator<T> c) {
super(is);
this.c = c;
}
public BinarySearchTree(Node is) {
this(is, new DefaultComparator<T>());
}
/**
* Create a new instance of this class
* @warning child must set sampleNode before anything that
* might make calls to newNode()
*/
public BinarySearchTree() {
this(null, new DefaultComparator<T>());
}
/**
* Search for a value in the tree
* @return the last node on the search path for x
*/
public Node findLast(T x) {
Node w = r, prev = nil;
while (w != nil) {
prev = w;
int comp = c.compare(x, w.x);
if (comp < 0) {
w = w.left;
} else if (comp > 0) {
w = w.right;
} else {
return w;
}
}
return prev;
}
/**
* Search for a value in the tree
* @return the last node on the search path for x
*/
public Node findGENode(T x) {
Node w = r, z = nil;
while (w != nil) {
int comp = c.compare(x, w.x);
if (comp < 0) {
z = w;
w = w.left;
} else if (comp > 0) {
w = w.right;
} else {
return w;
}
}
return z;
}
public T findEQ(T x) {
Node u = r;
while (u != nil) {
int comp = c.compare(x, u.x);
if (comp < 0)
u = u.left;
else if (comp > 0)
u = u.right;
else
return u.x;
}
return null;
}
public T find(T x) {
Node w = r, z = nil;
while (w != nil) {
int comp = c.compare(x, w.x);
if (comp < 0) {
z = w;
w = w.left;
} else if (comp > 0) {
w = w.right;
} else {
return w.x;
}
}
return z == nil ? null : z.x;
}
public T findGE(T u) {
if (u == null) { // find the minimum value
Node w = r;
if (w == nil) return null;
while (w.left != nil)
w = w.left;
return w.x;
}
Node w = findGENode(u);
return w == nil ? null : w.x;
}
/**
* Search for a value in the tree
* @return the last node on the search path for x
*/
public Node findLTNode(T x) {
Node u = r, z = nil;
while (u != nil) {
int comp = c.compare(x, u.x);
if (comp < 0) {
u = u.left;
} else if (comp > 0) {
z = u;
u = u.right;
} else {
return u;
}
}
return z;
}
public T findLT(T x) {
if (x == null) { // find the maximum value
Node w = r;
if (w == nil) return null;
while (w.right != nil)
w = w.right;
return w.x;
}
Node w = findLTNode(x);
return w == nil ? null : w.x;
}
/**
* Add the node u as a child of node p -- ASSUMES p has no child
* where u should be added
* @param p
* @param u
* @return true if the child was added, false otherwise
*/
public boolean addChild(Node p, Node u) {
if (p == nil) {
r = u; // inserting into empty tree
} else {
int comp = c.compare(u.x, p.x);
if (comp < 0) {
p.left = u;
} else if (comp > 0) {
p.right = u;
} else {
return false; // u.x is already in the tree
}
u.parent = p;
}
n++;
return true;
}
/**
* Add a new value
* @param x
* @return
*/
public boolean add(T x) {
Node p = findLast(x);
return addChild(p, newNode(x));
}
/**
* Add a new value
* @param x
* @return
*/
public boolean add(Node u) {
Node p = findLast(u.x);
return addChild(p, u);
}
/**
* Remove the node u --- ASSUMING u has at most one child
* @param u
*/
public void splice(Node u) {
Node s, p;
if (u.left != nil) {
s = u.left;
} else {
s = u.right;
}
if (u == r) {
r = s;
p = nil;
} else {
p = u.parent;
if (p.left == u) {
p.left = s;
} else {
p.right = s;
}
}
if (s != nil) {
s.parent = p;
}
n--;
}
/**
* Remove the node u from the binary search tree
* @param u
*/
public void remove(Node u) {
if (u.left == nil || u.right == nil) {
splice(u);
} else {
Node w = u.right;
while (w.left != nil)
w = w.left;
u.x = w.x;
splice(w);
}
}
/**
* Do a left rotation at u
* @param u
*/
public void rotateLeft(Node u) {
Node w = u.right;
w.parent = u.parent;
if (w.parent != nil) {
if (w.parent.left == u) {
w.parent.left = w;
} else {
w.parent.right = w;
}
}
u.right = w.left;
if (u.right != nil) {
u.right.parent = u;
}
u.parent = w;
w.left = u;
if (u == r) { r = w; r.parent = nil; }
}
/**
* Do a right rotation at u
* @param u
*/
public void rotateRight(Node u) {
Node w = u.left;
w.parent = u.parent;
if (w.parent != nil) {
if (w.parent.left == u) {
w.parent.left = w;
} else {
w.parent.right = w;
}
}
u.left = w.right;
if (u.left != nil) {
u.left.parent = u;
}
u.parent = w;
w.right = u;
if (u == r) { r = w; r.parent = nil; }
}
/**
* Remove a node
* @param x
* @return
*/
public boolean remove(T x) {
Node u = findLast(x);
if (u != nil && c.compare(x,u.x) == 0) {
remove(u);
return true;
}
return false;
}
public String toString() {
String s = "[";
Iterator<T> it = iterator();
while (it.hasNext()) {
s += it.next().toString() + (it.hasNext() ? "," : "");
}
s += "]";
return s;
}
@SuppressWarnings({"unchecked"})
public boolean contains(Object x) {
Node u = findLast((T)x);
return u != nil && c.compare(u.x, (T)x) == 0;
}
public boolean containsAll(Collection<?> c) {
for (Object x : c)
if (!contains(x))
return false;
return true;
}
public Iterator<T> iterator(Node u) {
class BTI implements Iterator<T> {
public Node w, prev;
public BTI(Node iw) {
w = iw;
}
public boolean hasNext() {
return w != nil;
}
public T next() {
T x = w.x;
prev = w;
w = nextNode(w);
return x;
}
public void remove() {
// FIXME: This is a bug. remove() methods have to be changed
BinarySearchTree.this.remove(prev);
}
}
return new BTI(u);
}
public Iterator<T> iterator() {
return iterator(firstNode());
}
public Iterator<T> iterator(T x) {
return iterator(findGENode(x));
}
public int size() {
return n;
}
public boolean isEmpty() {
return n == 0;
}
public void clear() {
super.clear();
n = 0;
}
public Comparator<? super T> comparator() {
return c;
}
}
CountdownTree.java
/**
* An unfinished implementation of an Countdown tree (for exercises)
*
* @author morin
*
* @param <T>
*/
public class CountdownTree<T> extends BinarySearchTree<CountdownTree.Node<T>, T> implements SSet<T> {
// countdown delay factor
double d;
public static class Node<T> extends BSTNode<Node<T>, T> {
int timer; // the height of the node
}
public CountdownTree(double d) {
this.d = d;
sampleNode = new Node<T>();
c = new DefaultComparator<T>();
}
public boolean add(T x) {
Node<T> u = new Node<T>();
u.timer = (int) Math.ceil(d);
u.x = x;
if (super.add(u)) {
u = u.parent; // no need to decrement the node that was just added
while (u != nil) {
u.timer--;
if (u.timer == 0) {
this.explode(u);
}
u = u.parent; // iterate
}
return true;
}
return false;
}
public void splice(Node<T> u) {
Node<T> w = u.parent;
super.splice(u);
while (w != nil) {
w.timer--;
if (w.timer == 0)
this.explode(w);
w = w.parent; // iterate
}
}
protected void explode(Node<T> u) {
// rebalance
this.rebuild(u);
}
void rebuild(Node<T> u) {
int ns = size(u);
Node<T> p = u.parent;
Node<T>[] a = (Node<T>[]) Array.newInstance(Node.class, ns);
packIntoArray(u, a, 0);
if (p == nil) {
r = buildBalanced(a, 0, ns);
r.parent = nil;
} else if (p.right == u) {
p.right = buildBalanced(a, 0, ns);
p.right.parent = p;
} else {
p.left = buildBalanced(a, 0, ns);
p.left.parent = p;
}
}
int packIntoArray(Node<T> u, Node<T>[] a, int i) {
if (u == nil) {
return i;
}
i = packIntoArray(u.left, a, i);
a[i++] = u;
return packIntoArray(u.right, a, i);
}
Node<T> buildBalanced(Node<T>[] a, int i, int ns) {
if (ns == 0)
return nil;
int m = ns / 2;
a[i + m].left = buildBalanced(a, i, m);
if (a[i + m].left != nil)
a[i + m].left.parent = a[i + m];
a[i + m].right = buildBalanced(a, i + m + 1, ns - m - 1);
if (a[i + m].right != nil)
a[i + m].right.parent = a[i + m];
a[i + m].timer = (int) Math.ceil(d * size(a[i + m]));
return a[i + m];
}
// Here is some test code you can use
public static void main(String[] args) {
Testum.sortedSetSanityTests(new SortedSSet<Integer>(new CountdownTree<Integer>(1)), 1000);
Testum.sortedSetSanityTests(new SortedSSet<Integer>(new CountdownTree<Integer>(2.5)), 1000);
Testum.sortedSetSanityTests(new SortedSSet<Integer>(new CountdownTree<Integer>(0.5)), 1000);
java.util.List<SortedSet<Integer>> ell = new java.util.ArrayList<SortedSet<Integer>>();
ell.add(new java.util.TreeSet<Integer>());
ell.add(new SortedSSet<Integer>(new CountdownTree<Integer>(1)));
ell.add(new SortedSSet<Integer>(new CountdownTree<Integer>(2.5)));
ell.add(new SortedSSet<Integer>(new CountdownTree<Integer>(0.5)));
Testum.sortedSetSpeedTests(ell, 1000000);
}
}
RangeSSet.java
/**
* This represents a view of the part of a SortedSSet in the interval [a,b).
* This implementation adds only a constant additive overhead to methods except
* size(), which runs in linear time.
*
* @author morin
*
* @param <T>
*/
public class RangeSSet<T> extends SortedSSet<T> {
T a;
T b;
public RangeSSet(SSet<T> s, T a, T b) {
super(s);
this.a = a;
this.b = b;
}
public Iterator<T> iterator() {
class IT implements Iterator<T> {
protected Iterator<T> it;
T next, prev;
public IT(Iterator<T> it) {
this.it = it;
if (it.hasNext()) {
next = it.next();
}
}
public boolean hasNext() {
return next != null && (b == null || s.comparator().compare(next, b) < 0);
}
public T next() {
if (!hasNext())
throw new NoSuchElementException();
prev = next;
next = it.next();
return prev;
}
public void remove() {
s.remove(prev);
}
}
return new IT(s.iterator(a));
}
@SuppressWarnings("unchecked")
public boolean contains(Object o) {
T x = (T) o;
Comparator<? super T> c = s.comparator();
if (a != null && c.compare(x, a) < 0)
return false;
if (b != null && c.compare(x, b) >= 0)
return false;
return super.contains(x);
}
public T first() {
return s.findGE(a);
}
public int size() {
Iterator<T> it = iterator();
int n = 0;
while (it.hasNext()) {
it.next();
n++;
}
return n;
}
public T last() {
return s.findLT(b);
}
protected final T max(T x, T y) {
if (x == null)
return y;
if (y == null)
return x;
if (s.comparator().compare(x, y) > 0)
return x;
return y;
}
protected final T min(T x, T y) {
if (x == null)
return y;
if (y == null)
return x;
if (s.comparator().compare(x, y) < 0)
return x;
return y;
}
protected final void rangeCheck(T x) {
Comparator<? super T> c = s.comparator();
if ((a != null && c.compare(x, a) < 0) || (b != null && c.compare(x, b) >= 0))
throw new IllegalArgumentException();
}
public boolean add(T x) {
rangeCheck(x);
return super.add(x);
}
@SuppressWarnings("unchecked")
public boolean remove(Object x) {
rangeCheck((T) x);
return super.remove(x);
}
public SortedSet<T> subSet(T a, T b) {
return new RangeSSet<T>(s, max(a, this.a), min(b, this.b));
}
public SortedSet<T> headSet(T b) {
return subSet(a, b);
}
public SortedSet<T> tailSet(T a) {
return subSet(a, b);
}
}
Output
random insertions (java.util.TreeSet)... 1.694123991 seconds
random insertions (SortedSSet)... 8.809220077 seconds
random insertions (SortedSSet)... 2.5618191030000004 seconds
random insertions (SortedSSet)... 5.252303713000001 seconds
random contains (java.util.TreeSet)... 1.140186873 seconds
random contains (SortedSSet)... 2.081156671 seconds
random contains (SortedSSet)... 2.820264185 seconds
random contains (SortedSSet)... 2.8178051180000003 seconds
random removals (java.util.TreeSet)... 2.9152482670000004 seconds
random removals (SortedSSet)... 4.118869827 seconds
random removals (SortedSSet)... 4.65517687 seconds
random removals (SortedSSet)... 4.523284858 seconds
random headSets (java.util.TreeSet)... 0.17237354300000002 seconds
random headSets (SortedSSet)... 0.164563872 seconds
random headSets (SortedSSet)... 0.06564742900000001 seconds
random headSets (SortedSSet)... 0.06720843 seconds
iteration (java.util.TreeSet)... 0.083907784 seconds
iteration (SortedSSet)... 0.045956233000000006 seconds
iteration (SortedSSet)... 0.019485924 seconds
iteration (SortedSSet)... 0.010513666000000001 seconds
clear (java.util.TreeSet)... 1.867E-6 seconds
clear (SortedSSet)... 1.8660000000000002E-6 seconds
clear (SortedSSet)... 9.330000000000001E-7 seconds
clear (SortedSSet)... 9.330000000000001E-7 seconds
sequential insertions (java.util.TreeSet)... 0.512649429 seconds
sequential insertions (SortedSSet)... 9.883405427000001 seconds
sequential insertions (SortedSSet)... 5.4314517030000005 seconds
sequential insertions (SortedSSet)... 9.641019157 seconds
sequential contains (java.util.TreeSet)... 0.24703148500000002 seconds
sequential contains (SortedSSet)... 0.49023604400000004 seconds
sequential contains (SortedSSet)... 0.259007248 seconds
sequential contains (SortedSSet)... 0.29749484000000004 seconds
sequential headSets (java.util.TreeSet)... 0.44287276400000003 seconds
sequential headSets (SortedSSet)... 0.06685200300000001 seconds
sequential headSets (SortedSSet)... 0.185247838 seconds
sequential headSets (SortedSSet)... 0.008032206 seconds
iteration over subSets (java.util.TreeSet)... 0.025508795 seconds
iteration over subSets (SortedSSet)... 0.01871662 seconds
iteration over subSets (SortedSSet)... 0.013139749000000001 seconds
iteration over subSets (SortedSSet)... 0.012349451000000001 seconds
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.