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