Power set: Difference between revisions

Implements an (incomplete) immutable set type mimic python's frozenset, then the powset function is defined.

<lang d>module powset ;

import std.stdio, std.format : fmx = format ;

class Set(T) {

alias Set!(T) Z ;

alias bool[T] S ;

private const S set ;

private const size_t len ;

private const hash_t hash ;

private T[] memberList ;

static Z emptySet() { return new Z ; }

this() { this(cast(T[])null) ; }

this(T k) { this([k]) ; }

this(T[] k) {

S mset ;

foreach(e ; k) mset[e] = true ;

set = mset ;

memberList = set.keys.sort ;

len = set.length ;

hash_t h ;

foreach(e ; memberList)

h = h*0xfff1 + typeid(T).getHash(&e) ;

hash = h ;

}

Z dup() { return new Z(memberList) ; }

alias add opCat ;

Z add(T k) { return new Z(memberList ~ k) ; }

Z add(T[] k) { return new Z(memberList ~ k) ; }

Z add(Z k) { return new Z(memberList ~ k.members) ; }

alias contains opIn_r;

bool contains(T k) { return (k in set)||false ; }

bool isEmpty() { return len == 0 ; }

T[] members() { return memberList.dup ; }

size_t length() { return len ; }

hash_t toHash() { return hash ; }

string toString() { return fmx("<%s>", fmx("%s", memberList)[1..$-1]) ; }

private Z toZ(Object o) {

auto c = cast(Z) o ;

if(c is null) throw new Exception("Compare to different type") ;

return c ;

}

int opEquals(Object rhs) { return hash == toZ(rhs).toHash ; }

// opCmp only for sort, should not be equivalent <= to subsetof

int opCmp(Object rhs) { return len - toZ(rhs).length ; }

int opApply(int delegate(inout T) dg) {

foreach(e ; memberList) if(dg(e)) break ;

return 1 ;

}

}

Set!(Set!(T)) powSet(T)(Set!(T) set) {

Set!(T)[] ps = [Set!(T).emptySet] ;

foreach(e ; set)

foreach(ss ; ps)

ps ~= ss.add(e) ;

return new Set!(Set!(T))(ps) ;

}

void main() {

Set!(int) iset = new Set!(int)([2,1]) ;

auto pset = powSet(iset) ;

writefln(iset) ;

writefln(pset) ;

writefln("set is in its powset? ", iset in pset) ;

writefln(powSet(pset)) ;

}</lang>

Short alternative version, using just arrays: