Algorithmen & Datenstrukturen mit Java: Beispielklasse für Verzeichnisse als binäre Patricia-Bäume
| Algorithmen & Datenstrukturen mit Java: Beispielklasse für Verzeichnisse als binäre Patricia-Bäume |
|
1package ds.interfaces;
2
3/** Simple interface for maps
4 */
5
6import java.util.Iterator;
7
8import ds.util.Invariant;
9import ds.util.Function2;
10
11import ds.util.K; // example class for keys
12import ds.util.V; // example class for values
13import ds.util.KV; // key value pair
14
15public
16 interface Map
17 extends Iterable<KV>,
18 Invariant {
19
20 boolean isEmpty();
21 boolean member(K k);
22 V lookup(K k);
23 int size();
24 KV findMin();
25 KV findMax();
26 Map insert(K k, V v);
27 Map remove(K k);
28 Map union(Map m2);
29 Map difference(Map m2);
30 Map unionWith(Function2<V,V,V> op, Map m2);
31 Map differenceWith(Function2<V,V,V> op, Map m2);
32 Map copy();
33
34 // inherited
35
36 // public Iterator<KV> iterator();
37 // public inv();
38}
1package ds.persistent.map;
2
3/** Implementation of maps by a binary Patricia tree.
4 Runtime for lookup, insert and remove is O(1),
5 (it does not depend on the size of the map).
6 This is guaranted by limiting the depth of the tree
7 by the # of bits (32) used for an int value.
8
9 The keys are restricted to int values
10
11 This is a PERSISTENT implementation.
12*/
13
14import ds.persistent.genlist.LinkedList;
15
16import ds.interfaces.Map;
17
18import ds.util.K; // example class for keys
19import ds.util.V; // example class for values
20import ds.util.KV; // key value pair
21import ds.util.Queue; // for iterators
22import ds.util.Function2;
23import ds.util.NullIterator;
24
25import ds.util.Function2;
26import ds.util.Invariant;
27import ds.util.Pair;
28import ds.util.Predicate;
29import ds.util.NullIterator;
30import ds.util.SingletonIterator;
31
32import static ds.util.K.mkK;
33import static ds.util.KV.mkPair;
34import static ds.util.Integer.max;
35import static ds.util.Integer.min;
36import static ds.util.Integer.compareUnsigned;
37import static ds.util.Integer.getPrefix;
38import static ds.util.Integer.commonPrefixMask;
39import static ds.util.Integer.matchPrefix;
40import static ds.util.Integer.shorterMask;
41import static ds.util.Integer.toStringBS;
42import static ds.util.Integer.toStringPX;
43import static ds.util.Undef.undefined;
44
45import java.util.Iterator;
46
47import static java.lang.Integer.MIN_VALUE;
48
49//----------------------------------------
50
51public abstract
52 class IntMap
53 implements Map {
54
55 //----------------------------------------
56 // the smart constructors
57
58 // empty tree
59 public static
60 IntMap empty() {
61 return
62 EMPTY;
63 }
64
65 // singleton tree
66 public static
67 IntMap singleton(K k, V v) {
68 return
69 new Leaf(k.intValue(), v);
70 }
71
72 // build search tree from arbitrary sequence (iterator)
73 public static
74 IntMap fromIterator(Iterator<KV> elems) {
75
76 IntMap res = empty();
77 while ( elems.hasNext() ) {
78 KV p = elems.next();
79 res = res.insert(p.fst, p.snd);
80 }
81 return
82 res;
83 }
84
85 //----------------------------------------
86 // public methods
87
88 public boolean isEmpty() {
89 return false;
90 }
91
92 public boolean member(K k) {
93 return
94 lookup(k) != null;
95 }
96
97 public V lookup(K k) {
98 return
99 lookup1(k.intValue());
100 }
101
102 abstract public int depth();
103 abstract public int minDepth();
104
105 public KV findMin() { return leafExpected(); }
106 public KV findMax() { return leafExpected(); }
107
108
109 public abstract IntMap insert(K k, V v);
110 public abstract IntMap remove(K k);
111
112 abstract public
113 IntMap unionWith(Function2<V,V,V> op,
114 Map m2);
115
116 abstract public
117 IntMap differenceWith(Function2<V,V,V> op,
118 Map m2);
119
120 public IntMap union(Map m2) {
121 Function2<V,V,V> op = new Function2<V,V,V>() {
122 public V apply(V v1, V v2) {
123 return
124 v1;
125 }
126 };
127 return
128 unionWith(op, m2);
129 }
130
131 public IntMap difference(Map m2) {
132 Function2<V,V,V> op = new Function2<V,V,V>() {
133 public V apply(V v1, V v2) {
134 return
135 null;
136 }
137 };
138 return
139 differenceWith(op, m2);
140 }
141
142 public String toString() {
143 return
144 iterator().toString();
145 }
146
147 public IntMap copy() {
148 return
149 this;
150 }
151
152 //----------------------------------------
153
154 boolean isLeaf() { return false; }
155 boolean isFork() { return false; }
156
157 // getter
158 K key() { return leafExpected(); }
159 K value() { return leafExpected(); }
160 IntMap left() { return forkExpected(); }
161 IntMap right() { return forkExpected(); }
162
163 //----------------------------------------
164 // internal methods
165
166 abstract V lookup1(int k);
167
168 Fork getFork() { return forkExpected(); }
169 Leaf getLeaf() { return leafExpected(); }
170
171 private static <A> A leafExpected() {
172 return
173 undefined("Leaf expected");
174 }
175 private static <A> A forkExpected() {
176 return
177 undefined("Fork expected");
178 }
179
180 //----------------------------------------
181 // the empty tree implemented by applying the singleton design pattern
182
183 // the "generic" empty list object (with a raw type)
184
185 private static final IntMap EMPTY
186 = new Empty();
187
188 // the singleton class for the empty list object
189
190 private static final
191 class Empty
192 extends IntMap {
193
194 // predicates and attributes
195 public boolean isEmpty() { return true; }
196 public int size() { return 0; }
197 public int depth() { return 0; }
198 public int minDepth() { return 0; }
199
200 public boolean inv() { return true; }
201 public String toString() { return "<empty>"; }
202
203 public Iterator<KV> iterator() {
204 ++cntIter;
205 return
206 new NullIterator<KV>();
207 }
208
209 V lookup1(int k) {
210 return
211 null;
212 }
213
214 public IntMap insert(K k, V v) {
215 return
216 singleton(k, v);
217 }
218
219 public IntMap remove(K k) {
220 return
221 this;
222 }
223
224 public IntMap unionWith(Function2<V,V,V> op,
225 Map m2) {
226 return
227 (IntMap)m2;
228 }
229
230 public IntMap differenceWith(Function2<V,V,V> op,
231 Map m2) {
232 return
233 this;
234 }
235
236 //----------------------------------------
237 // not public stuff
238
239 Empty() { }
240 }
241
242 //----------------------------------------
243 // the Leaf class for storing a key value pair
244
245 private static final
246 class Leaf
247 extends IntMap {
248
249 final int k;
250
251 /* persistent */
252 final V v;
253
254 /* destructive *
255 V v;
256 /**/
257
258 Leaf(int k, V v) {
259 this.k = k;
260 this.v = v;
261 ++cntLeaf;
262 }
263
264 /* destructive *
265 public IntMap copy() {
266 return
267 new Leaf(k, v);
268 }
269 /**/
270
271 public boolean inv() { return true; }
272 public boolean isLeaf() { return true; }
273 public int depth() { return 1; }
274 public int minDepth() { return 1; }
275 public int size() { return 1; }
276
277 Leaf getLeaf() { return this; }
278
279
280 public KV findMin() {
281 return
282 mkPair(mkK(k), v);
283 }
284
285 public KV findMax() {
286 return
287 findMin();
288 }
289
290 public V lookup1(int k) {
291 return
292 k == this.k
293 ? v
294 : (V)null;
295 }
296
297 public IntMap insert(K k, V v) {
298 int k0 = k.intValue();
299
300 if ( k0 == this.k ) {
301 return
302 setValue(v);
303 }
304 return
305 join(k0, singleton(k, v),
306 this.k, this);
307 }
308
309 public IntMap remove(K k) {
310 if ( k.intValue() == this.k ) {
311 return
312 empty(); // the only place where an empty tree is given back
313 }
314 return
315 this;
316 }
317
318 public IntMap unionWith(Function2<V,V,V> op,
319 Map m) {
320 IntMap m2 = (IntMap)m;
321
322 // case 1: m2 is empty
323
324 if ( m2.isEmpty() )
325 return
326 this;
327
328 // case 2: m2 is a leaf: union of 2 leafs
329 // this is the only case where the op is used
330
331 if ( m2.isLeaf() ) {
332 Leaf l2 = m2.getLeaf();
333 if ( l2.k == this.k )
334 return
335 setValue(op.apply(v, l2.v));
336
337 return
338 join( l2.k, l2,
339 this.k, this);
340 }
341
342 // case 3: m2 is a fork
343 // "insert" this.k and this.v into m2
344
345 Fork f2 = m2.getFork();
346
347 if ( ! matchPrefix(k, f2.prefix, f2.mask) )
348 return
349 join(k, this,
350 f2.prefix, f2);
351
352 if ( (k & f2.mask) != 0 )
353 return
354 f2.setR(unionWith(op, f2.r));
355 return
356 f2.setL(unionWith(op, f2.l));
357 }
358
359 public IntMap differenceWith(Function2<V,V,V> op,
360 Map m) {
361 IntMap m2 = (IntMap)m;
362
363 V v2 = m2.lookup1(k);
364 if ( v2 == null ) // not there, do nothing
365 return
366 this;
367
368 V v1 = op.apply(v, v2); // combine values
369 if ( v1 == null ) // remove leaf
370 return
371 empty();
372
373 // update value
374 return
375 setValue(v1);
376 }
377
378 public Iterator<KV> iterator() {
379 return
380 new SingletonIterator<KV>(mkPair(mkK(k), v));
381 }
382
383 Leaf setValue(V v) {
384 /* persistent */
385 if ( v == this.v ) // nothing will change
386 return
387 this;
388 return
389 new Leaf(k, v);
390 /* destructive *
391 this.v = v;
392 return
393 this;
394 /**/
395 }
396 }
397
398 //----------------------------------------
399
400 private static
401 class Fork
402 extends IntMap {
403
404 final int prefix;
405 final int mask;
406
407 /* persistent */
408 final IntMap l;
409 final IntMap r;
410
411 /* destructive *
412 IntMap l;
413 IntMap r;
414 /**/
415
416 Fork(int prefix, int mask, IntMap l, IntMap r) {
417 this.prefix = prefix;
418 this.mask = mask;
419 this.l = l;
420 this.r = r;
421 ++cntFork;
422 }
423
424 /* destructive *
425 public IntMap copy() {
426 return
427 new Fork(prefix, mask,
428 l.copy(),
429 r.copy());
430 }
431 /**/
432
433
434 boolean isFork() {
435 return true;
436 }
437 Fork getFork() {
438 return this;
439 }
440
441 public boolean inv() {
442 return
443 ! l.isEmpty() && ! r.isEmpty()
444 &&
445 ( compareUnsigned(findMin().fst.intValue(),
446 findMax().fst.intValue()
447 ) < 0 )
448 &&
449 l.inv()
450 &&
451 r.inv();
452 }
453
454 public int size() {
455 return
456 l.size() + r.size();
457 }
458
459 public int depth() {
460 return
461 1 + max(l.depth(), r.depth());
462 }
463
464 public int minDepth() {
465 return
466 1 + min(l.minDepth(), r.minDepth());
467 }
468
469 V lookup1(int k) {
470 if ( matchPrefix(k, prefix, mask) ) {
471
472 IntMap t1 = (k & mask) != 0 ? r : l;
473 return
474 t1.lookup1(k);
475
476 }
477 return
478 null;
479 }
480
481 public KV findMin() {
482 return
483 l.findMin();
484 }
485
486 public KV findMax() {
487 return
488 r.findMax();
489 }
490
491 public Iterator<KV> iterator() {
492 return
493 new IntMapIteratorAscending(this);
494 }
495
496
497 public IntMap insert(K k, V v) {
498 int k0 = k.intValue();
499
500 if ( ! matchPrefix(k0, prefix, mask) )
501 return
502 join(k0, singleton(k, v),
503 prefix, this);
504
505 if ( (k0 & mask) != 0 )
506 return
507 setR(r.insert(k, v));
508 return
509 setL(l.insert(k, v));
510 }
511
512 public IntMap remove(K k) {
513 int k0 = k.intValue();
514
515 if ( ! matchPrefix(k0, prefix, mask) )
516 return
517 this;
518 if ( (k0 & mask) != 0 ) {
519 IntMap r1 = r.remove(k);
520 if ( r1.isEmpty() ) // no more fork needed
521 return
522 l;
523 return
524 setR(r1);
525 } else {
526 IntMap l1 = l.remove(k);
527 if ( l1.isEmpty() ) // no more fork needed
528 return
529 r;
530 return
531 setL(l1);
532 }
533 }
534
535 public IntMap unionWith(Function2<V,V,V> op,
536 Map m) {
537 IntMap m2 = (IntMap)m;
538
539 // case 1: m2 is empty
540
541 if ( m2.isEmpty() )
542 return
543 this;
544
545 // case 2: m2 is a leaf
546
547 if ( m2.isLeaf() ) {
548 Leaf l2 = m2.getLeaf();
549
550 // "insert" l2.k and l2.v
551 if ( ! matchPrefix(l2.k, prefix, mask) )
552 return
553 join(l2.k, l2, prefix, this);
554
555 if ( (l2.k & mask) != 0 )
556 return
557 setR(r.unionWith(op, m2));
558 return
559 setL(l.unionWith(op, m2));
560 }
561
562 // case 3: two forks must be merged
563
564 Fork f2 = m2.getFork();
565
566 // this fork is nearer by the root than fork f2
567 if ( shorterMask(mask, f2.mask) ) {
568
569 // prefixes don't match, add a fork for storing both subtrees
570 if ( ! matchPrefix(f2.prefix, prefix, mask) )
571 return
572 join(prefix, this, f2.prefix, f2);
573
574 // prefixes match, merge f2 with lefth or right subtree
575 if ( (f2.prefix & mask) == 0 )
576 return
577 setL(l.unionWith(op, f2));
578
579 return
580 setR(r.unionWith(op, f2));
581 }
582
583 // symmetric case, fork f2 is nearer by the root than this
584 if ( shorterMask(f2.mask, mask) ) {
585 if ( ! matchPrefix(prefix, f2.prefix, f2.mask) )
586 return
587 join(f2.prefix, f2, prefix, this);
588 if ( (prefix & f2.mask) == 0 )
589 return
590 f2.setL(f2.l.unionWith(op, this));
591 return
592 f2.setR(f2.r.unionWith(op, this));
593 }
594
595 // masks are equal and prefixes are equal
596 // merge left and right subtrees
597 if ( prefix == f2.prefix )
598 return
599 setL(l.unionWith(op, f2.l)).
600 setR(r.unionWith(op, f2.r));
601
602 // prefixes don't match, join them like in the two 1. subcases above
603 return
604 join(prefix, this, f2.prefix, f2);
605 }
606
607 public IntMap differenceWith(Function2<V,V,V> op,
608 Map m) {
609 IntMap m2 = (IntMap)m;
610
611 // case 1: m2 is empty
612
613 if ( m2.isEmpty() )
614 return
615 this;
616
617 // case 2: m2 is a leaf
618
619 if ( m2.isLeaf() ) {
620 Leaf l2 = m2.getLeaf();
621
622 // "delete" l2.k
623 if ( ! matchPrefix(l2.k, prefix, mask) )
624 // nothing to delete
625 return
626 this;
627
628 // delete l2.k in one of the children
629 if ( (l2.k & mask) != 0)
630 return
631 setR(r.differenceWith(op, m2));
632 return
633 setL(l.differenceWith(op, m2));
634 }
635
636 // case 3: diff with a fork
637
638 Fork f2 = m2.getFork();
639
640 // this for is nearer by the root than fork f2
641 if ( shorterMask(mask, f2.mask) ) {
642
643 // prefixes don't match, nothing to remove
644 if ( ! matchPrefix(f2.prefix, prefix, mask) )
645 return
646 this;
647
648 // prefixes match, remove elements within one of the children
649 if ( (f2.prefix & mask) == 0 )
650 return
651 setL(l.differenceWith(op, f2));
652 return
653 setR(r.differenceWith(op, f2));
654
655 }
656 if ( shorterMask(f2.mask, mask) ) {
657
658 // prefixes don't match, nothing to remove
659 if ( ! matchPrefix(prefix, f2.prefix, f2.mask) )
660 return
661 this;
662
663 // remove all elems given in f2.l
664 if ( (prefix & f2.mask) == 0 )
665 return
666 differenceWith(op, f2.l);
667
668 // remove all elems given in f2.r
669 return
670 differenceWith(op, f2.r);
671
672 }
673
674 // masks and prefixes are equal
675 if ( prefix == f2.prefix )
676 return
677 setL(l.differenceWith(op, f2.l)).
678 setR(r.differenceWith(op, f2.r));
679
680 // prefixes don't match, nothing to remove
681 return
682 this;
683 }
684
685 Fork setL(IntMap l) {
686 /* persistent */
687 if ( l == this.l ) // nothing will change, may occurs with remove
688 return
689 this;
690 return
691 new Fork(prefix, mask, l, this.r);
692 /* destructive *
693 this.l = l;
694 return
695 this;
696 /**/
697 }
698 Fork setR(IntMap r) {
699 /* persistent */
700 if ( r == this.r ) // nothing will change, may occurs with remove
701 return
702 this;
703 return
704 new Fork(prefix, mask, this.l, r);
705 /* destructive *
706 this.r = r;
707 return
708 this;
709 /**/
710 }
711 }
712
713 private static IntMap join(int px1, IntMap t1,
714 int px2, IntMap t2) {
715 int mask = commonPrefixMask(px1, px2);
716 int px = getPrefix(px1, mask);
717
718 if ( (px1 & mask) != 0 )
719 return
720 new Fork(px, mask, t2, t1);
721
722 return
723 new Fork(px, mask, t1, t2);
724 }
725
726 //----------------------------------------
727 // iterators
728
729 private static
730 class IntMapIteratorAscending
731 extends ds.util.Iterator<KV> {
732
733 Queue queue;
734
735 IntMapIteratorAscending(Fork f) {
736 queue = Queue.empty();
737 add(f);
738 ++cntIter;
739 }
740
741 void add(IntMap m) {
742 if ( ! m.isEmpty() )
743 queue = queue.cons(m);
744 }
745
746 void destruct(Fork f) {
747 // insertion is done by taking keys as unsigned int
748 // so for the Fork with the sign bit set
749 // the subtrees are swapped
750
751 if ( f.mask == MIN_VALUE ) {
752 queue = queue.cons(f.l).cons(f.r);
753 } else {
754 queue = queue.cons(f.r).cons(f.l);
755 }
756 }
757
758 public boolean hasNext() {
759 return
760 ! queue.isEmpty();
761 }
762
763 public KV next() {
764 if ( queue.isEmpty() )
765 return
766 undefined("empty IntMap");
767 IntMap m = (IntMap)queue.head();
768 queue = queue.tail();
769 if ( m.isLeaf() ) {
770 Leaf l = m.getLeaf();
771 return
772 mkPair(mkK(l.k), l.v);
773 }
774 assert m.isFork();
775 destruct(m.getFork());
776 return
777 next();
778 }
779 }
780
781 private static
782 class IntMapIteratorDescending
783 extends IntMapIteratorAscending {
784 IntMapIteratorDescending(Fork f) {
785 super(f);
786 }
787
788 void destruct(Fork f) {
789 if ( f.mask == MIN_VALUE ) {
790 queue = queue.cons(f.r).cons(f.l);
791 } else {
792 queue = queue.cons(f.l).cons(f.r);
793 }
794 }
795 }
796
797 //----------------------------------------
798 // test output trees
799
800 static void indent(StringBuffer out, int level) {
801 for (int i = 0; i < level; ++i)
802 out.append(' ');
803 }
804
805 void showIntMap(StringBuffer out, int level) {
806 indent(out, level);
807 if ( this.isEmpty() ) {
808 out.append("Nil\n");
809 return;
810 }
811 if ( this.isLeaf() ) {
812 Leaf l = this.getLeaf();
813 out.append("\"");
814 out.append(toStringBS(l.k));
815 out.append("\"\t");
816 out.append(l.v.toString());
817 out.append("\n");
818 return;
819 }
820 {
821 Fork f = this.getFork();
822 out.append("\"");
823 out.append(toStringPX(f.prefix, f.mask));
824 out.append("\"\n");
825 f.l.showIntMap(out, level + 2);
826 f.r.showIntMap(out, level + 2);
827 }
828 }
829
830 void showIntMap(StringBuffer out, String s) {
831 // out.append(s);
832 // out.append(this.toString());
833 // out.append("\n");
834 showIntMap(out, 0);
835 // out.append("\n");
836 }
837
838 public String showIntMap() {
839 StringBuffer out = new StringBuffer();
840 showIntMap(out, "");
841 return
842 new String(out);
843 }
844
845 //----------------------------------------
846 // profiling
847
848 private static int cntFork = 0;
849 private static int cntLeaf = 0;
850 private static int cntIter = 0;
851
852 public static String stats() {
853 return
854 "stats for ds.persistent.map.IntMap:\n" +
855 "# new Fork() : " + cntFork + "\n" +
856 "# new Leaf() : " + cntLeaf + "\n" +
857 "# new IntMapIterator() : " + cntIter + "\n";
858 }
859
860 public String objStats() {
861 int s = size();
862 int o = s + (s - 1) + 1; // leafs + forks + anchor
863 int l = 2 * s;
864 int f = 4 * (s - 1);
865 int m = o + 1 + l + f;
866
867 return
868 "mem stats for ds.persistent.map.IntMap object:\n" +
869 "# elements (size) : " + s + "\n" +
870 "# objects : " + o + "\n" +
871 "# fields : " + f + "\n" +
872 "# mem words : " + m + "\n";
873 }
874}
1package ds.util;
2
3import static ds.util.Boolean.toInt;
4
5
6public
7 class Integer {
8 // min and max become obsolete with Java 8
9
10 public static int max(int i, int j) {
11 return
12 i <= j ? j : i;
13 }
14 public static int min(int i, int j) {
15 return
16 j <= i ? j : i;
17 }
18
19 // second try
20 public static int compareUnsigned(int i1, int i2) {
21 long l1 = (long)i1 & 0xFFFFFFFFl;
22 long l2 = (long)i2 & 0xFFFFFFFFl;
23
24 return
25 toInt(l1 >= l2) - toInt(l1 <= l2);
26 }
27
28 //----------------------------------------
29 // bitstring operations
30 // unsed in IntMap implementation
31
32 // access the leading bits of a word
33 public static int getPrefix(int bs, int mask) {
34 return
35 bs & (~ (mask - 1) ^ mask);
36 }
37
38 // compute the mask identifying the common prefix of two words
39 public static int commonPrefixMask(int bs1, int bs2) {
40 return
41 zeroPrefix(bs1 ^ bs2);
42 }
43
44 // compare the leading part of a word with a prefix
45 public static boolean matchPrefix(int bs, int px, int mask) {
46 return
47 getPrefix(bs, mask) == px;
48 }
49
50 // remove all bits set except the most significant
51 public static int zeroPrefix(int bs1) {
52 bs1 |= bs1 >>> 1;
53 bs1 |= bs1 >>> 2;
54 bs1 |= bs1 >>> 4;
55 bs1 |= bs1 >>> 8;
56 bs1 |= bs1 >>> 16;
57 // bs1 |= bs1 >>> 32; // needed for long
58
59 return
60 bs1 ^ (bs1 >>> 1);
61 }
62
63 public static boolean shorterMask(int mask1, int mask2) {
64 return
65 compareUnsigned(mask1, mask2) > 0;
66 }
67
68 //----------------------------------------
69 // a mask is a int which has set a single bit
70 // the mask is used for indexing a single bit within a word
71 // or to access all leading bit downto the bit index
72
73 public static boolean invMask(int m) {
74 return
75 ( m != 0
76 &&
77 (m ^ (m & (~m + 1))) == 0 );
78 }
79
80 //----------------------------------------
81 // test output for bitstrings
82
83 static final int LEN_BITSTRING = 32; // int
84
85 public static String toStringBS(int bs) {
86 StringBuffer res = new StringBuffer();
87 int i = LEN_BITSTRING;
88 boolean blank = false;
89
90 while ( i > 0 ) {
91 if ( blank )
92 res.append(' ');
93 --i;
94 res.append((char)(((bs >>> i) & 0x1) + (int)'0'));
95 blank = i % 8 == 0;
96 }
97 return
98 new String(res);
99 }
100
101 public static String toStringPX(int px, int mask) {
102 StringBuffer res = new StringBuffer();
103 int i = LEN_BITSTRING;
104 boolean blank = false;
105
106 while ( (((int)1 << (i - 1)) & mask) == 0 ) {
107 if ( blank )
108 res.append(' ');
109 --i;
110 res.append((char)(((px >>> i) & 0x1) + (int)'0'));
111 blank = i % 8 == 0;
112 }
113 return
114 new String(res);
115 }
116
117}
|
| Letzte Änderung: 03.01.2018 | © Prof. Dr. Uwe Schmidt |
