View Javadoc

1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
18   *
19   */
20  package org.apache.directory.server.core.avltree;
21  
22  
23  import org.apache.directory.server.core.cursor.AbstractCursor;
24  import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
25  
26  
27  /**
28   * A Cursor for an AvlTree.
29   *
30   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
31   * @version $Rev$, $Date$
32   */
33  public class AvlTreeCursor<K> extends AbstractCursor<K>
34  {
35      private AvlTree<K> tree;
36      private LinkedAvlNode<K> node;
37      private boolean onNode = false;
38      private boolean isAfterLast = false;
39      private boolean isBeforeFirst = true;
40   
41      
42      public AvlTreeCursor( AvlTree<K> tree )
43      {
44          this.tree = tree;
45      }
46  
47      
48      public void after( K element ) throws Exception 
49      {
50          checkNotClosed( "after" );
51  
52          if ( element == null )
53          {
54              afterLast();
55              return;
56          }
57  
58          LinkedAvlNode<K> found = tree.findGreater( element );
59          
60          if ( found == null )
61          {
62              node = tree.getLast();
63              onNode = false;
64              isAfterLast = true;
65              isBeforeFirst = false;
66              return;
67          }
68  
69          node = found;
70          isAfterLast = false;
71          isBeforeFirst = false;
72          onNode = false;
73      }
74  
75  
76      public void afterLast() throws Exception 
77      {
78          checkNotClosed( "afterLast" );
79          node = tree.getLast();
80          isBeforeFirst = false;
81          isAfterLast = true;
82          onNode = false;
83      }
84  
85  
86      public boolean available()
87      {
88          return onNode;
89      }
90  
91  
92      public void before( K element ) throws Exception 
93      {
94          checkNotClosed( "before" );
95  
96          if ( element == null )
97          {
98              beforeFirst();
99              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 }