src/org/xwt/util/Vec.java

   1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.util;
   3
   4 import java.util.*;
   5 import java.io.*;
   6
   7 /**
   8  *  An unsynchronized Vector implementation; same semantics as
   9  *  java.util.Vector. Useful for JDK1.1 platforms that don't have
  10  *  java.util.ArrayList.
  11  *  @see java.util.Vector
  12  */
  13 public final class Vec implements Serializable {
  14
  15     private Object[] store;
  16     private int size = 0;
  17
  18     public Vec() { this(10); }
  19     public Vec(int i) { store = new Object[i]; }
  20
  21     private void grow() { grow(store.length * 2); }
  22     private void grow(int newsize) {
  23         Object[] newstore = new Object[newsize];
  24         System.arraycopy(store, 0, newstore, 0, size);
  25         store = newstore;
  26     }
  27
  28     public void removeAllElements() {
  29         for(int i=0; i<size; i++) store[i] = null;
  30         size = 0;
  31     }
  32
  33     public void toArray(Object[] o) {
  34         for(int i=0; i<size; i++)
  35             o[i] = store[i];
  36     }
  37
  38     public int indexOf(Object o) {
  39         for(int i=0; i<size; i++)
  40             if (store[i] == o) return i;
  41         return -1;
  42     }
  43
  44     public void addElement(Object o) {
  45         if (size >= store.length - 1) grow();
  46         store[size++] = o;
  47     }
  48
  49     public Object peek() {
  50         return lastElement();
  51     }
  52
  53     public Object elementAt(int i) {
  54         return store[i];
  55     }
  56
  57     public Object lastElement() {
  58         if (size == 0) return null;
  59         return store[size - 1];
  60     }
  61
  62     public void push(Object o) { addElement(o); }
  63     public Object pop() {
  64         Object ret = lastElement();
  65         if (size > 0) store[size--] = null;
  66         return ret;
  67     }
  68
  69     public int size() { return size; }
  70
  71     public void setSize(int newSize) {
  72         if (newSize < 0) throw new RuntimeException("tried to set size to negative value");
  73         if (newSize > store.length) grow(newSize * 2);
  74         if (newSize < size)
  75             for(int i=newSize; i<size; i++)
  76                 store[i] = null;
  77         size = newSize;
  78     }
  79
  80     public void copyInto(Object[] out) {
  81         for(int i=0; i<size; i++)
  82             out[i] = store[i];
  83     }
  84
  85     public void fromArray(Object[] in) {
  86         setSize(in.length);
  87         for(int i=0; i<size; i++)
  88             store[i] = in[i];
  89     }
  90
  91     public void removeElementAt(int i) {
  92         if (i >= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits");
  93         for(int j=i; j<size - 1; j++)
  94             store[j] = store[j + 1];
  95         setSize(size - 1);
  96     }
  97
  98     public void setElementAt(Object o, int i) {
  99         if (i >= size) setSize(i);
 100         store[i] = o;
 101     }
 102
 103     public void removeElement(Object o) {
 104         for(int i=0; i<size; i++)
 105             if (store[i] == o) {
 106                 removeElementAt(i);
 107                 return;
 108             }
 109     }
 110
 111     public void insertElementAt(Object o, int at) {
 112         if (size == store.length) grow();
 113         for(int i=size; i>at; i--)
 114             store[i] = store[i-1];
 115         store[at] = o;
 116         size++;
 117     }
 118
 119     public interface CompareFunc {
 120         public int compare(Object a, Object b);
 121     }
 122
 123     public void sort(CompareFunc c) {
 124         sort(c,0,size-1);
 125     }
 126
 127     private final void swap(int a, int b) {
 128         if(a != b) {
 129             Object tmp = store[a];
 130             store[a] = store[b];
 131             store[b] = tmp;
 132         }
 133     }
 134
 135     private void sort(CompareFunc c, int start, int end) {
 136         Object tmp;
 137         if(start >= end) return;
 138         if(end-start <= 6) {
 139             for(int i=start+1;i<=end;i++) {
 140                 tmp = store[i];
 141                 int j;
 142                 for(j=i-1;j>=start;j--) {
 143                     if(c.compare(store[j],tmp) <= 0) break;
 144                     store[j+1] = store[j];
 145                 }
 146                 store[j+1] = tmp;
 147             }
 148             return;
 149         }
 150         Object pivot = store[end];
 151         int lo = start - 1;
 152         int hi = end;
 153         do {
 154             while(c.compare(store[++lo],pivot) < 0) { }
 155             while((hi > lo) && c.compare(store[--hi],pivot) > 0) { }
 156             swap(lo,hi);
 157         } while(lo < hi);
 158         swap(lo,end);
 159         sort(c,start,lo-1);
 160         sort(c,lo+1,end);
 161     }
 162 }