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.avl;
21
22
23 import java.util.Iterator;
24
25
26 /**
27 * AVL Tree Set iterator
28 *
29 * @author Vladimir Lysyy (http://bobah.net)
30 *
31 */
32 final class AvlTreeIterator<T extends Comparable<T>> implements Iterator<T>
33 {
34 private AvlNode<T> root;
35 private AvlNode<T> next = null;
36 private boolean initial = true;
37
38
39 AvlTreeIterator( AvlNode<T> root )
40 {
41 this.root = root;
42 findNext();
43 }
44
45
46 @Override
47 public boolean hasNext()
48 {
49 return next != null || ( initial && root != null );
50 }
51
52
53 @Override
54 public T next()
55 {
56 T value = next == null ? null : next.value;
57 findNext();
58 return value;
59 }
60
61
62 public void findNext()
63 {
64 if ( next == null )
65 {
66 if ( root == null || !initial )
67 {
68 return;
69 }
70
71 initial = false;
72 next = root;
73
74 while ( next.left != null )
75 {
76 next = next.left;
77 }
78 }
79 else
80 {
81 if ( next.right != null )
82 {
83 next = next.right;
84
85 while ( next.left != null )
86 {
87 next = next.left;
88 }
89 }
90 else
91 {
92 AvlNode<T> parent = next.parent;
93
94 while ( parent != null && parent.left != next )
95 {
96 next = parent;
97 parent = next.parent;
98 }
99
100 next = parent;
101 }
102 }
103 }
104
105
106 @Override
107 public void remove()
108 {
109 assert false : "not supported";
110 }
111 }