Logo Search packages:      
Sourcecode: uimaj version File versions  Download package

IntArrayRBT.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.uima.internal.util.rb_trees;

import java.util.NoSuchElementException;
import java.util.Random;

import org.apache.uima.internal.util.ComparableIntIterator;
import org.apache.uima.internal.util.ComparableIntPointerIterator;
import org.apache.uima.internal.util.IntArrayUtils;
import org.apache.uima.internal.util.IntComparator;
import org.apache.uima.internal.util.IntListIterator;
import org.apache.uima.internal.util.IntPointerIterator;
import org.apache.uima.internal.util.StringUtils;

/**
 * Red-black tree implementation based on integer arrays. Preliminary performance measurements on
 * j2se 1.4 indicate that the performance improvement as opposed to an object-based implementation
 * are miniscule. This seems to indicate a much improved object creation handling in this vm.
 * 
 * <p>
 * This tree implementation knows two modes of insertion: keys that are already in the tree can be
 * rejected, or inserted as duplicates. Duplicate key insertion is randomized so that the tree's
 * performance degrades gracefully in the presence of many identical keys.
 * 
 * 
 */
00045 public class IntArrayRBT {

  /**
   * Implement a comparable iterator over the keys.
   * 
   * 
   */
00052   private class ComparablePointerIterator extends PointerIterator implements
          ComparableIntPointerIterator {

    private final IntComparator comp;

    private int modificationSnapshot; // to catch illegal modifications

    private int[] detectIllegalIndexUpdates; // shared copy with Index Repository

    private int typeCode;

    public boolean isConcurrentModification() {
      return modificationSnapshot != detectIllegalIndexUpdates[typeCode];
    }

    public void resetConcurrentModification() {
      modificationSnapshot = detectIllegalIndexUpdates[typeCode];
    }

    private ComparablePointerIterator(IntComparator comp) {
      super();
      this.comp = comp;
    }

    /**
     * @see java.lang.Comparable#compareTo(Object)
     */
00079     public int compareTo(Object o) throws NoSuchElementException {
      ComparableIntPointerIterator it = (ComparableIntPointerIterator) o;
      // assert(this.comp != null);
      return this.comp.compare(get(), it.get());
    }

00085     public Object copy() {
      ComparablePointerIterator copy = new ComparablePointerIterator(this.comp);
      copy.currentNode = this.currentNode;
      return copy;
    }
  }

  /**
   * Class comment for IntArrayRBT.java goes here.
   * 
   * 
   */
00097   private class PointerIterator implements IntPointerIterator {

    protected int currentNode;

    private PointerIterator() {
      super();
      moveToFirst();
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#dec()
     */
00109     public void dec() {
      this.currentNode = previousNode(this.currentNode);
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#get()
     */
00116     public int get() {
      if (!isValid()) {
        throw new NoSuchElementException();
      }
      return IntArrayRBT.this.key[this.currentNode];
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#inc()
     */
00126     public void inc() {
      this.currentNode = nextNode(this.currentNode);
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#isValid()
     */
00133     public boolean isValid() {
      return (this.currentNode != NIL);
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#moveToFirst()
     */
00140     public void moveToFirst() {
      this.currentNode = getFirstNode();
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#moveToLast()
     */
00147     public void moveToLast() {
      this.currentNode = IntArrayRBT.this.greatestNode;
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#copy()
     */
00154     public Object copy() {
      PointerIterator it = new PointerIterator();
      it.currentNode = this.currentNode;
      return it;
    }

    /**
     * @see org.apache.uima.internal.util.IntPointerIterator#moveTo(int)
     */
00163     public void moveTo(int i) {
      this.currentNode = findInsertionPoint(i);
    }

  }

00169   private class IntArrayRBTKeyIterator implements IntListIterator {

    protected int currentNode;

    protected IntArrayRBTKeyIterator() {
      super();
      this.currentNode = NIL;
    }

00178     public final boolean hasNext() {
      return (this.currentNode != IntArrayRBT.this.greatestNode);
    }

00182     public final int next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      this.currentNode = nextNode(this.currentNode);
      return IntArrayRBT.this.key[this.currentNode];
    }

    /**
     * @see org.apache.uima.internal.util.IntListIterator#hasPrevious()
     */
00193     public boolean hasPrevious() {
      return (this.currentNode != NIL);
    }

    /**
     * @see org.apache.uima.internal.util.IntListIterator#previous()
     */
00200     public int previous() {
      if (!hasPrevious()) {
        throw new NoSuchElementException();
      }
      final int currentKey = IntArrayRBT.this.key[this.currentNode];
      if (this.currentNode == getFirstNode()) {
        this.currentNode = NIL;
      } else {
        this.currentNode = previousNode(this.currentNode);
      }
      return currentKey;
    }

    /**
     * @see org.apache.uima.internal.util.IntListIterator#moveToEnd()
     */
00216     public void moveToEnd() {
      this.currentNode = IntArrayRBT.this.greatestNode;
    }

    /**
     * @see org.apache.uima.internal.util.IntListIterator#moveToStart()
     */
00223     public void moveToStart() {
      this.currentNode = NIL;
    }

    protected final int getKey(int node) {
      return IntArrayRBT.this.key[node];
    }

  }

00233   private class ComparableIterator extends IntArrayRBTKeyIterator implements ComparableIntIterator {

    private final IntComparator comparator;

    private ComparableIterator(IntComparator comp) {
      super();
      this.comparator = comp;
    }

    /**
     * @see java.lang.Comparable#compareTo(Object)
     */
00245     public int compareTo(Object o) {
      ComparableIterator it = (ComparableIterator) o;
      return this.comparator.compare(IntArrayRBT.this.key[this.currentNode], it
              .getKey(it.currentNode));
    }

  }

  // Keys.
  protected int[] key;

  // Left daughters.
  protected int[] left;

  // Right daughters.
  protected int[] right;

  // Parents.
  protected int[] parent;

  // Colors.
  protected boolean[] color;

  // The index of the next node.
  private int next;

  // The current size of the tree. Since we can remove nodes, since needs to
  // be kept separate from the next free cell.
  private int size;

  // The root of the tree.
  protected int root;

  // Keep a pointer to the largest node around so we can optimize for
  // inserting
  // keys that are larger than all keys already in the tree.
  protected int greatestNode;

  protected static final int default_size = 1024;

  private static final int default_growth_factor = 2;

  private static final int default_multiplication_limit = 2000000;

  private int growth_factor;

  private int multiplication_limit;

  // The NIL sentinel
  public static final int NIL = 0;

  // The colors.
  protected static final boolean red = true;

  protected static final boolean black = false;

  // Random number generator to randomize inserts of identical keys.
  protected final Random rand;

  /**
   * Constructor for IntArrayRBT.
   */
00307   public IntArrayRBT() {
    this(default_size);
  }

  public IntArrayRBT(int initialSize) {
    super();
    this.rand = new Random();
    if (initialSize < 1) {
      initialSize = 1;
    }
    initVars();
    // Increase initialSize by one since we use one slot for sentinel.
    ++initialSize;
    this.growth_factor = default_growth_factor;
    this.multiplication_limit = default_multiplication_limit;
    // Init the arrays.
    this.key = new int[initialSize];
    this.left = new int[initialSize];
    this.right = new int[initialSize];
    this.parent = new int[initialSize];
    this.color = new boolean[initialSize];
    this.left[NIL] = NIL;
    this.right[NIL] = NIL;
    this.parent[NIL] = NIL;
    this.color[NIL] = black;
  }

  private void initVars() {
    this.root = NIL;
    this.greatestNode = NIL;
    this.next = 1;
    this.size = 0;
  }

  public void flush() {
    // All we do for flush is set the root to NIL and the size to 0.
    initVars();
  }

  public final int size() {
    return this.size;
  }

  private void grow(int initialSize) {
    this.key = grow(this.key, initialSize);
    this.left = grow(this.left, initialSize);
    this.right = grow(this.right, initialSize);
    this.parent = grow(this.parent, initialSize);
    this.color = grow(this.color, initialSize);
  }
  
  public int getKeyForNode(final int node) {
    return this.key[node];
  }

  protected int treeInsert(int k) {
    int x = this.root;
    int y, z;
    if ((this.greatestNode != NIL) && (this.key[this.greatestNode] < k)) {
      y = this.greatestNode;
      z = newNode(k);
      this.greatestNode = z;
    } else {
      y = NIL;
      int xKey;
      while (x != NIL) {
        y = x;
        xKey = this.key[x];
        if (k < xKey) {
          x = this.left[x];
        } else if (k == xKey) {
          return -x;
        } else { // k == key[x]
          x = this.right[x];
        }
      }
      // The key was not found, so we create a new node, inserting the
      // key.
      z = newNode(k);
    }
    if (y == NIL) {
      setAsRoot(z);
      this.greatestNode = z;
      this.parent[z] = NIL;
    } else {
      this.parent[z] = y;
      if (k < this.key[y]) {
        this.left[y] = z;
      } else {
        this.right[y] = z;
      }
    }
    return z;
  }

  protected int treeInsertWithDups(int k) {
    int x = this.root;
    int y, z;
    if ((this.greatestNode != NIL) && (this.key[this.greatestNode] <= k)) {
      y = this.greatestNode;
      z = newNode(k);
      this.greatestNode = z;
      this.right[y] = z;
      this.parent[z] = y;
      return z;
    }
    y = NIL;
    int xKey;
    while (x != NIL) {
      y = x;
      xKey = this.key[x];
      if (k < xKey) {
        x = this.left[x];
      } else if (k > xKey) {
        x = this.right[x];
      } else { // k == key[x]
        // Randomly search to the left or right.
        if (this.rand.nextBoolean()) {
          x = this.left[x];
        } else {
          x = this.right[x];
        }
      }
    }
    z = newNode(k);
    if (y == NIL) {
      setAsRoot(z);
      this.greatestNode = z;
      this.parent[z] = NIL;
    } else {
      this.parent[z] = y;
      if (k < this.key[y]) {
        this.left[y] = z;
      } else if (k > this.key[y]) {
        this.right[y] = z;
      } else { // k == key[y]
        // Randomly insert node to the left or right.
        if (this.rand.nextBoolean()) {
          this.left[y] = z;
        } else {
          this.right[y] = z;
        }
      }
    }
    return z;
  }

  protected int newNode(int k) {
    // Make sure the tree is big enough to accomodate a new node.
    if (this.next >= this.key.length) {
      grow(this.next + 1);
    }
    // assert(key.length > next);
    final int z = this.next;
    ++this.next;
    ++this.size;
    this.key[z] = k;
    this.left[z] = NIL;
    this.right[z] = NIL;
    this.color[z] = red;
    return z;
  }

  private final void setAsRoot(int x) {
    this.root = x;
    this.parent[this.root] = NIL;
  }

  private final int[] grow(int[] array, int newSize) {
    return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
  }

  private final boolean[] grow(boolean[] array, int newSize) {
    return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
  }

  private final void leftRotate(int x) {
    final int y = this.right[x];
    this.right[x] = this.left[y];
    if (this.left[y] != NIL) {
      this.parent[this.left[y]] = x;
    }
    this.parent[y] = this.parent[x];
    if (this.root == x) {
      setAsRoot(y);
    } else {
      if (x == this.left[this.parent[x]]) {
        this.left[this.parent[x]] = y;
      } else {
        this.right[this.parent[x]] = y;
      }
    }
    this.left[y] = x;
    this.parent[x] = y;
  }

  private final void rightRotate(int x) {
    final int y = this.left[x];
    this.left[x] = this.right[y];
    if (this.right[y] != NIL) {
      this.parent[this.right[y]] = x;
    }
    this.parent[y] = this.parent[x];
    if (this.root == x) {
      setAsRoot(y);
    } else {
      if (x == this.right[this.parent[x]]) {
        this.right[this.parent[x]] = y;
      } else {
        this.left[this.parent[x]] = y;
      }
    }
    this.right[y] = x;
    this.parent[x] = y;
  }

  public int insertKey(int k) {
    return insertKey(k, false);
  }

  public int insertKeyWithDups(int k) {
    return insertKey(k, true);
  }

  private int insertKey(int k, boolean withDups) {
    int x;
    if (this.root == NIL) {
      x = newNode(k);
      setAsRoot(x);
      this.color[this.root] = black;
      this.greatestNode = x;
      return x;
    }
    if (withDups) {
      x = treeInsertWithDups(k);
    } else {
      x = treeInsert(k);
      if (x < NIL) {
        return -x;
      }
    }
    this.color[x] = red;
    int y;
    final int node = x;
    while ((x != this.root) && (this.color[this.parent[x]] == red)) {
      if (this.parent[x] == this.left[this.parent[this.parent[x]]]) {
        y = this.right[this.parent[this.parent[x]]];
        if (this.color[y] == red) {
          this.color[this.parent[x]] = black;
          this.color[y] = black;
          this.color[this.parent[this.parent[x]]] = red;
          x = this.parent[this.parent[x]];
        } else {
          if (x == this.right[this.parent[x]]) {
            x = this.parent[x];
            leftRotate(x);
          }
          this.color[this.parent[x]] = black;
          this.color[this.parent[this.parent[x]]] = red;
          rightRotate(this.parent[this.parent[x]]);
        }
      } else {
        y = this.left[this.parent[this.parent[x]]];
        if (this.color[y] == red) {
          this.color[this.parent[x]] = black;
          this.color[y] = black;
          this.color[this.parent[this.parent[x]]] = red;
          x = this.parent[this.parent[x]];
        } else {
          if (x == this.left[this.parent[x]]) {
            x = this.parent[x];
            rightRotate(x);
          }
          this.color[this.parent[x]] = black;
          this.color[this.parent[this.parent[x]]] = red;
          leftRotate(this.parent[this.parent[x]]);
        }
      }
    }
    this.color[this.root] = black;
    return node;
  }

  // private final boolean isNewNode(int node) {
  // return (node == (next - 1));
  // }

  /**
   * Find the first node such that k &lt;= key[node].
   */
00597   public int findKey(int k) {
    int node = this.root;
    while (node != NIL) {
      if (k < this.key[node]) {
        node = this.left[node];
      } else if (k == this.key[node]) {
        return node;
      } else {
        node = this.right[node];
      }
    }
    // node == NIL
    return NIL;
  }

  /**
   * Find the node such that key[node] >= k and key[previous(node)] < k.
   */
00615   public int findInsertionPoint(int k) {
    int node = this.root;
    int found = node;
    while (node != NIL) {
      found = node;
      if (k < this.key[node]) {
        node = this.left[node];
      } else if (k == this.key[node]) {
        // In the presence of duplicates, we have to check if there are
        // identical
        // keys to the left of us.
        while ((this.left[node] != NIL) && (this.key[this.left[node]] == this.key[node])) {
          node = this.left[node];
        }
        return node;
      } else {
        node = this.right[node];
      }
    }
    // node == NIL
    return found;
  }

  /**
   * Find the node such that key[node] >= k and key[previous(node)] < k.
   */
00641   public int findInsertionPointNoDups(int k) {
    int node = this.root;
    int found = node;
    while (node != NIL) {
      found = node;
      if (k < this.key[node]) {
        node = this.left[node];
      } else if (k == this.key[node]) {
        return node;
      } else {
        node = this.right[node];
      }
    }
    // node == NIL
    return found;
  }

  public final boolean containsKey(int k) {
    return (findKey(k) != NIL);
  }

  private final boolean isLeftDtr(int node) {
    return ((node != this.root) && (node == this.left[this.parent[node]]));
  }

  // private final boolean isRightDtr(int node) {
  // return ((node != root) && (node == right[parent[node]]));
  // }

  private final int getFirstNode() {
    if (this.root == NIL) {
      return NIL;
    }
    int node = this.root;
    while (this.left[node] != NIL) {
      node = this.left[node];
    }
    return node;
  }

  // private final int nextNode(int node) {
  // if (right[node] != NIL) {
  // node = right[node];
  // while (left[node] != NIL) {
  // node = left[node];
  // }
  // } else {
  // while (isRightDtr(node)) {
  // node = parent[node];
  // }
  // if (node == root) {
  // return NIL;
  // }
  // // node is now a left dtr, so we can go one up.
  // node = parent[node];
  // }
  // return node;
  // }

  protected final int nextNode(int node) {
    int y;
    if (this.right[node] != NIL) {
      node = this.right[node];
      while (this.left[node] != NIL) {
        node = this.left[node];
      }
    } else {
      y = this.parent[node];
      while ((y != NIL) && (node == this.right[y])) {
        node = y;
        y = this.parent[y];
      }
      node = y;
    }
    return node;
  }

  private final int previousNode(int node) {
    if (this.left[node] != NIL) {
      node = this.left[node];
      while (this.right[node] != NIL) {
        node = this.right[node];
      }
    } else {
      while (isLeftDtr(node)) {
        node = this.parent[node];
      }
      if (node == this.root) {
        return NIL;
      }
      // node is now a left dtr, so we can go one up.
      node = this.parent[node];
    }
    return node;
  }

  public boolean deleteKey(int aKey) {
    int node = findKey(aKey);
    if (node == NIL) {
      return false;
    }
    deleteNode(node);
    --this.size;
    return true;
  }

  private void deleteNode(int z) {
    int x, y;
    if ((this.left[z] == NIL) || (this.right[z] == NIL)) {
      y = z;
    } else {
      y = nextNode(z);
    }
    if (this.left[y] != NIL) {
      x = this.left[y];
    } else {
      x = this.right[y];
    }
    this.parent[x] = this.parent[y];
    if (this.parent[y] == NIL) {
      setAsRoot(x);
    } else {
      if (y == this.left[this.parent[y]]) {
        this.left[this.parent[y]] = x;
      } else {
        this.right[this.parent[y]] = x;
      }
    }
    if (y != z) {
      this.key[z] = this.key[y];
    }
    if (this.color[y] == black) {
      deleteFixup(x);
    }
  }

  private void deleteFixup(int x) {
    int w;
    while ((x != this.root) && (this.color[x] == black)) {
      if (x == this.left[this.parent[x]]) {
        w = this.right[this.parent[x]];
        if (this.color[w] == red) {
          this.color[w] = black;
          this.color[this.parent[x]] = red;
          leftRotate(this.parent[x]);
          w = this.right[this.parent[x]];
        }
        if ((this.color[this.left[w]] == black) && (this.color[this.right[w]] == black)) {
          this.color[w] = red;
          x = this.parent[x];
        } else {
          if (this.color[this.right[w]] == black) {
            this.color[this.left[w]] = black;
            this.color[w] = red;
            rightRotate(w);
            w = this.right[this.parent[x]];
          }
          this.color[w] = this.color[this.parent[x]];
          this.color[this.parent[x]] = black;
          this.color[this.right[w]] = black;
          leftRotate(this.parent[x]);
          x = this.root;
        }
      } else {
        w = this.left[this.parent[x]];
        if (this.color[w] == red) {
          this.color[w] = black;
          this.color[this.parent[x]] = red;
          rightRotate(this.parent[x]);
          w = this.left[this.parent[x]];
        }
        if ((this.color[this.left[w]] == black) && (this.color[this.right[w]] == black)) {
          this.color[w] = red;
          x = this.parent[x];
        } else {
          if (this.color[this.left[w]] == black) {
            this.color[this.right[w]] = black;
            this.color[w] = red;
            leftRotate(w);
            w = this.left[this.parent[x]];
          }
          this.color[w] = this.color[this.parent[x]];
          this.color[this.parent[x]] = black;
          this.color[this.left[w]] = black;
          rightRotate(this.parent[x]);
          x = this.root;
        }
      }
    }
    this.color[x] = black;
  }

  /**
   * Method iterator.
   * 
   * @return IntListIterator
   */
00838   public ComparableIntIterator iterator(IntComparator comp) {
    return new ComparableIterator(comp);
  }

  public IntListIterator iterator() {
    return new IntArrayRBTKeyIterator();
  }

  public IntPointerIterator pointerIterator() {
    return new PointerIterator();
  }

  public IntPointerIterator pointerIterator(int aKey) {
    PointerIterator it = new PointerIterator();
    it.currentNode = this.findKey(aKey);
    return it;
  }

  public ComparableIntPointerIterator pointerIterator(IntComparator comp,
          int[] detectIllegalIndexUpdates, int typeCode) {
    // assert(comp != null);
    ComparablePointerIterator cpi = new ComparablePointerIterator(comp);
    cpi.modificationSnapshot = detectIllegalIndexUpdates[typeCode];
    cpi.detectIllegalIndexUpdates = detectIllegalIndexUpdates;
    cpi.typeCode = typeCode;
    return cpi;
  }

  // ///////////////////////////////////////////////////////////////////////////
  // Debug utilities

  public boolean satisfiesRedBlackProperties() {
    // Compute depth of black nodes.
    int node = this.root;
    int blackDepth = 0;
    while (node != NIL) {
      if (this.color[node] == black) {
        ++blackDepth;
      }
      node = this.left[node];
    }
    return satisfiesRBProps(this.root, blackDepth, 0);
  }

  private boolean satisfiesRBProps(int node, final int blackDepth, int currentBlack) {
    if (node == NIL) {
      return (currentBlack == blackDepth);
    }
    if (this.color[node] == red) {
      if (this.color[this.left[node]] == red || this.color[this.right[node]] == red) {
        return false;
      }
    } else {
      ++currentBlack;
    }
    return (satisfiesRBProps(this.left[node], blackDepth, currentBlack) && satisfiesRBProps(
            this.right[node], blackDepth, currentBlack));
  }

  public int maxDepth() {
    return maxDepth(this.root, 0);
  }

  public int minDepth() {
    return minDepth(this.root, 0);
  }

  public int nodeDepth(int k) {
    return nodeDepth(this.root, 1, k);
  }

  private int nodeDepth(int node, int depth, int k) {
    if (node == NIL) {
      return -1;
    }
    if (k == this.key[node]) {
      return depth;
    } else if (k < this.key[node]) {
      return nodeDepth(this.left[node], depth + 1, k);
    } else {
      return nodeDepth(this.right[node], depth + 1, k);
    }
  }

  private int maxDepth(int node, int depth) {
    if (node == NIL) {
      return depth;
    }
    int depth1 = maxDepth(this.left[node], depth + 1);
    int depth2 = maxDepth(this.right[node], depth + 1);
    return (depth1 > depth2) ? depth1 : depth2;
  }

  private int minDepth(int node, int depth) {
    if (node == NIL) {
      return depth;
    }
    int depth1 = maxDepth(this.left[node], depth + 1);
    int depth2 = maxDepth(this.right[node], depth + 1);
    return (depth1 > depth2) ? depth2 : depth1;
  }

  public final void printKeys() {
    if (this.size() == 0) {
      System.out.println("Tree is empty.");
      return;
    }
    StringBuffer buf = new StringBuffer();
    printKeys(this.root, 0, buf);
    System.out.println(buf);
  }

  private final void printKeys(int node, int offset, StringBuffer buf) {
    if (node == NIL) {
      // StringUtils.printSpaces(offset, buf);
      // buf.append("NIL\n");
      return;
    }
    StringUtils.printSpaces(offset, buf);
    buf.append(Integer.toString(this.key[node]));
    if (this.color[node] == black) {
      buf.append(" BLACK");
    }
    buf.append("\n");
    printKeys(this.left[node], offset + 2, buf);
    printKeys(this.right[node], offset + 2, buf);
  }

  public static void main(String[] args) {
    System.out.println("Constructing tree.");
    IntArrayRBT tree = new IntArrayRBT();
    tree.insertKeyWithDups(2);
    tree.insertKeyWithDups(1);
    // assert(tree.color[0] == black);
    // assert(tree.size() == 0);
    // assert(tree.insertKey(5) == 1);
    // assert(tree.size() == 1);
    // assert(tree.insertKeyWithDups(5) == 2);
    // assert(tree.insertKey(3) == 3);
    // assert(tree.size() == 3);
    // assert(tree.insertKey(4) == 4);
    // assert(tree.size() == 4);
    // assert(tree.insertKey(2) == 5);
    // assert(tree.size() == 5);
    // tree.printKeys();
    // System.out.println("Constructing tree.");
    // tree = new IntArrayRBT();
    // int max = 10;
    // for (int i = 1; i <= max; i++) {
    // tree.insertKeyWithDups(i);
    // }
    // for (int i = 1; i <= max; i++) {
    // tree.insertKeyWithDups(i);
    // }
    // tree.printKeys();
    // tree = new IntArrayRBT();
    // max = 100;
    // // System.out.println("Creating tree.");
    // for (int i = 1; i <= max; i++) {
    // tree.insertKeyWithDups(1);
    // }
    // // System.out.println("Printing tree.");
    // tree.printKeys();
    // // IntIterator it = tree.iterator();
    // // int numElements = 0;
    // // while (it.hasNext()) {
    // // it.next();
    // // ++numElements;
    // // }
  }

}

Generated by  Doxygen 1.6.0   Back to index