001: package prefuse.util.collections;
002:
003: import java.util.BitSet;
004: import java.util.Comparator;
005: import java.util.NoSuchElementException;
006:
007: /**
008: * Sorted map implementation using bit vectors to map from boolean keys to
009: * int values.
010: *
011: * @author <a href="http://jheer.org">jeffrey heer</a>
012: */
013: public class BooleanIntBitSetMap implements BooleanIntSortedMap {
014:
015: private BitSet m_true = new BitSet();
016: private BitSet m_false = new BitSet();
017:
018: public BooleanIntBitSetMap() {
019: }
020:
021: public boolean firstKey() {
022: return false;
023: }
024:
025: public boolean lastKey() {
026: return true;
027: }
028:
029: public boolean containsKey(boolean key) {
030: BitSet set = key ? m_true : m_false;
031: return set.cardinality() > 0;
032: }
033:
034: public IntIterator valueRangeIterator(boolean fromKey,
035: boolean fromInc, boolean toKey, boolean toInc) {
036: if (!fromInc && !toInc) {
037: // empty iterator
038: return new BitSetIterator(null);
039: } else if (fromKey == toKey || !toInc) {
040: return new BitSetIterator(fromKey ? m_true : m_false);
041: } else if (!fromInc) {
042: return new BitSetIterator(toKey ? m_true : m_false);
043: } else {
044: return new BitSetIterator(fromKey ? m_true : m_false,
045: toKey ? m_true : m_false);
046: }
047: }
048:
049: public LiteralIterator keyIterator() {
050: return new BitSetIterator(m_false, m_true);
051: }
052:
053: public LiteralIterator keyRangeIterator(boolean fromKey,
054: boolean fromInc, boolean toKey, boolean toInc) {
055: if (!fromInc && !toInc) {
056: // empty iterator
057: return new BitSetIterator(null);
058: } else if (fromKey == toKey || !toInc) {
059: return new BitSetIterator(fromKey ? m_true : m_false);
060: } else if (!fromInc) {
061: return new BitSetIterator(toKey ? m_true : m_false);
062: } else {
063: return new BitSetIterator(fromKey ? m_true : m_false,
064: toKey ? m_true : m_false);
065: }
066: }
067:
068: public int get(boolean key) {
069: BitSet set = key ? m_true : m_false;
070: return set.nextSetBit(0);
071: }
072:
073: public int remove(boolean key) {
074: BitSet set = key ? m_true : m_false;
075: int idx = set.length() - 1;
076: set.clear(idx);
077: return idx;
078: }
079:
080: public int remove(boolean key, int value) {
081: BitSet set = key ? m_true : m_false;
082: if (set.get(value)) {
083: set.clear(value);
084: return value;
085: } else {
086: return Integer.MIN_VALUE;
087: }
088: }
089:
090: public int put(boolean key, int value) {
091: BitSet set = key ? m_true : m_false;
092: boolean ret = set.get(value);
093: set.set(value);
094: return ret ? value : Integer.MIN_VALUE;
095: }
096:
097: public int getMinimum() {
098: if (m_false.cardinality() > 0) {
099: return m_false.nextSetBit(0);
100: } else if (m_true.cardinality() > 0) {
101: return m_true.nextSetBit(0);
102: } else {
103: return Integer.MIN_VALUE;
104: }
105: }
106:
107: public int getMaximum() {
108: int idx = m_true.length() - 1;
109: return idx > 0 ? idx : m_false.length() - 1;
110: }
111:
112: public int getMedian() {
113: int fsize = m_false.cardinality();
114: int tsize = m_true.cardinality();
115: if (fsize == 0 && tsize == 0)
116: return Integer.MIN_VALUE;
117:
118: int med = (fsize + tsize) / 2;
119: BitSet set = (fsize > tsize ? m_false : m_true);
120: for (int i = set.nextSetBit(0), j = 0; i >= 0; i = set
121: .nextSetBit(i + 1), ++j) {
122: if (j == med)
123: return i;
124: }
125: // shouldn't ever happen
126: return Integer.MIN_VALUE;
127: }
128:
129: public int getUniqueCount() {
130: int count = 0;
131: if (m_false.cardinality() > 0)
132: ++count;
133: if (m_true.cardinality() > 0)
134: ++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 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: public IntIterator valueIterator(boolean ascending) {
164: if (!ascending) {
165: return new BitSetIterator(m_true, m_false);
166: } else {
167: return new BitSetIterator(m_false, m_true);
168: }
169: }
170:
171: public class BitSetIterator extends IntIterator {
172:
173: private BitSet m_cur, m_next;
174: private int m_val = -1;
175:
176: public BitSetIterator(BitSet set) {
177: this (set, null);
178: }
179:
180: public BitSetIterator(BitSet first, BitSet 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:
191: private void advance() {
192: int idx = m_cur.nextSetBit(m_val + 1);
193: if (idx < 0) {
194: if (m_next != null) {
195: m_cur = m_next;
196: m_next = null;
197: m_val = -1;
198: advance();
199: } else {
200: m_val = -2;
201: }
202: return;
203: } else {
204: m_val = idx;
205: }
206: }
207:
208: public int nextInt() {
209: if (m_val < 0)
210: throw new NoSuchElementException();
211: int retval = m_val;
212: advance();
213: return retval;
214: }
215:
216: public boolean nextBoolean() {
217: if (m_cur == m_true) {
218: advance();
219: return true;
220: } else if (m_cur == m_false) {
221: advance();
222: return false;
223: } else {
224: throw new NoSuchElementException();
225: }
226: }
227:
228: public boolean hasNext() {
229: return m_val >= 0;
230: }
231:
232: public void remove() {
233: throw new UnsupportedOperationException();
234: }
235: }
236:
237: } // end of class BooleanIntBitSetMap
|