← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/core/FastVector.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/core/FastVector.java
 
1
/*
 
2
 *    This program is free software; you can redistribute it and/or modify
 
3
 *    it under the terms of the GNU General Public License as published by
 
4
 *    the Free Software Foundation; either version 2 of the License, or
 
5
 *    (at your option) any later version.
 
6
 *
 
7
 *    This program is distributed in the hope that it will be useful,
 
8
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 *    GNU General Public License for more details.
 
11
 *
 
12
 *    You should have received a copy of the GNU General Public License
 
13
 *    along with this program; if not, write to the Free Software
 
14
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 *    FastVector.java
 
19
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 
20
 *
 
21
 */
 
22
 
 
23
package weka.core;
 
24
 
 
25
import java.io.Serializable;
 
26
import java.util.Enumeration;
 
27
 
 
28
/**
 
29
 * Implements a fast vector class without synchronized
 
30
 * methods. Replaces java.util.Vector. (Synchronized methods tend to
 
31
 * be slow.)
 
32
 *
 
33
 * @author Eibe Frank (eibe@cs.waikato.ac.nz)
 
34
 * @version $Revision: 1.14 $
 
35
 */
 
36
public class FastVector
 
37
  implements Copyable, Serializable {
 
38
 
 
39
  /** for serialization */
 
40
  private static final long serialVersionUID = -2173635135622930169L;
 
41
 
 
42
  /**
 
43
   * Class for enumerating the vector's elements.
 
44
   */
 
45
  public class FastVectorEnumeration implements Enumeration {
 
46
 
 
47
    /** The counter. */
 
48
    private int m_Counter;
 
49
    // These JML commands say how m_Counter implements Enumeration
 
50
    //@ in moreElements;
 
51
    //@ private represents moreElements = m_Counter < m_Vector.size();
 
52
    //@ private invariant 0 <= m_Counter && m_Counter <= m_Vector.size();
 
53
 
 
54
    /** The vector. */
 
55
    private /*@non_null@*/ FastVector m_Vector;
 
56
 
 
57
    /** Special element. Skipped during enumeration. */
 
58
    private int m_SpecialElement;
 
59
    //@ private invariant -1 <= m_SpecialElement;
 
60
    //@ private invariant m_SpecialElement < m_Vector.size();
 
61
    //@ private invariant m_SpecialElement>=0 ==> m_Counter!=m_SpecialElement;
 
62
 
 
63
    /**
 
64
     * Constructs an enumeration.
 
65
     *
 
66
     * @param vector the vector which is to be enumerated
 
67
     */
 
68
    public FastVectorEnumeration(/*@non_null@*/FastVector vector) {
 
69
 
 
70
      m_Counter = 0;
 
71
      m_Vector = vector;
 
72
      m_SpecialElement = -1;
 
73
    }
 
74
 
 
75
    /**
 
76
     * Constructs an enumeration with a special element.
 
77
     * The special element is skipped during the enumeration.
 
78
     *
 
79
     * @param vector the vector which is to be enumerated
 
80
     * @param special the index of the special element
 
81
     */
 
82
    //@ requires 0 <= special && special < vector.size();
 
83
    public FastVectorEnumeration(/*@non_null@*/FastVector vector, int special){
 
84
 
 
85
      m_Vector = vector;
 
86
      m_SpecialElement = special;
 
87
      if (special == 0) {
 
88
        m_Counter = 1;
 
89
      } else {
 
90
        m_Counter = 0;
 
91
      }
 
92
    }
 
93
 
 
94
 
 
95
    /**
 
96
     * Tests if there are any more elements to enumerate.
 
97
     *
 
98
     * @return true if there are some elements left
 
99
     */
 
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
  //@ invariant 1 <= m_CapacityMultiplier;
 
143
 
 
144
  // Make sure the size will increase...
 
145
  //@ invariant 3 <= m_CapacityMultiplier + m_CapacityIncrement;
 
146
 
 
147
  /**
 
148
   * Constructs an empty vector with initial
 
149
   * capacity zero.
 
150
   */
 
151
  public FastVector() {
 
152
  
 
153
    m_Objects = new Object[0];
 
154
  }
 
155
 
 
156
  /**
 
157
   * Constructs a vector with the given capacity.
 
158
   *
 
159
   * @param capacity the vector's initial capacity
 
160
   */
 
161
  //@ requires capacity >= 0;
 
162
  public FastVector(int capacity) {
 
163
 
 
164
    m_Objects = new Object[capacity];
 
165
  }
 
166
 
 
167
  /**
 
168
   * Adds an element to this vector. Increases its
 
169
   * capacity if its not large enough.
 
170
   *
 
171
   * @param element the element to add
 
172
   */
 
173
  public final void addElement(Object element) {
 
174
 
 
175
    Object[] newObjects;
 
176
 
 
177
    if (m_Size == m_Objects.length) {
 
178
      newObjects = new Object[m_CapacityMultiplier *
 
179
                             (m_Objects.length +
 
180
                              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
  /**
 
286
   * Returns the first element of the vector.
 
287
   *
 
288
   * @return the first element of the vector
 
289
   */
 
290
  //@ requires m_Size > 0;
 
291
  public final /*@pure@*/ Object firstElement() {
 
292
 
 
293
    return m_Objects[0];
 
294
  }
 
295
 
 
296
  /**
 
297
   * Searches for the first occurence of the given argument, 
 
298
   * testing for equality using the equals method. 
 
299
   *
 
300
   * @param element the element to be found
 
301
   * @return the index of the first occurrence of the argument 
 
302
   * in this vector; returns -1 if the object is not found
 
303
   */
 
304
  public final /*@pure@*/ int indexOf(/*@non_null@*/ Object element) {
 
305
 
 
306
    for (int i = 0; i < m_Size; i++) {
 
307
      if (element.equals(m_Objects[i])) {
 
308
        return i;
 
309
      }
 
310
    }
 
311
    return -1;
 
312
  }
 
313
 
 
314
  /**
 
315
   * Inserts an element at the given position.
 
316
   *
 
317
   * @param element the element to be inserted
 
318
   * @param index the element's index
 
319
   */
 
320
  public final void insertElementAt(Object element, int index) {
 
321
 
 
322
    Object[] newObjects;
 
323
 
 
324
    if (m_Size < m_Objects.length) {
 
325
      System.arraycopy(m_Objects, index, m_Objects, index + 1, 
 
326
                       m_Size - index);
 
327
      m_Objects[index] = element;
 
328
    } else {
 
329
      newObjects = new Object[m_CapacityMultiplier *
 
330
                             (m_Objects.length +
 
331
                              m_CapacityIncrement)];
 
332
      System.arraycopy(m_Objects, 0, newObjects, 0, index);
 
333
      newObjects[index] = element;
 
334
      System.arraycopy(m_Objects, index, newObjects, index + 1,
 
335
                       m_Size - index);
 
336
      m_Objects = newObjects;
 
337
    }
 
338
    m_Size++;
 
339
  }
 
340
 
 
341
  /**
 
342
   * Returns the last element of the vector.
 
343
   *
 
344
   * @return the last element of the vector
 
345
   */
 
346
  //@ requires m_Size > 0;
 
347
  public final /*@pure@*/ Object lastElement() {
 
348
 
 
349
    return m_Objects[m_Size - 1];
 
350
  }
 
351
 
 
352
  /**
 
353
   * Deletes an element from this vector.
 
354
   *
 
355
   * @param index the index of the element to be deleted
 
356
   */
 
357
  //@ requires 0 <= index && index < m_Size;
 
358
  public final void removeElementAt(int index) {
 
359
 
 
360
    System.arraycopy(m_Objects, index + 1, m_Objects, index, 
 
361
                     m_Size - index - 1);
 
362
    m_Size--;
 
363
  }
 
364
 
 
365
  /**
 
366
   * Removes all components from this vector and sets its 
 
367
   * size to zero. 
 
368
   */
 
369
  public final void removeAllElements() {
 
370
 
 
371
    m_Objects = new Object[m_Objects.length];
 
372
    m_Size = 0;
 
373
  }
 
374
 
 
375
  /**
 
376
   * Appends all elements of the supplied vector to this vector.
 
377
   *
 
378
   * @param toAppend the FastVector containing elements to append.
 
379
   */
 
380
  public final void appendElements(FastVector toAppend) {
 
381
 
 
382
    setCapacity(size() + toAppend.size());
 
383
    System.arraycopy(toAppend.m_Objects, 0, m_Objects, size(), toAppend.size());
 
384
    m_Size = m_Objects.length;
 
385
  }
 
386
 
 
387
  /** 
 
388
   * Returns all the elements of this vector as an array
 
389
   *
 
390
   * @return an array containing all the elements of this vector
 
391
   */
 
392
  public final Object [] toArray() {
 
393
 
 
394
    Object [] newObjects = new Object[size()];
 
395
    System.arraycopy(m_Objects, 0, newObjects, 0, size());
 
396
    return newObjects;
 
397
  }
 
398
 
 
399
  /**
 
400
   * Sets the vector's capacity to the given value.
 
401
   *
 
402
   * @param capacity the new capacity
 
403
   */
 
404
  public final void setCapacity(int capacity) {
 
405
 
 
406
    Object[] newObjects = new Object[capacity];
 
407
   
 
408
    System.arraycopy(m_Objects, 0, newObjects, 0, Math.min(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
}
 
464