001: /*
002: * This program is free software; you can redistribute it and/or modify
003: * it under the terms of the GNU General Public License as published by
004: * the Free Software Foundation; either version 2 of the License, or
005: * (at your option) any later version.
006: *
007: * This program is distributed in the hope that it will be useful,
008: * but WITHOUT ANY WARRANTY; without even the implied warranty of
009: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
010: * GNU General Public License for more details.
011: *
012: * You should have received a copy of the GNU General Public License
013: * along with this program; if not, write to the Free Software
014: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
015: */
016:
017: /*
018: * FastVector.java
019: * Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
020: *
021: */
022:
023: package weka.core;
024:
025: import java.io.Serializable;
026: import java.util.Enumeration;
027:
028: /**
029: * Implements a fast vector class without synchronized
030: * methods. Replaces java.util.Vector. (Synchronized methods tend to
031: * be slow.)
032: *
033: * @author Eibe Frank (eibe@cs.waikato.ac.nz)
034: * @version $Revision: 1.14 $
035: */
036: public class FastVector implements Copyable, Serializable {
037:
038: /** for serialization */
039: private static final long serialVersionUID = -2173635135622930169L;
040:
041: /**
042: * Class for enumerating the vector's elements.
043: */
044: public class FastVectorEnumeration implements Enumeration {
045:
046: /** The counter. */
047: private int m_Counter;
048: // These JML commands say how m_Counter implements Enumeration
049: //@ in moreElements;
050: //@ private represents moreElements = m_Counter < m_Vector.size();
051: //@ private invariant 0 <= m_Counter && m_Counter <= m_Vector.size();
052:
053: /** The vector. */
054: private/*@non_null@*/FastVector m_Vector;
055:
056: /** Special element. Skipped during enumeration. */
057: private int m_SpecialElement;
058:
059: //@ private invariant -1 <= m_SpecialElement;
060: //@ private invariant m_SpecialElement < m_Vector.size();
061: //@ private invariant m_SpecialElement>=0 ==> m_Counter!=m_SpecialElement;
062:
063: /**
064: * Constructs an enumeration.
065: *
066: * @param vector the vector which is to be enumerated
067: */
068: public FastVectorEnumeration(/*@non_null@*/FastVector vector) {
069:
070: m_Counter = 0;
071: m_Vector = vector;
072: m_SpecialElement = -1;
073: }
074:
075: /**
076: * Constructs an enumeration with a special element.
077: * The special element is skipped during the enumeration.
078: *
079: * @param vector the vector which is to be enumerated
080: * @param special the index of the special element
081: */
082: //@ requires 0 <= special && special < vector.size();
083: public FastVectorEnumeration(/*@non_null@*/FastVector vector,
084: int special) {
085:
086: m_Vector = vector;
087: m_SpecialElement = special;
088: if (special == 0) {
089: m_Counter = 1;
090: } else {
091: m_Counter = 0;
092: }
093: }
094:
095: /**
096: * Tests if there are any more elements to enumerate.
097: *
098: * @return true if there are some elements left
099: */
100: public final/*@pure@*/boolean hasMoreElements() {
101:
102: if (m_Counter < m_Vector.size()) {
103: return true;
104: }
105: return false;
106: }
107:
108: /**
109: * Returns the next element.
110: *
111: * @return the next element to be enumerated
112: */
113: //@ also requires hasMoreElements();
114: public final Object nextElement() {
115:
116: Object result = m_Vector.elementAt(m_Counter);
117:
118: m_Counter++;
119: if (m_Counter == m_SpecialElement) {
120: m_Counter++;
121: }
122: return result;
123: }
124: }
125:
126: /** The array of objects. */
127: private/*@spec_public@*/Object[] m_Objects;
128: //@ invariant m_Objects != null;
129: //@ invariant m_Objects.length >= 0;
130:
131: /** The current size; */
132: private/*@spec_public@*/int m_Size = 0;
133: //@ invariant 0 <= m_Size;
134: //@ invariant m_Size <= m_Objects.length;
135:
136: /** The capacity increment */
137: private/*@spec_public@*/int m_CapacityIncrement = 1;
138: //@ invariant 1 <= m_CapacityIncrement;
139:
140: /** The capacity multiplier. */
141: private/*@spec_public@*/int m_CapacityMultiplier = 2;
142:
143: //@ invariant 1 <= m_CapacityMultiplier;
144:
145: // Make sure the size will increase...
146: //@ invariant 3 <= m_CapacityMultiplier + m_CapacityIncrement;
147:
148: /**
149: * Constructs an empty vector with initial
150: * capacity zero.
151: */
152: public FastVector() {
153:
154: m_Objects = new Object[0];
155: }
156:
157: /**
158: * Constructs a vector with the given capacity.
159: *
160: * @param capacity the vector's initial capacity
161: */
162: //@ requires capacity >= 0;
163: public FastVector(int capacity) {
164:
165: m_Objects = new Object[capacity];
166: }
167:
168: /**
169: * Adds an element to this vector. Increases its
170: * capacity if its not large enough.
171: *
172: * @param element the element to add
173: */
174: public final void addElement(Object element) {
175:
176: Object[] newObjects;
177:
178: if (m_Size == m_Objects.length) {
179: newObjects = new Object[m_CapacityMultiplier
180: * (m_Objects.length + m_CapacityIncrement)];
181: System.arraycopy(m_Objects, 0, newObjects, 0, m_Size);
182: m_Objects = newObjects;
183: }
184: m_Objects[m_Size] = element;
185: m_Size++;
186: }
187:
188: /**
189: * Returns the capacity of the vector.
190: *
191: * @return the capacity of the vector
192: */
193: //@ ensures \result == m_Objects.length;
194: public final/*@pure@*/int capacity() {
195:
196: return m_Objects.length;
197: }
198:
199: /**
200: * Produces a shallow copy of this vector.
201: *
202: * @return the new vector
203: */
204: public final Object copy() {
205:
206: FastVector copy = new FastVector(m_Objects.length);
207:
208: copy.m_Size = m_Size;
209: copy.m_CapacityIncrement = m_CapacityIncrement;
210: copy.m_CapacityMultiplier = m_CapacityMultiplier;
211: System.arraycopy(m_Objects, 0, copy.m_Objects, 0, m_Size);
212: return copy;
213: }
214:
215: /**
216: * Clones the vector and shallow copies all its elements.
217: * The elements have to implement the Copyable interface.
218: *
219: * @return the new vector
220: */
221: public final Object copyElements() {
222:
223: FastVector copy = new FastVector(m_Objects.length);
224:
225: copy.m_Size = m_Size;
226: copy.m_CapacityIncrement = m_CapacityIncrement;
227: copy.m_CapacityMultiplier = m_CapacityMultiplier;
228: for (int i = 0; i < m_Size; i++) {
229: copy.m_Objects[i] = ((Copyable) m_Objects[i]).copy();
230: }
231: return copy;
232: }
233:
234: /**
235: * Returns the element at the given position.
236: *
237: * @param index the element's index
238: * @return the element with the given index
239: */
240: //@ requires 0 <= index;
241: //@ requires index < m_Objects.length;
242: public final/*@pure@*/Object elementAt(int index) {
243:
244: return m_Objects[index];
245: }
246:
247: /**
248: * Returns an enumeration of this vector.
249: *
250: * @return an enumeration of this vector
251: */
252: public final/*@pure@*/Enumeration elements() {
253:
254: return new FastVectorEnumeration(this );
255: }
256:
257: /**
258: * Returns an enumeration of this vector, skipping the
259: * element with the given index.
260: *
261: * @param index the element to skip
262: * @return an enumeration of this vector
263: */
264: //@ requires 0 <= index && index < size();
265: public final/*@pure@*/Enumeration elements(int index) {
266:
267: return new FastVectorEnumeration(this , index);
268: }
269:
270: /**
271: * added by akibriya
272: */
273: public/*@pure@*/boolean contains(Object o) {
274: if (o == null)
275: return false;
276:
277: for (int i = 0; i < m_Objects.length; i++)
278: if (o.equals(m_Objects[i]))
279: return true;
280:
281: return false;
282: }
283:
284: /**
285: * Returns the first element of the vector.
286: *
287: * @return the first element of the vector
288: */
289: //@ requires m_Size > 0;
290: public final/*@pure@*/Object firstElement() {
291:
292: return m_Objects[0];
293: }
294:
295: /**
296: * Searches for the first occurence of the given argument,
297: * testing for equality using the equals method.
298: *
299: * @param element the element to be found
300: * @return the index of the first occurrence of the argument
301: * in this vector; returns -1 if the object is not found
302: */
303: public final/*@pure@*/int indexOf(/*@non_null@*/Object element) {
304:
305: for (int i = 0; i < m_Size; i++) {
306: if (element.equals(m_Objects[i])) {
307: return i;
308: }
309: }
310: return -1;
311: }
312:
313: /**
314: * Inserts an element at the given position.
315: *
316: * @param element the element to be inserted
317: * @param index the element's index
318: */
319: public final void insertElementAt(Object element, int index) {
320:
321: Object[] newObjects;
322:
323: if (m_Size < m_Objects.length) {
324: System.arraycopy(m_Objects, index, m_Objects, index + 1,
325: m_Size - index);
326: m_Objects[index] = element;
327: } else {
328: newObjects = new Object[m_CapacityMultiplier
329: * (m_Objects.length + m_CapacityIncrement)];
330: System.arraycopy(m_Objects, 0, newObjects, 0, index);
331: newObjects[index] = element;
332: System.arraycopy(m_Objects, index, newObjects, index + 1,
333: m_Size - index);
334: m_Objects = newObjects;
335: }
336: m_Size++;
337: }
338:
339: /**
340: * Returns the last element of the vector.
341: *
342: * @return the last element of the vector
343: */
344: //@ requires m_Size > 0;
345: public final/*@pure@*/Object lastElement() {
346:
347: return m_Objects[m_Size - 1];
348: }
349:
350: /**
351: * Deletes an element from this vector.
352: *
353: * @param index the index of the element to be deleted
354: */
355: //@ requires 0 <= index && index < m_Size;
356: public final void removeElementAt(int index) {
357:
358: System.arraycopy(m_Objects, index + 1, m_Objects, index, m_Size
359: - index - 1);
360: m_Size--;
361: }
362:
363: /**
364: * Removes all components from this vector and sets its
365: * size to zero.
366: */
367: public final void removeAllElements() {
368:
369: m_Objects = new Object[m_Objects.length];
370: m_Size = 0;
371: }
372:
373: /**
374: * Appends all elements of the supplied vector to this vector.
375: *
376: * @param toAppend the FastVector containing elements to append.
377: */
378: public final void appendElements(FastVector toAppend) {
379:
380: setCapacity(size() + toAppend.size());
381: System.arraycopy(toAppend.m_Objects, 0, m_Objects, size(),
382: toAppend.size());
383: m_Size = m_Objects.length;
384: }
385:
386: /**
387: * Returns all the elements of this vector as an array
388: *
389: * @return an array containing all the elements of this vector
390: */
391: public final Object[] toArray() {
392:
393: Object[] newObjects = new Object[size()];
394: System.arraycopy(m_Objects, 0, newObjects, 0, size());
395: return newObjects;
396: }
397:
398: /**
399: * Sets the vector's capacity to the given value.
400: *
401: * @param capacity the new capacity
402: */
403: public final void setCapacity(int capacity) {
404:
405: Object[] newObjects = new Object[capacity];
406:
407: System.arraycopy(m_Objects, 0, newObjects, 0, Math.min(
408: capacity, m_Size));
409: m_Objects = newObjects;
410: if (m_Objects.length < m_Size)
411: m_Size = m_Objects.length;
412: }
413:
414: /**
415: * Sets the element at the given index.
416: *
417: * @param element the element to be put into the vector
418: * @param index the index at which the element is to be placed
419: */
420: //@ requires 0 <= index && index < size();
421: public final void setElementAt(Object element, int index) {
422:
423: m_Objects[index] = element;
424: }
425:
426: /**
427: * Returns the vector's current size.
428: *
429: * @return the vector's current size
430: */
431: //@ ensures \result == m_Size;
432: public final/*@pure@*/int size() {
433:
434: return m_Size;
435: }
436:
437: /**
438: * Swaps two elements in the vector.
439: *
440: * @param first index of the first element
441: * @param second index of the second element
442: */
443: //@ requires 0 <= first && first < size();
444: //@ requires 0 <= second && second < size();
445: public final void swap(int first, int second) {
446:
447: Object help = m_Objects[first];
448:
449: m_Objects[first] = m_Objects[second];
450: m_Objects[second] = help;
451: }
452:
453: /**
454: * Sets the vector's capacity to its size.
455: */
456: public final void trimToSize() {
457:
458: Object[] newObjects = new Object[m_Size];
459:
460: System.arraycopy(m_Objects, 0, newObjects, 0, m_Size);
461: m_Objects = newObjects;
462: }
463: }
|