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<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 }