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     * An interface to the AVL tree based map. The implementations
028     * should hold a value(s) along with a key  
029     *
030     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
031     * @version $Rev$, $Date$
032     */
033    public interface AvlTreeMap<K, V>
034    {
035    
036        /**
037         * @return the key comparator associated with this tree 
038         */
039        Comparator<K> getKeyComparator();
040    
041    
042        /**
043         * @return the value comparator associated with this tree 
044         */
045        Comparator<V> getValueComparator();
046    
047    
048        /**
049         * Inserts a LinkedAvlMapNode with the given key and value.
050         *
051         * @param key the item to be inserted
052         * @param value the value associated with the key
053         * @return the replaced value if any exists else null
054         * Note: Replaces a nodes value if duplicate keys are not allowed and the new value is
055         *       not equal to the existing value.
056         */
057        V insert( K key, V value );
058    
059    
060        /**
061         * Removes the LinkedAvlMapNode present in the tree with the given key and value
062         *
063         * @param key the key of the node to be removed
064         * @param value the value of the node
065         * @return the removed value, if any, or null if the key or value does not exist
066         * @throws IllegalArgumentException if key or value is null
067         */
068        V remove( K key, V value );
069    
070    
071        /**
072         * Removes a node associated with the given key
073         * The entire node will be removed irrespective of whether duplicate keys
074         * are enabled or not
075         * 
076         * @param key the key of the node to be removed
077         * @return a SingletonOrOrderedSet
078         * @throws IllegalArgumentException if key is null
079         */
080        SingletonOrOrderedSet<V> remove( K key );
081    
082        
083        /**
084         * Tests if the tree is logically empty.
085         * 
086         * @return true if the tree is empty, false otherwise
087         */
088        boolean isEmpty();
089    
090    
091        /**
092         * returns the number of nodes present in this tree.
093         * 
094         * @return the number of nodes present in this tree
095         */
096        int getSize();
097    
098    
099        /**
100         * @return the root element of this tree (i.e., not the first, but the
101         * topmost element)
102         */
103        LinkedAvlMapNode<K, V> getRoot();
104    
105    
106        /**
107         * @return a list of the stored keys in this tree
108         */
109        List<K> getKeys();
110    
111    
112        /**
113         * Prints the contents of AVL tree in pretty format
114         */
115        void printTree();
116    
117    
118        /**
119         * @return The first element of this tree
120         */
121        LinkedAvlMapNode<K, V> getFirst();
122    
123    
124        /**
125         * @return The last element in this tree
126         */
127        LinkedAvlMapNode<K, V> getLast();
128    
129    
130        /**
131         * Finds a LinkedAvlMapNode<K,V> whose key is higher than the given key.
132         *
133         * @param key the key
134         * @return the LinkedAvlMapNode<K,V> whose key is greater than the given key ,<br>
135         *         null if there is no node with a higher key than the given key.
136         */
137        LinkedAvlMapNode<K, V> findGreater( K key );
138    
139    
140        /**
141         * Finds a LinkedAvlMapNode<K,V> whose key is higher than the given key.
142         *
143         * @param key the key
144         * @return the LinkedAvlMapNode<K,V> whose key is greater than the given key ,<br>
145         *         null if there is no node with a higher key than the given key.
146         */
147        LinkedAvlMapNode<K, V> findGreaterOrEqual( K key );
148    
149    
150        /**
151         * Finds a LinkedAvlMapNode<K,V> whose key is lower than the given key.
152         *
153         * @param key the key
154         * @return the LinkedAvlMapNode<K,V> whose key is lower than the given key ,<br>
155         *         null if there is no node with a lower key than the given key.
156         */
157        LinkedAvlMapNode<K, V> findLess( K key );
158    
159    
160        /**
161         * Finds a LinkedAvlMapNode<K,V> whose key is lower than the given key.
162         *
163         * @param key the key
164         * @return the LinkedAvlMapNode<K,V> whose key is lower than the given key ,<br>
165         *         null if there is no node with a lower key than the given key.
166         */
167        LinkedAvlMapNode<K, V> findLessOrEqual( K key );
168    
169    
170        /**
171         * 
172         * Find a LinkedAvlMapNode with the given key value in the tree.
173         *
174         * @param key the key to find
175         * @return the list of traversed LinkedAvlMapNode.
176         */
177        LinkedAvlMapNode<K, V> find( K key );
178    
179    
180        /**
181         * 
182         * Find a LinkedAvlMapNode with the given key and value in the tree.
183         *
184         * @param key the key of the node
185         * @param value the value of the node
186         * @return LinkedAvlMapNode having the given key and value
187         */
188        LinkedAvlMapNode<K, V> find( K key, V value );
189    
190    
191        /**
192         * tells if the duplicate keys are supported or not. 
193         *
194         * @return true if duplicate keys are allowed, false otherwise
195         */
196        boolean isDupsAllowed();
197    
198    }