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