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 org.apache.directory.shared.ldap.cursor.AbstractCursor; 024 import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException; 025 026 027 /** 028 * A Cursor for an AvlTree. 029 * 030 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 031 * @version $Rev$, $Date$ 032 */ 033 public class AvlTreeCursor<K> extends AbstractCursor<K> 034 { 035 private AvlTree<K> tree; 036 private LinkedAvlNode<K> node; 037 private boolean onNode = false; 038 private boolean isAfterLast = false; 039 private boolean isBeforeFirst = true; 040 041 042 public AvlTreeCursor( AvlTree<K> tree ) 043 { 044 this.tree = tree; 045 } 046 047 048 public void after( K element ) throws Exception 049 { 050 checkNotClosed( "after" ); 051 052 if ( element == null ) 053 { 054 afterLast(); 055 return; 056 } 057 058 LinkedAvlNode<K> found = tree.findGreater( element ); 059 060 if ( found == null ) 061 { 062 node = tree.getLast(); 063 onNode = false; 064 isAfterLast = true; 065 isBeforeFirst = false; 066 return; 067 } 068 069 node = found; 070 isAfterLast = false; 071 isBeforeFirst = false; 072 onNode = false; 073 } 074 075 076 public void afterLast() throws Exception 077 { 078 checkNotClosed( "afterLast" ); 079 node = tree.getLast(); 080 isBeforeFirst = false; 081 isAfterLast = true; 082 onNode = false; 083 } 084 085 086 public boolean available() 087 { 088 return onNode; 089 } 090 091 092 public void before( K element ) throws Exception 093 { 094 checkNotClosed( "before" ); 095 096 if ( element == null ) 097 { 098 beforeFirst(); 099 return; 100 } 101 102 LinkedAvlNode<K> found = tree.findLess( element ); 103 if ( found == null ) 104 { 105 node = tree.getFirst(); 106 isAfterLast = false; 107 isBeforeFirst = true; 108 } 109 else 110 { 111 node = found.next; 112 isAfterLast = false; 113 isBeforeFirst = false; 114 } 115 onNode = false; 116 } 117 118 119 public void beforeFirst() throws Exception 120 { 121 checkNotClosed( "beforeFirst" ); 122 node = tree.getFirst(); 123 isBeforeFirst = true; 124 isAfterLast = false; 125 onNode = false; 126 } 127 128 129 public boolean first() throws Exception 130 { 131 checkNotClosed( "first" ); 132 node = tree.getFirst(); 133 isBeforeFirst = false; 134 isAfterLast = false; 135 return onNode = node != null; 136 } 137 138 139 public K get() throws Exception 140 { 141 checkNotClosed( "get" ); 142 if ( onNode ) 143 { 144 return node.getKey(); 145 } 146 147 throw new InvalidCursorPositionException(); 148 } 149 150 151 public boolean isElementReused() 152 { 153 return true; 154 } 155 156 157 public boolean last() throws Exception 158 { 159 checkNotClosed( "last" ); 160 node = tree.getLast(); 161 isBeforeFirst = false; 162 isAfterLast = false; 163 return onNode = node != null; 164 } 165 166 167 public boolean next() throws Exception 168 { 169 checkNotClosed( "next" ); 170 171 if ( isBeforeFirst ) 172 { 173 node = tree.getFirst(); 174 isBeforeFirst = false; 175 isAfterLast = false; 176 return onNode = node != null; 177 } 178 179 if ( isAfterLast ) 180 { 181 return false; 182 } 183 else if ( onNode ) 184 { 185 if ( node == null ) 186 { 187 node = tree.getFirst(); 188 return true; 189 } 190 191 if ( node.next == null ) 192 { 193 onNode = false; 194 isAfterLast = true; 195 isBeforeFirst = false; 196 return false; 197 } 198 199 node = node.next; 200 return true; 201 } 202 203 return node != null && ( onNode = true ); 204 } 205 206 207 public boolean previous() throws Exception 208 { 209 checkNotClosed( "previous" ); 210 211 if ( isBeforeFirst ) 212 { 213 return false; 214 } 215 216 if ( isAfterLast ) 217 { 218 node = tree.getLast(); 219 isBeforeFirst = false; 220 isAfterLast = false; 221 return onNode = node != null; 222 } 223 224 if ( onNode ) 225 { 226 if ( node == null ) 227 { 228 node = tree.getLast(); 229 return true; 230 } 231 if ( node.previous == null ) 232 { 233 onNode = false; 234 isAfterLast = false; 235 isBeforeFirst = true; 236 return false; 237 } 238 239 node = node.previous; 240 return true; 241 } 242 243 return false; 244 } 245 }