|
1 " |
|
2 COPYRIGHT (c) 2006 by eXept Software AG |
|
3 All Rights Reserved |
|
4 |
|
5 This software is furnished under a license and may be used |
|
6 only in accordance with the terms of that license and with the |
|
7 inclusion of the above copyright notice. This software may not |
|
8 be provided or otherwise made available to, or used by, any |
|
9 other person. No title to or ownership of the software is |
|
10 hereby transferred. |
|
11 " |
|
12 |
|
13 "{ Package: 'stx:libbasic2' }" |
|
14 |
|
15 Collection subclass:#PowerSet |
|
16 instanceVariableNames:'baseSet' |
|
17 classVariableNames:'' |
|
18 poolDictionaries:'' |
|
19 category:'Collections-Unordered' |
|
20 ! |
|
21 |
|
22 !PowerSet class methodsFor:'documentation'! |
|
23 |
|
24 copyright |
|
25 " |
|
26 COPYRIGHT (c) 2006 by eXept Software AG |
|
27 All Rights Reserved |
|
28 |
|
29 This software is furnished under a license and may be used |
|
30 only in accordance with the terms of that license and with the |
|
31 inclusion of the above copyright notice. This software may not |
|
32 be provided or otherwise made available to, or used by, any |
|
33 other person. No title to or ownership of the software is |
|
34 hereby transferred. |
|
35 " |
|
36 ! |
|
37 |
|
38 documentation |
|
39 " |
|
40 This is an example collection class; |
|
41 its main purpose is to be useful as a tutorial example on concepts. |
|
42 |
|
43 A PowerSet of a collection is the set of all possible (sub-)collections |
|
44 built from the original collection's elements. |
|
45 This includes the empty collection. |
|
46 |
|
47 The PowerSet of [1 2 3] is therefore: |
|
48 [] |
|
49 [1] |
|
50 [2] |
|
51 [3] |
|
52 [1 2] |
|
53 [1 3] |
|
54 [2 3] |
|
55 [1 2 3] |
|
56 |
|
57 As the powerset can quickly become huge in size (for a baseSet of n elements, we |
|
58 get a powerSet size of 2^N), the elements of the powerset are created dynamically. |
|
59 I.e. they are only created on demand. |
|
60 As this, this is a good example of polymorphism: powerSets represent collections, |
|
61 but do not really store their elements (see Interval for another such Collection). |
|
62 |
|
63 [author:] |
|
64 Claus Gittinger |
|
65 |
|
66 [see also:] |
|
67 Set Interval |
|
68 " |
|
69 ! ! |
|
70 |
|
71 !PowerSet class methodsFor:'instance creation'! |
|
72 |
|
73 for:aCollection |
|
74 "Create & return a new instance for aCollection." |
|
75 |
|
76 ^ self basicNew initializeFor:aCollection |
|
77 ! ! |
|
78 |
|
79 !PowerSet methodsFor:'enumerating'! |
|
80 |
|
81 do:aBlock |
|
82 "evaluate the argument, aBlock for each element" |
|
83 |
|
84 |firstElement restElements restPowerSet| |
|
85 |
|
86 baseSet isEmpty ifTrue:[ |
|
87 aBlock value:#(). |
|
88 ] ifFalse:[ |
|
89 baseSet isSequenceable ifTrue:[ |
|
90 firstElement := baseSet first. |
|
91 restElements := baseSet from:2. |
|
92 ] ifFalse:[ |
|
93 firstElement := baseSet anElement. |
|
94 restElements := Set withAll:baseSet. |
|
95 restElements remove:firstElement. |
|
96 ]. |
|
97 |
|
98 restPowerSet := PowerSet for:restElements. |
|
99 restPowerSet do:[:each | |
|
100 aBlock value:(baseSet species with:firstElement) , each. |
|
101 ]. |
|
102 restPowerSet do:aBlock. |
|
103 ]. |
|
104 ! ! |
|
105 |
|
106 !PowerSet methodsFor:'initialization'! |
|
107 |
|
108 initializeFor:aCollection |
|
109 baseSet := aCollection. |
|
110 ! ! |
|
111 |
|
112 !PowerSet methodsFor:'queries'! |
|
113 |
|
114 size |
|
115 ^ 2 raisedTo:baseSet size |
|
116 ! ! |
|
117 |
|
118 !PowerSet class methodsFor:'documentation'! |
|
119 |
|
120 version |
|
121 ^ '$Header: /cvs/stx/stx/libbasic2/PowerSet.st,v 1.1 2006-03-20 08:50:28 cg Exp $' |
|
122 ! ! |