2
* Copyright 2002-2004 The Apache Software Foundation.
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
8
* http://www.apache.org/licenses/LICENSE-2.0
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.
19
package org.apache.xml.utils;
22
* A very simple table that stores a list of objects.
24
* This version is based on a "realloc" strategy -- a simle array is
25
* used, and when more storage is needed, a larger array is obtained
26
* and all existing data is recopied into it. As a result, read/write
27
* access to existing nodes is O(1) fast but appending may be O(N**2)
31
public class ObjectVector implements Cloneable
34
/** Size of blocks to allocate */
35
protected int m_blocksize;
37
/** Array of objects */
38
protected Object m_map[];
40
/** Number of ints in array */
41
protected int m_firstFree = 0;
44
protected int m_mapSize;
47
* Default constructor. Note that the default
48
* block size is very small, for small lists.
54
m_mapSize = m_blocksize;
55
m_map = new Object[m_blocksize];
59
* Construct a IntVector, using the given block size.
61
* @param blocksize Size of block to allocate
63
public ObjectVector(int blocksize)
66
m_blocksize = blocksize;
67
m_mapSize = blocksize;
68
m_map = new Object[blocksize];
72
* Construct a IntVector, using the given block size.
74
* @param blocksize Size of block to allocate
76
public ObjectVector(int blocksize, int increaseSize)
79
m_blocksize = increaseSize;
80
m_mapSize = blocksize;
81
m_map = new Object[blocksize];
85
* Copy constructor for ObjectVector
87
* @param v Existing ObjectVector to copy
89
public ObjectVector(ObjectVector v)
91
m_map = new Object[v.m_mapSize];
92
m_mapSize = v.m_mapSize;
93
m_firstFree = v.m_firstFree;
94
m_blocksize = v.m_blocksize;
95
System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree);
99
* Get the length of the list.
101
* @return length of the list
103
public final int size()
109
* Get the length of the list.
111
* @return length of the list
113
public final void setSize(int sz)
120
* Append an object onto the vector.
122
* @param value Object to add to the list
124
public final void addElement(Object value)
127
if ((m_firstFree + 1) >= m_mapSize)
129
m_mapSize += m_blocksize;
131
Object newMap[] = new Object[m_mapSize];
133
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
138
m_map[m_firstFree] = value;
144
* Append several Object values onto the vector.
146
* @param value Object to add to the list
148
public final void addElements(Object value, int numberOfElements)
151
if ((m_firstFree + numberOfElements) >= m_mapSize)
153
m_mapSize += (m_blocksize+numberOfElements);
155
Object newMap[] = new Object[m_mapSize];
157
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
162
for (int i = 0; i < numberOfElements; i++)
164
m_map[m_firstFree] = value;
170
* Append several slots onto the vector, but do not set the values.
172
* @param numberOfElements number of slots to append
174
public final void addElements(int numberOfElements)
177
if ((m_firstFree + numberOfElements) >= m_mapSize)
179
m_mapSize += (m_blocksize+numberOfElements);
181
Object newMap[] = new Object[m_mapSize];
183
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
188
m_firstFree += numberOfElements;
193
* Inserts the specified object in this vector at the specified index.
194
* Each component in this vector with an index greater or equal to
195
* the specified index is shifted upward to have an index one greater
196
* than the value it had previously.
198
* @param value Object to insert
199
* @param at Index of where to insert
201
public final void insertElementAt(Object value, int at)
204
if ((m_firstFree + 1) >= m_mapSize)
206
m_mapSize += m_blocksize;
208
Object newMap[] = new Object[m_mapSize];
210
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
215
if (at <= (m_firstFree - 1))
217
System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
226
* Remove all elements objects from the list.
228
public final void removeAllElements()
231
for (int i = 0; i < m_firstFree; i++)
240
* Removes the first occurrence of the argument from this vector.
241
* If the object is found in this vector, each component in the vector
242
* with an index greater or equal to the object's index is shifted
243
* downward to have an index one smaller than the value it had
246
* @param s Object to remove from array
248
* @return True if the object was removed, false if it was not found
250
public final boolean removeElement(Object s)
253
for (int i = 0; i < m_firstFree; i++)
257
if ((i + 1) < m_firstFree)
258
System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
272
* Deletes the component at the specified index. Each component in
273
* this vector with an index greater or equal to the specified
274
* index is shifted downward to have an index one smaller than
275
* the value it had previously.
277
* @param i index of where to remove an object
279
public final void removeElementAt(int i)
283
System.arraycopy(m_map, i + 1, m_map, i, m_firstFree);
291
* Sets the component at the specified index of this vector to be the
292
* specified object. The previous component at that position is discarded.
294
* The index must be a value greater than or equal to 0 and less
295
* than the current size of the vector.
297
* @param value object to set
298
* @param index Index of where to set the object
300
public final void setElementAt(Object value, int index)
302
m_map[index] = value;
306
* Get the nth element.
308
* @param i index of object to get
310
* @return object at given index
312
public final Object elementAt(int i)
318
* Tell if the table contains the given Object.
320
* @param s object to look for
322
* @return true if the object is in the list
324
public final boolean contains(Object s)
327
for (int i = 0; i < m_firstFree; i++)
337
* Searches for the first occurence of the given argument,
338
* beginning the search at index, and testing for equality
339
* using the equals method.
341
* @param elem object to look for
342
* @param index Index of where to begin search
343
* @return the index of the first occurrence of the object
344
* argument in this vector at position index or later in the
345
* vector; returns -1 if the object is not found.
347
public final int indexOf(Object elem, int index)
350
for (int i = index; i < m_firstFree; i++)
352
if (m_map[i] == elem)
356
return java.lang.Integer.MIN_VALUE;
360
* Searches for the first occurence of the given argument,
361
* beginning the search at index, and testing for equality
362
* using the equals method.
364
* @param elem object to look for
365
* @return the index of the first occurrence of the object
366
* argument in this vector at position index or later in the
367
* vector; returns -1 if the object is not found.
369
public final int indexOf(Object elem)
372
for (int i = 0; i < m_firstFree; i++)
374
if (m_map[i] == elem)
378
return java.lang.Integer.MIN_VALUE;
382
* Searches for the first occurence of the given argument,
383
* beginning the search at index, and testing for equality
384
* using the equals method.
386
* @param elem Object to look for
387
* @return the index of the first occurrence of the object
388
* argument in this vector at position index or later in the
389
* vector; returns -1 if the object is not found.
391
public final int lastIndexOf(Object elem)
394
for (int i = (m_firstFree - 1); i >= 0; i--)
396
if (m_map[i] == elem)
400
return java.lang.Integer.MIN_VALUE;
404
* Reset the array to the supplied size.
408
public final void setToSize(int size) {
410
Object newMap[] = new Object[size];
412
System.arraycopy(m_map, 0, newMap, 0, m_firstFree);
420
* Returns clone of current ObjectVector
422
* @return clone of current ObjectVector
424
public Object clone()
425
throws CloneNotSupportedException
427
return new ObjectVector(this);
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
10
* http://www.apache.org/licenses/LICENSE-2.0
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.
21
package org.apache.xml.utils;
24
* A very simple table that stores a list of objects.
26
* This version is based on a "realloc" strategy -- a simle array is
27
* used, and when more storage is needed, a larger array is obtained
28
* and all existing data is recopied into it. As a result, read/write
29
* access to existing nodes is O(1) fast but appending may be O(N**2)
33
public class ObjectVector implements Cloneable
36
/** Size of blocks to allocate */
37
protected int m_blocksize;
39
/** Array of objects */
40
protected Object m_map[];
42
/** Number of ints in array */
43
protected int m_firstFree = 0;
46
protected int m_mapSize;
49
* Default constructor. Note that the default
50
* block size is very small, for small lists.
56
m_mapSize = m_blocksize;
57
m_map = new Object[m_blocksize];
61
* Construct a IntVector, using the given block size.
63
* @param blocksize Size of block to allocate
65
public ObjectVector(int blocksize)
68
m_blocksize = blocksize;
69
m_mapSize = blocksize;
70
m_map = new Object[blocksize];
74
* Construct a IntVector, using the given block size.
76
* @param blocksize Size of block to allocate
78
public ObjectVector(int blocksize, int increaseSize)
81
m_blocksize = increaseSize;
82
m_mapSize = blocksize;
83
m_map = new Object[blocksize];
87
* Copy constructor for ObjectVector
89
* @param v Existing ObjectVector to copy
91
public ObjectVector(ObjectVector v)
93
m_map = new Object[v.m_mapSize];
94
m_mapSize = v.m_mapSize;
95
m_firstFree = v.m_firstFree;
96
m_blocksize = v.m_blocksize;
97
System.arraycopy(v.m_map, 0, m_map, 0, m_firstFree);
101
* Get the length of the list.
103
* @return length of the list
105
public final int size()
111
* Get the length of the list.
113
* @return length of the list
115
public final void setSize(int sz)
122
* Append an object onto the vector.
124
* @param value Object to add to the list
126
public final void addElement(Object value)
129
if ((m_firstFree + 1) >= m_mapSize)
131
m_mapSize += m_blocksize;
133
Object newMap[] = new Object[m_mapSize];
135
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
140
m_map[m_firstFree] = value;
146
* Append several Object values onto the vector.
148
* @param value Object to add to the list
150
public final void addElements(Object value, int numberOfElements)
153
if ((m_firstFree + numberOfElements) >= m_mapSize)
155
m_mapSize += (m_blocksize+numberOfElements);
157
Object newMap[] = new Object[m_mapSize];
159
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
164
for (int i = 0; i < numberOfElements; i++)
166
m_map[m_firstFree] = value;
172
* Append several slots onto the vector, but do not set the values.
174
* @param numberOfElements number of slots to append
176
public final void addElements(int numberOfElements)
179
if ((m_firstFree + numberOfElements) >= m_mapSize)
181
m_mapSize += (m_blocksize+numberOfElements);
183
Object newMap[] = new Object[m_mapSize];
185
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
190
m_firstFree += numberOfElements;
195
* Inserts the specified object in this vector at the specified index.
196
* Each component in this vector with an index greater or equal to
197
* the specified index is shifted upward to have an index one greater
198
* than the value it had previously.
200
* @param value Object to insert
201
* @param at Index of where to insert
203
public final void insertElementAt(Object value, int at)
206
if ((m_firstFree + 1) >= m_mapSize)
208
m_mapSize += m_blocksize;
210
Object newMap[] = new Object[m_mapSize];
212
System.arraycopy(m_map, 0, newMap, 0, m_firstFree + 1);
217
if (at <= (m_firstFree - 1))
219
System.arraycopy(m_map, at, m_map, at + 1, m_firstFree - at);
228
* Remove all elements objects from the list.
230
public final void removeAllElements()
233
for (int i = 0; i < m_firstFree; i++)
242
* Removes the first occurrence of the argument from this vector.
243
* If the object is found in this vector, each component in the vector
244
* with an index greater or equal to the object's index is shifted
245
* downward to have an index one smaller than the value it had
248
* @param s Object to remove from array
250
* @return True if the object was removed, false if it was not found
252
public final boolean removeElement(Object s)
255
for (int i = 0; i < m_firstFree; i++)
259
if ((i + 1) < m_firstFree)
260
System.arraycopy(m_map, i + 1, m_map, i - 1, m_firstFree - i);
274
* Deletes the component at the specified index. Each component in
275
* this vector with an index greater or equal to the specified
276
* index is shifted downward to have an index one smaller than
277
* the value it had previously.
279
* @param i index of where to remove an object
281
public final void removeElementAt(int i)
285
System.arraycopy(m_map, i + 1, m_map, i, m_firstFree);
293
* Sets the component at the specified index of this vector to be the
294
* specified object. The previous component at that position is discarded.
296
* The index must be a value greater than or equal to 0 and less
297
* than the current size of the vector.
299
* @param value object to set
300
* @param index Index of where to set the object
302
public final void setElementAt(Object value, int index)
304
m_map[index] = value;
308
* Get the nth element.
310
* @param i index of object to get
312
* @return object at given index
314
public final Object elementAt(int i)
320
* Tell if the table contains the given Object.
322
* @param s object to look for
324
* @return true if the object is in the list
326
public final boolean contains(Object s)
329
for (int i = 0; i < m_firstFree; i++)
339
* Searches for the first occurence of the given argument,
340
* beginning the search at index, and testing for equality
341
* using the equals method.
343
* @param elem object to look for
344
* @param index Index of where to begin search
345
* @return the index of the first occurrence of the object
346
* argument in this vector at position index or later in the
347
* vector; returns -1 if the object is not found.
349
public final int indexOf(Object elem, int index)
352
for (int i = index; i < m_firstFree; i++)
354
if (m_map[i] == elem)
358
return java.lang.Integer.MIN_VALUE;
362
* Searches for the first occurence of the given argument,
363
* beginning the search at index, and testing for equality
364
* using the equals method.
366
* @param elem object to look for
367
* @return the index of the first occurrence of the object
368
* argument in this vector at position index or later in the
369
* vector; returns -1 if the object is not found.
371
public final int indexOf(Object elem)
374
for (int i = 0; i < m_firstFree; i++)
376
if (m_map[i] == elem)
380
return java.lang.Integer.MIN_VALUE;
384
* Searches for the first occurence of the given argument,
385
* beginning the search at index, and testing for equality
386
* using the equals method.
388
* @param elem Object to look for
389
* @return the index of the first occurrence of the object
390
* argument in this vector at position index or later in the
391
* vector; returns -1 if the object is not found.
393
public final int lastIndexOf(Object elem)
396
for (int i = (m_firstFree - 1); i >= 0; i--)
398
if (m_map[i] == elem)
402
return java.lang.Integer.MIN_VALUE;
406
* Reset the array to the supplied size.
410
public final void setToSize(int size) {
412
Object newMap[] = new Object[size];
414
System.arraycopy(m_map, 0, newMap, 0, m_firstFree);
422
* Returns clone of current ObjectVector
424
* @return clone of current ObjectVector
426
public Object clone()
427
throws CloneNotSupportedException
429
return new ObjectVector(this);
added
removed
src/org/apache/xml/utils/ObjectVector.java
