Binary search tree
BinarySearchTree.java
package comp2402a5;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
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;
}
}
BinaryTree.java
package comp2402a5;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
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);
}
}
}
}
BinaryTreeNode.java
package comp2402a5;
/**
* This class represents a node in a binary tree. This class is abstract and
* should be subclassed by a concrete class. See, for example the class
* SimpleBinaryTreeNode.
*
* @author morin
*
* @param <Node>
* the class of the children of this node
*/
public class BinaryTreeNode<Node extends BinaryTreeNode<Node>> {
public Node left;
public Node right;
public Node parent;
}
BSTNode.java
package comp2402a5;
public class BSTNode<Node extends BSTNode<Node,T>,T>
extends BinaryTreeNode<Node> {
/**
* The key stored at this node
*/
T x;
}
CountdownTree.java
package comp2402a5;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeSet;
/**
* An unfinished implementation of an Countdown tree (for exercises)
*
* @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)) {
// add some code here
return true;
}
return false;
}
public void splice(Node<T> u) {
Node<T> w = u.parent;
super.splice(u);
// add some code here (we just removed u from the tree
}
protected void explode(Node<T> u) {
// Write this code to explode u
// Make sure to update u.parent and/or r (the tree root) as appropriate
}
// 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);
}
}
DefaultComparator.java
package comp2402a5;
import java.util.Comparator;
class DefaultComparator<T> implements Comparator<T> {
@SuppressWarnings(“unchecked”)
public int compare(T a, T b) {
return ((Comparable<T>)a).compareTo(b);
}
}
RangeSSet.java
package comp2402a5;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.SortedSet;
/**
* 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.
*
* @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);
}
}
SortedSSet.java
package comp2402a5;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
/**
* This class is a wrapper that allows any class that implements SSet<T> to
* allow it to also implement SortedSet<T>.
* @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();
}
}
SSet.java
package comp2402a5;
import java.util.Comparator;
import java.util.Iterator;
/**
* 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);
}
Testum.java
package comp2402a5;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
/**
* 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;
}
}
Solution
BinarySearchTree.java
package comp2402a5;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
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;
}
}
BinaryTree.java
package comp2402a5;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
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);
}
}
}
}
BinaryTreeNode.java
package comp2402a5;
/**
* This class represents a node in a binary tree. This class is abstract and
* should be subclassed by a concrete class. See, for example the class
* SimpleBinaryTreeNode.
* @param <Node>
* the class of the children of this node
*/
public class BinaryTreeNode<Node extends BinaryTreeNode<Node>> {
public Node left;
public Node right;
public Node parent;
}
BSTNode.java
package comp2402a5;
public class BSTNode<Node extends BSTNode<Node,T>,T>
extends BinaryTreeNode<Node> {
/**
* The key stored at this node
*/
T x;
}
CountdownTree.java
package comp2402a5;
import java.lang.reflect.Array;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeSet;
/**
* 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)) {
// add some code here
u = u.parent;
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);
// add some code here (we just removed u from the tree
while (w != nil) {
w.timer–;
if (w.timer == 0) {
this.explode(w);
}
w = w.parent; // iterate
}
}
protected void explode(Node<T> u) {
// Write this code to explode u
// Make sure to update u.parent and/or r (the tree root) as appropriate
int ns = size(u);
Node<T> p = u.parent;
@SuppressWarnings(“unchecked”)
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);
}
}
DefaultComparator.java
package comp2402a5;
import java.util.Comparator;
class DefaultComparator<T> implements Comparator<T> {
@SuppressWarnings(“unchecked”)
public int compare(T a, T b) {
return ((Comparable<T>)a).compareTo(b);
}
}
RangeSSet.java
package comp2402a5;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.SortedSet;
/**
* 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.
* @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);
}
}
SortedSSet.java
package comp2402a5;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
/**
* This class is a wrapper that allows any class that implements SSet<T> to
* allow it to also implement SortedSet<T>.
* @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();
}
}
SSet.java
package comp2402a5;
import java.util.Comparator;
import java.util.Iterator;
/**
* 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);
}
Testum.java
package comp2402a5;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
/**
* A utility class with some static methods for testing List implementations
*/
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;
}
}
