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