KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sf > saxon > sort > GroupByIterator


1 package net.sf.saxon.sort;
2
3 import net.sf.saxon.expr.Expression;
4 import net.sf.saxon.expr.LastPositionFinder;
5 import net.sf.saxon.expr.XPathContext;
6 import net.sf.saxon.om.Item;
7 import net.sf.saxon.om.ListIterator;
8 import net.sf.saxon.om.SequenceIterator;
9 import net.sf.saxon.om.LookaheadIterator;
10 import net.sf.saxon.trace.Location;
11 import net.sf.saxon.trans.XPathException;
12 import net.sf.saxon.value.AtomicValue;
13
14 import java.util.ArrayList JavaDoc;
15 import java.util.Comparator JavaDoc;
16 import java.util.HashMap JavaDoc;
17 import java.util.List JavaDoc;
18
19 /**
20  * A GroupByIterator iterates over a sequence of groups defined by
21  * xsl:for-each-group group-by="x". The groups are returned in
22  * order of first appearance. Note that an item can appear in several groups;
23  * indeed, an item may be the leading item of more than one group, which means
24  * that knowing the leading item is not enough to know the current group.
25  *
26  * <p>The GroupByIterator acts as a SequenceIterator, where successive calls of
27  * next() return the leading item of each group in turn. The current item of
28  * the iterator is therefore the leading item of the current group. To get access
29  * to all the members of the current group, the method iterateCurrentGroup() is used;
30  * this underpins the current-group() function in XSLT. The grouping key for the
31  * current group is available via the getCurrentGroupingKey() method.</p>
32  */
33
34 public class GroupByIterator implements GroupIterator, LastPositionFinder, LookaheadIterator {
35
36     // The implementation of group-by is not pipelined. All the items in the population
37 // are read at the start, their grouping keys are calculated, and the groups are formed
38 // in memory as a hash table indexed by the grouping key. This hash table is then
39 // flattened into three parallel lists: a list of groups (each group being represented
40 // as a list of items in population order), a list of grouping keys, and a list of
41 // the initial items of the groups.
42
43     private SequenceIterator population;
44     private Expression keyExpression;
45     private Comparator JavaDoc collator;
46     private XPathContext keyContext;
47     private int position = 0;
48
49     // Main data structure holds one entry for each group. The entry is also an ArrayList,
50 // which contains the Items that are members of the group, in population order.
51 // The groups are arranged in order of first appearance within the population.
52 private ArrayList JavaDoc groups = new ArrayList JavaDoc(40);
53
54     // This parallel structure identifies the grouping key for each group. The list
55 // corresponds one-to-one with the list of groups.
56 private ArrayList JavaDoc groupKeys = new ArrayList JavaDoc(40);
57
58     // For convenience (so that we can use a standard ArrayListIterator) we define
59 // another parallel array holding the initial items of each group.
60 private ArrayList JavaDoc initialItems = new ArrayList JavaDoc(40);
61
62     // An AtomicSortComparer is used to do the comparisons
63 private AtomicSortComparer comparer;
64
65
66     /**
67      * Create a GroupByIterator
68      * @param population iterator over the population to be grouped
69      * @param keyExpression the expression used to calculate the grouping key
70      * @param keyContext dynamic context for calculating the grouping key
71      * @param collator Collation to be used for comparing grouping keys
72      * @throws XPathException
73      */
74
75     public GroupByIterator(SequenceIterator population, Expression keyExpression,
76                                  XPathContext keyContext, Comparator JavaDoc collator)
77     throws XPathException {
78         this.population = population;
79         this.keyExpression = keyExpression;
80         this.keyContext = keyContext;
81         this.collator = collator;
82         this.comparer = new AtomicSortComparer(collator, keyContext);
83         buildIndexedGroups();
84     }
85
86     /**
87       * Build the grouping table forming groups of items with equal keys.
88       * This form of grouping allows a member of the population to be present in zero
89       * or more groups, one for each value of the grouping key.
90      */
91
92     private void buildIndexedGroups() throws XPathException {
93         HashMap JavaDoc index = new HashMap JavaDoc(40);
94         XPathContext c2 = keyContext.newMinorContext();
95         c2.setCurrentIterator(population);
96         c2.setOriginatingConstructType(Location.GROUPING_KEY);
97         while (true) {
98             Item item = population.next();
99             if (item==null) {
100                 break;
101             }
102             SequenceIterator keys = keyExpression.iterate(c2);
103             boolean firstKey = true;
104             while (true) {
105                 AtomicValue key = (AtomicValue) keys.next();
106                 if (key==null) {
107                     break;
108                 }
109                 AtomicSortComparer.ComparisonKey comparisonKey = comparer.getComparisonKey(key);
110                 ArrayList JavaDoc g = (ArrayList JavaDoc) index.get(comparisonKey);
111                 if (g == null) {
112                     ArrayList JavaDoc newGroup = new ArrayList JavaDoc(20);
113                     newGroup.add(item);
114                     groups.add(newGroup);
115                     groupKeys.add(key);
116                     initialItems.add(item);
117                     index.put(comparisonKey, newGroup);
118                 } else {
119                     if (firstKey) {
120                         g.add(item);
121                     } else {
122                         // if this is not the first key value for this item, we
123 // check whether the item is already in this group before
124 // adding it again. If it is in this group, then we know
125 // it will be at the end.
126 if (g.get(g.size() - 1) != item) {
127                             g.add(item);
128                         }
129                     }
130                 }
131                 firstKey = false;
132             }
133         }
134     }
135
136     /**
137      * Get the value of the grouping key for the current group
138      * @return the grouping key
139      */
140
141     public AtomicValue getCurrentGroupingKey() {
142         return (AtomicValue)groupKeys.get(position-1);
143     }
144
145     /**
146      * Get an iterator over the items in the current group
147      * @return the iterator
148      */
149
150     public SequenceIterator iterateCurrentGroup() {
151         return new ListIterator((ArrayList JavaDoc)groups.get(position-1));
152     }
153
154     /**
155      * Get the contents of the current group as a java List
156      * @return the contents of the current group
157      */
158
159     public List JavaDoc getCurrentGroup() {
160         return (ArrayList JavaDoc)groups.get(position-1);
161     }
162
163     public boolean hasNext() {
164         return position < groups.size();
165     }
166
167     public Item next() throws XPathException {
168         if (position < groups.size()) {
169             position++;
170             return current();
171         } else {
172             position = -1;
173             return null;
174         }
175     }
176
177     public Item current() {
178         if (position < 1) {
179             return null;
180         }
181         // return the initial item of the current group
182 return (Item)((ArrayList JavaDoc)groups.get(position-1)).get(0);
183     }
184
185     public int position() {
186         return position;
187     }
188
189     public SequenceIterator getAnother() throws XPathException {
190         XPathContext c2 = keyContext.newMinorContext();
191         c2.setOriginatingConstructType(Location.GROUPING_KEY);
192         return new GroupByIterator(population.getAnother(), keyExpression, c2, collator);
193     }
194
195     /**
196      * Get properties of this iterator, as a bit-significant integer.
197      *
198      * @return the properties of this iterator. This will be some combination of
199      * properties such as {@link GROUNDED}, {@link LAST_POSITION_FINDER},
200      * and {@link LOOKAHEAD}. It is always
201      * acceptable to return the value zero, indicating that there are no known special properties.
202      * It is acceptable for the properties of the iterator to change depending on its state.
203      */
204
205     public int getProperties() {
206         return LAST_POSITION_FINDER | LOOKAHEAD;
207     }
208
209     /**
210      * Get the last position (that is, the number of groups)
211      */
212
213     public int getLastPosition() throws XPathException {
214         return groups.size();
215     }
216
217 }
218
219
220 //
221 // The contents of this file are subject to the Mozilla Public License Version 1.0 (the "License");
222 // you may not use this file except in compliance with the License. You may obtain a copy of the
223 // License at http://www.mozilla.org/MPL/
224 //
225 // Software distributed under the License is distributed on an "AS IS" basis,
226 // WITHOUT WARRANTY OF ANY KIND, either express or implied.
227 // See the License for the specific language governing rights and limitations under the License.
228 //
229 // The Original Code is: all this file.
230 //
231 // The Initial Developer of the Original Code is Michael H. Kay
232 //
233 // Portions created by (your name) are Copyright (C) (your legal entity). All Rights Reserved.
234 //
235 // Contributor(s): none
236 //
Popular Tags