org.apache.directory.server.core.avltree

Class AvlTreeMapImpl<K,V>

java.lang.Object

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.

Field Summary

Fields

Modifier and Type	Field and Description
private boolean	allowDuplicates flag to allow storing duplicate keys
private LinkedAvlMapNode<K,V>	first node representing the start of the doubly linked list formed with the tree nodes
private java.util.Comparator<K>	keyComparator The Comparator used for comparing the keys
private LinkedAvlMapNode<K,V>	last node representing the end of the doubly linked list formed with the tree nodes
private LinkedAvlMapNode<K,V>	root the root of the tree
private int	size size of the map
private java.util.Comparator<V>	valueComparator The Comparator used for comparing the values

Constructor Summary

Constructors

Constructor and Description
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) Creates a new instance of AVLTreeMap without support for duplicate keys.

Method Summary

Modifier and Type	Method and Description
private void	balance(java.util.List<LinkedAvlMapNode<K,V>> treePath) Balances the tree by visiting the nodes present in the List of nodes present in the treePath parameter. This really does the balancing if the height of the tree is greater than 2 and the balance factor is greater than +1 or less than -1. For an excellent info please read the Wikipedia article on AVL tree.
private void	balanceNodesAfterRemove(java.util.List<LinkedAvlMapNode<K,V>> treePath, LinkedAvlMapNode<K,V> delNode) changes the order of nodes after a delete operation and then balances the tree
private void	detachNodes(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode) Detach a LinkedAvlMapNode from its parent
private LinkedAvlMapNode<K,V>	fetchNonNullNode(K key, LinkedAvlMapNode<K,V> startNode, LinkedAvlMapNode<K,V> parent)
LinkedAvlMapNode<K,V>	find(K key) Find a LinkedAvlMapNode with the given key value in the tree.
private LinkedAvlMapNode<K,V>	find(K key, LinkedAvlMapNode<K,V> startNode)
private java.util.List<LinkedAvlMapNode<K,V>>	find(K key, LinkedAvlMapNode<K,V> startNode, java.util.List<LinkedAvlMapNode<K,V>> path) Find a LinkedAvlMapNode with the given key value in the tree starting from the startNode.
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.
private java.util.List<LinkedAvlMapNode<K,V>>	findMax(LinkedAvlMapNode<K,V> startNode) Find the LinkedAvlMapNode having the max key value in the tree starting from the startNode.
private java.util.List<LinkedAvlMapNode<K,V>>	findMin(LinkedAvlMapNode<K,V> startNode) Find the LinkedAvlMapNode having the min key value in the tree starting from the startNode.
private int	getBalance(LinkedAvlMapNode<K,V> node) Get balance-factor of the given LinkedAvlMapNode.
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.
private V	insertDupKey(V value, LinkedAvlMapNode<K,V> existingNode)
private void	insertInList(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode, int pos)
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
void	removeAll() removes all the nodes from the tree
private void	removeFromList(LinkedAvlMapNode<K,V> node)
private void	replaceNode(LinkedAvlMapNode<K,V> deleteNode, LinkedAvlMapNode<K,V> replaceNode, LinkedAvlMapNode<K,V> parentNode) Replace a LinkedAvlMapNode to be removed with a new existing LinkedAvlMapNode
private void	rotateSingleLeft(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode) Rotate the node left side once.
private void	rotateSingleRight(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode) Rotate the node right side once.
(package private) void	setFirst(LinkedAvlMapNode<K,V> first) Set the first element of the tree Note : this method is used by the deserialization method
(package private) void	setLast(LinkedAvlMapNode<K,V> last) Set the last element of the tree Note : this method is used by the deserialization method
(package private) void	setRoot(LinkedAvlMapNode<K,V> root) Set the root of the tree.
private void	visit(LinkedAvlMapNode<K,V> node, LinkedAvlMapNode<K,V> parentNode)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

root

private LinkedAvlMapNode<K,V> root

the root of the tree

keyComparator

private java.util.Comparator<K> keyComparator

The Comparator used for comparing the keys

valueComparator

private java.util.Comparator<V> valueComparator

The Comparator used for comparing the values

first

private LinkedAvlMapNode<K,V> first

node representing the start of the doubly linked list formed with the tree nodes

last

private LinkedAvlMapNode<K,V> last

node representing the end of the doubly linked list formed with the tree nodes

allowDuplicates

private boolean allowDuplicates

flag to allow storing duplicate keys

size

private int size

size of the map

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:

keyComparator - the comparator to be used for comparing keys

valueComparator - the comparator to be used for comparing values

AvlTreeMapImpl

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

Creates a new instance of AVLTreeMap without support for duplicate keys.

Parameters:

keyComparator - the comparator to be used for comparing keys

valueComparator - the comparator to be used for comparing values

allowDuplicates - are duplicates keyComparators allowed?

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.

insertDupKey

private V insertDupKey(V value,
                       LinkedAvlMapNode<K,V> existingNode)

removeFromList

private void removeFromList(LinkedAvlMapNode<K,V> node)

insertInList

private void insertInList(LinkedAvlMapNode<K,V> node,
                          LinkedAvlMapNode<K,V> parentNode,
                          int pos)

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

balanceNodesAfterRemove

private void balanceNodesAfterRemove(java.util.List<LinkedAvlMapNode<K,V>> treePath,
                                     LinkedAvlMapNode<K,V> delNode)

changes the order of nodes after a delete operation and then balances the tree

Parameters:

treePath - the path traversed to find the node temp

delNode - the node to be deleted

balance

private void balance(java.util.List<LinkedAvlMapNode<K,V>> treePath)

Balances the tree by visiting the nodes present in the List of nodes present in the treePath parameter.

This really does the balancing if the height of the tree is greater than 2 and the
balance factor is greater than +1 or less than -1.

For an excellent info please read the Wikipedia article on AVL tree.

Parameters:

treePath - the traversed list of LinkedAvlMapNodes after performing an insert/delete operation.

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

setRoot

void setRoot(LinkedAvlMapNode<K,V> root)

Set the root of the tree. Note : this method is used by the deserialization method

Parameters:

root - the root of the tree

setFirst

void setFirst(LinkedAvlMapNode<K,V> first)

Set the first element of the tree Note : this method is used by the deserialization method

Parameters:

first - the first element to be added

setLast

void setLast(LinkedAvlMapNode<K,V> last)

Set the last element of the tree Note : this method is used by the deserialization method

Parameters:

last - the last element to be added

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

rotateSingleLeft

private void rotateSingleLeft(LinkedAvlMapNode<K,V> node,
                              LinkedAvlMapNode<K,V> parentNode)

Rotate the node left side once.

Parameters:

node - the LinkedAvlMapNode to be rotated

parentNode - parent LinkedAvlMapNode of node

rotateSingleRight

private void rotateSingleRight(LinkedAvlMapNode<K,V> node,
                               LinkedAvlMapNode<K,V> parentNode)

Rotate the node right side once.

Parameters:

node - the LinkedAvlMapNode to be rotated

parentNode - parent LinkedAvlMapNode of node

detachNodes

private void detachNodes(LinkedAvlMapNode<K,V> node,
                         LinkedAvlMapNode<K,V> parentNode)

Detach a LinkedAvlMapNode from its parent

Parameters:

node - the LinkedAvlMapNode to be detached

parentNode - the parent LinkedAvlMapNode of the node

replaceNode

private void replaceNode(LinkedAvlMapNode<K,V> deleteNode,
                         LinkedAvlMapNode<K,V> replaceNode,
                         LinkedAvlMapNode<K,V> parentNode)

Replace a LinkedAvlMapNode to be removed with a new existing LinkedAvlMapNode

Parameters:

deleteNode - the LinkedAvlMapNode to be deleted

replaceNode - the LinkedAvlMapNode to replace the deleteNode

parentNode - the parent LinkedAvlMapNode of deleteNode

find

private java.util.List<LinkedAvlMapNode<K,V>> find(K key,
                                                   LinkedAvlMapNode<K,V> startNode,
                                                   java.util.List<LinkedAvlMapNode<K,V>> path)

Find a LinkedAvlMapNode with the given key value in the tree starting from the startNode.

Parameters:

key - the key to find

startNode - starting node of a subtree/tree

path - the list to be filled with traversed nodes

Returns:

the list of traversed LinkedAvlMapNodes.

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.

fetchNonNullNode

private LinkedAvlMapNode<K,V> fetchNonNullNode(K key,
                                               LinkedAvlMapNode<K,V> startNode,
                                               LinkedAvlMapNode<K,V> parent)

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

find

private LinkedAvlMapNode<K,V> find(K key,
                                   LinkedAvlMapNode<K,V> startNode)

findMax

private java.util.List<LinkedAvlMapNode<K,V>> findMax(LinkedAvlMapNode<K,V> startNode)

Find the LinkedAvlMapNode having the max key value in the tree starting from the startNode.

Parameters:

startNode - starting node of a subtree/tree

Returns:

the list of traversed LinkedAvlMapNodes.

findMin

private java.util.List<LinkedAvlMapNode<K,V>> findMin(LinkedAvlMapNode<K,V> startNode)

Find the LinkedAvlMapNode having the min key value in the tree starting from the startNode.

Parameters:

startNode - starting node of a subtree/tree

Returns:

the list of traversed LinkedAvlMapNodes.

getBalance

private int getBalance(LinkedAvlMapNode<K,V> node)

Get balance-factor of the given LinkedAvlMapNode.

Parameters:

node - a LinkedAvlMapNode

Returns:

balance-factor of the node

visit

private void visit(LinkedAvlMapNode<K,V> node,
                   LinkedAvlMapNode<K,V> parentNode)

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

removeAll

public void removeAll()

removes all the nodes from the tree