NodeVector


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  /*
17   * $Id: NodeVector.java,v 1.9 2004/02/17 04:21:14 minchau Exp $
18   */
19  package org.apache.xml.utils;
20  
21  import java.io.Serializable  ;
22  
23  import org.apache.xml.dtm.DTM;
24  
25  /**
26   * A very simple table that stores a list of Nodes.
27   * @xsl.usage internal
28   */
29  public class NodeVector implements Serializable  , Cloneable  
30  {
31  
32    /**
33     * Size of blocks to allocate.
34     *  @serial          
35     */
36    private int m_blocksize;
37  
38    /**
39     * Array of nodes this points to.
40     *  @serial          
41     */
42    private int m_map[];
43  
44    /**
45     * Number of nodes in this NodeVector.
46     *  @serial          
47     */
48    protected int m_firstFree = 0;
49  
50    /**
51     * Size of the array this points to.
52     *  @serial           
53     */
54    private int m_mapSize;  // lazy initialization
55  
56    /**
57     * Default constructor.
58     */
59    public NodeVector()
60    {
61      m_blocksize = 32;
62      m_mapSize = 0;
63    }
64  
65    /**
66     * Construct a NodeVector, using the given block size.
67     *
68     * @param blocksize Size of blocks to allocate
69     */
70    public NodeVector(int blocksize)
71    {
72      m_blocksize = blocksize;
73      m_mapSize = 0;
74    }
75  
76    /**
77     * Get a cloned LocPathIterator.
78     *
79     * @return A clone of this
80     *
81     * @throws CloneNotSupportedException
82     */
83    public Object   clone() throws CloneNotSupportedException  
84    {
85  
86      NodeVector clone = (NodeVector) super.clone();
87  
88      if ((null != this.m_map) && (this.m_map == clone.m_map))
89      {
90        clone.m_map = new int[this.m_map.length];
91  
92        System.arraycopy(this.m_map, 0, clone.m_map, 0, this.m_map.length);
93      }
94  
95      return clone;
96    }
97  
98    /**
99     * Get the length of the list.
100    *
101    * @return Number of nodes in this NodeVector
102    */
103   public int size()
104   {
105     return m_firstFree;
106   }
107 
108   /**
109    * Append a Node onto the vector.
110    *
111    * @param value Node to add to the vector
112    */
113   public void addElement(int value)
114   {
115 
116     if ((m_firstFree + 1) >= m_mapSize)
117     {
118       if (null == m_map)
119       {
120         m_map = new int[m_blocksize];
121         m_mapSize = m_blocksize;
122       }
123       else
124       {
125         m_mapSize += m_blocksize;
126 
127         int newMap[] = new int[m_mapSize];
128 
129         System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
130 
131         m_map = newMap;
132       }
133     }
134 
135     m_map[m_firstFree] = value;
136 
137     m_firstFree++;
138   }
139 
140   /**
141    * Append a Node onto the vector.
142    *
143    * @param value Node to add to the vector
144    */
145   public final void push(int value)
146   {
147 
148     int ff = m_firstFree;
149 
150     if ((ff + 1) >= m_mapSize)
151     {
152       if (null == m_map)
153       {
154         m_map = new int[m_blocksize];
155         m_mapSize = m_blocksize;
156       }
157       else
158       {
159         m_mapSize += m_blocksize;
160 
161         int newMap[] = new int[m_mapSize];
162 
163         System.arraycopy(m_map, 0, newMap, 0, ff + 1);
164 
165         m_map = newMap;
166       }
167     }
168 
169     m_map[ff] = value;
170 
171     ff++;
172 
173     m_firstFree = ff;
174   }
175 
176   /**
177    * Pop a node from the tail of the vector and return the result.
178    *
179    * @return the node at the tail of the vector
180    */
181   public final int pop()
182   {
183 
184     m_firstFree--;
185 
186     int n = m_map[m_firstFree];
187 
188     m_map[m_firstFree] = DTM.NULL;
189 
190     return n;
191   }
192 
193   /**
194    * Pop a node from the tail of the vector and return the
195    * top of the stack after the pop.
196    *
197    * @return The top of the stack after it's been popped
198    */
199   public final int popAndTop()
200   {
201 
202     m_firstFree--;
203 
204     m_map[m_firstFree] = DTM.NULL;
205 
206     return (m_firstFree == 0) ? DTM.NULL : m_map[m_firstFree - 1];
207   }
208 
209   /**
210    * Pop a node from the tail of the vector.
211    */
212   public final void popQuick()
213   {
214 
215     m_firstFree--;
216 
217     m_map[m_firstFree] = DTM.NULL;
218   }
219 
220   /**
221    * Return the node at the top of the stack without popping the stack.
222    * Special purpose method for TransformerImpl, pushElemTemplateElement.
223    * Performance critical.
224    *
225    * @return Node at the top of the stack or null if stack is empty.
226    */
227   public final int peepOrNull()
228   {
229     return ((null != m_map) && (m_firstFree > 0))
230            ? m_map[m_firstFree - 1] : DTM.NULL;
231   }
232 
233   /**
234    * Push a pair of nodes into the stack.
235    * Special purpose method for TransformerImpl, pushElemTemplateElement.
236    * Performance critical.
237    *
238    * @param v1 First node to add to vector
239    * @param v2 Second node to add to vector
240    */
241   public final void pushPair(int v1, int v2)
242   {
243 
244     if (null == m_map)
245     {
246       m_map = new int[m_blocksize];
247       m_mapSize = m_blocksize;
248     }
249     else
250     {
251       if ((m_firstFree + 2) >= m_mapSize)
252       {
253         m_mapSize += m_blocksize;
254 
255         int newMap[] = new int[m_mapSize];
256 
257         System.arraycopy(m_map, 0, newMap, 0, m_firstFree);
258 
259         m_map = newMap;
260       }
261     }
262 
263     m_map[m_firstFree] = v1;
264     m_map[m_firstFree + 1] = v2;
265     m_firstFree += 2;
266   }
267 
268   /**
269    * Pop a pair of nodes from the tail of the stack.
270    * Special purpose method for TransformerImpl, pushElemTemplateElement.
271    * Performance critical.
272    */
273   public final void popPair()
274   {
275 
276     m_firstFree -= 2;
277     m_map[m_firstFree] = DTM.NULL;
278     m_map[m_firstFree + 1] = DTM.NULL;
279   }
280 
281   /**
282    * Set the tail of the stack to the given node.
283    * Special purpose method for TransformerImpl, pushElemTemplateElement.
284    * Performance critical.
285    *
286    * @param n Node to set at the tail of vector
287    */
288   public final void setTail(int n)
289   {
290     m_map[m_firstFree - 1] = n;
291   }
292 
293   /**
294    * Set the given node one position from the tail.
295    * Special purpose method for TransformerImpl, pushElemTemplateElement.
296    * Performance critical.
297    *
298    * @param n Node to set
299    */
300   public final void setTailSub1(int n)
301   {
302     m_map[m_firstFree - 2] = n;
303   }
304 
305   /**
306    * Return the node at the tail of the vector without popping
307    * Special purpose method for TransformerImpl, pushElemTemplateElement.
308    * Performance critical.
309    *
310    * @return Node at the tail of the vector
311    */
312   public final int peepTail()
313   {
314     return m_map[m_firstFree - 1];
315   }
316 
317   /**
318    * Return the node one position from the tail without popping.
319    * Special purpose method for TransformerImpl, pushElemTemplateElement.
320    * Performance critical.
321    *
322    * @return Node one away from the tail
323    */
324   public final int peepTailSub1()
325   {
326     return m_map[m_firstFree - 2];
327   }
328 
329   /**
330    * Insert a node in order in the list.
331    *
332    * @param value Node to insert
333    */
334   public void insertInOrder(int value)
335   {
336 
337     for (int i = 0; i < m_firstFree; i++)
338     {
339       if (value < m_map[i])
340       {
341         insertElementAt(value, i);
342 
343         return;
344       }
345     }
346 
347     addElement(value);
348   }
349 
350   /**
351    * Inserts the specified node in this vector at the specified index.
352    * Each component in this vector with an index greater or equal to
353    * the specified index is shifted upward to have an index one greater
354    * than the value it had previously.
355    *
356    * @param value Node to insert
357    * @param at Position where to insert
358    */
359   public void insertElementAt(int value, int at)
360   {
361 
362     if (null == m_map)
363     {
364       m_map = new int[m_blocksize];
365       m_mapSize = m_blocksize;
366     }
367     else if ((m_firstFree + 1) >= m_mapSize)
368     {
369       m_mapSize += m_blocksize;
370 
371       int newMap[] = new int[m_mapSize];
372 
373       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
374 
375       m_map = newMap;
376     }
377 
378     if (at <= (m_firstFree - 1))
379     {
380       System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
381     }
382 
383     m_map[at] = value;
384 
385     m_firstFree++;
386   }
387 
388   /**
389    * Append the nodes to the list.
390    *
391    * @param nodes NodeVector to append to this list
392    */
393   public void appendNodes(NodeVector nodes)
394   {
395 
396     int nNodes = nodes.size();
397 
398     if (null == m_map)
399     {
400       m_mapSize = nNodes + m_blocksize;
401       m_map = new int[m_mapSize];
402     }
403     else if ((m_firstFree + nNodes) >= m_mapSize)
404     {
405       m_mapSize += (nNodes + m_blocksize);
406 
407       int newMap[] = new int[m_mapSize];
408 
409       System.arraycopy(m_map, 0, newMap, 0, m_firstFree + nNodes);
410 
411       m_map = newMap;
412     }
413 
414     System.arraycopy(nodes.m_map, 0, m_map, m_firstFree, nNodes);
415 
416     m_firstFree += nNodes;
417   }
418 
419   /**
420    * Inserts the specified node in this vector at the specified index.
421    * Each component in this vector with an index greater or equal to
422    * the specified index is shifted upward to have an index one greater
423    * than the value it had previously.
424    */
425   public void removeAllElements()
426   {
427 
428     if (null == m_map)
429       return;
430 
431     for (int i = 0; i < m_firstFree; i++)
432     {
433       m_map[i] = DTM.NULL;
434     }
435 
436     m_firstFree = 0;
437   }
438   
439   /**
440    * Set the length to zero, but don't clear the array.
441    */
442   public void RemoveAllNoClear()
443   {
444 
445     if (null == m_map)
446       return;
447 
448     m_firstFree = 0;
449   }
450 
451   /**
452    * Removes the first occurrence of the argument from this vector.
453    * If the object is found in this vector, each component in the vector
454    * with an index greater or equal to the object's index is shifted
455    * downward to have an index one smaller than the value it had
456    * previously.
457    *
458    * @param s Node to remove from the list
459    *
460    * @return True if the node was successfully removed
461    */
462   public boolean removeElement(int s)
463   {
464 
465     if (null == m_map)
466       return false;
467 
468     for (int i = 0; i < m_firstFree; i++)
469     {
470       int node = m_map[i];
471 
472       if (node == s)
473       {
474         if (i > m_firstFree)
475           System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
476         else
477           m_map[i] = DTM.NULL;
478 
479         m_firstFree--;
480 
481         return true;
482       }
483     }
484 
485     return false;
486   }
487 
488   /**
489    * Deletes the component at the specified index. Each component in
490    * this vector with an index greater or equal to the specified
491    * index is shifted downward to have an index one smaller than
492    * the value it had previously.
493    *
494    * @param i Index of node to remove
495    */
496   public void removeElementAt(int i)
497   {
498 
499     if (null == m_map)
500       return;
501 
502     if (i > m_firstFree)
503       System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
504     else
505       m_map[i] = DTM.NULL;
506   }
507 
508   /**
509    * Sets the component at the specified index of this vector to be the
510    * specified object. The previous component at that position is discarded.
511    *
512    * The index must be a value greater than or equal to 0 and less
513    * than the current size of the vector.
514    *
515    * @param node Node to set
516    * @param index Index of where to set the node
517    */
518   public void setElementAt(int node, int index)
519   {
520 
521     if (null == m_map)
522     {
523       m_map = new int[m_blocksize];
524       m_mapSize = m_blocksize;
525     }
526     
527     if(index == -1)
528         addElement(node);
529 
530     m_map[index] = node;
531   }
532 
533   /**
534    * Get the nth element.
535    *
536    * @param i Index of node to get
537    *
538    * @return Node at specified index
539    */
540   public int elementAt(int i)
541   {
542 
543     if (null == m_map)
544       return DTM.NULL;
545 
546     return m_map[i];
547   }
548 
549   /**
550    * Tell if the table contains the given node.
551    *
552    * @param s Node to look for
553    *
554    * @return True if the given node was found.
555    */
556   public boolean contains(int s)
557   {
558 
559     if (null == m_map)
560       return false;
561 
562     for (int i = 0; i < m_firstFree; i++)
563     {
564       int node = m_map[i];
565 
566       if (node == s)
567         return true;
568     }
569 
570     return false;
571   }
572 
573   /**
574    * Searches for the first occurence of the given argument,
575    * beginning the search at index, and testing for equality
576    * using the equals method.
577    *
578    * @param elem Node to look for
579    * @param index Index of where to start the search
580    * @return the index of the first occurrence of the object
581    * argument in this vector at position index or later in the
582    * vector; returns -1 if the object is not found.
583    */
584   public int indexOf(int elem, int index)
585   {
586 
587     if (null == m_map)
588       return -1;
589 
590     for (int i = index; i < m_firstFree; i++)
591     {
592       int node = m_map[i];
593 
594       if (node == elem)
595         return i;
596     }
597 
598     return -1;
599   }
600 
601   /**
602    * Searches for the first occurence of the given argument,
603    * beginning the search at index, and testing for equality
604    * using the equals method.
605    *
606    * @param elem Node to look for
607    * @return the index of the first occurrence of the object
608    * argument in this vector at position index or later in the
609    * vector; returns -1 if the object is not found.
610    */
611   public int indexOf(int elem)
612   {
613 
614     if (null == m_map)
615       return -1;
616 
617     for (int i = 0; i < m_firstFree; i++)
618     {
619       int node = m_map[i];
620 
621       if (node == elem)
622         return i;
623     }
624 
625     return -1;
626   }
627 
628   /**
629    * Sort an array using a quicksort algorithm.
630    *
631    * @param a The array to be sorted.
632    * @param lo0  The low index.
633    * @param hi0  The high index.
634    *
635    * @throws Exception
636    */
637   public void sort(int a[], int lo0, int hi0) throws Exception  
638   {
639 
640     int lo = lo0;
641     int hi = hi0;
642 
643     // pause(lo, hi);
644     if (lo >= hi)
645     {
646       return;
647     }
648     else if (lo == hi - 1)
649     {
650 
651       /*
652        *  sort a two element list by swapping if necessary
653        */
654       if (a[lo] > a[hi])
655       {
656         int T = a[lo];
657 
658         a[lo] = a[hi];
659         a[hi] = T;
660       }
661 
662       return;
663     }
664 
665     /*
666      *  Pick a pivot and move it out of the way
667      */
668     int pivot = a[(lo + hi) / 2];
669 
670     a[(lo + hi) / 2] = a[hi];
671     a[hi] = pivot;
672 
673     while (lo < hi)
674     {
675 
676       /*
677        *  Search forward from a[lo] until an element is found that
678        *  is greater than the pivot or lo >= hi
679        */
680       while (a[lo] <= pivot && lo < hi)
681       {
682         lo++;
683       }
684 
685       /*
686        *  Search backward from a[hi] until element is found that
687        *  is less than the pivot, or lo >= hi
688        */
689       while (pivot <= a[hi] && lo < hi)
690       {
691         hi--;
692       }
693 
694       /*
695        *  Swap elements a[lo] and a[hi]
696        */
697       if (lo < hi)
698       {
699         int T = a[lo];
700 
701         a[lo] = a[hi];
702         a[hi] = T;
703 
704         // pause();
705       }
706 
707       // if (stopRequested) {
708       //    return;
709       // }
710     }
711 
712     /*
713      *  Put the median in the "center" of the list
714      */
715     a[hi0] = a[hi];
716     a[hi] = pivot;
717 
718     /*
719      *  Recursive calls, elements a[lo0] to a[lo-1] are less than or
720      *  equal to pivot, elements a[hi+1] to a[hi0] are greater than
721      *  pivot.
722      */
723     sort(a, lo0, lo - 1);
724     sort(a, hi + 1, hi0);
725   }
726 
727   /**
728    * Sort an array using a quicksort algorithm.
729    *
730    * @param a The array to be sorted.
731    * @param lo0  The low index.
732    * @param hi0  The high index.
733    *
734    * @throws Exception
735    */
736   public void sort() throws Exception  
737   {
738     sort(m_map, 0, m_firstFree - 1);
739   }
740 }
741
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags