KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > mckoi > database > SelectableRangeSet


1 /**
2  * com.mckoi.database.SelectableRangeSet 18 Nov 2001
3  *
4  * Mckoi SQL Database ( http://www.mckoi.com/database )
5  * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * Version 2 as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License Version 2 for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * Version 2 along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Change Log:
21  *
22  *
23  */
24
25 package com.mckoi.database;
26
27 import java.util.ArrayList JavaDoc;
28 import java.util.ListIterator JavaDoc;
29
30 /**
31  * Represents a complex normalized range of a list. This is essentially a
32  * set of SelectableRange objects that make up a complex view of a range. For
33  * example, say we had a query
34  * '(a > 10 and a < 20 and a <> 15) or a >= 50',
35  * we could represent this range by the following range set;
36  * <p><pre>
37  * RANGE: AFTER_LAST_VALUE 10, BEFORE_FIRST_VALUE 15
38  * RANGE: AFTER_LAST_VALUE 15, BEFORE_FIRST_VALUE 20
39  * RANGE: FIRST_VALUE 50, LAST_VALUE LAST_IN_SET
40  * </pre><p>
41  * The range is constructed by calls to 'intersect', and 'union'.
42  *
43  * @author Tobias Downer
44  */
45
46 public final class SelectableRangeSet {
47
48   /**
49    * The list of ranges.
50    */
51   private final ArrayList JavaDoc range_set;
52
53   /**
54    * Constructs the SelectableRangeSet to a full range (a range that encompases
55    * all values). If 'no_nulls' is true then the range can't include null
56    * values.
57    */
58   public SelectableRangeSet() {
59     range_set = new ArrayList JavaDoc();
60     range_set.add(SelectableRange.FULL_RANGE);
61   }
62
63   /**
64    * Intersects the given SelectableRange object with the given Operator and
65    * value constraint.
66    * <p>
67    * NOTE: This does not work with the '<>' operator which must be handled
68    * another way.
69    */
70   private static SelectableRange intersectRange(SelectableRange range,
71                               Operator op, TObject val, boolean null_check) {
72     TObject start = range.getStart();
73     byte start_flag = range.getStartFlag();
74     TObject end = range.getEnd();
75     byte end_flag = range.getEndFlag();
76
77     boolean inclusive = op.is("is") || op.is("=") ||
78                         op.is(">=") || op.is("<=");
79
80     if (op.is("is") || op.is("=") || op.is(">") || op.is(">=")) {
81       // With this operator, NULL values must return null.
82 if (null_check && val.isNull()) {
83         return null;
84       }
85     
86       if (start == SelectableRange.FIRST_IN_SET) {
87         start = val;
88         start_flag = inclusive ? SelectableRange.FIRST_VALUE :
89                                  SelectableRange.AFTER_LAST_VALUE;
90       }
91       else {
92         int c = val.compareTo(start);
93         if ((c == 0 && start_flag == SelectableRange.FIRST_VALUE) || c > 0) {
94           start = val;
95           start_flag = inclusive ? SelectableRange.FIRST_VALUE :
96                                    SelectableRange.AFTER_LAST_VALUE;
97         }
98       }
99     }
100     if (op.is("is") || op.is("=") || op.is("<") || op.is("<=")) {
101       // With this operator, NULL values must return null.
102 if (null_check && val.isNull()) {
103         return null;
104       }
105
106       // If start is first in set, then we have to change it to after NULL
107 if (null_check && start == SelectableRange.FIRST_IN_SET) {
108         start = TObject.nullVal();
109         start_flag = SelectableRange.AFTER_LAST_VALUE;
110       }
111     
112       if (end == SelectableRange.LAST_IN_SET) {
113         end = val;
114         end_flag = inclusive ? SelectableRange.LAST_VALUE :
115                                SelectableRange.BEFORE_FIRST_VALUE;
116       }
117       else {
118         int c = val.compareTo(end);
119         if ((c == 0 && end_flag == SelectableRange.LAST_VALUE) || c < 0) {
120           end = val;
121           end_flag = inclusive ? SelectableRange.LAST_VALUE :
122                                  SelectableRange.BEFORE_FIRST_VALUE;
123         }
124       }
125     }
126
127     // If start and end are not null types (if either are, then it means it
128 // is a placeholder value meaning start or end of set).
129 if (start != SelectableRange.FIRST_IN_SET &&
130         end != SelectableRange.LAST_IN_SET) {
131       // If start is higher than end, return null
132 int c = start.compareTo(end);
133       if ((c == 0 && (start_flag == SelectableRange.AFTER_LAST_VALUE ||
134                       end_flag == SelectableRange.BEFORE_FIRST_VALUE)) ||
135           c > 0) {
136         return null;
137       }
138     }
139
140     // The new intersected range
141 return new SelectableRange(start_flag, start, end_flag, end);
142   }
143
144   /**
145    * Returns true if the two SelectableRange ranges intersect.
146    */
147   private static boolean rangeIntersectedBy(SelectableRange range1,
148                                             SelectableRange range2) {
149     byte start_flag_1 = range1.getStartFlag();
150     TObject start_1 = range1.getStart();
151     byte end_flag_1 = range1.getEndFlag();
152     TObject end_1 = range1.getEnd();
153
154     byte start_flag_2 = range2.getStartFlag();
155     TObject start_2 = range2.getStart();
156     byte end_flag_2 = range2.getEndFlag();
157     TObject end_2 = range2.getEnd();
158
159     TObject start_cell_1, end_cell_1;
160     TObject start_cell_2, end_cell_2;
161
162     start_cell_1 = start_1 == SelectableRange.FIRST_IN_SET ? null : start_1;
163     end_cell_1 = end_1 == SelectableRange.LAST_IN_SET ? null : end_1;
164     start_cell_2 = start_2 == SelectableRange.FIRST_IN_SET ? null : start_2;
165     end_cell_2 = end_2 == SelectableRange.LAST_IN_SET ? null : end_2;
166
167     boolean intersect_1 = false;
168     if (start_cell_1 != null && end_cell_2 != null) {
169       int c = start_cell_1.compareTo(end_cell_2);
170       if (c < 0 ||
171           (c == 0 && (start_flag_1 == SelectableRange.FIRST_VALUE ||
172                       end_flag_2 == SelectableRange.LAST_VALUE))) {
173         intersect_1 = true;
174       }
175     }
176     else {
177       intersect_1 = true;
178     }
179
180     boolean intersect_2 = false;
181     if (start_cell_2 != null && end_cell_1 != null) {
182       int c = start_cell_2.compareTo(end_cell_1);
183       if (c < 0 ||
184           (c == 0 && (start_flag_2 == SelectableRange.FIRST_VALUE ||
185                       end_flag_1 == SelectableRange.LAST_VALUE))) {
186         intersect_2 = true;
187       }
188     }
189     else {
190       intersect_2 = true;
191     }
192
193     return (intersect_1 && intersect_2);
194   }
195
196   /**
197    * Alters the first range so it encompasses the second range. This assumes
198    * that range1 intersects range2.
199    */
200   private static SelectableRange changeRangeSizeToEncompass(
201                             SelectableRange range1, SelectableRange range2) {
202
203     byte start_flag_1 = range1.getStartFlag();
204     TObject start_1 = range1.getStart();
205     byte end_flag_1 = range1.getEndFlag();
206     TObject end_1 = range1.getEnd();
207
208     byte start_flag_2 = range2.getStartFlag();
209     TObject start_2 = range2.getStart();
210     byte end_flag_2 = range2.getEndFlag();
211     TObject end_2 = range2.getEnd();
212
213     if (start_1 != SelectableRange.FIRST_IN_SET) {
214       if (start_2 != SelectableRange.FIRST_IN_SET) {
215         TObject cell = start_1;
216         int c = cell.compareTo(start_2);
217         if (c > 0 ||
218             c == 0 && start_flag_1 == SelectableRange.AFTER_LAST_VALUE &&
219                       start_flag_2 == SelectableRange.FIRST_VALUE) {
220           start_1 = start_2;
221           start_flag_1 = start_flag_2;
222         }
223       }
224       else {
225         start_1 = start_2;
226         start_flag_1 = start_flag_2;
227       }
228     }
229
230     if (end_1 != SelectableRange.LAST_IN_SET) {
231       if (end_2 != SelectableRange.LAST_IN_SET) {
232         TObject cell = (TObject) end_1;
233         int c = cell.compareTo(end_2);
234         if (c < 0 ||
235             c == 0 && end_flag_1 == SelectableRange.BEFORE_FIRST_VALUE &&
236                       end_flag_2 == SelectableRange.LAST_VALUE) {
237           end_1 = end_2;
238           end_flag_1 = end_flag_2;
239         }
240       }
241       else {
242         end_1 = end_2;
243         end_flag_1 = end_flag_2;
244       }
245     }
246
247     return new SelectableRange(start_flag_1, start_1, end_flag_1, end_1);
248   }
249
250   /**
251    * Intersects this range with the given Operator and value constraint.
252    * For example, if a range is 'a' -> [END] and the given operator is '<=' and
253    * the value is 'z' the result range is 'a' -> 'z'.
254    */
255   public void intersect(Operator op, TObject val) {
256     int sz = range_set.size();
257     ListIterator JavaDoc i = range_set.listIterator();
258
259     if (op.is("<>") || op.is("is not")) {
260
261       boolean null_check = op.is("<>");
262
263       while (i.hasNext()) {
264         SelectableRange range = (SelectableRange) i.next();
265         SelectableRange left_range =
266                     intersectRange(range, Operator.get("<"), val, null_check);
267         SelectableRange right_range =
268                     intersectRange(range, Operator.get(">"), val, null_check);
269         i.remove();
270         if (left_range != null) {
271           i.add(left_range);
272         }
273         if (right_range != null) {
274           i.add(right_range);
275         }
276       }
277
278     }
279     else {
280
281       boolean null_check = !op.is("is");
282
283       while (i.hasNext()) {
284         SelectableRange range = (SelectableRange) i.next();
285         range = intersectRange(range, op, val, null_check);
286         if (range == null) {
287           i.remove();
288         }
289         else {
290           i.set(range);
291         }
292       }
293
294     }
295
296   }
297
298   /**
299    * Unions this range with the given Operator and value constraint.
300    */
301   public void union(Operator op, TObject val) {
302     throw new Error JavaDoc("PENDING");
303   }
304
305   /**
306    * Unions the current range set with the given range set.
307    */
308   public void union(SelectableRangeSet union_to) {
309     ArrayList JavaDoc input_set = union_to.range_set;
310
311     int in_sz = input_set.size();
312     for (int n = 0; n < in_sz; ++n) {
313       // The range to merge in.
314 SelectableRange in_range = (SelectableRange) input_set.get(n);
315
316       // For each range in this set
317 int sz = range_set.size();
318       ListIterator JavaDoc i = range_set.listIterator();
319       while (i.hasNext()) {
320         SelectableRange range = (SelectableRange) i.next();
321         if (rangeIntersectedBy(in_range, range)) {
322           i.remove();
323           in_range = changeRangeSizeToEncompass(in_range, range);
324         }
325       }
326
327       // Insert into sorted position
328 byte start_flag = in_range.getStartFlag();
329       TObject start = in_range.getStart();
330       byte end_flag = in_range.getEndFlag();
331       TObject end = in_range.getEnd();
332
333       if (start == SelectableRange.FIRST_IN_SET) {
334         range_set.add(0, in_range);
335       }
336       else {
337         TObject start_cell = start;
338         i = range_set.listIterator();
339         while (i.hasNext()) {
340           SelectableRange range = (SelectableRange) i.next();
341           TObject cur_start = range.getStart();
342           if (cur_start != SelectableRange.FIRST_IN_SET) {
343             if (cur_start.compareTo(start_cell) > 0) {
344               i.previous();
345               break;
346             }
347           }
348         }
349         i.add(in_range);
350       }
351
352     }
353
354   }
355
356   /**
357    * Returns the range as an array of SelectableRange or an empty array if
358    * there is no range.
359    */
360   public SelectableRange[] toSelectableRangeArray() {
361     int sz = range_set.size();
362     SelectableRange[] ranges = new SelectableRange[sz];
363     for (int i = 0; i < sz; ++i) {
364       ranges[i] = (SelectableRange) range_set.get(i);
365     }
366     return ranges;
367   }
368
369
370
371   /**
372    * Outputs this range as a string, for diagnostic and testing purposes.
373    */
374   public String JavaDoc toString() {
375     StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
376     if (range_set.size() == 0) {
377       return "(NO RANGE)";
378     }
379     for (int i = 0; i < range_set.size(); ++i) {
380       buf.append(range_set.get(i));
381       buf.append(", ");
382     }
383     return new String JavaDoc(buf);
384   }
385
386
387
388   /**
389    * A test application.
390    */
391   public static void main(String JavaDoc[] args) {
392
393     TType ttype = TType.STRING_TYPE;
394
395     SelectableRangeSet range_set = new SelectableRangeSet();
396     System.out.println(range_set);
397     range_set.intersect(Operator.get(">="), new TObject(ttype, "2"));
398     System.out.println(range_set);
399     range_set.intersect(Operator.get("<>"), new TObject(ttype, "4"));
400     System.out.println(range_set);
401     range_set.intersect(Operator.get("<>"), new TObject(ttype, "2"));
402     System.out.println(range_set);
403     range_set.intersect(Operator.get("<>"), new TObject(ttype, "3"));
404     System.out.println(range_set);
405     range_set.intersect(Operator.get("<>"), new TObject(ttype, "2"));
406     System.out.println(range_set);
407     range_set.intersect(Operator.get("<>"), new TObject(ttype, "1"));
408     System.out.println(range_set);
409     range_set.intersect(Operator.get(">="), new TObject(ttype, "3"));
410     System.out.println(range_set);
411     range_set.intersect(Operator.get("<="), new TObject(ttype, "5"));
412     System.out.println(range_set);
413     range_set.intersect(Operator.get("<"), new TObject(ttype, "5"));
414     System.out.println(range_set);
415     range_set.intersect(Operator.get(">="), new TObject(ttype, "6"));
416     System.out.println(range_set);
417
418     System.out.println("---");
419     SelectableRangeSet range1 = new SelectableRangeSet();
420     range1.intersect(Operator.get("="), new TObject(ttype, "k"));
421     SelectableRangeSet range2 = new SelectableRangeSet();
422     range2.intersect(Operator.get("<>"), new TObject(ttype, "d"));
423     range2.intersect(Operator.get("<"), new TObject(ttype, "g"));
424     SelectableRangeSet range3 = new SelectableRangeSet();
425     range3.intersect(Operator.get(">"), new TObject(ttype, "o"));
426     range2.union(range3);
427     range1.union(range2);
428     System.out.println(range1);
429
430   }
431
432 }
433
Popular Tags