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 22package com.sun.org.apache.xalan.internal.xsltc.dom; 23 24import com.sun.org.apache.xalan.internal.xsltc.runtime.BasisLibrary; 25import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator; 26import 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 */ 33public 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 43 public SortingIterator(DTMAxisIterator source, 44 NodeSortRecordFactory factory) { 45 _source = source; 46 _factory = factory; 47 } 48 49 public int next() { 50 return _current < _free ? _data[_current++].getNode() : END; 51 } 52 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 74 public int getPosition() { 75 return _current == 0 ? 1 : _current; 76 } 77 78 public int getLast() { 79 return _free; 80 } 81 82 public void setMark() { 83 _source.setMark(); 84 _markedNode = _current; 85 } 86 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 */ 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 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} 150