1 package prefuse.util.collections; 2 3 import java.util.BitSet ; 4 import java.util.Comparator ; 5 import java.util.NoSuchElementException ; 6 7 13 public class BooleanIntBitSetMap implements BooleanIntSortedMap { 14 15 private BitSet m_true = new BitSet (); 16 private BitSet m_false = new BitSet (); 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 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 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 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 set = key ? m_true : m_false; 72 return set.nextSetBit(0); 73 } 74 75 public int remove(boolean key) { 76 BitSet 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 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 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 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 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 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 m_cur, m_next; 175 private int m_val = -1; 176 177 public BitSetIterator(BitSet set) { 178 this(set, null); 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 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 (); 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 (); 222 } 223 } 224 public boolean hasNext() { 225 return m_val >= 0; 226 } 227 public void remove() { 228 throw new UnsupportedOperationException (); 229 } 230 } 231 232 } | Popular Tags |