org.apache.directory.server.core.avltree
Class ArrayTree<K>

java.lang.Object
  extended by org.apache.directory.server.core.avltree.ArrayTree<K>

public class ArrayTree<K>
extends java.lang.Object

A data structure simulating a tree (ie, a sorted list of elements) using an array.

Version:
$Rev$, $Date$
Author:
Apache Directory Project

Constructor Summary
ArrayTree(java.util.Comparator<K> comparator)
          Creates a new instance of AVLTree.
ArrayTree(java.util.Comparator<K> comparator, K[] array)
          Creates a new instance of AVLTree.
 
Method Summary
 boolean contains(K key)
          Tells if a key exist in the array.
 K find(K key)
          Find an element in the array.
 K findGreater(K key)
          Finds a key higher than the given key.
 K findGreaterOrEqual(K key)
          Finds a key higher than the given key.
 K findLess(K key)
          Finds a key which is lower than the given key.
 K findLessOrEqual(K key)
          Finds a key chich is lower than the given key.
 K get(int position)
          Get the element at a given position
 int getAfterPosition(K key)
          Find the element position in the array, or the position of the closest greater element in the array.
 int getBeforePosition(K key)
          Find the element position in the array, or the position of the closest greater element in the array.
 java.util.Comparator<K> getComparator()
           
 K getFirst()
          Get the first element in the tree.
 java.util.List<K> getKeys()
           
 K getLast()
          Get the last element in the tree.
 int getPosition(K key)
          Find the element position in the array.
 K insert(K key)
          Inserts a key.
 boolean isEmpty()
          Tests if the tree is empty.
 void printTree()
          Prints the contents of AVL tree in pretty format
 K remove(K key)
          Removes a key present in the tree
 int size()
          returns the number of nodes present in this tree.
 java.lang.String toString()
          
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

ArrayTree

public ArrayTree(java.util.Comparator<K> comparator)
Creates a new instance of AVLTree.

Parameters:
comparator - the comparator to be used for comparing keys

ArrayTree

public ArrayTree(java.util.Comparator<K> comparator,
                 K[] array)
Creates a new instance of AVLTree.

Parameters:
comparator - the comparator to be used for comparing keys
Method Detail

getComparator

public java.util.Comparator<K> getComparator()
Returns:
the comparator associated with this tree

insert

public K insert(K key)
Inserts a key. Null value insertion is not allowed.

Parameters:
key - the item to be inserted, should not be null
Returns:
the replaced key if it already exists Note: Ignores if the given key already exists.

remove

public K remove(K key)
Removes a key present in the tree

Parameters:
key - the value to be removed
Returns:
the removed key, if any, or null if the key does not exist

isEmpty

public boolean isEmpty()
Tests if the tree is empty.

Returns:
true if the tree is empty, false otherwise

size

public int size()
returns the number of nodes present in this tree.

Returns:
the number of nodes present in this tree

getKeys

public java.util.List<K> getKeys()
Returns:
a list of the stored keys in this tree

printTree

public void printTree()
Prints the contents of AVL tree in pretty format


get

public K get(int position)
      throws java.lang.ArrayIndexOutOfBoundsException
Get the element at a given position

Parameters:
position - The position in the tree
Returns:
The found key, or null if the position is out of scope
Throws:
java.lang.ArrayIndexOutOfBoundsException - If the position is not within the array boundaries

getFirst

public K getFirst()
Get the first element in the tree. It sets the current position to this element.

Returns:
The first element of this tree

getLast

public K getLast()
Get the last element in the tree. It sets the current position to this element.

Returns:
The last element in this tree

findGreater

public K findGreater(K key)
Finds a key higher than the given key. Sets the current position to this element.

Parameters:
key - the key to find
Returns:
the LinkedAvlNode whose key is greater than the given key ,
null if there is no node with a higher key than the given key.

findGreaterOrEqual

public K findGreaterOrEqual(K key)
Finds a key higher than the given key.

Parameters:
key - the key
Returns:
the key chich is greater than the given key ,
null if there is no higher key than the given key.

findLess

public K findLess(K key)
Finds a key which is lower than the given key.

Parameters:
key - the key
Returns:
the key lower than the given key ,
null if there is no node with a lower key than the given key.

findLessOrEqual

public K findLessOrEqual(K key)
Finds a key chich is lower than the given key.

Parameters:
key - the key
Returns:
the key which is lower than the given key ,
null if there is no node with a lower key than the given key.

find

public K find(K key)
Find an element in the array.

Parameters:
key - the key to find
Returns:
the found node, or null

getPosition

public int getPosition(K key)
Find the element position in the array.

Parameters:
key - the key to find
Returns:
the position in the array, or -1 if not found

getAfterPosition

public int getAfterPosition(K key)
Find the element position in the array, or the position of the closest greater element in the array.

Parameters:
key - the key to find
Returns:
the position in the array, or -1 if not found

getBeforePosition

public int getBeforePosition(K key)
Find the element position in the array, or the position of the closest greater element in the array.

Parameters:
key - the key to find
Returns:
the position in the array, or -1 if not found

contains

public boolean contains(K key)
Tells if a key exist in the array.

Parameters:
key - The key to look for
Returns:
true if the key exist in the array

toString

public java.lang.String toString()

Overrides:
toString in class java.lang.Object


Copyright © 2003-2011 Apache Software Foundation. All Rights Reserved.