KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xalan > xsltc > dom > SortingIterator


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 /*
17  * $Id: SortingIterator.java,v 1.6 2004/02/16 22:54:59 minchau Exp $
18  */
19
20 package org.apache.xalan.xsltc.dom;
21
22 import org.apache.xalan.xsltc.runtime.BasisLibrary;
23 import org.apache.xml.dtm.DTMAxisIterator;
24 import org.apache.xml.dtm.ref.DTMAxisIteratorBase;
25
26 /**
27  * @author Jacek Ambroziak
28  * @author Santiago Pericas-Geertsen
29  * @author Morten Jorgensen
30  */
31 public final class SortingIterator extends DTMAxisIteratorBase {
32     private final static int INIT_DATA_SIZE = 16;
33
34     private DTMAxisIterator _source;
35     private NodeSortRecordFactory _factory;
36
37     private NodeSortRecord[] _data;
38     private int _free = 0;
39     private int _current; // index in _nodes of the next node to try
40
41     public SortingIterator(DTMAxisIterator source,
42                NodeSortRecordFactory factory) {
43     _source = source;
44     _factory = factory;
45     }
46
47     public int next() {
48     return _current < _free ? _data[_current++].getNode() : END;
49     }
50     
51     public DTMAxisIterator setStartNode(int node) {
52     try {
53         _source.setStartNode(_startNode = node);
54         _data = new NodeSortRecord[INIT_DATA_SIZE];
55         _free = 0;
56
57         // gather all nodes from the source iterator
58 while ((node = _source.next()) != END) {
59         addRecord(_factory.makeNodeSortRecord(node,_free));
60         }
61         // now sort the records
62 quicksort(0, _free - 1);
63
64         _current = 0;
65         return this;
66     }
67     catch (Exception JavaDoc e) {
68         return this;
69     }
70     }
71     
72     public int getPosition() {
73     return _current == 0 ? 1 : _current;
74     }
75
76     public int getLast() {
77     return _free;
78     }
79
80     public void setMark() {
81     _source.setMark();
82     _markedNode = _current;
83     }
84
85     public void gotoMark() {
86     _source.gotoMark();
87     _current = _markedNode;
88     }
89     
90     /**
91      * Clone a <code>SortingIterator</code> by cloning its source
92      * iterator and then sharing the factory and the array of
93      * <code>NodeSortRecords</code>.
94      */
95     public DTMAxisIterator cloneIterator() {
96     try {
97         final SortingIterator clone = (SortingIterator) super.clone();
98         clone._source = _source.cloneIterator();
99         clone._factory = _factory; // shared between clones
100 clone._data = _data; // shared between clones
101 clone._free = _free;
102         clone._current = _current;
103         clone.setRestartable(false);
104         return clone.reset();
105     }
106     catch (CloneNotSupportedException JavaDoc e) {
107         BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
108                       e.toString());
109         return null;
110     }
111     }
112
113     private void addRecord(NodeSortRecord record) {
114     if (_free == _data.length) {
115         NodeSortRecord[] newArray = new NodeSortRecord[_data.length * 2];
116         System.arraycopy(_data, 0, newArray, 0, _free);
117         _data = newArray;
118     }
119     _data[_free++] = record;
120     }
121
122     private void quicksort(int p, int r) {
123     while (p < r) {
124         final int q = partition(p, r);
125         quicksort(p, q);
126         p = q + 1;
127     }
128     }
129     
130     private int partition(int p, int r) {
131     final NodeSortRecord x = _data[(p + r) >>> 1];
132     int i = p - 1;
133     int j = r + 1;
134     while (true) {
135         while (x.compareTo(_data[--j]) < 0);
136         while (x.compareTo(_data[++i]) > 0);
137         if (i < j) {
138         final NodeSortRecord t = _data[i];
139         _data[i] = _data[j];
140         _data[j] = t;
141         }
142         else {
143         return(j);
144         }
145     }
146     }
147 }
148
Popular Tags