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.fusesource.hawtdb.api;
018    
019    import java.util.Arrays;
020    import java.util.Comparator;
021    import java.util.List;
022    
023    /**
024     * Implements commonly used Predicates like AND, OR, <, > etc. etc. 
025     *
026     * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
027     */
028    final public class Predicates {
029        
030        /**
031         * Implements a logical OR predicate over a list of predicate expressions.
032         *
033         * @param <Key>
034         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
035         */
036        static class OrPredicate<Key> implements Predicate<Key> {
037            private final List<Predicate<Key>> conditions;
038    
039            public OrPredicate(List<Predicate<Key>> conditions) {
040                this.conditions = conditions;
041            }
042    
043            final public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
044                for (Predicate<Key> condition : conditions) {
045                    if( condition.isInterestedInKeysBetween(first, second, comparator) ) {
046                        return true;
047                    }
048                }
049                return false;
050            }
051    
052            final public boolean isInterestedInKey(Key key, Comparator comparator) {
053                for (Predicate<Key> condition : conditions) {
054                    if( condition.isInterestedInKey(key, comparator) ) {
055                        return true;
056                    }
057                }
058                return false;
059            }
060    
061            @Override
062            public String toString() {
063                StringBuilder sb = new StringBuilder();
064                boolean first=true;
065                for (Predicate<Key> condition : conditions) {
066                    if( !first ) {
067                        sb.append(" OR ");
068                    }
069                    first=false;
070                    sb.append("(");
071                    sb.append(condition);
072                    sb.append(")");
073                }
074                return sb.toString();
075            }
076        }
077    
078        /**
079         * Implements a logical AND predicate over a list of predicate expressions.
080         *
081         * @param <Key> 
082         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
083         */
084        static class AndPredicate<Key> implements Predicate<Key> {
085            private final List<Predicate<Key>> conditions;
086    
087            public AndPredicate(List<Predicate<Key>> conditions) {
088                this.conditions = conditions;
089            }
090    
091            final public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
092                for (Predicate<Key> condition : conditions) {
093                    if( !condition.isInterestedInKeysBetween(first, second, comparator) ) {
094                        return false;
095                    }
096                }
097                return true;
098            }
099    
100            final public boolean isInterestedInKey(Key key, Comparator comparator) {
101                for (Predicate<Key> condition : conditions) {
102                    if( !condition.isInterestedInKey(key, comparator) ) {
103                        return false;
104                    }
105                }
106                return true;
107            }
108    
109            @Override
110            public String toString() {
111                StringBuilder sb = new StringBuilder();
112                boolean first=true;
113                for (Predicate<Key> condition : conditions) {
114                    if( !first ) {
115                        sb.append(" AND ");
116                    }
117                    first=false;
118                    sb.append("(");
119                    sb.append(condition);
120                    sb.append(")");
121                }
122                return sb.toString();
123            }
124        }
125    
126        abstract static class ComparingPredicate<Key> implements Predicate<Key> {
127    
128            final public int compare(Key key, Key value, Comparator comparator) {
129                if( comparator==null ) {
130                    return ((Comparable)key).compareTo(value);
131                } else {
132                    return comparator.compare(key, value);
133                }
134            }
135    
136        }
137    
138        /**
139         * Implements a BETWEEN predicate between two key values.  It matches inclusive on
140         * the first value and exclusive on the last value.  The predicate expression is
141         * equivalent to: <code>(first <= x) AND (x < last)</code>
142         *
143         * @param <Key> the class being compared
144         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
145         */
146        @SuppressWarnings({"unchecked"})
147        static class BetweenPredicate<Key> extends ComparingPredicate<Key> {
148            private final Key first;
149            private final Key last;
150    
151            public BetweenPredicate(Key first, Key last) {
152                this.first = first;
153                this.last = last;
154            }
155    
156            final public boolean isInterestedInKeysBetween(Key left, Key right, Comparator comparator) {
157                return (right==null || compare(right, first, comparator)>=0)
158                        && (left==null || compare(left, last, comparator)<0);
159            }
160    
161            final public boolean isInterestedInKey(Key key, Comparator comparator) {
162                return compare(key, first, comparator) >=0 && compare(key, last, comparator) <0;
163            }
164    
165            @Override
166            public String toString() {
167                return first+" <= key < "+last;
168            }
169        }
170    
171        /**
172         * Implements a greater than predicate.  The predicate expression is
173         * equivalent to: <code>x > value</code>
174         *
175         * @param <Key> the class being compared
176         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
177         */
178        @SuppressWarnings({"unchecked"})
179        static class GTPredicate<Key> extends ComparingPredicate<Key> {
180            final private Key value;
181    
182            public GTPredicate(Key value) {
183                this.value = value;
184            }
185    
186            final public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
187                return second==null || isInterestedInKey(second, comparator);
188            }
189    
190            final public boolean isInterestedInKey(Key key, Comparator comparator) {
191                return compare(key, value, comparator) > 0;
192            }
193    
194            @Override
195            public String toString() {
196                return "key > "+ value;
197            }
198        }
199    
200        /**
201         * Implements a greater than or equal to predicate.  The predicate expression is
202         * equivalent to: <code>x >= value</code>
203         *
204         * @param <Key> the class being compared
205         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
206         */
207        @SuppressWarnings({"unchecked"})
208        static class GTEPredicate<Key> extends ComparingPredicate<Key> {
209            final private Key value;
210    
211            public GTEPredicate(Key value) {
212                this.value = value;
213            }
214    
215            final public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
216                return second==null || isInterestedInKey(second, comparator);
217            }
218    
219            final public boolean isInterestedInKey(Key key, Comparator comparator) {
220                return compare(key, value, comparator)>=0;
221            }
222    
223            @Override
224            public String toString() {
225                return "key >= "+ value;
226            }
227        }
228    
229        /**
230         * Implements a less than predicate.  The predicate expression is
231         * equivalent to: <code>x < value</code>
232         *
233         * @param <Key> the class being compared
234         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
235         */
236        @SuppressWarnings({"unchecked"})
237        static class LTPredicate<Key> extends ComparingPredicate<Key> {
238            final private Key value;
239    
240            public LTPredicate(Key value) {
241                this.value = value;
242            }
243    
244            final public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
245                return first==null || isInterestedInKey(first, comparator);
246            }
247    
248            final public boolean isInterestedInKey(Key key, Comparator comparator) {
249                return compare(key, value, comparator)<0;
250            }
251    
252            @Override
253            public String toString() {
254                return "key < "+ value;
255            }
256        }
257    
258        /**
259         * Implements a less than or equal to predicate.  The predicate expression is
260         * equivalent to: <code>x <= value</code>.
261         *
262         * @param <Key> the class being compared
263         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
264         */
265        @SuppressWarnings({"unchecked"})
266        static class LTEPredicate<Key> extends ComparingPredicate<Key> {
267            final private Key value;
268    
269            public LTEPredicate(Key value) {
270                this.value = value;
271            }
272    
273            final public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
274                return first==null || isInterestedInKey(first, comparator);
275            }
276    
277            final public boolean isInterestedInKey(Key key, Comparator comparator) {
278                return compare(key, value, comparator)<=0;
279            }
280    
281            @Override
282            public String toString() {
283                return "key <= "+ value;
284            }
285        }
286    
287    
288        /**
289         * Implements a predicate that matches all entries.
290         *
291         * @param <Key> the class being compared
292         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
293         */
294        final static class AllPredicate<Key> implements Predicate<Key> {
295            public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
296                return true;
297            }
298            public boolean isInterestedInKey(Key key, Comparator comparator) {
299                return true;
300            }
301            @Override
302            public String toString() {
303                return "all";
304            }
305        }
306    
307        /**
308         * Implements a predicate that matches no entries.
309         *
310         * @param <Key> the class being compared
311         * @author <a href="http://hiramchirino.com">Hiram Chirino</a>
312         */
313        final static class NonePredicate<Key> implements Predicate<Key> {
314            public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
315                return false;
316            }
317            public boolean isInterestedInKey(Key key, Comparator comparator) {
318                return false;
319            }
320            @Override
321            public String toString() {
322                return "none";
323            }
324        }
325    
326        //
327        // Helper static methods to help create predicate expressions.
328        //
329        public static <Key> Predicate<Key> none() {
330            return new NonePredicate<Key>();
331        }
332        public static <Key> Predicate<Key> all() {
333            return new AllPredicate<Key>();
334        }
335    
336        public static <Key> Predicate<Key> or(Predicate<Key>... conditions) {
337            return new OrPredicate<Key>(Arrays.asList(conditions));
338        }
339    
340        public static <Key> Predicate<Key> or(List<Predicate<Key>> conditions) {
341            return new OrPredicate<Key>(conditions);
342        }
343    
344        public static <Key> Predicate<Key> and(Predicate<Key>... conditions) {
345            return new AndPredicate<Key>(Arrays.asList(conditions));
346        }
347    
348        public static <Key> Predicate<Key> and(List<Predicate<Key>> conditions) {
349            return new AndPredicate<Key>(conditions);
350        }
351    
352        public static <Key> Predicate<Key> gt(Key key) {
353            return new GTPredicate<Key>(key);
354        }
355        public static <Key> Predicate<Key> gte(Key key) {
356            return new GTEPredicate<Key>(key);
357        }
358    
359        public static <Key> Predicate<Key> lt(Key key) {
360            return new LTPredicate<Key>(key);
361        }
362        public static <Key> Predicate<Key> lte(Key key) {
363            return new LTEPredicate<Key>(key);
364        }
365    
366        public static <Key> Predicate<Key> lte(Key first, Key last) {
367            return new BetweenPredicate<Key>(first, last);
368        }
369    
370        /**
371         * Uses a predicates to select the keys that will be visited.
372         *
373         * @param <Key>
374         * @param <Value>
375         */
376        static class PredicateVisitor<Key, Value> implements IndexVisitor<Key, Value> {
377    
378            public static final int UNLIMITED=-1;
379    
380            private final Predicate<Key> predicate;
381            private int limit;
382    
383            public PredicateVisitor(Predicate<Key> predicate) {
384                this(predicate, UNLIMITED);
385            }
386    
387            public PredicateVisitor(Predicate<Key> predicate, int limit) {
388                this.predicate = predicate;
389                this.limit = limit;
390            }
391    
392            final public void visit(List<Key> keys, List<Value> values, Comparator comparator) {
393                for( int i=0; i < keys.size() && !isSatiated(); i++) {
394                    Key key = keys.get(i);
395                    if( predicate.isInterestedInKey(key, comparator) ) {
396                        if(limit > 0 )
397                            limit--;
398                        matched(key, values.get(i));
399                    }
400                }
401            }
402    
403            public boolean isInterestedInKeysBetween(Key first, Key second, Comparator comparator) {
404                return predicate.isInterestedInKeysBetween(first, second, comparator);
405            }
406    
407            public boolean isSatiated() {
408                return limit==0;
409            }
410    
411            /**
412             * Subclasses should override.  This method will be called for each key,
413             * value pair that matches the predicate.
414             *
415             * @param key
416             * @param value
417             */
418            protected void matched(Key key, Value value) {
419            }
420    
421        }
422    
423        public static <Key, Value> IndexVisitor<Key, Value> visitor(Predicate<Key> predicate) {
424            return new PredicateVisitor<Key, Value>(predicate);
425        }
426    
427    }