286N/A/*
286N/A * reserved comment block
286N/A * DO NOT REMOVE OR ALTER!
286N/A */
286N/A/*
286N/A * Copyright 2001-2004 The Apache Software Foundation.
286N/A *
286N/A * Licensed under the Apache License, Version 2.0 (the "License");
286N/A * you may not use this file except in compliance with the License.
286N/A * You may obtain a copy of the License at
286N/A *
286N/A * http://www.apache.org/licenses/LICENSE-2.0
286N/A *
286N/A * Unless required by applicable law or agreed to in writing, software
286N/A * distributed under the License is distributed on an "AS IS" BASIS,
286N/A * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
286N/A * See the License for the specific language governing permissions and
286N/A * limitations under the License.
286N/A */
286N/A/*
286N/A * $Id: SortingIterator.java,v 1.2.4.1 2005/09/06 10:23:32 pvedula Exp $
286N/A */
286N/A
286N/Apackage com.sun.org.apache.xalan.internal.xsltc.dom;
286N/A
286N/Aimport com.sun.org.apache.xalan.internal.xsltc.runtime.BasisLibrary;
286N/Aimport com.sun.org.apache.xml.internal.dtm.DTMAxisIterator;
286N/Aimport com.sun.org.apache.xml.internal.dtm.ref.DTMAxisIteratorBase;
286N/A
286N/A/**
286N/A * @author Jacek Ambroziak
286N/A * @author Santiago Pericas-Geertsen
286N/A * @author Morten Jorgensen
286N/A */
286N/Apublic final class SortingIterator extends DTMAxisIteratorBase {
286N/A private final static int INIT_DATA_SIZE = 16;
286N/A
286N/A private DTMAxisIterator _source;
286N/A private NodeSortRecordFactory _factory;
286N/A
286N/A private NodeSortRecord[] _data;
286N/A private int _free = 0;
286N/A private int _current; // index in _nodes of the next node to try
286N/A
286N/A public SortingIterator(DTMAxisIterator source,
286N/A NodeSortRecordFactory factory) {
286N/A _source = source;
286N/A _factory = factory;
286N/A }
286N/A
286N/A public int next() {
286N/A return _current < _free ? _data[_current++].getNode() : END;
286N/A }
286N/A
286N/A public DTMAxisIterator setStartNode(int node) {
286N/A try {
286N/A _source.setStartNode(_startNode = node);
286N/A _data = new NodeSortRecord[INIT_DATA_SIZE];
286N/A _free = 0;
286N/A
286N/A // gather all nodes from the source iterator
286N/A while ((node = _source.next()) != END) {
286N/A addRecord(_factory.makeNodeSortRecord(node,_free));
286N/A }
286N/A // now sort the records
286N/A quicksort(0, _free - 1);
286N/A
286N/A _current = 0;
286N/A return this;
286N/A }
286N/A catch (Exception e) {
286N/A return this;
286N/A }
286N/A }
286N/A
286N/A public int getPosition() {
286N/A return _current == 0 ? 1 : _current;
286N/A }
286N/A
286N/A public int getLast() {
286N/A return _free;
286N/A }
286N/A
286N/A public void setMark() {
286N/A _source.setMark();
286N/A _markedNode = _current;
286N/A }
286N/A
286N/A public void gotoMark() {
286N/A _source.gotoMark();
286N/A _current = _markedNode;
286N/A }
286N/A
286N/A /**
286N/A * Clone a <code>SortingIterator</code> by cloning its source
286N/A * iterator and then sharing the factory and the array of
286N/A * <code>NodeSortRecords</code>.
286N/A */
286N/A public DTMAxisIterator cloneIterator() {
286N/A try {
286N/A final SortingIterator clone = (SortingIterator) super.clone();
286N/A clone._source = _source.cloneIterator();
286N/A clone._factory = _factory; // shared between clones
286N/A clone._data = _data; // shared between clones
286N/A clone._free = _free;
286N/A clone._current = _current;
286N/A clone.setRestartable(false);
286N/A return clone.reset();
286N/A }
286N/A catch (CloneNotSupportedException e) {
286N/A BasisLibrary.runTimeError(BasisLibrary.ITERATOR_CLONE_ERR,
286N/A e.toString());
286N/A return null;
286N/A }
286N/A }
286N/A
286N/A private void addRecord(NodeSortRecord record) {
286N/A if (_free == _data.length) {
286N/A NodeSortRecord[] newArray = new NodeSortRecord[_data.length * 2];
286N/A System.arraycopy(_data, 0, newArray, 0, _free);
286N/A _data = newArray;
286N/A }
286N/A _data[_free++] = record;
286N/A }
286N/A
286N/A private void quicksort(int p, int r) {
286N/A while (p < r) {
286N/A final int q = partition(p, r);
286N/A quicksort(p, q);
286N/A p = q + 1;
286N/A }
286N/A }
286N/A
286N/A private int partition(int p, int r) {
286N/A final NodeSortRecord x = _data[(p + r) >>> 1];
286N/A int i = p - 1;
286N/A int j = r + 1;
286N/A while (true) {
286N/A while (x.compareTo(_data[--j]) < 0);
286N/A while (x.compareTo(_data[++i]) > 0);
286N/A if (i < j) {
286N/A final NodeSortRecord t = _data[i];
286N/A _data[i] = _data[j];
286N/A _data[j] = t;
286N/A }
286N/A else {
286N/A return(j);
286N/A }
286N/A }
286N/A }
286N/A}