001/*
002 *   Licensed to the Apache Software Foundation (ASF) under one
003 *   or more contributor license agreements.  See the NOTICE file
004 *   distributed with this work for additional information
005 *   regarding copyright ownership.  The ASF licenses this file
006 *   to you under the Apache License, Version 2.0 (the
007 *   "License"); you may not use this file except in compliance
008 *   with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 *   Unless required by applicable law or agreed to in writing,
013 *   software distributed under the License is distributed on an
014 *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 *   KIND, either express or implied.  See the License for the
016 *   specific language governing permissions and limitations
017 *   under the License.
018 *
019 */
020package org.apache.directory.server.core.avltree;
021
022
023import java.util.Comparator;
024import java.util.List;
025
026
027/**
028 * The interface for an AVL Tree.
029 *
030 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
031 */
032public interface AvlTree<K>
033{
034
035    /**
036     * @return the comparator associated with this tree 
037     */
038    Comparator<K> getComparator();
039
040
041    /**
042     * Inserts a LinkedAvlNode with the given key.
043     *
044     * @param key the item to be inserted
045     * @return the replaced key if it already exists
046     * Note: Ignores if a node with the given key already exists.
047     */
048    K insert( K key );
049
050
051    /**
052     * Removes the LinkedAvlNode present in the tree with the given key value
053     *
054     * @param key the value of the node to be removed
055     * @return the removed key, if any, or null if the key does not exist
056     */
057    K remove( K key );
058
059
060    /**
061     * Tests if the tree is logically empty.
062     * 
063     * @return true if the tree is empty, false otherwise
064     */
065    boolean isEmpty();
066
067
068    /**
069     * returns the number of nodes present in this tree.
070     * 
071     * @return the number of nodes present in this tree
072     */
073    //NOTE: This method is internally used by AVLTreeMarshaller
074    int getSize();
075
076
077    /**
078     * @return the root element of this tree (ie, not the first, but the
079     * topmost element)
080     */
081    LinkedAvlNode<K> getRoot();
082
083
084    /**
085     * @return a list of the stored keys in this tree
086     */
087    List<K> getKeys();
088
089
090    /**
091     * Prints the contents of AVL tree in pretty format
092     */
093    void printTree();
094
095
096    /**
097     * @return The first element of this tree
098     */
099    LinkedAvlNode<K> getFirst();
100
101
102    /**
103     * @return The last element in this tree
104     */
105    LinkedAvlNode<K> getLast();
106
107
108    /**
109     * Finds a LinkedAvlNode whose key is higher than the given key.
110     *
111     * @param key the key
112     * @return the LinkedAvlNode whose key is greater than the given key ,<br>
113     *         null if there is no node with a higher key than the given key.
114     */
115    LinkedAvlNode<K> findGreater( K key );
116
117
118    /**
119     * Finds a LinkedAvlNode whose key is higher than the given key.
120     *
121     * @param key the key
122     * @return the LinkedAvlNode whose key is greater than the given key ,<br>
123     *         null if there is no node with a higher key than the given key.
124     */
125    LinkedAvlNode<K> findGreaterOrEqual( K key );
126
127
128    /**
129     * Finds a LinkedAvlNode whose key is lower than the given key.
130     *
131     * @param key the key
132     * @return the LinkedAvlNode whose key is lower than the given key ,<br>
133     *         null if there is no node with a lower key than the given key.
134     */
135    LinkedAvlNode<K> findLess( K key );
136
137
138    /**
139     * Finds a LinkedAvlNode whose key is lower than the given key.
140     *
141     * @param key the key
142     * @return the LinkedAvlNode whose key is lower than the given key ,<br>
143     *         null if there is no node with a lower key than the given key.
144     */
145    LinkedAvlNode<K> findLessOrEqual( K key );
146
147
148    /**
149     * 
150     * Find a LinkedAvlNode with the given key value in the tree.
151     *
152     * @param key the key to find
153     * @return the list of traversed LinkedAvlNode.
154     */
155    LinkedAvlNode<K> find( K key );
156}