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