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 * An interface to the AVL tree based map. The implementations 029 * should hold a value(s) along with a key 030 * 031 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 032 */ 033public 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 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}