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 public AvlTreeIterator( AvlNode<T> root )
40 {
41 this.root = root;
42 find_next();
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 find_next();
58 return value;
59 }
60
61
62 public void find_next()
63 {
64 if ( next == null )
65 {
66 if ( root == null || !initial )
67 return;
68 initial = false;
69 next = root;
70 while ( next.left != null )
71 next = next.left;
72 }
73 else
74 {
75 if ( next.right != null )
76 {
77 next = next.right;
78 while ( next.left != null )
79 next = next.left;
80 }
81 else
82 {
83 AvlNode<T> parent = next.parent;
84
85 while ( parent != null && parent.left != next )
86 {
87 next = parent;
88 parent = next.parent;
89 }
90
91 next = parent;
92 }
93 }
94 }
95
96
97 @Override
98 public void remove()
99 {
100 assert false : "not supported";
101 }
102 }