1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 /* 19 * $Id: NodeVector.java 468655 2006-10-28 07:12:06Z minchau $ 20 */ 21 package org.apache.xml.utils; 22 23 import java.io.Serializable; 24 25 import org.apache.xml.dtm.DTM; 26 27 /** 28 * A very simple table that stores a list of Nodes. 29 * @xsl.usage internal 30 */ 31 public class NodeVector implements Serializable, Cloneable 32 { 33 static final long serialVersionUID = -713473092200731870L; 34 35 /** 36 * Size of blocks to allocate. 37 * @serial 38 */ 39 private int m_blocksize; 40 41 /** 42 * Array of nodes this points to. 43 * @serial 44 */ 45 private int m_map[]; 46 47 /** 48 * Number of nodes in this NodeVector. 49 * @serial 50 */ 51 protected int m_firstFree = 0; 52 53 /** 54 * Size of the array this points to. 55 * @serial 56 */ 57 private int m_mapSize; // lazy initialization 58 59 /** 60 * Default constructor. 61 */ NodeVector()62 public NodeVector() 63 { 64 m_blocksize = 32; 65 m_mapSize = 0; 66 } 67 68 /** 69 * Construct a NodeVector, using the given block size. 70 * 71 * @param blocksize Size of blocks to allocate 72 */ NodeVector(int blocksize)73 public NodeVector(int blocksize) 74 { 75 m_blocksize = blocksize; 76 m_mapSize = 0; 77 } 78 79 /** 80 * Get a cloned LocPathIterator. 81 * 82 * @return A clone of this 83 * 84 * @throws CloneNotSupportedException 85 */ clone()86 public Object clone() throws CloneNotSupportedException 87 { 88 89 NodeVector clone = (NodeVector) super.clone(); 90 91 if ((null != this.m_map) && (this.m_map == clone.m_map)) 92 { 93 clone.m_map = new int[this.m_map.length]; 94 95 System.arraycopy(this.m_map, 0, clone.m_map, 0, this.m_map.length); 96 } 97 98 return clone; 99 } 100 101 /** 102 * Get the length of the list. 103 * 104 * @return Number of nodes in this NodeVector 105 */ size()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 */ addElement(int value)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 */ push(int value)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 */ pop()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 */ popAndTop()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 */ popQuick()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 */ peepOrNull()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 */ pushPair(int v1, int v2)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 */ popPair()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 */ setTail(int n)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 */ setTailSub1(int n)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 */ peepTail()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 */ peepTailSub1()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 */ insertInOrder(int value)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 */ insertElementAt(int value, int at)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 */ appendNodes(NodeVector nodes)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 */ removeAllElements()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 */ RemoveAllNoClear()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 */ removeElement(int s)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 */ removeElementAt(int i)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 */ setElementAt(int node, int index)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 */ elementAt(int i)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 */ contains(int s)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 */ indexOf(int elem, int index)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 */ indexOf(int elem)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 */ sort(int a[], int lo0, int hi0)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 pivot = a[(lo + hi) / 2]; 672 673 a[(lo + hi) / 2] = a[hi]; 674 a[hi] = pivot; 675 676 while (lo < hi) 677 { 678 679 /* 680 * Search forward from a[lo] until an element is found that 681 * is greater than the pivot or lo >= hi 682 */ 683 while (a[lo] <= pivot && lo < hi) 684 { 685 lo++; 686 } 687 688 /* 689 * Search backward from a[hi] until element is found that 690 * is less than the pivot, or lo >= hi 691 */ 692 while (pivot <= a[hi] && lo < hi) 693 { 694 hi--; 695 } 696 697 /* 698 * Swap elements a[lo] and a[hi] 699 */ 700 if (lo < hi) 701 { 702 int T = a[lo]; 703 704 a[lo] = a[hi]; 705 a[hi] = T; 706 707 // pause(); 708 } 709 710 // if (stopRequested) { 711 // return; 712 // } 713 } 714 715 /* 716 * Put the median in the "center" of the list 717 */ 718 a[hi0] = a[hi]; 719 a[hi] = pivot; 720 721 /* 722 * Recursive calls, elements a[lo0] to a[lo-1] are less than or 723 * equal to pivot, elements a[hi+1] to a[hi0] are greater than 724 * pivot. 725 */ 726 sort(a, lo0, lo - 1); 727 sort(a, hi + 1, hi0); 728 } 729 730 /** 731 * Sort an array using a quicksort algorithm. 732 * 733 * @throws Exception 734 */ sort()735 public void sort() throws Exception 736 { 737 sort(m_map, 0, m_firstFree - 1); 738 } 739 } 740