# [hset.h] Type: Hash Set/Relation

## contents

#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'