src/org/ibex/util/Vec.java

   1 // Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
   2 //
   3 // You may modify, copy, and redistribute this code under the terms of
   4 // the GNU Library Public License version 2.1, with the exception of
   5 // the portion of clause 6a after the semicolon (aka the "obnoxious
   6 // relink clause")
   7
   8 package org.ibex.util;
   9 import java.io.*;
  10
  11 /**
  12  *  An unsynchronized Vector implementation; same semantics as
  13  *  java.util.Vector. Useful for JDK1.1 platforms that don't have
  14  *  java.util.ArrayList.
  15  *
  16  *  May contain nulls.
  17  *
  18  *  @see java.util.Vector
  19  */
  20 public final class Vec implements Serializable {
  21
  22     private Object[] store;
  23     private int size = 0;
  24
  25     public Vec() { this(10); }
  26     public Vec(int i) { store = new Object[i]; }
  27     public Vec(int i, Object[] store) { size = i; this.store = store; }
  28
  29     private void grow() { grow(store.length * 2); }
  30     private void grow(int newsize) {
  31         Object[] newstore = new Object[newsize];
  32         System.arraycopy(store, 0, newstore, 0, size);
  33         store = newstore;
  34     }
  35
  36     public void removeAllElements() {
  37         for(int i=0; i<size; i++) store[i] = null;
  38         size = 0;
  39     }
  40
  41     public void toArray(Object[] o) {
  42         for(int i=0; i<size; i++)
  43             o[i] = store[i];
  44     }
  45
  46     public int indexOf(Object o) {
  47         for(int i=0; i<size; i++)
  48             if (o == null ? store[i] == null : store[i].equals(o)) return i;
  49
  50         return -1;
  51     }
  52
  53     public void addElement(Object o) {
  54         if (size >= store.length - 1) grow();
  55         store[size++] = o;
  56     }
  57
  58     public Object peek() {
  59         return lastElement();
  60     }
  61
  62     public Object elementAt(int i) {
  63         return store[i];
  64     }
  65
  66     public Object lastElement() {
  67         if (size == 0) return null;
  68         return store[size - 1];
  69     }
  70
  71     public void push(Object o) { addElement(o); }
  72     public Object pop() {
  73         Object ret = lastElement();
  74         if (size > 0) store[--size] = null;
  75         return ret;
  76     }
  77
  78     public int size() { return size; }
  79
  80     public void setSize(int newSize) {
  81         if (newSize < 0) throw new RuntimeException("tried to set size to negative value");
  82         if (newSize > store.length) grow(newSize * 2);
  83         if (newSize < size)
  84             for(int i=newSize; i<size; i++)
  85                 store[i] = null;
  86         size = newSize;
  87     }
  88
  89     public Object[] copyInto(Object[] out) {
  90         for(int i=0; i<size; i++)
  91             out[i] = store[i];
  92         return out;
  93     }
  94
  95     public void fromArray(Object[] in) {
  96         setSize(in.length);
  97         for(int i=0; i<size; i++)
  98             store[i] = in[i];
  99     }
 100
 101     public void removeElementAt(int i) {
 102         if (i >= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits");
 103         for(int j=i; j<size - 1; j++)
 104             store[j] = store[j + 1];
 105         setSize(size - 1);
 106     }
 107
 108     public void setElementAt(Object o, int i) {
 109         if (i >= size) setSize(i);
 110         store[i] = o;
 111     }
 112
 113     public void removeElement(Object o) {
 114         int idx = indexOf(o);
 115         if (idx != -1) removeElementAt(idx);
 116     }
 117
 118     public void insertElementAt(Object o, int at) {
 119         if (size == store.length) grow();
 120         for(int i=size; i>at; i--)
 121             store[i] = store[i-1];
 122         store[at] = o;
 123         size++;
 124     }
 125
 126     public interface CompareFunc {
 127         public int compare(Object a, Object b);
 128     }
 129
 130     public void sort(CompareFunc c) {
 131         sort(this, null, c, 0, size-1);
 132     }
 133
 134     public static void sort(Vec a, Vec b, CompareFunc c) {
 135         if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec a and b must be of equal size");
 136         sort(a, b, c, 0, a.size-1);
 137     }
 138
 139     private static final void sort(Vec a, Vec b, CompareFunc c, int start, int end) {
 140         Object tmpa, tmpb = null;
 141         if(start >= end) return;
 142         if(end-start <= 6) {
 143             for(int i=start+1;i<=end;i++) {
 144                 tmpa = a.store[i];
 145                 if (b != null) tmpb = b.store[i];
 146                 int j;
 147                 for(j=i-1;j>=start;j--) {
 148                     if(c.compare(a.store[j],tmpa) <= 0) break;
 149                     a.store[j+1] = a.store[j];
 150                     if (b != null) b.store[j+1] = b.store[j];
 151                 }
 152                 a.store[j+1] = tmpa;
 153                 if (b != null) b.store[j+1] = tmpb;
 154             }
 155             return;
 156         }
 157
 158         Object pivot = a.store[end];
 159         int lo = start - 1;
 160         int hi = end;
 161
 162         do {
 163             while(c.compare(a.store[++lo],pivot) < 0) { }
 164             while((hi > lo) && c.compare(a.store[--hi],pivot) > 0) { }
 165             swap(a, lo,hi);
 166             if (b != null) swap(b, lo,hi);
 167         } while(lo < hi);
 168
 169         swap(a, lo,end);
 170         if (b != null) swap(b, lo,end);
 171
 172         sort(a, b, c, start, lo-1);
 173         sort(a, b, c, lo+1, end);
 174     }
 175
 176     private static final void swap(Vec vec, int a, int b) {
 177         if(a != b) {
 178             Object tmp = vec.store[a];
 179             vec.store[a] = vec.store[b];
 180             vec.store[b] = tmp;
 181         }
 182     }
 183
 184     public static final void sortInts(int[] a, int start, int end) {
 185         int tmpa;
 186         if(start >= end) return;
 187         if(end-start <= 6) {
 188             for(int i=start+1;i<=end;i++) {
 189                 tmpa = a[i];
 190                 int j;
 191                 for(j=i-1;j>=start;j--) {
 192                     if(a[j] <= tmpa) break;
 193                     a[j+1] = a[j];
 194                 }
 195                 a[j+1] = tmpa;
 196             }
 197             return;
 198         }
 199         int pivot = a[end];
 200         int lo = start - 1;
 201         int hi = end;
 202         do {
 203             while(a[++lo] < pivot) { }
 204             while((hi > lo) && a[--hi] > pivot) { }
 205             swapInts(a, lo, hi);
 206         } while(lo < hi);
 207         swapInts(a, lo, end);
 208         sortInts(a, start, lo-1);
 209         sortInts(a, lo+1, end);
 210     }
 211     private static final void swapInts(int[] vec, int a, int b) {
 212         if(a != b) {
 213             int tmp = vec[a];
 214             vec[a] = vec[b];
 215             vec[b] = tmp;
 216         }
 217     }
 218
 219
 220
 221     // just a cut-and-paste copy of Vec with int storage
 222     public static class Int {
 223         private int[] store;
 224         private int size = 0;
 225
 226         public Int() { this(10); }
 227         public Int(int i) { store = new int[i]; }
 228         public Int(int i, int[] store) { size = i; this.store = store; }
 229
 230         private void grow() { grow(store.length * 2); }
 231         private void grow(int newsize) {
 232             int[] newstore = new int[newsize];
 233             System.arraycopy(store, 0, newstore, 0, size);
 234             store = newstore;
 235         }
 236
 237         public void removeAllElements() {
 238             for(int i=0; i<size; i++) store[i] = 0;
 239             size = 0;
 240         }
 241
 242         public void toArray(int[] o) {
 243             for(int i=0; i<size; i++)
 244                 o[i] = store[i];
 245         }
 246
 247         public int[] dump() { int[] o = new int[size]; toArray(o); return o; }
 248
 249         public int indexOf(int o) {
 250             for(int i=0; i<size; i++)
 251                 if (o == store[i]) return i;
 252
 253             return -1;
 254         }
 255
 256         public void addElement(int o) {
 257             if (size >= store.length - 1) grow();
 258             store[size++] = o;
 259         }
 260
 261         public int peek() {
 262             return lastElement();
 263         }
 264
 265         public int elementAt(int i) {
 266             return store[i];
 267         }
 268
 269         public int lastElement() {
 270             if (size == 0) return 0;
 271             return store[size - 1];
 272         }
 273
 274         public void push(int o) { addElement(o); }
 275         public int pop() {
 276             int ret = lastElement();
 277             if (size > 0) store[size--] = 0;
 278             return ret;
 279         }
 280
 281         public int size() { return size; }
 282
 283         public void setSize(int newSize) {
 284             if (newSize < 0) throw new RuntimeException("tried to set size to negative value");
 285             if (newSize > store.length) grow(newSize * 2);
 286             if (newSize < size)
 287                 for(int i=newSize; i<size; i++)
 288                     store[i] = 0;
 289             size = newSize;
 290         }
 291
 292         public int[] copyInto(int[] out) {
 293             for(int i=0; i<size; i++)
 294                 out[i] = store[i];
 295             return out;
 296         }
 297
 298         public void fromArray(int[] in) {
 299             setSize(in.length);
 300             for(int i=0; i<size; i++)
 301                 store[i] = in[i];
 302         }
 303
 304         public void removeElementAt(int i) {
 305             if (i >= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits");
 306             for(int j=i; j<size - 1; j++)
 307                 store[j] = store[j + 1];
 308             setSize(size - 1);
 309         }
 310
 311         public void setElementAt(int o, int i) {
 312             if (i >= size) setSize(i);
 313             store[i] = o;
 314         }
 315
 316         public void removeElement(int o) {
 317             int idx = indexOf(o);
 318             if (idx != -1) removeElementAt(idx);
 319         }
 320
 321         public void insertElementAt(int o, int at) {
 322             if (size == store.length) grow();
 323             for(int i=size; i>at; i--)
 324                 store[i] = store[i-1];
 325             store[at] = o;
 326             size++;
 327         }
 328
 329         public void sort() { sort(this, null, 0, size-1); }
 330
 331         public static void sort(Vec.Int a, Vec.Int b) {
 332             if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec.Int a and b must be of equal size");
 333             sort(a, b, 0, a.size-1);
 334         }
 335
 336         private static final void sort(Vec.Int a, Vec.Int b, int start, int end) {
 337             int tmpa, tmpb = 0;
 338             if(start >= end) return;
 339             if(end-start <= 6) {
 340                 for(int i=start+1;i<=end;i++) {
 341                     tmpa = a.store[i];
 342                     if (b != null) tmpb = b.store[i];
 343                     int j;
 344                     for(j=i-1;j>=start;j--) {
 345                         if((a.store[j]-tmpa) <= 0) break;
 346                         a.store[j+1] = a.store[j];
 347                         if (b != null) b.store[j+1] = b.store[j];
 348                     }
 349                     a.store[j+1] = tmpa;
 350                     if (b != null) b.store[j+1] = tmpb;
 351                 }
 352                 return;
 353             }
 354
 355             int pivot = a.store[end];
 356             int lo = start - 1;
 357             int hi = end;
 358
 359             do {
 360                 while((a.store[++lo]-pivot) < 0) { }
 361                 while((hi > lo) && (a.store[--hi]-pivot) > 0) { }
 362                 swap(a, lo,hi);
 363                 if (b != null) swap(b, lo,hi);
 364             } while(lo < hi);
 365
 366             swap(a, lo,end);
 367             if (b != null) swap(b, lo,end);
 368
 369             sort(a, b, start, lo-1);
 370             sort(a, b, lo+1, end);
 371         }
 372
 373         private static final void swap(Vec.Int vec, int a, int b) {
 374             if(a != b) {
 375                 int tmp = vec.store[a];
 376                 vec.store[a] = vec.store[b];
 377                 vec.store[b] = tmp;
 378             }
 379         }
 380
 381         public static final void sortInts(int[] a, int start, int end) {
 382             int tmpa;
 383             if(start >= end) return;
 384             if(end-start <= 6) {
 385                 for(int i=start+1;i<=end;i++) {
 386                     tmpa = a[i];
 387                     int j;
 388                     for(j=i-1;j>=start;j--) {
 389                         if(a[j] <= tmpa) break;
 390                         a[j+1] = a[j];
 391                     }
 392                     a[j+1] = tmpa;
 393                 }
 394                 return;
 395             }
 396
 397             int pivot = a[end];
 398             int lo = start - 1;
 399             int hi = end;
 400
 401             do {
 402                 while(a[++lo] < pivot) { }
 403                 while((hi > lo) && a[--hi] > pivot) { }
 404                 swapInts(a, lo, hi);
 405             } while(lo < hi);
 406             swapInts(a, lo, end);
 407             sortInts(a, start, lo-1);
 408             sortInts(a, lo+1, end);
 409         }
 410
 411         private static final void swapInts(int[] vec, int a, int b) {
 412             if(a != b) {
 413                 int tmp = vec[a];
 414                 vec[a] = vec[b];
 415                 vec[b] = tmp;
 416             }
 417         }
 418     }
 419
 420
 421
 422     public static final void sortFloats(float[] a, int start, int end) {
 423         float tmpa;
 424         if(start >= end) return;
 425         if(end-start <= 6) {
 426             for(int i=start+1;i<=end;i++) {
 427                 tmpa = a[i];
 428                 int j;
 429                 for(j=i-1;j>=start;j--) {
 430                     if(a[j] <= tmpa) break;
 431                     a[j+1] = a[j];
 432                 }
 433                 a[j+1] = tmpa;
 434             }
 435             return;
 436         }
 437         float pivot = a[end];
 438         int lo = start - 1;
 439         int hi = end;
 440         do {
 441             while(a[++lo] < pivot) { }
 442             while((hi > lo) && a[--hi] > pivot) { }
 443             swapFloats(a, lo, hi);
 444         } while(lo < hi);
 445         swapFloats(a, lo, end);
 446         sortFloats(a, start, lo-1);
 447         sortFloats(a, lo+1, end);
 448     }
 449     private static final void swapFloats(float[] vec, int a, int b) {
 450         if(a != b) {
 451             float tmp = vec[a];
 452             vec[a] = vec[b];
 453             vec[b] = tmp;
 454         }
 455     }
 456 }