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