uimaj-2.3.0-incubating/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntRBTArray.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;

// The following is only imported to trick javadoc.

/**
 * Helper class to read array-based binary search trees with integers as keys and values. No write
 * access to the tree is provided. See
 * {@link org.apache.uima.internal.util.rb_trees.IntRedBlackTree IntRedBlackTree} on how to generate
 * such an array representation. The name is a bit of a misnomer, since nothing in this class is
 * specific to red-black trees.
 * 
 * <p>
 * Suppose <code>i</code> is the position of the first cell encoding a tree node in array
 * <code>a</code>. Then the expected memory layout of <code>a</code> is:
 * <ul>
 * <li><code>a[i]</code> is the key of the node</li>
 * <li><code>a[i+1]</code> is the element of the node</li>
 * <li><code>a[i+2]</code> is one of:
 * <ul>
 * <li><code>IntRBTArray.TERMINAL</code>: this is a terminal node</li>
 * <li><code>IntRBTArray.LEFTDTR</code>: this node only has a left daughter, so
 * <code>a[i+3]</code> is the first cell of the left daughter node</li>
 * <li><code>IntRBTArray.RIGHTDTR</code>: this node only has a right daughter, so
 * <code>a[i+3]</code> is the first cell of the right daughter node</li>
 * <li><code>IntRBTArray.TWODTRS</code>: this node has two daughters. <code>a[i+3]</code>
 * contains the address of the right daughter, and <code>a[i+4]</code> is the start of the left
 * daughter node</li>
 * </ul>
 * </li>
 * </ul>
 * 
 * <p>
 * Note that the array from which an IntRBTArray object is constructed can contain other data as
 * well. However, we assume that the addressing (the right daughter addresses, to be precise), must
 * be absolute (i.e., not relative to some starting point within the array).
 */
public class IntRBTArray {

  /** Code for a terminal node in the array. */
  public static final int TERMINAL = 0;

  /** Code for a node with only a left daughter. */
  public static final int LEFTDTR = 1;

  /** Code for a node with only a right daughter. */
  public static final int RIGHTDTR = 2;

  /** Code for a node with two daughters. */
  public static final int TWODTRS = 3;

  // The array that holds the search tree.
  private int[] array;

  // The address of the root node.
  private int offset;

  /**
   * Constructor that takes a start point as parameter.
   * 
   * @param start
   *          Address of the root node of the tree.
   * @param array
   *          The array containing the search tree.
   */
  public IntRBTArray(int[] array, int start) {
    this.offset = start;
    this.array = array;
  }

  /**
   * This constructor assumes that the root node is located at <code>0</code>.
   * 
   * @param array
   *          The array containing the search tree.
   */
  public IntRBTArray(int[] array) {
    this(array, 0);
  }

  /**
   * Getter for the internal array.
   * 
   * @return The internal array.
   */
  public int[] toArray() {
    return this.array;
  }

  /**
   * Set the address of the root node of the tree.
   * 
   * @param start
   *          the address.
   */
  public void setRootAddress(int start) {
    this.offset = start;
  }

  /**
   * Retrieve the value for a certain key.
   * 
   * @param i
   *          The input key.
   * @return The value, if key was found.
   * @throws NoSuchElementException
   *           If the key is not defined in the tree.
   */
  public int get(int i) throws NoSuchElementException {
    int pos = getPosition(i);
    if (pos >= 0) {
      return this.array[pos];
    }
    throw new NoSuchElementException();
  }

  /**
   * Get the position of a value for a key.
   * 
   * @param i
   *          The key.
   * @return The address of the value for <code>i</code>, if it's found; <code>-1</code>,
   *         else. This routine may also return <code>-1</code> when the tree is corrupted. Of
   *         course, with a corrupted tree, results will in general be unpredictable. However, this
   *         routine will not throw an
   *         {@link java.lang.ArrayIndexOutOfBoundsException ArrayIndexOutOfBoundsException}.
   */
  public int getPosition(int i) throws NoSuchElementException {
    // See the comments about the memory layout of the array at the
    // top of the file.
    int current = this.offset;
    if (this.array == null || this.array.length < (current + 3)) {
      return -1;
    }
    int key;
    int dtrCode;
    while (current >= 0 && this.array.length >= (current + 3)) {
      key = this.array[current];
      dtrCode = this.array[current + 2];
      if (key > i) {
        switch (dtrCode) {
          case TERMINAL:
            return -1;
          case LEFTDTR:
            current += 3;
            break;
          case RIGHTDTR:
            return -1;
          case TWODTRS:
            current += 4;
            break;
        }
      } else if (key < i) {
        switch (dtrCode) {
          case TERMINAL:
            return -1;
          case LEFTDTR:
            return -1;
          case RIGHTDTR:
            current += 3;
            break;
          case TWODTRS:
            if ((current + 3) > this.array.length) {
              return -1;
            }
            current = this.array[current + 3];
            break;
        }
      } else { // key == i
        return current + 1;
      }
    }
    return -1;
  }

  // /** Get the position of a value for a key. THIS VERSION DOES NOT WORK!
  // @param i The key.
  // @return The address of the value for <code>i</code>, if it's
  // found; <code>-1</code>, else. This routine may also return
  // <code>-1</code> when the tree is corrupted. Of course, with a
  // corrupted tree, results will in general be unpredictable.
  // In that case, this routine may throw an
  // {@link ArrayIndexOutOfBoundsException ArrayIndexOutOfBoundsException}.
  // */
  // public int getPosition(int i) {
  // // See the comments about the memory layout of the array at the
  // // top of the file.
  // int current = this.offset;
  // if (array == null || array.length < (current+2)) {
  // return -1;
  // }
  // int key = array[current];
  // current += 2;
  // int dtrCode = array[current];
  // while (current > 1 && array.length >= current) {
  // if (key > i) {
  // switch (dtrCode) {
  // case TERMINAL:
  // return -1;
  // case LEFTDTR:
  // ++current;
  // break;
  // case RIGHTDTR:
  // return -1;
  // case TWODTRS:
  // current += 2;
  // break;
  // }
  // } else if (key < i) {
  // switch (dtrCode) {
  // case TERMINAL:
  // return -1;
  // case LEFTDTR:
  // return -1;
  // case RIGHTDTR:
  // ++current;
  // break;
  // case TWODTRS:
  // ++current;
  // current = array[current];
  // break;
  // }
  // } else { // key == i
  // return current-1;
  // }
  // key = array[current];
  // current += 2;
  // dtrCode = array[current];
  // }
  // return -1;
  // }

}