CARD EndProg ;required for ALLOCATE.ACT

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

DEFINE PTR="CARD"
DEFINE NODE_SIZE="6"
TYPE SetNode=[PTR data,prv,nxt]
TYPE SetInfo=[PTR name,begin,end]

PROC PrintSet(SetInfo POINTER s)
  SetNode POINTER n
  CHAR ARRAY a

  n=s.begin
  PrintF("%S=(",s.name)
  WHILE n
  DO
    Print(n.data)
    a=n.data
    IF n.nxt THEN
      Print(", ")
    FI
    n=n.nxt
  OD
  PrintE(")")
RETURN

PROC CreateSet(SetInfo POINTER s CHAR ARRAY n)
  s.name=n
  s.begin=0
  s.end=0
RETURN

PTR FUNC Find(SetInfo POINTER s CHAR ARRAY v)
  SetNode POINTER n

  n=s.begin
  WHILE n
  DO
    IF SCompare(v,n.data)=0 THEN
      RETURN (n)
    FI
    n=n.nxt
  OD
RETURN (0)

BYTE FUNC Contains(SetInfo POINTER s CHAR ARRAY v)
  SetNode POINTER n

  n=Find(s,v)
  IF n=0 THEN
    RETURN (0)
  FI
RETURN (1)

PROC Append(SetInfo POINTER s CHAR ARRAY v)
  SetNode POINTER n,tmp

  IF Contains(s,v) THEN RETURN FI

  n=Alloc(NODE_SIZE)
  n.data=v
  n.prv=s.end
  n.nxt=0
  IF s.end THEN
    tmp=s.end tmp.nxt=n
  ELSE
    s.begin=n
  FI
  s.end=n
RETURN

PROC Remove(SetInfo POINTER s CHAR ARRAY v)
  SetNode POINTER n,prev,next

  n=Find(s,v)
  IF n=0 THEN RETURN FI

  prev=n.prv
  next=n.nxt

  Free(n,NODE_SIZE)

  IF prev THEN
    prev.nxt=next
  ELSE
    s.begin=next
  FI
  IF next THEN
    next.prv=prev
  ELSE
    s.end=prev
  FI
RETURN

PROC AppendSet(SetInfo POINTER s,other)
  SetNode POINTER n

  n=other.begin
  WHILE n
  DO
    Append(s,n.data)
    n=n.nxt
  OD
RETURN

PROC RemoveSet(SetInfo POINTER s,other)
  SetNode POINTER n

  n=other.begin
  WHILE n
  DO
    Remove(s,n.data)
    n=n.nxt
  OD
RETURN

PROC Clear(SetInfo POINTER s)
  SetNode POINTER n

  DO
    n=s.begin
    IF n=0 THEN RETURN FI
    Remove(s,n.data)
  OD
RETURN

PROC Union(SetInfo POINTER a,b,res)
  Clear(res)
  AppendSet(res,a)
  AppendSet(res,b)
RETURN

PROC Difference(SetInfo POINTER a,b,res)
  Clear(res)
  AppendSet(res,a)
  RemoveSet(res,b)
RETURN

PROC SymmetricDifference(SetInfo POINTER a,b,res)
  SetInfo tmp1,tmp2

  CreateSet(tmp1,"")
  CreateSet(tmp2,"")
  Difference(a,b,tmp1)
  Difference(b,a,tmp2)
  Union(tmp1,tmp2,res)
  Clear(tmp1)
  Clear(tmp2)
RETURN

PROC TestSymmetricDifference(SetInfo POINTER a,b,res)
  SymmetricDifference(a,b,res)
  PrintF("%S XOR %S: ",a.name,b.name)
  PrintSet(res)
RETURN

PROC TestDifference(SetInfo POINTER a,b,res)
  Difference(a,b,res)
  PrintF("%S-%S: ",a.name,b.name)
  PrintSet(res)
RETURN

PROC Main()
  SetInfo s1,s2,s3

  Put(125) PutE() ;clear screen

  AllocInit(0)
  CreateSet(s1,"A")
  CreateSet(s2,"B")
  CreateSet(s3,"C")

  Append(s1,"John") Append(s1,"Bob")
  Append(s1,"Mary") Append(s1,"Serena")
  Append(s2,"Jim") Append(s2,"Mary")
  Append(s2,"John") Append(s2,"Bob")

  PrintSet(s1) PrintSet(s2)
  PutE()

  TestSymmetricDifference(s1,s2,s3)
  TestDifference(s1,s2,s3)
  TestDifference(s2,s1,s3)

  Clear(s1)
  Clear(s2)
  Clear(s3)
RETURN