IntegerVector


1   /**
2    * com.mckoi.util.IntegerVector  10 Mar 1998
3    *
4    * Mckoi SQL Database ( http://www.mckoi.com/database )
5    * Copyright (C) 2000, 2001, 2002  Diehl and Associates, Inc.
6    *
7    * This program is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * Version 2 as published by the Free Software Foundation.
10   *
11   * This program is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License Version 2 for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * Version 2 along with this program; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19   *
20   * Change Log:
21   * 
22   * 
23   */
24  
25  package com.mckoi.util;
26  
27  /**
28   * Similar to the Vector class, except this can only store integer values.
29   * <p>
30   * @author Tobias Downer
31   */
32  
33  public final class IntegerVector implements java.io.Serializable   {
34  
35    /**
36     * The int array.
37     */
38    protected int[] list;
39  
40    /**
41     * The index of the last value of the array.
42     */
43    protected int index;
44  
45    /**
46     * The Constructors.
47     */
48    public IntegerVector() {
49      this(32);
50    }
51  
52    public IntegerVector(int initial_list_size) {
53      index = 0;
54      list = new int[initial_list_size];
55    }
56  
57    public IntegerVector(IntegerVector vec) {
58      if (vec != null && vec.list != null) {
59        list = new int[vec.list.length];
60        index = vec.index;
61        System.arraycopy(vec.list, 0, list, 0, index);
62      }
63      else {
64        index = 0;
65        list = new int[0];
66      }
67    }
68  
69    public IntegerVector(IntegerListInterface i_list) {
70      this(i_list.size());
71      if (i_list instanceof AbstractBlockIntegerList) {
72        AbstractBlockIntegerList bilist = (AbstractBlockIntegerList) i_list;
73        int bill_size = bilist.size();
74        bilist.copyToArray(list, 0, bill_size);
75        index = bill_size;
76      }
77      else {
78        IntegerIterator i = i_list.iterator();
79        // NOTE: We are guarenteed the size of the 'list' array matches the size
80        //   of input list.
81        while (i.hasNext()) {
82          list[index] = i.next();
83          ++index;
84        }
85      }
86    }
87  
88  
89    /**
90     * Ensures there's enough room to make a single addition to the list.
91     */
92    private void ensureCapacityForAddition() {
93      if (index >= list.length) {
94        int[] old_arr = list;
95  
96        int grow_size = old_arr.length + 1;
97        // Put a cap on the new size.
98        if (grow_size > 35000) {
99          grow_size = 35000;
100       }
101 
102       int new_size = old_arr.length + grow_size;
103       list = new int[new_size];
104       System.arraycopy(old_arr, 0, list, 0, index);
105     }
106   }
107 
108   /**
109    * Ensures there's enough room to make 'n' additions to the list.
110    */
111   private void ensureCapacityForAdditions(int n) {
112     int intended_size = index + n;
113     if (intended_size > list.length) {
114       int[] old_arr = list;
115 
116       int grow_size = old_arr.length + 1;
117       // Put a cap on the new size.
118       if (grow_size > 35000) {
119         grow_size = 35000;
120       }
121 
122       int new_size = Math.max(old_arr.length + grow_size, intended_size);
123       list = new int[new_size];
124       System.arraycopy(old_arr, 0, list, 0, index);
125     }
126   }
127 
128   /**
129    * Adds an int to the vector.
130    */
131   public void addInt(int val) {
132 //    if (list == null) {
133 //      list = new int[64];
134 //    }
135 
136     ensureCapacityForAddition();
137 
138     list[index] = val;
139     ++index;
140   }
141 
142   /**
143    * Removes an Int from the specified position in the list.
144    */
145   public void removeIntAt(int pos) {
146     --index;
147     System.arraycopy(list, pos + 1, list, pos, (index - pos));
148   }
149 
150   /**
151    * Removes the first Int found that matched the specified value.
152    */
153   public void removeInt(int val) {
154     int pos = indexOf(val);
155     if (pos == -1) {
156       throw new RuntimeException  ("Tried to remove none existant int.");
157     }
158     removeIntAt(pos);
159   }
160 
161   /**
162    * Crops the IntegerVector so it only contains values between start
163    * (inclusive) and end (exclusive).  So;
164    *   crop({ 4, 5, 4, 3, 9, 7 }, 0, 3)
165    *   would return {4, 5, 4)
166    * and,
167    *   crop({ 4, 5, 4, 3, 9, 7 }, 3, 4)
168    *   would return {3}
169    */
170   public void crop(int start, int end) {
171     if (start < 0) {
172       throw new Error  ("Crop start < 0.");
173     }
174     else if (start == 0) {
175       if (end > index) {
176         throw new Error  ("Crop end was past end.");
177       }
178       index = end;
179     }
180     else {
181       if (start >= index) {
182         throw new Error  ("start >= index");
183       }
184       int length = (end - start);
185       if (length < 0) {
186         throw new Error  ("end - start < 0");
187       }
188       System.arraycopy(list, start, list, 0, length);
189       index = length;
190     }
191   }
192 
193 
194   /**
195    * Inserts an int at the given position.
196    */
197   public void insertIntAt(int val, int pos) {
198     if (pos >= index) {
199       throw new ArrayIndexOutOfBoundsException  (pos + " >= " + index);
200     }
201 
202 //    if (list == null) {
203 //      list = new int[64];
204 //    }
205 
206     ensureCapacityForAddition();
207     System.arraycopy(list, pos, list, pos + 1, (index - pos));
208     ++index;
209     list[pos] = val;
210   }
211 
212   /**
213    * Sets an int at the given position, overwriting anything that was
214    * previously there.  It returns the value that was previously at the element.
215    */
216   public int setIntAt(int val, int pos) {
217     if (pos >= index) {
218       throw new ArrayIndexOutOfBoundsException  (pos + " >= " + index);
219     }
220 
221     int old = list[pos];
222     list[pos] = val;
223     return old;
224   }
225 
226   /**
227    * Places an int at the given position, overwriting anything that was
228    * previously there.  It returns the value that was previously at the
229    * element.  If 'pos' points to a place outside the bounds of the list then
230    * the list is expanded to include this value.
231    */
232   public int placeIntAt(int val, int pos) {
233     int llength = list.length;
234     if (pos >= list.length) {
235       ensureCapacityForAdditions((llength - index) + (pos - llength) + 5);
236     }
237 
238     if (pos >= index) {
239       index = pos + 1;
240     }
241 
242     int old = list[pos];
243     list[pos] = val;
244     return old;
245   }
246 
247 
248   /**
249    * Appends an IntegerVector to the end of the array.  Returns this object.
250    */
251   public IntegerVector append(IntegerVector vec) {
252     if (vec != null) {
253       int size = vec.size();
254       // Make sure there's enough room for the new array
255       ensureCapacityForAdditions(size);
256 
257       // Copy the list into this vector.
258       System.arraycopy(vec.list, 0, list, index, size);
259       index += size;
260 
261 //      int size = vec.size();
262 //      for (int i = 0; i < size; ++i) {
263 //        addInt(vec.intAt(i));
264 //      }
265     }
266     return this;
267   }
268 
269   /**
270    * Returns the Int at the given position.
271    */
272   public int intAt(int pos) {
273     if (pos >= index) {
274       throw new ArrayIndexOutOfBoundsException  (pos + " >= " + index);
275     }
276 
277     return list[pos];
278   }
279 
280   /**
281    * Returns the first index of the given row in the array, or -1 if not
282    * found.
283    */
284   public int indexOf(int val) {
285     for (int i = 0; i < index; ++i) {
286       if (list[i] == val) {
287         return i;
288       }
289     }
290     return -1;
291   }
292 
293   /**
294    * Returns true if the vector contains the given value.
295    */
296   public boolean contains(int val) {
297     return (indexOf(val) != -1);
298   }
299 
300   /**
301    * Returns the size of the vector.
302    */
303   public int getSize() {
304     return index;
305   }
306 
307   /**
308    * Returns the size of the vector.
309    */
310   public int size() {
311     return index;
312   }
313 
314   /**
315    * Converts the vector into an int[] array.
316    */
317   public int[] toIntArray() {
318     if (getSize() != 0) {
319       int[] out_list = new int[getSize()];
320       System.arraycopy(list, 0, out_list, 0, getSize());
321       return out_list;
322     }
323     return null;
324   }
325 
326   /**
327    * Clears the object to be re-used.
328    */
329   public void clear() {
330     index = 0;
331   }
332 
333   /**
334    * Converts the vector into a String.
335    */
336   public String   toString() {
337     StringBuffer   buf = new StringBuffer  ();
338     for (int i = 0; i < index; ++i) {
339       buf.append(list[i]);
340       buf.append(", ");
341     }
342     return new String  (buf);
343   }
344 
345   /**
346    * Returns true if this vector is equal to the given vector.
347    */
348   public boolean equals(IntegerVector ivec) {
349     int dest_index = ivec.index;
350     if (index != dest_index) {
351       return false;
352     }
353     for (int i = 0; i < index; ++i) {
354       if (list[i] != ivec.list[i]) {
355         return false;
356       }
357     }
358     return true;
359   }
360 
361   /**
362    * Reverses all the list of integers.  So integer[0] is swapped with
363    * integer[n - 1], integer[1] is swapped with integer[n - 2], etc where
364    * n is the size of the vector.
365    */
366   public void reverse() {
367     final int upper = index - 1;
368     final int bounds = index / 2;
369     int end_index, temp;
370 
371     // Swap ends and interate the two end pointers inwards.
372     // i         = lower end
373     // upper - i = upper end
374 
375     for (int i = 0; i < bounds; ++i) {
376       end_index = upper - i;
377 
378       temp = list[i];
379       list[i] = list[end_index];
380       list[end_index] = temp;
381     }
382   }
383 
384 
385 
386 
387   /**
388    * These methods are algorithms that can be used on the array, such as
389    * sorting and searching.
390    */
391 
392   /**
393    * Performs a quick sort on the array between the min and max bounds.
394    */
395   public final void quickSort(int min, int max) {
396     int left = min;
397     int right = max;
398 
399     if (max > min) {
400       int mid = list[(min + max) / 2];
401       while (left < right) {
402         while (left < max && list[left] < mid) {
403           ++left;
404         }
405         while (right > min && list[right] > mid) {
406           --right;
407         }
408         if (left <= right) {
409           if (left != right) {
410             int t = list[left];
411             list[left] = list[right];
412             list[right] = t;
413           }
414 
415           ++left;
416           --right;
417         }
418 
419       }
420 
421       if (min < right) {
422         quickSort(min, right);
423       }
424       if (left < max) {
425         quickSort(left, max);
426       }
427 
428     }
429   }
430 
431   /**
432    * Performs a quick sort on the entire vector.
433    */
434   public final void quickSort() {
435     quickSort(0, index - 1);
436   }
437 
438   /**
439    * This is a very quick search for a value given a sorted array.  The search
440    * is performed between the lower and higher bounds of the array.  If the
441    * requested value is not found, it returns the index where the value should
442    * be 'inserted' to maintain a sorted list.
443    */
444   public final int sortedIndexOf(int val, int lower, int higher) {
445 
446     if (lower >= higher) {
447       if (lower < index && val > list[lower]) {
448         return lower + 1;
449       }
450       else {
451         return lower;
452       }
453     }
454 
455     int mid = (lower + higher) / 2;
456     int mid_val = list[mid];
457 
458     if (val == mid_val) {
459       return mid;
460     }
461     else if (val < mid_val) {
462       return sortedIndexOf(val, lower, mid - 1);
463     }
464     else {
465       return sortedIndexOf(val, mid + 1, higher);
466     }
467 
468   }
469 
470   /**
471    * Searches the entire sorted list for the given value and returns the index
472    * of it.  If the value is not found, it returns the place in the list where
473    * the value should be insorted to maintain a sorted list.
474    */
475   public final int sortedIndexOf(int val) {
476     return sortedIndexOf(val, 0, index - 1);
477   }
478 
479   /**
480    * Given a sorted list, this will return the count of this value in the
481    * list.  This uses a quick search algorithm so should be quite fast.
482    */
483   public final int sortedIntCount(int val) {
484     if (index == 0) {
485       return 0;
486     }
487 
488     int count = 0;
489     int size = index - 1;
490 
491     int i = sortedIndexOf(val, 0, size);
492     if (i > size) {
493       return 0;
494     }
495     int temp_i = i;
496 
497     while (temp_i >= 0 && list[temp_i] == val) {
498       ++count;
499       --temp_i;
500     }
501     temp_i = i + 1;
502     while (temp_i <= size && list[temp_i] == val) {
503       ++count;
504       ++temp_i;
505     }
506 
507     return count;
508 
509   }
510 
511 
512 
513   /**
514    * Test routine to check vector is sorted.
515    */
516   public boolean isSorted() {
517     int cur = Integer.MIN_VALUE; //-1000000;
518     for (int i = 0; i < index; ++i) {
519       int a = list[i];
520       if (a >= cur) {
521         cur = a;
522       }
523       else {
524         return false;
525       }
526     }
527     return true;
528   }
529 
530 }
531
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags