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: SuballocatedIntVector.java,v 1.11 2005/01/23 01:02:10 mcnamara Exp $
018: */
019: package org.apache.xml.utils;
020:
021: /**
022: * A very simple table that stores a list of int. Very similar API to our
023: * IntVector class (same API); different internal storage.
024: *
025: * This version uses an array-of-arrays solution. Read/write access is thus
026: * a bit slower than the simple IntVector, and basic storage is a trifle
027: * higher due to the top-level array -- but appending is O(1) fast rather
028: * than O(N**2) slow, which will swamp those costs in situations where
029: * long vectors are being built up.
030: *
031: * Known issues:
032: *
033: * Some methods are private because they haven't yet been tested properly.
034: *
035: * Retrieval performance is critical, since this is used at the core
036: * of the DTM model. (Append performance is almost as important.)
037: * That's pushing me toward just letting reads from unset indices
038: * throw exceptions or return stale data; safer behavior would have
039: * performance costs.
040: * */
041: public class SuballocatedIntVector {
042: /** Size of blocks to allocate */
043: protected int m_blocksize;
044:
045: /** Bitwise addressing (much faster than div/remainder */
046: protected int m_SHIFT, m_MASK;
047:
048: /** The default number of blocks to (over)allocate by */
049: protected static final int NUMBLOCKS_DEFAULT = 32;
050:
051: /** The number of blocks to (over)allocate by */
052: protected int m_numblocks = NUMBLOCKS_DEFAULT;
053:
054: /** Array of arrays of ints */
055: protected int m_map[][];
056:
057: /** Number of ints in array */
058: protected int m_firstFree = 0;
059:
060: /** "Shortcut" handle to m_map[0]. Surprisingly helpful for short vectors. */
061: protected int m_map0[];
062:
063: /** "Shortcut" handle to most recently added row of m_map.
064: * Very helpful during construction.
065: * @xsl.usage internal
066: */
067: protected int m_buildCache[];
068: protected int m_buildCacheStartIndex;
069:
070: /**
071: * Default constructor. Note that the default
072: * block size is currently 2K, which may be overkill for
073: * small lists and undershootng for large ones.
074: */
075: public SuballocatedIntVector() {
076: this (2048);
077: }
078:
079: /**
080: * Construct a IntVector, using the given block size and number
081: * of blocks. For efficiency, we will round the requested size
082: * off to a power of two.
083: *
084: * @param blocksize Size of block to allocate
085: * @param numblocks Number of blocks to allocate
086: * */
087: public SuballocatedIntVector(int blocksize, int numblocks) {
088: //m_blocksize = blocksize;
089: for (m_SHIFT = 0; 0 != (blocksize >>>= 1); ++m_SHIFT)
090: ;
091: m_blocksize = 1 << m_SHIFT;
092: m_MASK = m_blocksize - 1;
093: m_numblocks = numblocks;
094:
095: m_map0 = new int[m_blocksize];
096: m_map = new int[numblocks][];
097: m_map[0] = m_map0;
098: m_buildCache = m_map0;
099: m_buildCacheStartIndex = 0;
100: }
101:
102: /** Construct a IntVector, using the given block size and
103: * the default number of blocks (32).
104: *
105: * @param blocksize Size of block to allocate
106: * */
107: public SuballocatedIntVector(int blocksize) {
108: this (blocksize, NUMBLOCKS_DEFAULT);
109: }
110:
111: /**
112: * Get the length of the list.
113: *
114: * @return length of the list
115: */
116: public int size() {
117: return m_firstFree;
118: }
119:
120: /**
121: * Set the length of the list. This will only work to truncate the list, and
122: * even then it has not been heavily tested and may not be trustworthy.
123: *
124: * @return length of the list
125: */
126: public void setSize(int sz) {
127: if (m_firstFree > sz) // Whups; had that backward!
128: m_firstFree = sz;
129: }
130:
131: /**
132: * Append a int onto the vector.
133: *
134: * @param value Int to add to the list
135: */
136: public void addElement(int value) {
137: int indexRelativeToCache = m_firstFree - m_buildCacheStartIndex;
138:
139: // Is the new index an index into the cache row of m_map?
140: if (indexRelativeToCache >= 0
141: && indexRelativeToCache < m_blocksize) {
142: m_buildCache[indexRelativeToCache] = value;
143: ++m_firstFree;
144: } else {
145: // Growing the outer array should be rare. We initialize to a
146: // total of m_blocksize squared elements, which at the default
147: // size is 4M integers... and we grow by at least that much each
148: // time. However, attempts to microoptimize for this (assume
149: // long enough and catch exceptions) yield no noticable
150: // improvement.
151:
152: int index = m_firstFree >>> m_SHIFT;
153: int offset = m_firstFree & m_MASK;
154:
155: if (index >= m_map.length) {
156: int newsize = index + m_numblocks;
157: int[][] newMap = new int[newsize][];
158: System.arraycopy(m_map, 0, newMap, 0, m_map.length);
159: m_map = newMap;
160: }
161: int[] block = m_map[index];
162: if (null == block)
163: block = m_map[index] = new int[m_blocksize];
164: block[offset] = value;
165:
166: // Cache the current row of m_map. Next m_blocksize-1
167: // values added will go to this row.
168: m_buildCache = block;
169: m_buildCacheStartIndex = m_firstFree - offset;
170:
171: ++m_firstFree;
172: }
173: }
174:
175: /**
176: * Append several int values onto the vector.
177: *
178: * @param value Int to add to the list
179: */
180: private void addElements(int value, int numberOfElements) {
181: if (m_firstFree + numberOfElements < m_blocksize)
182: for (int i = 0; i < numberOfElements; i++) {
183: m_map0[m_firstFree++] = value;
184: }
185: else {
186: int index = m_firstFree >>> m_SHIFT;
187: int offset = m_firstFree & m_MASK;
188: m_firstFree += numberOfElements;
189: while (numberOfElements > 0) {
190: if (index >= m_map.length) {
191: int newsize = index + m_numblocks;
192: int[][] newMap = new int[newsize][];
193: System.arraycopy(m_map, 0, newMap, 0, m_map.length);
194: m_map = newMap;
195: }
196: int[] block = m_map[index];
197: if (null == block)
198: block = m_map[index] = new int[m_blocksize];
199: int copied = (m_blocksize - offset < numberOfElements) ? m_blocksize
200: - offset
201: : numberOfElements;
202: numberOfElements -= copied;
203: while (copied-- > 0)
204: block[offset++] = value;
205:
206: ++index;
207: offset = 0;
208: }
209: }
210: }
211:
212: /**
213: * Append several slots onto the vector, but do not set the values.
214: * Note: "Not Set" means the value is unspecified.
215: *
216: * @param numberOfElements Int to add to the list
217: */
218: private void addElements(int numberOfElements) {
219: int newlen = m_firstFree + numberOfElements;
220: if (newlen > m_blocksize) {
221: int index = m_firstFree >>> m_SHIFT;
222: int newindex = (m_firstFree + numberOfElements) >>> m_SHIFT;
223: for (int i = index + 1; i <= newindex; ++i)
224: m_map[i] = new int[m_blocksize];
225: }
226: m_firstFree = newlen;
227: }
228:
229: /**
230: * Inserts the specified node in this vector at the specified index.
231: * Each component in this vector with an index greater or equal to
232: * the specified index is shifted upward to have an index one greater
233: * than the value it had previously.
234: *
235: * Insertion may be an EXPENSIVE operation!
236: *
237: * @param value Int to insert
238: * @param at Index of where to insert
239: */
240: private void insertElementAt(int value, int at) {
241: if (at == m_firstFree)
242: addElement(value);
243: else if (at > m_firstFree) {
244: int index = at >>> m_SHIFT;
245: if (index >= m_map.length) {
246: int newsize = index + m_numblocks;
247: int[][] newMap = new int[newsize][];
248: System.arraycopy(m_map, 0, newMap, 0, m_map.length);
249: m_map = newMap;
250: }
251: int[] block = m_map[index];
252: if (null == block)
253: block = m_map[index] = new int[m_blocksize];
254: int offset = at & m_MASK;
255: block[offset] = value;
256: m_firstFree = offset + 1;
257: } else {
258: int index = at >>> m_SHIFT;
259: int maxindex = m_firstFree >>> m_SHIFT; // %REVIEW% (m_firstFree+1?)
260: ++m_firstFree;
261: int offset = at & m_MASK;
262: int push;
263:
264: // ***** Easier to work down from top?
265: while (index <= maxindex) {
266: int copylen = m_blocksize - offset - 1;
267: int[] block = m_map[index];
268: if (null == block) {
269: push = 0;
270: block = m_map[index] = new int[m_blocksize];
271: } else {
272: push = block[m_blocksize - 1];
273: System.arraycopy(block, offset, block, offset + 1,
274: copylen);
275: }
276: block[offset] = value;
277: value = push;
278: offset = 0;
279: ++index;
280: }
281: }
282: }
283:
284: /**
285: * Wipe it out. Currently defined as equivalent to setSize(0).
286: */
287: public void removeAllElements() {
288: m_firstFree = 0;
289: m_buildCache = m_map0;
290: m_buildCacheStartIndex = 0;
291: }
292:
293: /**
294: * Removes the first occurrence of the argument from this vector.
295: * If the object is found in this vector, each component in the vector
296: * with an index greater or equal to the object's index is shifted
297: * downward to have an index one smaller than the value it had
298: * previously.
299: *
300: * @param s Int to remove from array
301: *
302: * @return True if the int was removed, false if it was not found
303: */
304: private boolean removeElement(int s) {
305: int at = indexOf(s, 0);
306: if (at < 0)
307: return false;
308: removeElementAt(at);
309: return true;
310: }
311:
312: /**
313: * Deletes the component at the specified index. Each component in
314: * this vector with an index greater or equal to the specified
315: * index is shifted downward to have an index one smaller than
316: * the value it had previously.
317: *
318: * @param i index of where to remove and int
319: */
320: private void removeElementAt(int at) {
321: // No point in removing elements that "don't exist"...
322: if (at < m_firstFree) {
323: int index = at >>> m_SHIFT;
324: int maxindex = m_firstFree >>> m_SHIFT;
325: int offset = at & m_MASK;
326:
327: while (index <= maxindex) {
328: int copylen = m_blocksize - offset - 1;
329: int[] block = m_map[index];
330: if (null == block)
331: block = m_map[index] = new int[m_blocksize];
332: else
333: System.arraycopy(block, offset + 1, block, offset,
334: copylen);
335: if (index < maxindex) {
336: int[] next = m_map[index + 1];
337: if (next != null)
338: block[m_blocksize - 1] = (next != null) ? next[0]
339: : 0;
340: } else
341: block[m_blocksize - 1] = 0;
342: offset = 0;
343: ++index;
344: }
345: }
346: --m_firstFree;
347: }
348:
349: /**
350: * Sets the component at the specified index of this vector to be the
351: * specified object. The previous component at that position is discarded.
352: *
353: * The index must be a value greater than or equal to 0 and less
354: * than the current size of the vector.
355: *
356: * @param value object to set
357: * @param at Index of where to set the object
358: */
359: public void setElementAt(int value, int at) {
360: if (at < m_blocksize)
361: m_map0[at] = value;
362: else {
363: int index = at >>> m_SHIFT;
364: int offset = at & m_MASK;
365:
366: if (index >= m_map.length) {
367: int newsize = index + m_numblocks;
368: int[][] newMap = new int[newsize][];
369: System.arraycopy(m_map, 0, newMap, 0, m_map.length);
370: m_map = newMap;
371: }
372:
373: int[] block = m_map[index];
374: if (null == block)
375: block = m_map[index] = new int[m_blocksize];
376: block[offset] = value;
377: }
378:
379: if (at >= m_firstFree)
380: m_firstFree = at + 1;
381: }
382:
383: /**
384: * Get the nth element. This is often at the innermost loop of an
385: * application, so performance is critical.
386: *
387: * @param i index of value to get
388: *
389: * @return value at given index. If that value wasn't previously set,
390: * the result is undefined for performance reasons. It may throw an
391: * exception (see below), may return zero, or (if setSize has previously
392: * been used) may return stale data.
393: *
394: * @throws ArrayIndexOutOfBoundsException if the index was _clearly_
395: * unreasonable (negative, or past the highest block).
396: *
397: * @throws NullPointerException if the index points to a block that could
398: * have existed (based on the highest index used) but has never had anything
399: * set into it.
400: * %REVIEW% Could add a catch to create the block in that case, or return 0.
401: * Try/Catch is _supposed_ to be nearly free when not thrown to. Do we
402: * believe that? Should we have a separate safeElementAt?
403: */
404: public int elementAt(int i) {
405: // This is actually a significant optimization!
406: if (i < m_blocksize)
407: return m_map0[i];
408:
409: return m_map[i >>> m_SHIFT][i & m_MASK];
410: }
411:
412: /**
413: * Tell if the table contains the given node.
414: *
415: * @param s object to look for
416: *
417: * @return true if the object is in the list
418: */
419: private boolean contains(int s) {
420: return (indexOf(s, 0) >= 0);
421: }
422:
423: /**
424: * Searches for the first occurence of the given argument,
425: * beginning the search at index, and testing for equality
426: * using the equals method.
427: *
428: * @param elem object to look for
429: * @param index Index of where to begin search
430: * @return the index of the first occurrence of the object
431: * argument in this vector at position index or later in the
432: * vector; returns -1 if the object is not found.
433: */
434: public int indexOf(int elem, int index) {
435: if (index >= m_firstFree)
436: return -1;
437:
438: int bindex = index >>> m_SHIFT;
439: int boffset = index & m_MASK;
440: int maxindex = m_firstFree >>> m_SHIFT;
441: int[] block;
442:
443: for (; bindex < maxindex; ++bindex) {
444: block = m_map[bindex];
445: if (block != null)
446: for (int offset = boffset; offset < m_blocksize; ++offset)
447: if (block[offset] == elem)
448: return offset + bindex * m_blocksize;
449: boffset = 0; // after first
450: }
451: // Last block may need to stop before end
452: int maxoffset = m_firstFree & m_MASK;
453: block = m_map[maxindex];
454: for (int offset = boffset; offset < maxoffset; ++offset)
455: if (block[offset] == elem)
456: return offset + maxindex * m_blocksize;
457:
458: return -1;
459: }
460:
461: /**
462: * Searches for the first occurence of the given argument,
463: * beginning the search at index, and testing for equality
464: * using the equals method.
465: *
466: * @param elem object to look for
467: * @return the index of the first occurrence of the object
468: * argument in this vector at position index or later in the
469: * vector; returns -1 if the object is not found.
470: */
471: public int indexOf(int elem) {
472: return indexOf(elem, 0);
473: }
474:
475: /**
476: * Searches for the first occurence of the given argument,
477: * beginning the search at index, and testing for equality
478: * using the equals method.
479: *
480: * @param elem Object to look for
481: * @return the index of the first occurrence of the object
482: * argument in this vector at position index or later in the
483: * vector; returns -1 if the object is not found.
484: */
485: private int lastIndexOf(int elem) {
486: int boffset = m_firstFree & m_MASK;
487: for (int index = m_firstFree >>> m_SHIFT; index >= 0; --index) {
488: int[] block = m_map[index];
489: if (block != null)
490: for (int offset = boffset; offset >= 0; --offset)
491: if (block[offset] == elem)
492: return offset + index * m_blocksize;
493: boffset = 0; // after first
494: }
495: return -1;
496: }
497:
498: /**
499: * Return the internal m_map0 array
500: * @return the m_map0 array
501: */
502: public final int[] getMap0() {
503: return m_map0;
504: }
505:
506: /**
507: * Return the m_map double array
508: * @return the internal map of array of arrays
509: */
510: public final int[][] getMap() {
511: return m_map;
512: }
513:
514: }
|