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