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     */
020    package org.apache.directory.server.core.avltree;
021    
022    
023    import java.util.Comparator;
024    import 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     * @version $Rev$, $Date$
032     */
033    public interface AvlTree<K>
034    {
035    
036        /**
037         * @return the comparator associated with this tree 
038         */
039        public abstract Comparator<K> getComparator();
040    
041    
042        /**
043         * Inserts a LinkedAvlNode with the given key.
044         *
045         * @param key the item to be inserted
046         * @return the replaced key if it already exists
047         * Note: Ignores if a node with the given key already exists.
048         */
049        public abstract K insert( K key );
050    
051    
052        /**
053         * Removes the LinkedAvlNode present in the tree with the given key value
054         *
055         * @param key the value of the node to be removed
056         * @return the removed key, if any, or null if the key does not exist
057         */
058        public abstract K remove( K key );
059    
060    
061        /**
062         * Tests if the tree is logically empty.
063         * 
064         * @return true if the tree is empty, false otherwise
065         */
066        public abstract boolean isEmpty();
067    
068    
069        /**
070         * returns the number of nodes present in this tree.
071         * 
072         * @return the number of nodes present in this tree
073         */
074        //NOTE: This method is internally used by AVLTreeMarshaller
075        public abstract int getSize();
076    
077    
078        /**
079         * @return the root element of this tree (ie, not the first, but the
080         * topmost element)
081         */
082        public abstract LinkedAvlNode<K> getRoot();
083    
084    
085        /**
086         * @return a list of the stored keys in this tree
087         */
088        public abstract List<K> getKeys();
089    
090    
091        /**
092         * Prints the contents of AVL tree in pretty format
093         */
094        public abstract void printTree();
095    
096    
097        /**
098         * @return The first element of this tree
099         */
100        public abstract LinkedAvlNode<K> getFirst();
101    
102    
103        /**
104         * @return The last element in this tree
105         */
106        public abstract LinkedAvlNode<K> getLast();
107    
108    
109        /**
110         * Finds a LinkedAvlNode<K> whose key is higher than the given key.
111         *
112         * @param key the key
113         * @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
114         *         null if there is no node with a higher key than the given key.
115         */
116        public abstract LinkedAvlNode<K> findGreater( K key );
117    
118    
119        /**
120         * Finds a LinkedAvlNode<K> whose key is higher than the given key.
121         *
122         * @param key the key
123         * @return the LinkedAvlNode<K> whose key is greater than the given key ,<br>
124         *         null if there is no node with a higher key than the given key.
125         */
126        public abstract LinkedAvlNode<K> findGreaterOrEqual( K key );
127    
128    
129        /**
130         * Finds a LinkedAvlNode<K> whose key is lower than the given key.
131         *
132         * @param key the key
133         * @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
134         *         null if there is no node with a lower key than the given key.
135         */
136        public abstract LinkedAvlNode<K> findLess( K key );
137    
138    
139        /**
140         * Finds a LinkedAvlNode<K> whose key is lower than the given key.
141         *
142         * @param key the key
143         * @return the LinkedAvlNode<K> whose key is lower than the given key ,<br>
144         *         null if there is no node with a lower key than the given key.
145         */
146        public abstract LinkedAvlNode<K> findLessOrEqual( K key );
147    
148    
149        /**
150         * 
151         * Find a LinkedAvlNode with the given key value in the tree.
152         *
153         * @param key the key to find
154         * @return the list of traversed LinkedAvlNode.
155         */
156        public abstract LinkedAvlNode<K> find( K key );
157    
158    }