KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > util > collections > BooleanIntBitSetMap


1 package prefuse.util.collections;
2
3 import java.util.BitSet JavaDoc;
4 import java.util.Comparator JavaDoc;
5 import java.util.NoSuchElementException JavaDoc;
6
7 /**
8  * Sorted map implementation using bit vectors to map from boolean keys to
9  * int values.
10  *
11  * @author <a HREF="http://jheer.org">jeffrey heer</a>
12  */

13 public class BooleanIntBitSetMap implements BooleanIntSortedMap {
14
15     private BitSet JavaDoc m_true = new BitSet JavaDoc();
16     private BitSet JavaDoc m_false = new BitSet JavaDoc();
17     
18     public BooleanIntBitSetMap() {
19     }
20     
21     public boolean firstKey() {
22         return false;
23     }
24
25     public boolean lastKey() {
26         return true;
27     }
28
29     public boolean containsKey(boolean key) {
30         BitSet JavaDoc set = key ? m_true : m_false;
31         return set.cardinality()>0;
32     }
33
34     public IntIterator valueRangeIterator(boolean fromKey, boolean fromInc,
35                                           boolean toKey, boolean toInc)
36     {
37         if ( !fromInc && !toInc ) {
38             // empty iterator
39
return new BitSetIterator(null);
40         } else if ( fromKey==toKey || !toInc ) {
41             return new BitSetIterator(fromKey ? m_true : m_false);
42         } else if ( !fromInc ) {
43             return new BitSetIterator(toKey ? m_true : m_false);
44         } else {
45             return new BitSetIterator(fromKey ? m_true : m_false,
46                                       toKey ? m_true : m_false);
47         }
48     }
49
50     public LiteralIterator keyIterator() {
51         return new BitSetIterator(m_false, m_true);
52     }
53
54     public LiteralIterator keyRangeIterator(boolean fromKey, boolean fromInc,
55                                             boolean toKey, boolean toInc)
56     {
57         if ( !fromInc && !toInc ) {
58             // empty iterator
59
return new BitSetIterator(null);
60         } else if ( fromKey==toKey || !toInc ) {
61             return new BitSetIterator(fromKey ? m_true : m_false);
62         } else if ( !fromInc ) {
63             return new BitSetIterator(toKey ? m_true : m_false);
64         } else {
65             return new BitSetIterator(fromKey ? m_true : m_false,
66                                       toKey ? m_true : m_false);
67         }
68     }
69
70     public int get(boolean key) {
71         BitSet JavaDoc set = key ? m_true : m_false;
72         return set.nextSetBit(0);
73     }
74
75     public int remove(boolean key) {
76         BitSet JavaDoc set = key ? m_true : m_false;
77         int idx = set.length()-1;
78         set.clear(idx);
79         return idx;
80     }
81
82     public int remove(boolean key, int value) {
83         BitSet JavaDoc set = key ? m_true : m_false;
84         if ( set.get(value) ) {
85             set.clear(value);
86             return value;
87         } else {
88             return Integer.MIN_VALUE;
89         }
90     }
91
92     public int put(boolean key, int value) {
93         BitSet JavaDoc set = key ? m_true : m_false;
94         boolean ret = set.get(value);
95         set.set(value);
96         return ret ? value : Integer.MIN_VALUE;
97     }
98
99     public int getMinimum() {
100         if ( m_false.cardinality() > 0 ) {
101             return m_false.nextSetBit(0);
102         } else if ( m_true.cardinality() > 0 ) {
103             return m_true.nextSetBit(0);
104         } else {
105             return Integer.MIN_VALUE;
106         }
107     }
108
109     public int getMaximum() {
110         int idx = m_true.length()-1;
111         return idx>0 ? idx : m_false.length()-1;
112     }
113
114     public int getMedian() {
115         int fsize = m_false.cardinality();
116         int tsize = m_true.cardinality();
117         if ( fsize == 0 && tsize == 0 )
118             return Integer.MIN_VALUE;
119
120         int med = (fsize+tsize)/2;
121         BitSet JavaDoc set = ( fsize>tsize ? m_false : m_true );
122         for( int i=set.nextSetBit(0), j=0; i>=0;
123              i=set.nextSetBit(i+1), ++j )
124         {
125             if ( j == med ) return i;
126         }
127         // shouldn't ever happen
128
return Integer.MIN_VALUE;
129     }
130
131     public int getUniqueCount() {
132         int count = 0;
133         if ( m_false.cardinality() > 0 ) ++count;
134         if ( m_true.cardinality() > 0 ) ++count;
135         return count;
136     }
137
138     public boolean isAllowDuplicates() {
139         return true;
140     }
141
142     public int size() {
143         return m_true.cardinality() + m_false.cardinality();
144     }
145
146     public boolean isEmpty() {
147         return m_true.isEmpty() && m_false.isEmpty();
148     }
149
150     public Comparator JavaDoc comparator() {
151         return DefaultLiteralComparator.getInstance();
152     }
153
154     public void clear() {
155         m_true.clear();
156         m_false.clear();
157     }
158
159     public boolean containsValue(int value) {
160         return m_false.get(value) || m_true.get(value);
161     }
162
163
164     public IntIterator valueIterator(boolean ascending) {
165         if ( !ascending ) {
166             return new BitSetIterator(m_true, m_false);
167         } else {
168             return new BitSetIterator(m_false, m_true);
169         }
170     }
171     
172     public class BitSetIterator extends IntIterator {
173
174         private BitSet JavaDoc m_cur, m_next;
175         private int m_val = -1;
176         
177         public BitSetIterator(BitSet JavaDoc set) {
178             this(set, null);
179         }
180         public BitSetIterator(BitSet JavaDoc first, BitSet JavaDoc second) {
181             m_cur = first;
182             m_next = second;
183             if ( first == null ) {
184                 m_val = -2;
185             } else {
186                 m_val = -1;
187                 advance();
188             }
189         }
190         private void advance() {
191             int idx = m_cur.nextSetBit(m_val+1);
192             if ( idx < 0 ) {
193                 if ( m_next != null ) {
194                     m_cur = m_next;
195                     m_next = null;
196                     m_val = -1;
197                     advance();
198                 } else {
199                     m_val = -2;
200                 }
201                 return;
202             } else {
203                 m_val = idx;
204             }
205         }
206         public int nextInt() {
207             if ( m_val < 0 )
208                 throw new NoSuchElementException JavaDoc();
209             int retval = m_val;
210             advance();
211             return retval;
212         }
213         public boolean nextBoolean() {
214             if ( m_cur == m_true ) {
215                 advance();
216                 return true;
217             } else if ( m_cur == m_false ) {
218                 advance();
219                 return false;
220             } else {
221                 throw new NoSuchElementException JavaDoc();
222             }
223         }
224         public boolean hasNext() {
225             return m_val >= 0;
226         }
227         public void remove() {
228             throw new UnsupportedOperationException JavaDoc();
229         }
230     }
231
232 } // end of class BooleanIntBitSetMap
233
Popular Tags