Category : C++ Source Code
Archive   : INTSET.ZIP
Filename : INTSET.H

 
Output of file : INTSET.H contained in archive : INTSET.ZIP

/* Module intset

Made by: Jarl Selle, N-5427 Urangsv†g, Norway, Phone/fax: +47 54 21 536

Description: positive INTegers SET module

Uses for interface: -
Uses for implementation: -

Classes: IntSet

Class utilities: -

Objects: -

*/

#ifndef intset_h
#define intset_h




/* Class IntSet

Description: positive INTeger SET class

Cardinality: n

Inherits (compatible type | new type): -
Superclasses: -

Uses for interface: -
Uses for implementation: -

Concurrency: sequential
Persistence: transitory


Constructor(s):

IntSet( IntSet_Elem m )
pre: m <= sizeof(IntSet_Bits)*8*maxvalue(IntSet_Lim)
post: constructed a new integer set that can have elements with values
up to and including m,
Card() = 0,
Maximum() = m,
if problems with allocation Constructed() = 0


Destructor:

~IntSet()
pre: -
post: set removed from memory


Modifiers:

IntSet& Insert( IntSet_Elem e )
pre: 0 <= e <= Maximum()
post: e in set


IntSet& Del( IntSet_Elem e )
pre: 0 <= e <= Maximum()
post: e not in set


IntSet& Assign( const IntSet& b )
pre: Maximum() = b.Maximum()
post: Assign = set = b


IntSet& Complement( const IntSet& b )
pre: Maximum() = b.Maximum()
post: Complement = set = !b



Selectors:

int Constructed() const
pre: -
post: constructed = set is allocated


IntSet_Elem Card() const
pre: -
post: card = |set|


IntSet_Elem Maximum() const
pre: -
post: Maximum = maximum value of an element in the set


int Member( IntSet_Elem e ) const
pre: 0 <= e <= Maximum()
post: Member = (e in set)


int IntSet::eq( const IntSet& b ) const
pre: Maximum() = b.Maximum()
post: eq = (set = b)


int IntSet::Sub( const IntSet& b ) const
pre: Maximum() = b.Maximum()
post: Sub = (set is a subset of b) (V equal)


int eqVneVsubsuper( const IntSet& b ) const
pre: Maximum() = b.Maximum()
post: eqVneVsubsuper = 0 => set is equal to b V
eqVneVsubsuper = 1 => set is not equal to b V
eqVneVsubsuper = 2 => set is a subset of b V
set is a superset of b


int ArelB( const IntSet& b ) const
pre: Maximum() = b.Maximum()
post: set equal b => ArelB = 0
set subset b => ArelB = 1
b subset set => ArelB = 2
(set unequal b) & (set intersection b = {}) => ArelB = 3
(set unequal b) & (set intersection b != {}) => ArelB = 4


Utilities:

IntSet& SetEmpty()
pre: -
post: (Ai: 0 <= i <= Maximum(): i not in set)


IntSet& Intersection( const IntSet& a, const IntSet& b )
pre: Maximum() = a.Maximum() = b.Maximum()
post: Intersection = set = a intersection b


IntSet& IntSet::Union( const IntSet& a, const IntSet& b )
pre: Maximum() = a.Maximum() = b.Maximum()
post: Union = set = a union b


IntSet& Eor( const IntSet& a, const IntSet& b )
pre: Maximum() = a.Maximum() = b.Maximum()
post: Eor = set = a eor b


IntSet& Minus( const IntSet& a, const IntSet& b )
pre: Maximum() = a.Maximum() = b.Maximum()
post: Minus = set = a minus b


int Empty() const
pre: -
post: empty = |set| = 0


IntSet_Elem Min() const
pre: -
post: Min = e | (e in set V e = Maximum()+1) &
(Aa: 0 <= a < e: a not in set)


IntSet_Elem DeleteMin()
pre: -
post: (DeleteMin = min{ t | t in set}) & (e not in set) V
Empty() & (DeleteMin = Maximum()+1)


IntSet_Elem NextMember( IntSet_Elem e ) const
pre: -
post: NextMember = i | (i >= e) & (Aj: e <= j < i: j not in set) &
(i in set) V (i = Maximum()+1)


*/


typedef unsigned long IntSet_Elem; // the integers is of this type
typedef unsigned IntSet_Bits; // set is an array of IntSet_Bits
typedef unsigned IntSet_Lim; /* number of IntSet_Bits needed in array has
this type => max number of elem. in set
<= sizeof(IntSet_Bits)*8*maxvalue(IntSet_Lim),
(this is used since unsigned is faster
than unsigned long on a PC) */

class IntSet {
public:

IntSet(IntSet_Elem);
~IntSet();

IntSet& Insert(IntSet_Elem);
IntSet& Del(IntSet_Elem);
IntSet& Assign(const IntSet&);
IntSet& Complement(const IntSet&);

int Constructed() const { return set != 0; }
IntSet_Elem Card() const { return cardinality; }
IntSet_Elem Maximum() const { return max; }
int Member(IntSet_Elem) const;
int eq(const IntSet&) const;
int Sub(const IntSet&) const;
int eqVneVsubsuper(const IntSet&) const;
int ArelB(const IntSet&) const;

IntSet& SetEmpty();
IntSet& Intersection(const IntSet&,const IntSet&);
IntSet& Union(const IntSet&,const IntSet&);
IntSet& Eor(const IntSet&,const IntSet&);
IntSet& Minus(const IntSet&,const IntSet&);
int Empty() const { return Card() == 0; }
IntSet_Elem Min() const;
IntSet_Elem DeleteMin();
IntSet_Elem NextMember(IntSet_Elem) const;

operator==(const IntSet& b) const { return eq(b); }
operator!=(const IntSet& b) const { return !eq(b); }
IntSet& operator=(const IntSet& b) { return Assign(b); }


private:

IntSet_Bits *set;
IntSet_Elem max,cardinality;
IntSet_Lim limit;

};



#endif