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 */
017package org.apache.activemq.store.kahadb.disk.index;
018
019import java.util.List;
020
021/**
022 * Interface used to selectively visit the entries in a BTree.
023 * 
024 * @param <Key>
025 * @param <Value>
026 */
027public 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}