001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: SortingIterator.java 468651 2006-10-28 07:04:25Z minchau $
020 */
021
022 package org.apache.xalan.xsltc.dom;
023
024 import org.apache.xalan.xsltc.runtime.BasisLibrary;
025 import org.apache.xml.dtm.DTMAxisIterator;
026 import org.apache.xml.dtm.ref.DTMAxisIteratorBase;
027
028 /**
029 * @author Jacek Ambroziak
030 * @author Santiago Pericas-Geertsen
031 * @author Morten Jorgensen
032 */
033 public final class SortingIterator extends DTMAxisIteratorBase {
034 private final static int INIT_DATA_SIZE = 16;
035
036 private DTMAxisIterator _source;
037 private NodeSortRecordFactory _factory;
038
039 private NodeSortRecord[] _data;
040 private int _free = 0;
041 private int _current; // index in _nodes of the next node to try
042
043 public SortingIterator(DTMAxisIterator source,
044 NodeSortRecordFactory factory) {
045 _source = source;
046 _factory = factory;
047 }
048
049 public int next() {
050 return _current < _free ? _data[_current++].getNode() : END;
051 }
052
053 public DTMAxisIterator setStartNode(int node) {
054 try {
055 _source.setStartNode(_startNode = node);
056 _data = new NodeSortRecord[INIT_DATA_SIZE];
057 _free = 0;
058
059 // gather all nodes from the source iterator
060 while ((node = _source.next()) != END) {
061 addRecord(_factory.makeNodeSortRecord(node,_free));
062 }
063 // now sort the records
064 quicksort(0, _free - 1);
065
066 _current = 0;
067 return this;
068 }
069 catch (Exception e) {
070 return this;
071 }
072 }
073
074 public int getPosition() {
075 return _current == 0 ? 1 : _current;
076 }
077
078 public int getLast() {
079 return _free;
080 }
081
082 public void setMark() {
083 _source.setMark();
084 _markedNode = _current;
085 }
086
087 public void gotoMark() {
088 _source.gotoMark();
089 _current = _markedNode;
090 }
091
092 /**
093 * Clone a <code>SortingIterator</code> by cloning its source
094 * iterator and then sharing the factory and the array of
095 * <code>NodeSortRecords</code>.
096 */
097 public DTMAxisIterator cloneIterator() {
098 try {
099 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
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
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
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 }