org.apache.directory.server.core.avltree
Class AvlTreeMapImpl<K,V>

java.lang.Object
  extended by org.apache.directory.server.core.avltree.AvlTreeMapImpl<K,V>
All Implemented Interfaces:
AvlTreeMap<K,V>

public class AvlTreeMapImpl<K,V>
extends java.lang.Object
implements AvlTreeMap<K,V>

An AvlTreeMap implementation with support to store both key and value. This implementation also supports duplicate keys. The values of a same key will be stored in a AvlTree.

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

Constructor Summary
AvlTreeMapImpl(java.util.Comparator<K> keyComparator, java.util.Comparator<V> valueComparator)
          Creates a new instance of AVLTreeMap without support for duplicate keys.
AvlTreeMapImpl(java.util.Comparator<K> keyComparator, java.util.Comparator<V> valueComparator, boolean allowDuplicates)
           
 
Method Summary
 LinkedAvlMapNode<K,V> find(K key)
          Find a LinkedAvlMapNode with the given key value in the tree.
 LinkedAvlMapNode<K,V> find(K key, V value)
          Find a LinkedAvlMapNode with the given key and value in the tree.
 LinkedAvlMapNode<K,V> findGreater(K key)
          Finds a LinkedAvlMapNode whose key is higher than the given key.
 LinkedAvlMapNode<K,V> findGreaterOrEqual(K key)
          Finds a LinkedAvlMapNode whose key is higher than the given key.
 LinkedAvlMapNode<K,V> findLess(K key)
          Finds a LinkedAvlMapNode whose key is lower than the given key.
 LinkedAvlMapNode<K,V> findLessOrEqual(K key)
          Finds a LinkedAvlMapNode whose key is lower than the given key.
 LinkedAvlMapNode<K,V> getFirst()
          
 java.util.Comparator<K> getKeyComparator()
          
 java.util.List<K> getKeys()
          
 LinkedAvlMapNode<K,V> getLast()
          
 LinkedAvlMapNode<K,V> getRoot()
          
 int getSize()
          returns the number of nodes present in this tree.
 java.util.Comparator<V> getValueComparator()
          
 V insert(K key, V value)
          Inserts a LinkedAvlMapNode with the given key and value.
 boolean isDupsAllowed()
          tells if the duplicate keys are supported or not.
 boolean isEmpty()
          Tests if the tree is logically empty.
 void printTree()
          Prints the contents of AVL tree in pretty format
 SingletonOrOrderedSet<V> remove(K key)
          Removes a node associated with the given key The entire node will be removed irrespective of whether duplicate keys are enabled or not
 V remove(K key, V value)
          Removes the LinkedAvlMapNode present in the tree with the given key and value
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AvlTreeMapImpl

public AvlTreeMapImpl(java.util.Comparator<K> keyComparator,
                      java.util.Comparator<V> valueComparator)
Creates a new instance of AVLTreeMap without support for duplicate keys.

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

AvlTreeMapImpl

public AvlTreeMapImpl(java.util.Comparator<K> keyComparator,
                      java.util.Comparator<V> valueComparator,
                      boolean allowDuplicates)
Method Detail

getKeyComparator

public java.util.Comparator<K> getKeyComparator()

Specified by:
getKeyComparator in interface AvlTreeMap<K,V>
Returns:
the key comparator associated with this tree

getValueComparator

public java.util.Comparator<V> getValueComparator()

Specified by:
getValueComparator in interface AvlTreeMap<K,V>
Returns:
the value comparator associated with this tree

insert

public V insert(K key,
                V value)
Inserts a LinkedAvlMapNode with the given key and value.

Specified by:
insert in interface AvlTreeMap<K,V>
Parameters:
key - the item to be inserted
value - the value associated with the key
Returns:
the replaced value if any exists else null Note: Replaces a nodes value if duplicate keys are not allowed and the new value is not equal to the existing value.

remove

public SingletonOrOrderedSet<V> remove(K key)
Removes a node associated with the given key The entire node will be removed irrespective of whether duplicate keys are enabled or not

Specified by:
remove in interface AvlTreeMap<K,V>
Parameters:
key - the key of the node to be removed
Returns:
a SingletonOrOrderedSet

remove

public V remove(K key,
                V value)
Removes the LinkedAvlMapNode present in the tree with the given key and value

Specified by:
remove in interface AvlTreeMap<K,V>
Parameters:
key - the key of the node to be removed
value - the value of the node
Returns:
the removed value, if any, or null if the key or value does not exist

isEmpty

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

Specified by:
isEmpty in interface AvlTreeMap<K,V>
Returns:
true if the tree is empty, false otherwise

getSize

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

Specified by:
getSize in interface AvlTreeMap<K,V>
Returns:
the number of nodes present in this tree

getRoot

public LinkedAvlMapNode<K,V> getRoot()

Specified by:
getRoot in interface AvlTreeMap<K,V>
Returns:
the root element of this tree (i.e., not the first, but the topmost element)

getKeys

public java.util.List<K> getKeys()

Specified by:
getKeys in interface AvlTreeMap<K,V>
Returns:
a list of the stored keys in this tree

printTree

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

Specified by:
printTree in interface AvlTreeMap<K,V>

getFirst

public LinkedAvlMapNode<K,V> getFirst()

Specified by:
getFirst in interface AvlTreeMap<K,V>
Returns:
The first element of this tree

getLast

public LinkedAvlMapNode<K,V> getLast()

Specified by:
getLast in interface AvlTreeMap<K,V>
Returns:
The last element in this tree

findGreater

public LinkedAvlMapNode<K,V> findGreater(K key)
Finds a LinkedAvlMapNode whose key is higher than the given key.

Specified by:
findGreater in interface AvlTreeMap<K,V>
Parameters:
key - the key
Returns:
the LinkedAvlMapNode whose key is greater than the given key ,
null if there is no node with a higher key than the given key.

findGreaterOrEqual

public LinkedAvlMapNode<K,V> findGreaterOrEqual(K key)
Finds a LinkedAvlMapNode whose key is higher than the given key.

Specified by:
findGreaterOrEqual in interface AvlTreeMap<K,V>
Parameters:
key - the key
Returns:
the LinkedAvlMapNode whose key is greater than the given key ,
null if there is no node with a higher key than the given key.

findLess

public LinkedAvlMapNode<K,V> findLess(K key)
Finds a LinkedAvlMapNode whose key is lower than the given key.

Specified by:
findLess in interface AvlTreeMap<K,V>
Parameters:
key - the key
Returns:
the LinkedAvlMapNode whose key is lower than the given key ,
null if there is no node with a lower key than the given key.

findLessOrEqual

public LinkedAvlMapNode<K,V> findLessOrEqual(K key)
Finds a LinkedAvlMapNode whose key is lower than the given key.

Specified by:
findLessOrEqual in interface AvlTreeMap<K,V>
Parameters:
key - the key
Returns:
the LinkedAvlMapNode whose key is lower than the given key ,
null if there is no node with a lower key than the given key.

find

public LinkedAvlMapNode<K,V> find(K key)
Find a LinkedAvlMapNode with the given key value in the tree.

Specified by:
find in interface AvlTreeMap<K,V>
Parameters:
key - the key to find
Returns:
the list of traversed LinkedAvlMapNode.

find

public LinkedAvlMapNode<K,V> find(K key,
                                  V value)
Find a LinkedAvlMapNode with the given key and value in the tree.

Specified by:
find in interface AvlTreeMap<K,V>
Parameters:
key - the key of the node
value - the value of the node
Returns:
LinkedAvlMapNode having the given key and value

isDupsAllowed

public boolean isDupsAllowed()
tells if the duplicate keys are supported or not.

Specified by:
isDupsAllowed in interface AvlTreeMap<K,V>
Returns:
true if duplicate keys are allowed, false otherwise


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