src/org/xwt/util/Vec.java

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