001: /*
002: * Copyright 1999-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: /*
017: * $Id: NodeVector.java,v 1.11 2005/01/23 00:52:41 mcnamara Exp $
018: */
019: package org.apache.xml.utils;
020:
021: import java.io.Serializable;
022:
023: import org.apache.xml.dtm.DTM;
024:
025: /**
026: * A very simple table that stores a list of Nodes.
027: * @xsl.usage internal
028: */
029: public class NodeVector implements Serializable, Cloneable {
030: static final long serialVersionUID = -713473092200731870L;
031:
032: /**
033: * Size of blocks to allocate.
034: * @serial
035: */
036: private int m_blocksize;
037:
038: /**
039: * Array of nodes this points to.
040: * @serial
041: */
042: private int m_map[];
043:
044: /**
045: * Number of nodes in this NodeVector.
046: * @serial
047: */
048: protected int m_firstFree = 0;
049:
050: /**
051: * Size of the array this points to.
052: * @serial
053: */
054: private int m_mapSize; // lazy initialization
055:
056: /**
057: * Default constructor.
058: */
059: public NodeVector() {
060: m_blocksize = 32;
061: m_mapSize = 0;
062: }
063:
064: /**
065: * Construct a NodeVector, using the given block size.
066: *
067: * @param blocksize Size of blocks to allocate
068: */
069: public NodeVector(int blocksize) {
070: m_blocksize = blocksize;
071: m_mapSize = 0;
072: }
073:
074: /**
075: * Get a cloned LocPathIterator.
076: *
077: * @return A clone of this
078: *
079: * @throws CloneNotSupportedException
080: */
081: public Object clone() throws CloneNotSupportedException {
082:
083: NodeVector clone = (NodeVector) super .clone();
084:
085: if ((null != this .m_map) && (this .m_map == clone.m_map)) {
086: clone.m_map = new int[this .m_map.length];
087:
088: System.arraycopy(this .m_map, 0, clone.m_map, 0,
089: this .m_map.length);
090: }
091:
092: return clone;
093: }
094:
095: /**
096: * Get the length of the list.
097: *
098: * @return Number of nodes in this NodeVector
099: */
100: public int size() {
101: return m_firstFree;
102: }
103:
104: /**
105: * Append a Node onto the vector.
106: *
107: * @param value Node to add to the vector
108: */
109: public void addElement(int value) {
110:
111: if ((m_firstFree + 1) >= m_mapSize) {
112: if (null == m_map) {
113: m_map = new int[m_blocksize];
114: m_mapSize = m_blocksize;
115: } else {
116: m_mapSize += m_blocksize;
117:
118: int newMap[] = new int[m_mapSize];
119:
120: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
121:
122: m_map = newMap;
123: }
124: }
125:
126: m_map[m_firstFree] = value;
127:
128: m_firstFree++;
129: }
130:
131: /**
132: * Append a Node onto the vector.
133: *
134: * @param value Node to add to the vector
135: */
136: public final void push(int value) {
137:
138: int ff = m_firstFree;
139:
140: if ((ff + 1) >= m_mapSize) {
141: if (null == m_map) {
142: m_map = new int[m_blocksize];
143: m_mapSize = m_blocksize;
144: } else {
145: m_mapSize += m_blocksize;
146:
147: int newMap[] = new int[m_mapSize];
148:
149: System.arraycopy(m_map, 0, newMap, 0, ff + 1);
150:
151: m_map = newMap;
152: }
153: }
154:
155: m_map[ff] = value;
156:
157: ff++;
158:
159: m_firstFree = ff;
160: }
161:
162: /**
163: * Pop a node from the tail of the vector and return the result.
164: *
165: * @return the node at the tail of the vector
166: */
167: public final int pop() {
168:
169: m_firstFree--;
170:
171: int n = m_map[m_firstFree];
172:
173: m_map[m_firstFree] = DTM.NULL;
174:
175: return n;
176: }
177:
178: /**
179: * Pop a node from the tail of the vector and return the
180: * top of the stack after the pop.
181: *
182: * @return The top of the stack after it's been popped
183: */
184: public final int popAndTop() {
185:
186: m_firstFree--;
187:
188: m_map[m_firstFree] = DTM.NULL;
189:
190: return (m_firstFree == 0) ? DTM.NULL : m_map[m_firstFree - 1];
191: }
192:
193: /**
194: * Pop a node from the tail of the vector.
195: */
196: public final void popQuick() {
197:
198: m_firstFree--;
199:
200: m_map[m_firstFree] = DTM.NULL;
201: }
202:
203: /**
204: * Return the node at the top of the stack without popping the stack.
205: * Special purpose method for TransformerImpl, pushElemTemplateElement.
206: * Performance critical.
207: *
208: * @return Node at the top of the stack or null if stack is empty.
209: */
210: public final int peepOrNull() {
211: return ((null != m_map) && (m_firstFree > 0)) ? m_map[m_firstFree - 1]
212: : DTM.NULL;
213: }
214:
215: /**
216: * Push a pair of nodes into the stack.
217: * Special purpose method for TransformerImpl, pushElemTemplateElement.
218: * Performance critical.
219: *
220: * @param v1 First node to add to vector
221: * @param v2 Second node to add to vector
222: */
223: public final void pushPair(int v1, int v2) {
224:
225: if (null == m_map) {
226: m_map = new int[m_blocksize];
227: m_mapSize = m_blocksize;
228: } else {
229: if ((m_firstFree + 2) >= m_mapSize) {
230: m_mapSize += m_blocksize;
231:
232: int newMap[] = new int[m_mapSize];
233:
234: System.arraycopy(m_map, 0, newMap, 0, m_firstFree);
235:
236: m_map = newMap;
237: }
238: }
239:
240: m_map[m_firstFree] = v1;
241: m_map[m_firstFree + 1] = v2;
242: m_firstFree += 2;
243: }
244:
245: /**
246: * Pop a pair of nodes from the tail of the stack.
247: * Special purpose method for TransformerImpl, pushElemTemplateElement.
248: * Performance critical.
249: */
250: public final void popPair() {
251:
252: m_firstFree -= 2;
253: m_map[m_firstFree] = DTM.NULL;
254: m_map[m_firstFree + 1] = DTM.NULL;
255: }
256:
257: /**
258: * Set the tail of the stack to the given node.
259: * Special purpose method for TransformerImpl, pushElemTemplateElement.
260: * Performance critical.
261: *
262: * @param n Node to set at the tail of vector
263: */
264: public final void setTail(int n) {
265: m_map[m_firstFree - 1] = n;
266: }
267:
268: /**
269: * Set the given node one position from the tail.
270: * Special purpose method for TransformerImpl, pushElemTemplateElement.
271: * Performance critical.
272: *
273: * @param n Node to set
274: */
275: public final void setTailSub1(int n) {
276: m_map[m_firstFree - 2] = n;
277: }
278:
279: /**
280: * Return the node at the tail of the vector without popping
281: * Special purpose method for TransformerImpl, pushElemTemplateElement.
282: * Performance critical.
283: *
284: * @return Node at the tail of the vector
285: */
286: public final int peepTail() {
287: return m_map[m_firstFree - 1];
288: }
289:
290: /**
291: * Return the node one position from the tail without popping.
292: * Special purpose method for TransformerImpl, pushElemTemplateElement.
293: * Performance critical.
294: *
295: * @return Node one away from the tail
296: */
297: public final int peepTailSub1() {
298: return m_map[m_firstFree - 2];
299: }
300:
301: /**
302: * Insert a node in order in the list.
303: *
304: * @param value Node to insert
305: */
306: public void insertInOrder(int value) {
307:
308: for (int i = 0; i < m_firstFree; i++) {
309: if (value < m_map[i]) {
310: insertElementAt(value, i);
311:
312: return;
313: }
314: }
315:
316: addElement(value);
317: }
318:
319: /**
320: * Inserts the specified node in this vector at the specified index.
321: * Each component in this vector with an index greater or equal to
322: * the specified index is shifted upward to have an index one greater
323: * than the value it had previously.
324: *
325: * @param value Node to insert
326: * @param at Position where to insert
327: */
328: public void insertElementAt(int value, int at) {
329:
330: if (null == m_map) {
331: m_map = new int[m_blocksize];
332: m_mapSize = m_blocksize;
333: } else if ((m_firstFree + 1) >= m_mapSize) {
334: m_mapSize += m_blocksize;
335:
336: int newMap[] = new int[m_mapSize];
337:
338: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
339:
340: m_map = newMap;
341: }
342:
343: if (at <= (m_firstFree - 1)) {
344: System
345: .arraycopy(m_map, at, m_map, at + 1, m_firstFree
346: - at);
347: }
348:
349: m_map[at] = value;
350:
351: m_firstFree++;
352: }
353:
354: /**
355: * Append the nodes to the list.
356: *
357: * @param nodes NodeVector to append to this list
358: */
359: public void appendNodes(NodeVector nodes) {
360:
361: int nNodes = nodes.size();
362:
363: if (null == m_map) {
364: m_mapSize = nNodes + m_blocksize;
365: m_map = new int[m_mapSize];
366: } else if ((m_firstFree + nNodes) >= m_mapSize) {
367: m_mapSize += (nNodes + m_blocksize);
368:
369: int newMap[] = new int[m_mapSize];
370:
371: System.arraycopy(m_map, 0, newMap, 0, m_firstFree + nNodes);
372:
373: m_map = newMap;
374: }
375:
376: System.arraycopy(nodes.m_map, 0, m_map, m_firstFree, nNodes);
377:
378: m_firstFree += nNodes;
379: }
380:
381: /**
382: * Inserts the specified node in this vector at the specified index.
383: * Each component in this vector with an index greater or equal to
384: * the specified index is shifted upward to have an index one greater
385: * than the value it had previously.
386: */
387: public void removeAllElements() {
388:
389: if (null == m_map)
390: return;
391:
392: for (int i = 0; i < m_firstFree; i++) {
393: m_map[i] = DTM.NULL;
394: }
395:
396: m_firstFree = 0;
397: }
398:
399: /**
400: * Set the length to zero, but don't clear the array.
401: */
402: public void RemoveAllNoClear() {
403:
404: if (null == m_map)
405: return;
406:
407: m_firstFree = 0;
408: }
409:
410: /**
411: * Removes the first occurrence of the argument from this vector.
412: * If the object is found in this vector, each component in the vector
413: * with an index greater or equal to the object's index is shifted
414: * downward to have an index one smaller than the value it had
415: * previously.
416: *
417: * @param s Node to remove from the list
418: *
419: * @return True if the node was successfully removed
420: */
421: public boolean removeElement(int s) {
422:
423: if (null == m_map)
424: return false;
425:
426: for (int i = 0; i < m_firstFree; i++) {
427: int node = m_map[i];
428:
429: if (node == s) {
430: if (i > m_firstFree)
431: System.arraycopy(m_map, i + 1, m_map, i - 1,
432: m_firstFree - i);
433: else
434: m_map[i] = DTM.NULL;
435:
436: m_firstFree--;
437:
438: return true;
439: }
440: }
441:
442: return false;
443: }
444:
445: /**
446: * Deletes the component at the specified index. Each component in
447: * this vector with an index greater or equal to the specified
448: * index is shifted downward to have an index one smaller than
449: * the value it had previously.
450: *
451: * @param i Index of node to remove
452: */
453: public void removeElementAt(int i) {
454:
455: if (null == m_map)
456: return;
457:
458: if (i > m_firstFree)
459: System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree
460: - i);
461: else
462: m_map[i] = DTM.NULL;
463: }
464:
465: /**
466: * Sets the component at the specified index of this vector to be the
467: * specified object. The previous component at that position is discarded.
468: *
469: * The index must be a value greater than or equal to 0 and less
470: * than the current size of the vector.
471: *
472: * @param node Node to set
473: * @param index Index of where to set the node
474: */
475: public void setElementAt(int node, int index) {
476:
477: if (null == m_map) {
478: m_map = new int[m_blocksize];
479: m_mapSize = m_blocksize;
480: }
481:
482: if (index == -1)
483: addElement(node);
484:
485: m_map[index] = node;
486: }
487:
488: /**
489: * Get the nth element.
490: *
491: * @param i Index of node to get
492: *
493: * @return Node at specified index
494: */
495: public int elementAt(int i) {
496:
497: if (null == m_map)
498: return DTM.NULL;
499:
500: return m_map[i];
501: }
502:
503: /**
504: * Tell if the table contains the given node.
505: *
506: * @param s Node to look for
507: *
508: * @return True if the given node was found.
509: */
510: public boolean contains(int s) {
511:
512: if (null == m_map)
513: return false;
514:
515: for (int i = 0; i < m_firstFree; i++) {
516: int node = m_map[i];
517:
518: if (node == s)
519: return true;
520: }
521:
522: return false;
523: }
524:
525: /**
526: * Searches for the first occurence of the given argument,
527: * beginning the search at index, and testing for equality
528: * using the equals method.
529: *
530: * @param elem Node to look for
531: * @param index Index of where to start the search
532: * @return the index of the first occurrence of the object
533: * argument in this vector at position index or later in the
534: * vector; returns -1 if the object is not found.
535: */
536: public int indexOf(int elem, int index) {
537:
538: if (null == m_map)
539: return -1;
540:
541: for (int i = index; i < m_firstFree; i++) {
542: int node = m_map[i];
543:
544: if (node == elem)
545: return i;
546: }
547:
548: return -1;
549: }
550:
551: /**
552: * Searches for the first occurence of the given argument,
553: * beginning the search at index, and testing for equality
554: * using the equals method.
555: *
556: * @param elem Node to look for
557: * @return the index of the first occurrence of the object
558: * argument in this vector at position index or later in the
559: * vector; returns -1 if the object is not found.
560: */
561: public int indexOf(int elem) {
562:
563: if (null == m_map)
564: return -1;
565:
566: for (int i = 0; i < m_firstFree; i++) {
567: int node = m_map[i];
568:
569: if (node == elem)
570: return i;
571: }
572:
573: return -1;
574: }
575:
576: /**
577: * Sort an array using a quicksort algorithm.
578: *
579: * @param a The array to be sorted.
580: * @param lo0 The low index.
581: * @param hi0 The high index.
582: *
583: * @throws Exception
584: */
585: public void sort(int a[], int lo0, int hi0) throws Exception {
586:
587: int lo = lo0;
588: int hi = hi0;
589:
590: // pause(lo, hi);
591: if (lo >= hi) {
592: return;
593: } else if (lo == hi - 1) {
594:
595: /*
596: * sort a two element list by swapping if necessary
597: */
598: if (a[lo] > a[hi]) {
599: int T = a[lo];
600:
601: a[lo] = a[hi];
602: a[hi] = T;
603: }
604:
605: return;
606: }
607:
608: /*
609: * Pick a pivot and move it out of the way
610: */
611: int pivot = a[(lo + hi) / 2];
612:
613: a[(lo + hi) / 2] = a[hi];
614: a[hi] = pivot;
615:
616: while (lo < hi) {
617:
618: /*
619: * Search forward from a[lo] until an element is found that
620: * is greater than the pivot or lo >= hi
621: */
622: while (a[lo] <= pivot && lo < hi) {
623: lo++;
624: }
625:
626: /*
627: * Search backward from a[hi] until element is found that
628: * is less than the pivot, or lo >= hi
629: */
630: while (pivot <= a[hi] && lo < hi) {
631: hi--;
632: }
633:
634: /*
635: * Swap elements a[lo] and a[hi]
636: */
637: if (lo < hi) {
638: int T = a[lo];
639:
640: a[lo] = a[hi];
641: a[hi] = T;
642:
643: // pause();
644: }
645:
646: // if (stopRequested) {
647: // return;
648: // }
649: }
650:
651: /*
652: * Put the median in the "center" of the list
653: */
654: a[hi0] = a[hi];
655: a[hi] = pivot;
656:
657: /*
658: * Recursive calls, elements a[lo0] to a[lo-1] are less than or
659: * equal to pivot, elements a[hi+1] to a[hi0] are greater than
660: * pivot.
661: */
662: sort(a, lo0, lo - 1);
663: sort(a, hi + 1, hi0);
664: }
665:
666: /**
667: * Sort an array using a quicksort algorithm.
668: *
669: * @throws Exception
670: */
671: public void sort() throws Exception {
672: sort(m_map, 0, m_firstFree - 1);
673: }
674: }
|