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    }