001 /** 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.kahadb.index; 018 019 import java.util.List; 020 021 /** 022 * Interface used to selectively visit the entries in a BTree. 023 * 024 * @param <Key> 025 * @param <Value> 026 */ 027 public interface BTreeVisitor<Key,Value> { 028 029 /** 030 * Do you want to visit the range of BTree entries between the first and and second key? 031 * 032 * @param first if null indicates the range of values before the second key. 033 * @param second if null indicates the range of values after the first key. 034 * @return true if you want to visit the values between the first and second key. 035 */ 036 boolean isInterestedInKeysBetween(Key first, Key second); 037 038 /** 039 * The keys and values of a BTree leaf node. 040 * 041 * @param keys 042 * @param values 043 */ 044 void visit(List<Key> keys, List<Value> values); 045 046 public interface Predicate<Key> { 047 boolean isInterestedInKeysBetween(Key first, Key second); 048 boolean isInterestedInKey(Key key); 049 } 050 051 abstract class PredicateVisitor<Key, Value> implements BTreeVisitor<Key, Value>, Predicate<Key> { 052 public void visit(List<Key> keys, List<Value> values) { 053 for( int i=0; i < keys.size(); i++) { 054 Key key = keys.get(i); 055 if( isInterestedInKey(key) ) { 056 matched(key, values.get(i)); 057 } 058 } 059 } 060 061 protected void matched(Key key, Value value) { 062 } 063 } 064 065 class OrVisitor<Key, Value> extends PredicateVisitor<Key, Value> { 066 private final List<Predicate<Key>> conditions; 067 068 public OrVisitor(List<Predicate<Key>> conditions) { 069 this.conditions = conditions; 070 } 071 072 public boolean isInterestedInKeysBetween(Key first, Key second) { 073 for (Predicate<Key> condition : conditions) { 074 if( condition.isInterestedInKeysBetween(first, second) ) { 075 return true; 076 } 077 } 078 return false; 079 } 080 081 public boolean isInterestedInKey(Key key) { 082 for (Predicate<Key> condition : conditions) { 083 if( condition.isInterestedInKey(key) ) { 084 return true; 085 } 086 } 087 return false; 088 } 089 090 @Override 091 public String toString() { 092 StringBuilder sb = new StringBuilder(); 093 boolean first=true; 094 for (Predicate<Key> condition : conditions) { 095 if( !first ) { 096 sb.append(" OR "); 097 } 098 first=false; 099 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 }