"
 COPYRIGHT (c) 2006 by eXept Software AG
              All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"
"{ Package: 'stx:libbasic2' }"

Collection subclass:#PowerSet
	instanceVariableNames:'baseSet'
	classVariableNames:''
	poolDictionaries:''
	category:'Collections-Unordered'
!

!PowerSet class methodsFor:'documentation'!

copyright
"
 COPYRIGHT (c) 2006 by eXept Software AG
              All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"
!

documentation
"
    A PowerSet of a collection is the set of all possible (sub-)collections
    built from the original collection's elements.
    This includes the empty collection.

    The PowerSet of [1 2 3] is therefore:
        []
        [1]
        [2]
        [3]
        [1 2]
        [1 3]
        [2 3]
        [1 2 3]

    As the powerset can quickly become huge in size (for a baseSet of n elements, we
    get a powerSet size of 2^N), the elements of the powerset are created dynamically.
    I.e. they are only created on demand.
    As this, this is a good example of polymorphism: powerSets represent collections,
    but do not really store their elements (see Interval for another such Collection).

    [author:]
        Claus Gittinger

    [see also:]
        Set Interval
"
!

examples
"
                                                                        [exBegin]
    |s p|

    s := #(1 2 3).
    p := PowerSet for:s.

    p do:[:eachSubSet |
        Transcript showCR:eachSubSet
    ].
                                                                        [exEnd]

  A huge powerSet - do not enumerate its elements ;-)
                                                                        [exBegin]
    |s p|

    s := (1 to:1000).
    p := PowerSet for:s.

    Transcript show:'p''s size is: '; showCR:p size
                                                                        [exEnd]

                                                                        [exBegin]
    |s p|

    s := (1 to:10).
    p := PowerSet for:s.
    p includes:#(1 2 3) asSet.   
    p includes:#(1 2 4) asSet.   
    p includes:#(0 1 2) asSet.         
                                                                        [exEnd]
"
! !

!PowerSet class methodsFor:'instance creation'!

for:aCollection 
    "Create & return a new instance for aCollection."

    ^ self basicNew initializeFor:aCollection 
! !

!PowerSet methodsFor:'enumerating'!

do:aBlock 
    "evaluate the argument, aBlock for each element"

    |firstElement restElements restPowerSet|

    baseSet isEmpty ifTrue:[
        aBlock value:baseSet species new.
    ] ifFalse:[
        baseSet isSequenceable ifTrue:[
            firstElement := baseSet first.
            restElements := baseSet from:2.
        ] ifFalse:[
            firstElement := baseSet anElement.
            restElements := Set withAll:baseSet.
            restElements remove:firstElement.
        ].

        restPowerSet := PowerSet for:restElements.
        restPowerSet do:[:each | 
            aBlock value:(baseSet species with:firstElement), each.
        ].
        restPowerSet do:aBlock.
    ].
! !

!PowerSet methodsFor:'initialization'!

initializeFor:aCollection 
    baseSet := aCollection.
! !

!PowerSet methodsFor:'queries'!

includes:aCollection
    ^ aCollection conform:[:each | baseSet includes:each].

    "Created: / 02-08-2012 / 19:32:24 / cg"
!

size
    ^ 2 raisedTo:baseSet size
! !

!PowerSet class methodsFor:'documentation'!

version
    ^ '$Header: /cvs/stx/stx/libbasic2/PowerSet.st,v 1.5 2014-02-23 01:14:33 cg Exp $'
! !