OrderedTuples


1   package gnu.xquery.util;
2   import gnu.lists.*;
3   import gnu.mapping.*;
4   import gnu.kawa.functions.NumberCompare;
5   import gnu.kawa.xml.KNode;
6   import gnu.kawa.xml.UntypedAtomic;
7   
8   /** Helper class used in conjunction with {@link OrderedMap}.
9    * It has the tuples from the {@code for} and {@code let}-clauses,
10   * as filtered by the {@code where}-clause.
11   *
12   * The tuples are sorted using a linked-list version of merge sort.
13   *
14   * The sequence of n tuples for m variables is represented using
15   * an array of length n where each element is an array of length m.
16   * A possible future optimization would be to instead use m
17   * different arrays of of length n.  The advantage is that each
18   * of the M arrays could have the "correct" type for each variable,
19   * and so we avoid casts or boxing/unboxing.
20   */
21  
22  public class OrderedTuples extends FilterConsumer
23  {
24    /** The number of tuples. */
25    int n;
26  
27    /** The sequence of tuples, in input (unsorted) order. */
28    Object  [] tuples; // Actually: Object[][] tuples.
29  
30    /** The compator functions.
31     * If there are k comparator, the array's length is 3*k.
32     * comps[3*i] is the i'th comparison function
33     *   (represented as a procedure on a tuple);
34     * comps[3*i+1] is the i'th set of flags encoded as a string;
35     * and comps[3*i+2] is the i'th collator
36     *   (either null or a NamedCollator).
37     */
38    Object  [] comps;
39  
40    /* The index of the first tuple, after sorting. */
41    int first;
42    /** Used to chain the tuples after sorting.
43     * I.e. if the i'th tuple (is sort order) is tuples[k],
44     * then the (i+1)'the sorted tuple is tuples[next[k]].
45     * The end of the list is indicated by -1.
46     */
47    int[] next;
48  
49    /** The return clause, encoded as a procedure on a tuple. */
50    Procedure body;
51  
52    public void writeObject(Object   v)
53    {
54      if (n >= tuples.length)
55        {
56          Object  [] tmp = new Object  [2 * n];
57          System.arraycopy(tuples, 0, tmp, 0, n);
58          tuples = tmp;
59        }
60      tuples[n++] = v;
61    }
62  
63    OrderedTuples ()
64    {
65      super(null);
66      tuples = new Object  [10];
67    }
68  
69    public static OrderedTuples make$V (Procedure body, Object  [] comps)
70    {
71      OrderedTuples tuples = new OrderedTuples();
72      tuples.comps = comps;
73      tuples.body = body;
74      return tuples;
75    }
76  
77    public void run$X (CallContext ctx)  throws Throwable  
78    {
79      first = listsort(0);
80      emit(ctx);
81    }
82  
83    void emit (CallContext ctx)  throws Throwable  
84    {
85      for (int p = first; p >= 0; p = next[p])
86        emit(p, ctx);
87    }
88  
89    void emit (int index, CallContext ctx)  throws Throwable  
90    {
91      Object  [] args = (Object  []) tuples[index];
92      body.checkN(args, ctx);
93      ctx.runUntilDone();
94    }
95  
96    // The following sort routine is derived from Simon Tatham's listsort.c.
97    // However we use array indexes instead of pointers, and the next
98    // element instead of a next field.
99    // I.e. p->next is mapped to next[p].
100   // Instead of NULL we use -1.
101 
102   /*
103    * Demonstration code for sorting a linked list.
104    * 
105    * The algorithm used is Mergesort, because that works really well
106    * on linked lists, without requiring the O(N) extra space it needs
107    * when you do it on arrays.
108    */
109 
110 /*
111  * This file is copyright 2001 Simon Tatham.
112  * 
113  * Permission is hereby granted, free of charge, to any person
114  * obtaining a copy of this software and associated documentation
115  * files (the "Software"), to deal in the Software without
116  * restriction, including without limitation the rights to use,
117  * copy, modify, merge, publish, distribute, sublicense, and/or
118  * sell copies of the Software, and to permit persons to whom the
119  * Software is furnished to do so, subject to the following
120  * conditions:
121  * 
122  * The above copyright notice and this permission notice shall be
123  * included in all copies or substantial portions of the Software.
124  * 
125  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
126  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
127  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
128  * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
129  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
130  * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
131  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
132  * SOFTWARE.
133  */
134 
135 int cmp(int a, int b)  throws Throwable  
136 {
137   for (int i = 0;  i < comps.length;  i += 3)
138     {
139       Procedure comparator = (Procedure) comps[i];
140       String   flags = (String  ) comps[i+1];
141       NamedCollator collator = (NamedCollator) comps[i+2];
142       if (collator == null)
143         collator = NamedCollator.codepointCollation;
144       Object   val1 = comparator.applyN((Object  []) tuples[a]);
145       Object   val2 = comparator.applyN((Object  []) tuples[b]);
146       val1 = KNode.atomicValue(val1);
147       val2 = KNode.atomicValue(val2);
148       if (val1 instanceof UntypedAtomic)
149         val1 = val1.toString();
150       if (val2 instanceof UntypedAtomic)
151         val2 = val2.toString();
152       boolean empty1 = SequenceUtils.isEmptySequence(val1);
153       boolean empty2 = SequenceUtils.isEmptySequence(val2);
154       if (empty1 && empty2)
155         continue;
156       int c;
157       if (empty1 || empty2)
158         {
159           char emptyOrder = flags.charAt(1);
160           c = empty1 == (emptyOrder == 'L') ? -1 : 1;
161         }
162       else
163         {
164           boolean isNaN1 = val1 instanceof Number  
165             && Double.isNaN(((Number  ) val1).doubleValue());
166           boolean isNaN2 = val2 instanceof Number  
167             && Double.isNaN(((Number  ) val2).doubleValue());
168           if (isNaN1 && isNaN2)
169             continue;
170           if (isNaN1 || isNaN2)
171             {
172               char emptyOrder = flags.charAt(1);
173               c = isNaN1 == (emptyOrder == 'L') ? -1 : 1;
174             }
175           else if (val1 instanceof Number   && val2 instanceof Number  )
176             c = NumberCompare.compare(val1, val2, false);
177           else
178             c = collator.compare(val1.toString(), val2.toString());
179         }
180       if (c == 0)
181         continue;
182       return flags.charAt(0) == 'A' ? c : -c;
183     }
184   return 0;
185 }
186 
187 /*
188  * This is the actual sort function. Notice that it returns the new
189  * head of the list. (It has to, because the head will not
190  * generally be the same element after the sort.) So unlike sorting
191  * an array, where you can do
192  * 
193  *     sort(myarray);
194  * 
195  * you now have to do
196  * 
197  *     list = listsort(mylist);
198  */
199   int listsort(int list) throws Throwable  
200   {// indexes
201     int p, q, e, tail, oldhead; 
202     int insize, nmerges, psize, qsize, i;
203 
204     /*
205      * Silly special case: if `list' was passed in as NULL, return
206      * NULL immediately.
207      */
208     if (n == 0)
209     return -1;
210 
211     next = new int[n];
212 
213     for (i = 1; ;  i++)
214       {
215         if (i == n)
216           {
217             next[i-1] = -1;
218             break;
219           }
220         else
221           next[i-1] = i;
222       }
223 
224     insize = 1;
225 
226     for (;;) {
227         p = list;
228         list = -1;
229         tail = -1;
230 
231         nmerges = 0;  /* count number of merges we do in this pass */
232 
233         while (p >= 0) {
234             nmerges++;  /* there exists a merge to be done */
235             /* step `insize' places along from p */
236             q = p;
237             psize = 0;
238             for (i = 0; i < insize; i++) {
239                 psize++;
240                 q = next[q];
241                 if (q < 0) break;
242             }
243             /* if q hasn't fallen off end, we have two lists to merge */
244             qsize = insize;
245 
246             /* now we have two lists; merge them */
247             while (psize > 0 || (qsize > 0 && q >= 0)) {
248 
249                 /* decide whether next element of merge comes from p or q */
250                 if (psize == 0) {
251             /* p is empty; e must come from q. */
252             e = q; q = next[q]; qsize--;
253         } else if (qsize == 0 || q < 0) {
254             /* q is empty; e must come from p. */
255             e = p; p = next[p]; psize--;
256         } else if (cmp(p,q) <= 0) {
257             /* First element of p is lower (or same);
258              * e must come from p. */
259             e = p; p = next[p]; psize--;
260         } else {
261             /* First element of q is lower; e must come from q. */
262             e = q; q = next[q]; qsize--;
263         }
264 
265                 /* add the next element to the merged list */
266         if (tail >= 0)
267                   next[tail] = e;
268         else
269             list = e;
270         tail = e;
271             }
272 
273             /* now p has stepped `insize' places along, and q has too */
274             p = q;
275         }
276         next[tail] = -1;
277 
278         /* If we have done only one merge, we're finished. */
279         if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
280             return list;
281 
282         /* Otherwise repeat, merging lists twice the size */
283         insize *= 2;
284     }
285 }
286 }
287
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags