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.activemq.store.kahadb.disk.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    }