File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\TreeCursor.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.index;
8
9 import org.h2.result.Row;
10 import org.h2.result.SearchRow;
11
12 /**
13 * The cursor implementation for a tree index.
14 */
15 public class TreeCursor implements Cursor {
16 private final TreeIndex tree;
17 private TreeNode node;
18 private boolean beforeFirst;
19 private final SearchRow first, last;
20
21 TreeCursor(TreeIndex tree, TreeNode node, SearchRow first, SearchRow last) {
22 this.tree = tree;
23 this.node = node;
24 this.first = first;
25 this.last = last;
26 beforeFirst = true;
27 }
28
29 public Row get() {
30 return node == null ? null : node.row;
31 }
32
33 public SearchRow getSearchRow() {
34 return get();
35 }
36
37 public boolean next() {
38 if (beforeFirst) {
39 beforeFirst = false;
40 if (node == null) {
41 return false;
42 }
43 if (first != null && tree.compareRows(node.row, first) < 0) {
44 node = next(node);
45 }
46 } else {
47 node = next(node);
48 }
49 if (node != null && last != null) {
50 if (tree.compareRows(node.row, last) > 0) {
51 node = null;
52 }
53 }
54 return node != null;
55 }
56
57 public boolean previous() {
58 node = previous(node);
59 return node != null;
60 }
61
62 /**
63 * Get the next node if there is one.
64 *
65 * @param x the node
66 * @return the next node or null
67 */
68 private static TreeNode next(TreeNode x) {
69 if (x == null) {
70 return null;
71 }
72 TreeNode r = x.right;
73 if (r != null) {
74 x = r;
75 TreeNode l = x.left;
76 while (l != null) {
77 x = l;
78 l = x.left;
79 }
80 return x;
81 }
82 TreeNode ch = x;
83 x = x.parent;
84 while (x != null && ch == x.right) {
85 ch = x;
86 x = x.parent;
87 }
88 return x;
89 }
90
91
92 /**
93 * Get the previous node if there is one.
94 *
95 * @param x the node
96 * @return the previous node or null
97 */
98 private static TreeNode previous(TreeNode x) {
99 if (x == null) {
100 return null;
101 }
102 TreeNode l = x.left;
103 if (l != null) {
104 x = l;
105 TreeNode r = x.right;
106 while (r != null) {
107 x = r;
108 r = x.right;
109 }
110 return x;
111 }
112 TreeNode ch = x;
113 x = x.parent;
114 while (x != null && ch == x.left) {
115 ch = x;
116 x = x.parent;
117 }
118 return x;
119 }
120
121 }
122