ArrayTree

java.lang.Object
- 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.

Field Summary

Fields
Modifier and Type	Field and Description
`private K[]`	`array` The array containing the data
`private java.util.Comparator<K>`	`comparator` The Comparator used for comparing the keys
`private static int`	`INCREMENT` The extend size to use when increasing the array size
`private int`	`size` The current number of elements in the array.

Constructor Summary

Constructors
Constructor and Description
`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

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`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
`private void`	`reduceArray()` q< Reduce the array size if neede
`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

- Field Detail
  - comparator
```
private java.util.Comparator<K> comparator
```
    The Comparator used for comparing the keys
  - array
```
private K[] array
```
    The array containing the data
  - size
```
private int size
```
    The current number of elements in the array. May be lower than the array size
  - INCREMENT
```
private static final int INCREMENT
```
    The extend size to use when increasing the array size
    
    See Also:
    
    Constant Field Values
- 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.
  - reduceArray
```
private void reduceArray()
```
    q< Reduce the array size if neede
  - 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

Class ArrayTree<K>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

comparator

array

size

INCREMENT

Constructor Detail

ArrayTree

ArrayTree

Method Detail

getComparator

insert

reduceArray

remove

isEmpty

size

getKeys

printTree

get

getFirst

getLast

findGreater

findGreaterOrEqual

findLess

findLessOrEqual

find

getPosition

getAfterPosition

getBeforePosition

contains

toString