001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021package org.biojava.utils;
022
023import java.util.AbstractSet;
024import java.util.Collection;
025import java.util.ConcurrentModificationException;
026import java.util.HashSet;
027import java.util.Iterator;
028import java.util.Set;
029
030/**
031 * Lightweight implementation of Set which uses little memory to store a small
032 * number of items, at the expense of scalability. Not recomended for more than
033 * 20-30 items.
034 *
035 * <p>
036 * This implementation has the useful property that the iteration order is the
037 * same as the order in which the items are added.
038 * </p>
039 *
040 * @author Matthew Pocock
041 */
042
043public class SmallSet extends AbstractSet {
044  private int vid = 0;
045  private Object[] items;
046  private int numItems;
047  
048  public SmallSet() {
049    this(2);
050  }
051  
052  public SmallSet(int size) {
053    items = new Object[size];
054    numItems = 0;
055  }
056  
057  public SmallSet(Collection col) {
058      if (! (col instanceof Set)) {
059          col = new HashSet(col);
060      }
061      numItems = col.size();
062      items = new Object[numItems];
063      items = col.toArray(items);
064  }
065  
066  public boolean contains(Object o) {
067    for(int i = 0; i < numItems; i++) {
068      if(items[i].equals(o)) {
069        return true;
070      }
071    }
072    
073    return false;
074  }
075  
076  public int size() {
077    return numItems;
078  }
079  
080  public boolean add(Object o) {
081    if(this.contains(o)) {
082      return false;
083    }
084    
085    if(numItems == items.length) {
086      Object[] tmp = new Object[items.length * items.length];
087      System.arraycopy(items, 0, tmp, 0, items.length);
088      this.items = tmp;
089    }
090    
091    this.items[this.numItems++] = o;
092    vid++;
093    
094    return true;
095  }
096  
097  // remove by index
098  private boolean remove(int i) {
099    System.arraycopy(items, i, items, i-1, numItems - i);
100    numItems--;
101    vid++;
102    
103    return true;
104  }
105  
106  public Iterator iterator() {
107    return new Iterator() {
108      int vid = SmallSet.this.vid;
109      
110      int i = 0;
111      
112      public boolean hasNext() {
113        validate();
114        return i < numItems;
115      }
116      
117      public Object next() {
118        validate();
119        return items[i++];
120      }
121      
122      public void remove() {
123        validate();
124        SmallSet.this.remove(i--);
125        this.vid = SmallSet.this.vid;
126      }
127      
128      private void validate() {
129        if(this.vid != SmallSet.this.vid) {
130          throw new ConcurrentModificationException();
131        }
132      }
133    };
134  }
135}