src/edu/berkeley/sbp/util/FastSet.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp.util;
   4 import java.util.*;
   5
   6 public /*final*/ class FastSet<T> implements Iterator<T>, Iterable<T>, Visitable<T> {
   7
   8     public static final int INITIAL_SIZE = 8;
   9
  10     private       Object[] array = null;
  11     private       T        only  = null;
  12     private       int      i     = -1;
  13     private       int      size  = 0;
  14
  15     public Iterator<T> iterator() { i=0; return this; }
  16     public void        remove()   { throw new Error(); }
  17     public boolean     hasNext()  { return only==null ? i<size : i<1; }
  18     public T           next()     { return only==null ? (T)array[i++] : (i++)==0 ? only : null; }
  19     public T get(int i) {
  20         if (i==0 && only!=null) return only;
  21         if (array==null) return null;
  22         return (T)array[i];
  23     }
  24
  25     public FastSet() { }
  26     public FastSet(T t) { only = t; }
  27     public FastSet(Set<T> s) {
  28         if (s.size()==1) { only = s.iterator().next(); return; }
  29         array = new Object[s.size()];
  30         for(T t : s) array[size++] = t;
  31     }
  32
  33     public void remove(T t) {
  34         if (only != null) {
  35             if (only==t) only=null;
  36             return;
  37         }
  38         boolean found = false;
  39         for(int j=0; j<size; j++) {
  40             if (array[j]==t) found = true;
  41             if (found && j<size-1) array[j] = array[j+1];
  42         }
  43         if (found) size--;
  44     }
  45
  46     public <B> void visit(Invokable<T,B> ivbc, B b) {
  47         if (only!=null) ivbc.invoke(only, b);
  48         else for(int j=0; j<size; j++)
  49             ivbc.invoke((T)array[j], b);
  50     }
  51
  52     public int size() { return only==null ? size : 1; }
  53     private void grow() {
  54         Object[] array2 = array==null ? new Object[INITIAL_SIZE] : new Object[array.length * 2];
  55         if (array != null) System.arraycopy(array, 0, array2, 0, array.length);
  56         array = array2;
  57         if (only!=null) {
  58             array[size++] = only;
  59             only = null;
  60         }
  61     }
  62     public void add(T t, boolean check) {
  63         //if (check) for(Object o : this) if (o.equals(t)) return;
  64         if (check) {
  65             if (only==t) return;
  66             if (array != null)
  67                 for(int i=0; i<size; i++)
  68                     if (array[i]==t) return;
  69         }
  70         add(t);
  71     }
  72     public void add(T t) {
  73         if (array==null) {
  74             if (only!=null) { only = t; return; }
  75             grow();
  76         } else if (size>=array.length-1) {
  77             grow();
  78         }
  79         array[size++] = t;
  80     }
  81
  82     public boolean contains(T t) {
  83         if (t==only) return true;
  84         if (array==null) return false;
  85         for(Object o : array) if (o==t) return true;
  86         return false;
  87     }
  88 }