1 package eu.simuline.util;
2
3 import java.util.AbstractList;
4 import java.util.Collection;
5 import java.util.BitSet;
6
7 /**
8 * Implements a list of integers <code>0</code> and <code>1</code>
9 * stored as bits in a {@link BitSet}.
10 * <p>
11 * Implementational note: <code>E</code> extends <code>Integer</code>
12 * which in turn is final.
13 * This means <code>E</code> is nothing but <code>Integer</code>.
14 *
15 *
16 * Created: Mon May 29 19:37:38 2006
17 *
18 * @author <a href="mailto:ernst.reissner@simuline.eu">Ernst Reissner</a>
19 * @version 1.0
20 */
21 public final class BitSetList extends AbstractList<Integer>
22 implements Cloneable {
23
24 /* -------------------------------------------------------------------- *
25 * fields. *
26 * -------------------------------------------------------------------- */
27
28 private BitSet wrapped;
29 private int size;
30 //private List<Integer> test;
31 //private int ones;// equals wrapped.cardinality() ****
32
33 /* -------------------------------------------------------------------- *
34 * constructors. *
35 * -------------------------------------------------------------------- */
36
37 /**
38 * Creates a new <code>BitSetList</code> instance.
39 *
40 */
41 public BitSetList() {
42 this(0);
43 }
44
45 /**
46 * Creates a new <code>BitSetList</code> instance.
47 *
48 * @param coll
49 * a collection which may not contain <code>null</code> pointers.
50 * @throws NullPointerException
51 * if <code>coll</code> contains a <code>null</code> pointer.
52 * @throws IllegalArgumentException
53 * if <code>coll</code> contains an <code>Integer</code> object
54 * other than <code>0</code> or <code>1</code>.
55 */
56 public BitSetList(Collection<? extends Integer> coll) {
57 this(coll.size() / 2);
58 this.addAll(coll);
59 //assert this.test.equals(this);
60 }
61
62 public BitSetList(int initialCapacity) {
63 this.wrapped = new BitSet(initialCapacity);
64 this.size = 0;
65 //this.test = new ArrayList<Integer>(initialCapacity);
66 //assert this.test.equals(this);
67 }
68
69
70 /* -------------------------------------------------------------------- *
71 * methods. *
72 * -------------------------------------------------------------------- */
73
74 /* -------------------------------------------------------------------- *
75 * methods: conversion boolean integer *
76 * -------------------------------------------------------------------- */
77
78 /**
79 * Returns the C-representation
80 * of the given <code>boolean</code> as an <code>int</code>.
81 *
82 * @param bool
83 * a <code>boolean</code> value.
84 * @return
85 * an <code>int</code> representation of <code>bool</code>:
86 * <ul>
87 * <li> <code>1</code> if <code>bool == true </code>.
88 * <li> <code>0</code> if <code>bool == false</code>.
89 * </ul>
90 * @see #int2bool
91 */
92 private static Integer bool2int(boolean bool) {
93 return bool ? 1 : 0;
94 }
95
96 /**
97 * Converts the given C-style-representation of a <code>boolean</code>.
98 *
99 * @return
100 * an <code>bool</code> representation of <code>num</code>:
101 * <ul>
102 * <li> <code>true </code> if <code>num == 1</code>.
103 * <li> <code>false</code> if <code>num == 0</code>.
104 * </ul>
105 * @throws IllegalArgumentException
106 * if <code>num</code> is neither <code>0</code> nor <code>1</code>.
107 * @see #bool2int
108 */
109 private static boolean int2bool(int num) {
110 assert num == 0 || num == 1;
111 return num == 0 ? false : true;
112 }
113
114 /* -------------------------------------------------------------------- *
115 * methods: implementation specific *
116 * -------------------------------------------------------------------- */
117
118 public int cardinality() {
119 return this.wrapped.cardinality();
120 }
121
122 public int sizeInternally() {
123 return this.wrapped.size();
124 }
125
126 /**
127 * Returns the "logical size" of this List:
128 * The index of the highest digit <code>1</code> in the List plus one.
129 * Returns zero if the List contains <code>0</code>'s only.
130 *
131 * @return
132 * the logical size of this List.
133 */
134 public int length1() {
135 return this.wrapped.length();
136 }
137
138 public void setW(int index) {
139 this.wrapped.set(index);
140 }
141
142 /*
143 public Integer set(int index) {
144 Integer ret = getW(index);
145 this.wrapped.set(index);
146 return ret;
147 }
148 */
149
150 /*
151 public void setW(int index, Integer integer) {
152 this.wrapped.set(index,int2bool(integer));
153 }
154 */
155 /*
156 public Integer setW(int index, Integer integer) {
157 Integer ret = getW(index);
158
159 switch (integer.intValue()) {
160 case 0:
161 this.wrapped.clear(index);
162 break;
163 case 1:
164 this.wrapped.set(index) ;
165 break;
166 default:
167 throw new IllegalArgumentException();
168 }
169 return ret;
170 }
171 */
172
173 /*
174
175 public Integer getW(int index) {
176 return bool2int(this.wrapped.get(index));
177 }
178 */
179 /**
180 * Returns the hash code value for this cyclic list.
181 * The hash code of a list
182 * is defined to be the result of the following calculation:
183 * <pre>
184 * hashCode = 1;
185 * Iterator i = list.iterator();
186 * while (i.hasNext()) {
187 * Object obj = i.next();
188 * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
189 * }
190 * </pre>
191 * This ensures that <code>list1.equals(list2)</code> implies that
192 * <code>list1.hashCode()==list2.hashCode()</code> for any two lists,
193 * <code>list1</code> and <code>list2</code>,
194 * as required by the general contract of <code>Object.hashCode</code>.
195 * <p>
196 * Note that this list does not allow null-elements
197 * and the hash code of an element is its value.
198 *
199 * @return
200 * the hash code value for this list.
201 * @see java.util.List#hashCode()
202 * @see Object#equals(Object)
203 * @see #equals(Object)
204 */
205 // Note that the magic number comes from the spec of List.hashCode
206 @SuppressWarnings("checkstyle:magicnumber")
207 public int hashCode() {
208 int hashCode = 1;
209 for (Integer cand : this) {
210 // hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
211 hashCode = 31 * hashCode + cand;
212 }
213 return hashCode;
214 }
215
216
217 public boolean equals(Object other) { // NOPMD
218 return super.equals(other);
219 }
220
221
222 /*
223 public boolean equals(Object o) {
224 if (o == this)
225 return true;
226 if (!(o instanceof List))
227 return false;
228
229 ListIterator<Integer> e1 = listIterator();
230 ListIterator e2 = ((List) o).listIterator();
231 while(e1.hasNext() && e2.hasNext()) {
232 Integer o1 = e1.next();
233 Object o2 = e2.next();
234 if (!(o1==null ? o2==null : o1.equals(o2)))
235 return false;
236 }
237 return !(e1.hasNext() || e2.hasNext());
238 }
239 */
240
241
242 /* -------------------------------------------------------------------- *
243 * methods: implementations of List *
244 * -------------------------------------------------------------------- */
245
246 /**
247 * Describe <code>add</code> method here.
248 *
249 * @param integer an <code>Integer</code> value
250 * @return a <code>boolean</code> value
251 */
252 /*
253 public boolean add(Integer integer) {
254 // throws a NullPointerException for integer == null as specified.
255 // System.out.println("1this.test"+this.test);
256 // System.out.println("1this.wrapped"+this.wrapped);
257 // System.out.println("1this.test.size()"+this.test.size());
258 // System.out.println("1this.size()"+this.size());
259 // System.out.println("integer"+integer);
260 assert this.test.equals(this);
261
262
263 // this.wrapped.set(size(),int2bool(integer));
264
265 // switch (integer.intValue()) {
266 // case 0:
267 // // nothing to to
268 // break;
269 // case 1:
270 // this.wrapped.set(size()) ;
271 // break;
272 // default:
273 // throw new IllegalArgumentException();
274 // }
275
276 this.size++;
277
278 assert this.test.add(integer);
279 assert this.test.size() == this.size;
280 // System.out.println("2this.test"+this.test);
281 // System.out.println("2this.wrapped"+this.wrapped);
282 assert this.test.equals(this);
283 return true;
284 }
285 */
286
287 /**
288 * Describe <code>add</code> method here.
289 *
290 * @param index an <code>int</code> value
291 * @param integer an <code>Integer</code> value
292 */
293 public void add(final int index, final Integer integer) {
294 // assert this.test.size() == this.size;
295
296 if (index < 0 || index > size()) {
297 throw new IndexOutOfBoundsException();
298 }
299 switch (integer.intValue()) {
300 case 0:
301 // nothing to to
302 break;
303 case 1:
304 // nothing to to
305 break;
306 default:
307 throw new IllegalArgumentException();
308 }
309 this.size++;
310
311 // this.test.add(index,integer);
312
313 // **** not quite optimal ****
314 for (int i = size(); i > index; i--) {
315 this.wrapped.set(i, this.wrapped.get(i - 1));
316 }
317
318 this.wrapped.set(index, int2bool(integer));
319
320 // assert this.test.equals(this);
321 }
322
323 /**
324 * Describe <code>clear</code> method here.
325 *
326 */
327 public void clear() {
328 this.wrapped.clear();
329 this.size = 0;
330
331 // this.test.clear();
332 // assert this.test.equals(this);
333 }
334
335 /**
336 * Describe <code>equals</code> method here.
337 *
338 * @param object an <code>Object</code> value
339 * @return a <code>boolean</code> value
340 */
341 /*
342 public final boolean equals(final Object object) {
343 return false;
344 }
345 */
346
347 /**
348 * Describe <code>contains</code> method here.
349 *
350 * @param object an <code>Object</code> value
351 * @return a <code>boolean</code> value
352 */
353 public boolean contains(final Object object) {
354 int cand = ((Integer) object).intValue();
355 switch (cand) {
356 case 0:
357 return this.wrapped.length() == this.wrapped.cardinality()
358 ? false : true;
359 case 1:
360 return this.wrapped.length() == 0
361 ? false : true;
362 default:
363 // this may only contain 0 or 1 and thus not object.
364 return false;
365 }
366 }
367
368 /**
369 * Describe <code>indexOf</code> method here.
370 *
371 * @param object an <code>Object</code> value
372 * @return an <code>int</code> value
373 */
374 /*
375 public int indexOf(final Object object) {
376 return 0;
377 }
378 */
379
380 /**
381 * Describe <code>lastIndexOf</code> method here.
382 *
383 * @param object an <code>Object</code> value
384 * @return an <code>int</code> value
385 */
386 /*
387 public int lastIndexOf(final Object object) {
388 return 0;
389 }
390 */
391
392 /**
393 * Describe <code>addAll</code> method here.
394 *
395 * @param collection a <code>Collection</code> value
396 * @return a <code>boolean</code> value
397 */
398 /*
399 public boolean addAll(final Collection<? extends E> collection) {
400 return false;
401 }
402 */
403
404 /**
405 * Describe <code>addAll</code> method here.
406 *
407 * @param n an <code>int</code> value
408 * @param collection a <code>Collection</code> value
409 * @return a <code>boolean</code> value
410 */
411 /*
412 public boolean addAll(final int n,
413 Collection<? extends E> collection) {
414 return false;
415 }
416 */
417
418 /**
419 * Describe <code>get</code> method here.
420 *
421 * @param index an <code>int</code> value
422 * @return an <code>Object</code> value
423 */
424 public Integer get(final int index) {
425 // assert this.test.size() == this.size;
426 if (index < 0 || index >= size()) {
427 throw new IndexOutOfBoundsException();
428 }
429
430 int ret = bool2int(this.wrapped.get(index));
431 /*
432 System.out.println("this.test"+this.test);
433 System.out.println("this"+this.wrapped);
434 System.out.println("index"+index);
435 System.out.println("this.test.get(index)"+this.test.get(index));
436 System.out.println("ret"+ret);
437 */
438 //assert ret == this.test.get(index);
439 //assert this.test.equals(this);
440 return ret; // NOPMD
441 }
442
443 /**
444 * Describe <code>iterator</code> method here.
445 *
446 * @return an <code>Iterator</code> value
447 */
448 /*
449 public Iterator<Integer> iterator() {
450 return null;
451 }
452 */
453
454 /**
455 * Describe <code>size</code> method here.
456 *
457 * @return an <code>int</code> value
458 */
459 public int size() {
460 // assert this.size == this.test.size();
461 return this.size;
462 }
463
464 /**
465 * Describe <code>toArray</code> method here.
466 *
467 * @return an <code>Object[]</code> value
468 */
469 /*
470 public Integer[] toArray() {
471 return null;
472 }
473 */
474
475 /**
476 * Describe <code>toArray</code> method here.
477 *
478 * @param objectArray an <code>Object[]</code> value
479 * @return an <code>Object[]</code> value
480 */
481 /*
482 public <E> E[] toArray(final E[] objectArray) {
483 return null;
484 }
485 */
486
487 /**
488 * Describe <code>remove</code> method here.
489 *
490 * @param object
491 * the <code>Object</code> to be removed, if present.
492 * @return
493 * the <code>boolean</code> value <code>true</code>
494 * if this list contained the specified element.
495 */
496 public boolean remove(final Object object) {
497
498 int cand = ((Integer) object).intValue();
499
500 switch (cand) {
501 case 0:
502 if (this.wrapped.length() == this.wrapped.cardinality()) {
503 // contains no 1's
504 return false;
505 }
506 assert this.wrapped.length() > this.wrapped.cardinality();
507 for (int i = 0; i < this.wrapped.length(); i++) {
508 if (!this.wrapped.get(i)) {
509 // Here found a 0.
510 remove(i);
511 }
512 }
513 // assert this.test.equals(this);
514 return true;
515 case 1:
516 if (this.wrapped.length() == 0) {
517 // contains no 1's
518 return false;
519 }
520 this.wrapped.clear(this.wrapped.length() - 1);
521 // assert this.test.equals(this);
522 return true;
523 default:
524 // this may only contain 0 or 1 and thus not object.
525 // assert this.test.equals(this);
526 return false;
527 }
528 }
529
530 /**
531 * Describe <code>remove</code> method here.
532 *
533 * @param index an <code>int</code> value
534 * @return an <code>Object</code> value
535 */
536 public Integer remove(final int index) {
537 if (index < 0 || index >= size()) {
538 throw new IndexOutOfBoundsException();
539 }
540 Integer ret = bool2int(this.wrapped.get(index));
541 // **** not quite optimal ****
542 for (int i = index; i < size() - 1; i++) {
543 this.wrapped.set(i, this.wrapped.get(i + 1));
544 }
545
546 // this.wrapped.clear(this.wrapped.length()-1);
547 this.size--;
548
549 // this.test.remove(index);
550 // assert this.test.equals(this);
551
552 return ret;
553 }
554
555 /**
556 * Describe <code>isEmpty</code> method here.
557 * This implementation returns <code>size() == 0</code>.
558 *
559 * @return a <code>boolean</code> value
560 */
561 /*
562 public boolean isEmpty() {
563 return false;
564 }
565 */
566
567 /**
568 * Describe <code>set</code> method here.
569 *
570 * @param index an <code>int</code> value
571 * @param integer an <code>Object</code> value
572 * @return an <code>Object</code> value
573 */
574 public Integer set(final int index, final Integer integer) {
575 /*
576 if (0 != System.currentTimeMillis()) {
577 throw new NullPointerException();
578 }
579 */
580 // may throw IndexOutOfBoundsException
581 Integer ret = get(index);
582 this.wrapped.set(index, int2bool(integer));
583
584
585 // assert ret == this.test.set(index,integer);
586 // assert this.test.equals(this);
587 /*
588 switch (integer.intValue()) {
589 case 0:
590 this.wrapped.clear(index) ;
591 break;
592 case 1:
593 this.wrapped.set(index) ;
594 break;
595 default:
596 throw new IllegalArgumentException();
597 }
598 */
599 return ret;
600 }
601
602 /*
603 * Describe <code>containsAll</code> method here.
604 *
605 * @param collection a <code>Collection</code> value
606 * @return a <code>boolean</code> value
607 */
608 /*
609 public boolean containsAll(final Collection<?> collection) {
610 return false;
611 }
612 */
613
614 /*
615 * Describe <code>removeAll</code> method here.
616 *
617 * @param collection a <code>Collection</code> value
618 * @return a <code>boolean</code> value
619 */
620 /*
621 public boolean removeAll(final Collection<?> collection) {
622 return false;
623 }
624 */
625
626 /*
627 * Describe <code>retainAll</code> method here.
628 *
629 * @param collection a <code>Collection</code> value
630 * @return a <code>boolean</code> value
631 */
632 /*
633 public boolean retainAll(final Collection<?> collection) {
634 return false;
635 }
636 */
637
638 /*
639 * Describe <code>subList</code> method here.
640 *
641 * @param n an <code>int</code> value
642 * @param n1 an <code>int</code> value
643 * @return a <code>List</code> value
644 */
645 /*
646 public List<Integer> subList(final int n, final int n1) {
647 return null;
648 }
649 */
650
651 /*
652 * Describe <code>listIterator</code> method here.
653 *
654 * @return a <code>ListIterator</code> value
655 */
656 /*
657 public ListIterator<Integer> listIterator() {
658 return null;
659 }
660 */
661
662 /*
663 * Describe <code>listIterator</code> method here.
664 *
665 * @param n an <code>int</code> value
666 * @return a <code>ListIterator</code> value
667 */
668 /*
669 public ListIterator<Integer> listIterator(final int n) {
670 return null;
671 }
672 */
673
674
675 public BitSetList clone() throws CloneNotSupportedException {
676 BitSetList res = (BitSetList) super .clone();
677 res.wrapped = (BitSet ) this.wrapped.clone();
678
679 // res.test = (List<Integer>)((ArrayList<Integer>)this.test).clone();
680 assert res.size == this.size;
681 return res;
682 }
683
684
685 }