1 /**
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.kahadb.index;
18
19 import java.util.List;
20
21 /**
22 * Interface used to selectively visit the entries in a BTree.
23 *
24 * @param <Key>
25 * @param <Value>
26 */
27 public interface BTreeVisitor<Key,Value> {
28
29 /**
30 * Do you want to visit the range of BTree entries between the first and and second key?
31 *
32 * @param first if null indicates the range of values before the second key.
33 * @param second if null indicates the range of values after the first key.
34 * @return true if you want to visit the values between the first and second key.
35 */
36 boolean isInterestedInKeysBetween(Key first, Key second);
37
38 /**
39 * The keys and values of a BTree leaf node.
40 *
41 * @param keys
42 * @param values
43 */
44 void visit(List<Key> keys, List<Value> values);
45
46 public interface Predicate<Key> {
47 boolean isInterestedInKeysBetween(Key first, Key second);
48 boolean isInterestedInKey(Key key);
49 }
50
51 abstract class PredicateVisitor<Key, Value> implements BTreeVisitor<Key, Value>, Predicate<Key> {
52 public void visit(List<Key> keys, List<Value> values) {
53 for( int i=0; i < keys.size(); i++) {
54 Key key = keys.get(i);
55 if( isInterestedInKey(key) ) {
56 matched(key, values.get(i));
57 }
58 }
59 }
60
61 protected void matched(Key key, Value value) {
62 }
63 }
64
65 class OrVisitor<Key, Value> extends PredicateVisitor<Key, Value> {
66 private final List<Predicate<Key>> conditions;
67
68 public OrVisitor(List<Predicate<Key>> conditions) {
69 this.conditions = conditions;
70 }
71
72 public boolean isInterestedInKeysBetween(Key first, Key second) {
73 for (Predicate<Key> condition : conditions) {
74 if( condition.isInterestedInKeysBetween(first, second) ) {
75 return true;
76 }
77 }
78 return false;
79 }
80
81 public boolean isInterestedInKey(Key key) {
82 for (Predicate<Key> condition : conditions) {
83 if( condition.isInterestedInKey(key) ) {
84 return true;
85 }
86 }
87 return false;
88 }
89
90 @Override
91 public String toString() {
92 StringBuilder sb = new StringBuilder();
93 boolean first=true;
94 for (Predicate<Key> condition : conditions) {
95 if( !first ) {
96 sb.append(" OR ");
97 }
98 first=false;
99 sb.append("(");
100 sb.append(condition);
101 sb.append(")");
102 }
103 return sb.toString();
104 }
105 }
106
107 class AndVisitor<Key, Value> extends PredicateVisitor<Key, Value> {
108 private final List<Predicate<Key>> conditions;
109
110 public AndVisitor(List<Predicate<Key>> conditions) {
111 this.conditions = conditions;
112 }
113
114 public boolean isInterestedInKeysBetween(Key first, Key second) {
115 for (Predicate<Key> condition : conditions) {
116 if( !condition.isInterestedInKeysBetween(first, second) ) {
117 return false;
118 }
119 }
120 return true;
121 }
122
123 public boolean isInterestedInKey(Key key) {
124 for (Predicate<Key> condition : conditions) {
125 if( !condition.isInterestedInKey(key) ) {
126 return false;
127 }
128 }
129 return true;
130 }
131
132 @Override
133 public String toString() {
134 StringBuilder sb = new StringBuilder();
135 boolean first=true;
136 for (Predicate<Key> condition : conditions) {
137 if( !first ) {
138 sb.append(" AND ");
139 }
140 first=false;
141 sb.append("(");
142 sb.append(condition);
143 sb.append(")");
144 }
145 return sb.toString();
146 }
147 }
148
149 class BetweenVisitor<Key extends Comparable<Key>, Value> extends PredicateVisitor<Key, Value> {
150 private final Key first;
151 private final Key last;
152
153 public BetweenVisitor(Key first, Key last) {
154 this.first = first;
155 this.last = last;
156 }
157
158 public boolean isInterestedInKeysBetween(Key first, Key second) {
159 return (second==null || second.compareTo(this.first)>=0)
160 && (first==null || first.compareTo(last)<0);
161 }
162
163 public boolean isInterestedInKey(Key key) {
164 return key.compareTo(first) >=0 && key.compareTo(last) <0;
165 }
166
167 @Override
168 public String toString() {
169 return first+" <= key < "+last;
170 }
171 }
172
173 class GTVisitor<Key extends Comparable<Key>, Value> extends PredicateVisitor<Key, Value> {
174 final private Key value;
175
176 public GTVisitor(Key value) {
177 this.value = value;
178 }
179
180 public boolean isInterestedInKeysBetween(Key first, Key second) {
181 return second==null || second.compareTo(value)>0;
182 }
183
184 public boolean isInterestedInKey(Key key) {
185 return key.compareTo(value)>0;
186 }
187
188 @Override
189 public String toString() {
190 return "key > "+ value;
191 }
192 }
193
194 class GTEVisitor<Key extends Comparable<Key>, Value> extends PredicateVisitor<Key, Value> {
195 final private Key value;
196
197 public GTEVisitor(Key value) {
198 this.value = value;
199 }
200
201 public boolean isInterestedInKeysBetween(Key first, Key second) {
202 return second==null || second.compareTo(value)>=0;
203 }
204
205 public boolean isInterestedInKey(Key key) {
206 return key.compareTo(value)>=0;
207 }
208
209 @Override
210 public String toString() {
211 return "key >= "+ value;
212 }
213 }
214
215 class LTVisitor<Key extends Comparable<Key>, Value> extends PredicateVisitor<Key, Value> {
216 final private Key value;
217
218 public LTVisitor(Key value) {
219 this.value = value;
220 }
221
222 public boolean isInterestedInKeysBetween(Key first, Key second) {
223 return first==null || first.compareTo(value)<0;
224 }
225
226 public boolean isInterestedInKey(Key key) {
227 return key.compareTo(value)<0;
228 }
229
230 @Override
231 public String toString() {
232 return "key < "+ value;
233 }
234 }
235
236 class LTEVisitor<Key extends Comparable<Key>, Value> extends PredicateVisitor<Key, Value> {
237 final private Key value;
238
239 public LTEVisitor(Key value) {
240 this.value = value;
241 }
242
243 public boolean isInterestedInKeysBetween(Key first, Key second) {
244 return first==null || first.compareTo(value)<=0;
245 }
246
247 public boolean isInterestedInKey(Key key) {
248 return key.compareTo(value)<=0;
249 }
250
251 @Override
252 public String toString() {
253 return "key <= "+ value;
254 }
255 }
256 }