View Javadoc

1   // BitStringSet.java, created May 5, 2004 12:15:22 PM 2004 by jwhaley
2   // Copyright (C) 2004 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package jwutil.collections;
5   
6   import java.util.AbstractSet;
7   import java.util.Iterator;
8   import java.util.List;
9   import jwutil.math.BitString;
10  
11  /***
12   * A set backed by a bitstring.
13   * 
14   * @author jwhaley
15   * @version $Id: BitStringSet.java 1934 2004-09-27 22:42:35Z joewhaley $
16   */
17  public class BitStringSet extends AbstractSet {
18  
19      final BitString b;
20      final List elements;
21      
22      /* (non-Javadoc)
23       * @see java.util.Collection#add(java.lang.Object)
24       */
25      public boolean add(Object arg0) {
26          int index = elements.indexOf(arg0);
27          boolean a;
28          if (index == -1) {
29              elements.add(arg0);
30              index = elements.size() - 1;
31              a = false;
32          } else {
33              a = b.get(index);
34          }
35          if (!a)
36              b.set(index);
37          return !a;
38      }
39      
40      /* (non-Javadoc)
41       * @see java.util.Collection#contains(java.lang.Object)
42       */
43      public boolean contains(Object arg0) {
44          int index = elements.indexOf(arg0);
45          if (index == -1) return false;
46          return b.get(index);
47      }
48      
49      /* (non-Javadoc)
50       * @see java.util.Collection#remove(java.lang.Object)
51       */
52      public boolean remove(Object arg0) {
53          int index = elements.indexOf(arg0);
54          if (index == -1) return false;
55          boolean a = b.get(index);
56          if (a) b.clear(index);
57          return a;
58      }
59      
60      public BitStringSet(BitString b, List elements) {
61          this.b = b;
62          this.elements = elements;
63      }
64      
65      /* (non-Javadoc)
66       * @see java.util.AbstractCollection#iterator()
67       */
68      public Iterator iterator() {
69          return new BitStringIterator(b.iterator(), elements);
70      }
71  
72      /* (non-Javadoc)
73       * @see java.util.AbstractCollection#size()
74       */
75      public int size() {
76          return b.numberOfOnes();
77      }
78      
79      static class BitStringIterator implements Iterator {
80          final BitString.BitStringIterator i;
81          final List elements;
82          
83          BitStringIterator(BitString.BitStringIterator i, List elements) {
84              this.i = i;
85              this.elements = elements;
86          }
87          
88          /* (non-Javadoc)
89           * @see java.util.Iterator#hasNext()
90           */
91          public boolean hasNext() {
92              return i.hasNext();
93          }
94          
95          /* (non-Javadoc)
96           * @see java.util.Iterator#next()
97           */
98          public Object next() {
99              int index = i.nextIndex();
100             return elements.get(index);
101         }
102 
103         /* (non-Javadoc)
104          * @see java.util.Iterator#remove()
105          */
106         public void remove() {
107             i.remove();
108         }
109         
110     }
111     
112 }