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.mvstore; |
7 | |
8 | import java.util.Iterator; |
9 | |
10 | /** |
11 | * A cursor to iterate over elements in ascending order. |
12 | * |
13 | * @param <K> the key type |
14 | * @param <V> the value type |
15 | */ |
16 | public class Cursor<K, V> implements Iterator<K> { |
17 | |
18 | private final MVMap<K, ?> map; |
19 | private final K from; |
20 | private CursorPos pos; |
21 | private K current, last; |
22 | private V currentValue, lastValue; |
23 | private Page lastPage; |
24 | private final Page root; |
25 | private boolean initialized; |
26 | |
27 | Cursor(MVMap<K, ?> map, Page root, K from) { |
28 | this.map = map; |
29 | this.root = root; |
30 | this.from = from; |
31 | } |
32 | |
33 | @Override |
34 | public boolean hasNext() { |
35 | if (!initialized) { |
36 | min(root, from); |
37 | initialized = true; |
38 | fetchNext(); |
39 | } |
40 | return current != null; |
41 | } |
42 | |
43 | @Override |
44 | public K next() { |
45 | hasNext(); |
46 | K c = current; |
47 | last = current; |
48 | lastValue = currentValue; |
49 | lastPage = pos == null ? null : pos.page; |
50 | fetchNext(); |
51 | return c; |
52 | } |
53 | |
54 | /** |
55 | * Get the last read key if there was one. |
56 | * |
57 | * @return the key or null |
58 | */ |
59 | public K getKey() { |
60 | return last; |
61 | } |
62 | |
63 | /** |
64 | * Get the last read value if there was one. |
65 | * |
66 | * @return the value or null |
67 | */ |
68 | public V getValue() { |
69 | return lastValue; |
70 | } |
71 | |
72 | Page getPage() { |
73 | return lastPage; |
74 | } |
75 | |
76 | /** |
77 | * Skip over that many entries. This method is relatively fast (for this map |
78 | * implementation) even if many entries need to be skipped. |
79 | * |
80 | * @param n the number of entries to skip |
81 | */ |
82 | public void skip(long n) { |
83 | if (!hasNext()) { |
84 | return; |
85 | } |
86 | if (n < 10) { |
87 | while (n-- > 0) { |
88 | fetchNext(); |
89 | } |
90 | return; |
91 | } |
92 | long index = map.getKeyIndex(current); |
93 | K k = map.getKey(index + n); |
94 | pos = null; |
95 | min(root, k); |
96 | fetchNext(); |
97 | } |
98 | |
99 | @Override |
100 | public void remove() { |
101 | throw DataUtils.newUnsupportedOperationException( |
102 | "Removing is not supported"); |
103 | } |
104 | |
105 | /** |
106 | * Fetch the next entry that is equal or larger than the given key, starting |
107 | * from the given page. This method retains the stack. |
108 | * |
109 | * @param p the page to start |
110 | * @param from the key to search |
111 | */ |
112 | private void min(Page p, K from) { |
113 | while (true) { |
114 | if (p.isLeaf()) { |
115 | int x = from == null ? 0 : p.binarySearch(from); |
116 | if (x < 0) { |
117 | x = -x - 1; |
118 | } |
119 | pos = new CursorPos(p, x, pos); |
120 | break; |
121 | } |
122 | int x = from == null ? -1 : p.binarySearch(from); |
123 | if (x < 0) { |
124 | x = -x - 1; |
125 | } else { |
126 | x++; |
127 | } |
128 | pos = new CursorPos(p, x + 1, pos); |
129 | p = p.getChildPage(x); |
130 | } |
131 | } |
132 | |
133 | /** |
134 | * Fetch the next entry if there is one. |
135 | */ |
136 | @SuppressWarnings("unchecked") |
137 | private void fetchNext() { |
138 | while (pos != null) { |
139 | if (pos.index < pos.page.getKeyCount()) { |
140 | int index = pos.index++; |
141 | current = (K) pos.page.getKey(index); |
142 | currentValue = (V) pos.page.getValue(index); |
143 | return; |
144 | } |
145 | pos = pos.parent; |
146 | if (pos == null) { |
147 | break; |
148 | } |
149 | if (pos.index < map.getChildPageCount(pos.page)) { |
150 | min(pos.page.getChildPage(pos.index++), null); |
151 | } |
152 | } |
153 | current = null; |
154 | } |
155 | |
156 | } |