[hset.h] Type: Hash Set/Relation

#include "standard.h"
#include "prim.h"

   [hset] implements sets and relations based on finite maps.

Types

HS_Set	Abstract set/relation type
HS_Elm	Abstract set/relation element type
HS_Dom	Abstract tuple component type
HS_Itr	Abstract set/relation iterator type

#define SET(type)   HS_Set   /* Polymorphic SET - Type */

Set/Relation Iterator

No changes are allowed on the underlaying set/relation while iterating !

HS_Itr HS_createItr(HS_Set set) #define HS_CREATE_ITR HS_createItr	creates an iterator on set/relation 'set'
void HS_dropItr(HS_Itr itr) #define HS_DROP_ITR HS_dropItr	removes iterator 'itr'
c_bool HS_emptyItr(HS_Itr itr) #define HS_EMPTY_ITR HS_emptyItr	whether iterator 'itr' is empty
void HS_get(HS_Itr itr, HS_Elm* elm) #define HS_GET(itr,pElm) HS_get(itr,(HS_Elm*)(pElm))	get the next element from iterator 'itr' into 'elm'

iterator macro for convenience

#define HS_FORALL(elm,itr,set) for                            \
                               (                              \
                                 itr = HS_CREATE_ITR(set);    \
                                 HS_EMPTY_ITR(itr)            \
                                 ? (HS_DROP_ITR(itr), C_False)  \
                                 : (HS_GET(itr, ((StdCPtr)&elm)), C_True); \
                               )

Sets & Relations

Creation of sets

HS_Set HS_createSet
       (                                    
         c_bool (*equal)(HS_Elm l, HS_Elm r), 
         long (*hash)(HS_Elm elm)           
       )
#define HS_CREATE_SET(type,equ,hsh)                                       \
        HS_createSet                                                      \
        (                                                                 \
          (c_bool (*)(HS_Elm l, HS_Elm r))(equ),(long (*)(HS_Elm elm))(hsh) \
        )
#define HS_CREATE_ADTSET(type) HS_CREATE_SET(type,primEqual,primHash)

creates a new set
function parameter:
equality on set elements
hash value of set element

Basics for sets and relations

void HS_dropSet(HS_Set set) #define HS_DROP_SET HS_dropSet	removes set/relation 'set'
HS_Set HS_clear(HS_Set set) #define HS_CLEAR HS_clear	clears set/relation 'set'; removes all elements
HS_Set HS_copy(HS_Set set) #define HS_COPY HS_copy	copies set/relation 'set'

Operations and predicates on one set/relation

long HS_card(HS_Set set) #define HS_CARD HS_card	cardinality of set/relation 'set'
c_bool HS_emptySet(HS_Set set) #define HS_EMPTY_SET HS_emptySet	whether set/relation 'set' is empty

   The following functions can also be applied to relations.
   In this case the element represents a tuple.

void HS_setElm(HS_Elm elm, HS_Set set) #define HS_SET_ELM(elm,set) HS_setElm(ABS_CAST(HS_Elm,elm),set)	set = set U { elm }
void HS_delElm(HS_Elm elm, HS_Set set) #define HS_DEL_ELM(elm,set) HS_delElm((HS_Elm)(elm),set)	set = set \ { elm }
c_bool HS_mbrElm(HS_Elm elm, HS_Set set) #define HS_MBR_ELM(elm,set) HS_mbrElm((HS_Elm)(elm),set)	whether 'elm' is a member of set/relation 'set'
HS_Set HS_part(HS_Set set, c_bool (wherepart)(HS_Elm elm)) #define HS_PART(set,where) HS_part(set,(c_bool ()(HS_Elm elm))(where))	result = { e in set \| wherepart(e) }

Operations and predicates on two sets/relations

The predicate functions expects equal types !

c_bool HS_equal(HS_Set l, HS_Set r) #define HS_EQUAL HS_equal	l = r ?
c_bool HS_subset(HS_Set l, HS_Set r) #define HS_SUBSET HS_subset	l <= r ?
HS_Set HS_union(HS_Set dst, HS_Set l, HS_Set r) #define HS_UNION HS_union	dst = l U r
HS_Set HS_minus(HS_Set dst, HS_Set l, HS_Set r) #define HS_MINUS HS_minus	dst = l \ r
HS_Set HS_inter(HS_Set dst, HS_Set l, HS_Set r) #define HS_INTER HS_inter	dst = l & r
HS_Set HS_product(HS_Set l, HS_Set r, c_bool plane) #define HS_PRODUCT HS_product	result = l X r ( plane --> no tuple hierarchy )

Creation of relations

HS_Set HS_createRel
       (                                    
         int argcnt,                        
         c_bool (*equal)(HS_Dom l, HS_Dom r), 
         long (*hash)(HS_Dom d), ...        
       )
#define HS_CREATE_REL_2(t1,e1,h1,t2,e2,h2)    \
        HS_createRel                          \
        (                                     \
          4,                                  \
          (c_bool (*)(HS_Dom l, HS_Dom r))(e1), \
          (long (*)(HS_Dom d))(h1),           \
          (c_bool (*)(HS_Dom l, HS_Dom r))(e2), \
          (long (*)(HS_Dom d))(h2)            \
        )
#define HS_CREATE_ADTREL_2(t1,t2) \
        HS_CREATE_REL_2(t1,primEqual,primHash,t2,primEqual,primHash)

creates a new relation
function parameter:
tuple arity; number of following pairs
equality on tuple components
hash value of tuple component

Basics for relations

int HS_arity(HS_Elm tpl) #define HS_ARITY HS_arity	number of tuple components
HS_Dom HS_tplcol(HS_Elm tpl, int Nth) #define HS_TPLCOL(typ,t,n) ((typ)HS_tplcol(t,n))	Nth tuple component ( Nth >= 1 )

Operations and predicates on one relation

void HS_setTpl(int argcnt, HS_Set rel, HS_Dom dom, ...) #define HS_SETTPL_2(d1,d2,rel) HS_setTpl(3,rel,(HS_Dom)(d1),(HS_Dom)(d2))	rel = rel U { (dom,...) }
void HS_delTpl(int argcnt, HS_Set rel, HS_Dom dom, ...) #define HS_DELTPL_2(d1,d2,rel) HS_delTpl(3,rel,(HS_Dom)(d1),(HS_Dom)(d2))	rel = rel \ { (dom,...) }
c_bool HS_mbrTpl ( int argcnt, HS_Set rel, HS_Dom dom, ... ) #define HS_MBRTPL_2(d1,d2,rel) HS_mbrTpl(3,rel,(HS_Dom)(d1),(HS_Dom)(d2))	whether (dom,...) is a member of relation 'rel'
HS_Set HS_project(HS_Set rel, int Nth) #define HS_PROJECT HS_project	result = rel.Nth column ( Nth >= 1 )
HS_Set HS_range ( int argcnt, HS_Set rel, HS_Dom dom, ... ) #define HS_RANGE_1(d,rel) HS_range(2,rel,(HS_Dom)(d))	result = Range((dom,...))
HS_Set HS_domain ( int argcnt, HS_Set rel, HS_Dom rng, ... ) #define HS_DOMAIN_1(r,rel) HS_domain(2,rel,(HS_Dom)(r))	result = Domain((rng,...))
HS_Set HS_trans(HS_Set rel) #define HS_TRANS HS_trans	R' (reverse elements)

   The following functions can be applied only to binary relations
   over a single domain !

HS_Set HS_rclosure(HS_Set dst, HS_Set rel, HS_Set set) #define HS_IR_RCLOSURE HS_rclosure #define HS_R_RCLOSURE(d,r) HS_rclosure(d,r,(HS_Set)NULL)	dst = R + Id ( relation 'rel', domain 'set' )
HS_Set HS_sclosure(HS_Set dst, HS_Set rel) #define HS_SCLOSURE HS_sclosure	dst = R + R'
HS_Set HS_closure(HS_Set dst, HS_Set rel, HS_Set set) #define HS_IR_CLOSURE HS_closure #define HS_R_CLOSURE(d,r) HS_closure(d,r,(HS_Set)NULL)	dst = R* ( relation 'rel', domain 'set' )
HS_Set HS_iclosure(HS_Set dst, HS_Set rel) #define HS_ICLOSURE HS_iclosure	dst = R+
HS_Set HS_eclosure ( HS_Set dst, HS_Set rel, HS_Set set, int (*compare)(HS_Dom l, HS_Dom r) ) #define HS_IR_ECLOSURE HS_eclosure #define HS_R_ECLOSURE(d,r,c) HS_eclosure(d,r,(HS_Set)NULL,c)	dst = (R + R')* ( relation 'rel', domain 'set' and 'compare' )
void HS_quotient(HS_Set eclosure,int (compare)(HS_Dom l, HS_Dom r)) #define HS_QUOTIENT(ecl,cmp) \ HS_quotient(ecl,(int ()(HS_Dom l, HS_Dom r))(cmp))	re-sets class representants [eclosure] of partition 'eclosure'
HS_Dom HS_class(HS_Dom dom, HS_Set eclosure) #define HS_CLASS(typ,dom,ecl) ((typ)HS_class((HS_Dom)(dom),ecl))	get class representant [dom] of domain 'dom' in partition 'eclosure'
HS_Set HS_kern(HS_Set dst, HS_Set iclosure) #define HS_KERN HS_kern	dst = R+ \ square(R+)
HS_Set HS_conclusion(HS_Set dst, HS_Set rel) #define HS_CONCLUSION HS_conclusion	dst = square(R)

Operations and predicates on two relations

HS_Set HS_join
       (
         int argcnt, HS_Set l, HS_Set r,  ...
       )
#define HS_JOIN(l,r)         HS_join(2,l,r)
#define HS_JOIN_1(l,r,cl,cr) HS_join(4,l,r,(long)(cl),(long)(cr))

joins two relations, using columns ( cl, cr ),...
( long cl, long cr )

   The following functions can be applied only to binary relations !

HS_Set HS_compose(HS_Set dst, HS_Set l, HS_Set r)
#define HS_COMPOSE HS_compose

dst = l * r ( special binary relation --> binary relation )

Printing

void HS_fprint
     (
       FILE* file,
       HS_Set set,
       int indent,
       void (*fpMember)(FILE *file, HS_Elm elm)
     )
#define HS_PRINT(set,ind,pMbr) \
        HS_fprint(STDOUT,set,(ind),(void (*)(FILE *file, HS_Elm elm))(pMbr))

prints set/relation 'set' to 'file'