1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 *
19 */
20 package org.apache.directory.server.core.avltree;
21
22
23 import java.util.Comparator;
24 import java.util.List;
25
26
27 /**
28 * An interface to the AVL tree based map. The implementations
29 * should hold a value(s) along with a key
30 *
31 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
32 */
33 public interface AvlTreeMap<K, V>
34 {
35
36 /**
37 * @return the key comparator associated with this tree
38 */
39 Comparator<K> getKeyComparator();
40
41
42 /**
43 * @return the value comparator associated with this tree
44 */
45 Comparator<V> getValueComparator();
46
47
48 /**
49 * Inserts a LinkedAvlMapNode with the given key and value.
50 *
51 * @param key the item to be inserted
52 * @param value the value associated with the key
53 * @return the replaced value if any exists else null
54 * Note: Replaces a nodes value if duplicate keys are not allowed and the new value is
55 * not equal to the existing value.
56 */
57 V insert( K key, V value );
58
59
60 /**
61 * Removes the LinkedAvlMapNode present in the tree with the given key and value
62 *
63 * @param key the key of the node to be removed
64 * @param value the value of the node
65 * @return the removed value, if any, or null if the key or value does not exist
66 * @throws IllegalArgumentException if key or value is null
67 */
68 V remove( K key, V value );
69
70
71 /**
72 * Removes a node associated with the given key
73 * The entire node will be removed irrespective of whether duplicate keys
74 * are enabled or not
75 *
76 * @param key the key of the node to be removed
77 * @return a SingletonOrOrderedSet
78 * @throws IllegalArgumentException if key is null
79 */
80 SingletonOrOrderedSet<V> remove( K key );
81
82
83 /**
84 * Tests if the tree is logically empty.
85 *
86 * @return true if the tree is empty, false otherwise
87 */
88 boolean isEmpty();
89
90
91 /**
92 * returns the number of nodes present in this tree.
93 *
94 * @return the number of nodes present in this tree
95 */
96 int getSize();
97
98
99 /**
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 whose key is higher than the given key.
132 *
133 * @param key the key
134 * @return the LinkedAvlMapNode 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 whose key is higher than the given key.
142 *
143 * @param key the key
144 * @return the LinkedAvlMapNode 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 whose key is lower than the given key.
152 *
153 * @param key the key
154 * @return the LinkedAvlMapNode 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 whose key is lower than the given key.
162 *
163 * @param key the key
164 * @return the LinkedAvlMapNode 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 }