PROCEDURE SubsetConstruct*(nfa: RegExpNFA.NFA): RegExpDFA.DFA;
   VAR
      dfa: RegExpDFA.DFA;
      trans: RegExpMaps.Transition;
      lstlstMarked, lstlstUnmarked: Lists.LongintListList;
      mapDFAStateNum: RegExpMaps.DFAStateNumMap;
      lstNFAInitial, lstFirst, lstAState, lstNext: Lists.LongintList;
      iNewState, iInput, i: LONGINT;
      
      PROCEDURE gen_new_state(): LONGINT;
      BEGIN
         INC(iNewState);
         RETURN iNewState
      END gen_new_state;
      
   BEGIN
      NEW(dfa);
      NEW(lstNFAInitial, {});
      NEW(lstlstMarked, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});
      NEW(lstlstUnmarked, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});
      NEW(mapDFAStateNum);
      iNewState := 0;
      lstNFAInitial.Add(nfa.iInitial);
      lstFirst := EpsClosure(nfa, lstNFAInitial);
      lstlstUnmarked.Add(lstFirst);
      dfa.iInitial := gen_new_state();
      mapDFAStateNum.Add(lstFirst, dfa.iInitial);
      WHILE ~lstlstUnmarked.IsEmpty() DO
         lstAState := lstlstUnmarked.GetItem(0);
         lstlstUnmarked.Remove(0);
         lstlstMarked.Add(lstAState);
         IF lstAState.IndexOf(nfa.iFinal) # -1 THEN
            i := mapDFAStateNum.IndexOf(lstAState);
            IF i # -1 THEN
               dfa.lstFinal.Add(mapDFAStateNum.GetItem(i).iState)
            END
         END;
         FOR iInput := 0 TO nfa.lstInputs.GetCount() - 1 DO
            lstNext := EpsClosure(nfa,
               Move(nfa, lstAState, nfa.lstInputs.GetItem(iInput)));
            IF (lstlstUnmarked.IndexOf(lstNext) = -1) &
               (lstlstMarked.IndexOf(lstNext) = -1)
            THEN
               lstlstUnmarked.Add(lstNext);
               mapDFAStateNum.Add(lstNext, gen_new_state())
            END;
            i := mapDFAStateNum.IndexOf(lstAState);
            IF i # -1 THEN
               trans := RegExpMaps.NewTransition(
                  mapDFAStateNum.GetItem(i).iState,
                  nfa.lstInputs.GetItem(iInput));
               i := mapDFAStateNum.IndexOf(lstNext);
               IF (i # -1) & (dfa.mapTransition.IndexOf(trans) = -1) THEN
                  dfa.mapTransition.Add(trans,
                     mapDFAStateNum.GetItem(i).iState)
               END
            END
         END
      END;
      dfa.nStates := mapDFAStateNum.GetCount();
      RETURN dfa
   END SubsetConstruct;

DFA subset_construct(NFA nfa)
{
   DFA dfa;

   // state_rep: a set of NFA states which is represented by some DFA state
   //
   typedef set<state> state_rep;
   set<state_rep> marked_states;
   set<state_rep> unmarked_states;
   
   // gives a number to each state in the DFA
   //
   map<state_rep, state> dfa_state_num;
   
   set<state> nfa_initial;
   nfa_initial.insert(nfa.initial);
      
   // initially, eps-closure(nfa.initial) is the only state in the DFAs states
   // and it's unmarked
   //
   state_rep first(build_eps_closure(nfa, nfa_initial));
   unmarked_states.insert(first);
   
   // the initial dfa state
   //
   state dfa_initial = gen_new_state();
   dfa_state_num[first] = dfa_initial;
   dfa.start = dfa_initial;
   
   while (!unmarked_states.empty())
   {
      // Take out one unmarked state and mark it (remove from the unmarked set,
      // insert into the marked set)
      //
      state_rep a_state = *(unmarked_states.begin());
      unmarked_states.erase(unmarked_states.begin());
      marked_states.insert(a_state);
      
      // If this state contains the NFA's final state, add it to the DFA's set
      // of final states
      //
      if (a_state.find(nfa.final) != a_state.end())
         dfa.final.insert(dfa_state_num[a_state]);
      
      // for each input symbol the nfa knows
      //
      for (set<input>::const_iterator inp_i = nfa.inputs.begin(); inp_i != nfa.inputs.end(); ++inp_i)
      {
         // next state
         //
         state_rep next = build_eps_closure(nfa, nfa.move(a_state, *inp_i));
         
         // if we haven't examined this state before, add it to the unmarked
         // states, and make up a new number for it
         //
         if (unmarked_states.find(next) == unmarked_states.end() &&
            marked_states.find(next) == marked_states.end())
         {
            unmarked_states.insert(next);
            dfa_state_num[next] = gen_new_state();
         }
         
         dfa.trans_table[make_pair(dfa_state_num[a_state], *inp_i)] = dfa_state_num[next];
      }
   }
   
   return dfa;
}

MODULE ListsOp;

   IMPORT
      Meta,
      Kernel, SYSTEM;
   
   CONST
      dataName* = 'data';
      
   TYPE
      List* = POINTER TO LIMITED RECORD
         root, last: Item;
      END;
      
      Item = POINTER TO RECORD
         data: ANYPTR;
         next: Item;
      END;
      
      AddOp* = ABSTRACT RECORD END;
      
      Host = RECORD END;
      
      MyData = POINTER TO RECORD END;
      
      MyAddOp* = RECORD (AddOp)
         data*: MyData;
      END;
      
   VAR
      host: Host;
   
   PROCEDURE (VAR h: Host) Lookup (VAR r: ANYREC; OUT i: Meta.Item), NEW;
      VAR type: Kernel.Type; mod: Kernel.Module; attr: Kernel.ItemAttr;
   BEGIN   (* create a meta item for a global variable passed as VAR parameter *)
      attr.obj := Meta.varObj;
      attr.typ := Meta.recTyp;
      attr.vis := Meta.exported;
      attr.adr := SYSTEM.ADR(r);
      attr.mod := NIL;
      attr.desc := SYSTEM.VAL(Kernel.Type, SYSTEM.TYP(r));
      attr.ptr := NIL;
      attr.ext := NIL;
      attr.mod := NIL;
      Meta.GetThisItem(attr, i)
   END Lookup;   
      
   PROCEDURE GetData(VAR rec: ANYREC): ANYPTR;
      VAR sc: Meta.Scanner; i: Meta.Item; vs: Meta.Name; data: ANYPTR;
   BEGIN
      host.Lookup(rec, i);
      sc.ConnectTo(i);
      WHILE ~sc.eos & (data=NIL) DO
         sc.Scan; sc.GetObjName(vs);
         IF (sc.this.obj#Meta.undef) & (vs$=dataName) THEN
            data:=sc.this.PtrVal();
         END
      END;
   RETURN data
   END GetData;
   
   PROCEDURE (l: List) Add(x: ANYPTR), NEW;
      VAR i: Item;
   BEGIN
      NEW(i); i.data:=x;
      IF l.last=NIL THEN l.root:=i; l.last:=i
      ELSE l.last.next:=i; l.last:=i END;
   END Add;
   
   PROCEDURE (l: List) Do (VAR op: ANYREC), NEW;
      VAR data: ANYPTR;
   BEGIN
      WITH op: AddOp DO
         data:=GetData(op);
         ASSERT(data#NIL, 40);
         l.Add(data)
      ELSE HALT(100) END;
   END Do;
      
   PROCEDURE New*(): List;
      VAR l: List;
   BEGIN
      NEW(l);
   RETURN l
   END New;
   
   PROCEDURE Test*;
      VAR i: INTEGER; ao: MyAddOp; l: List;
   BEGIN
      l:=New();
      i:=0;
      WHILE i<10 DO
         NEW(ao.data);
         l.Do(ao);
         INC(i);
      END;
      HALT(0);
   END Test;
   
BEGIN

END ListsOp.

(!)ListsOp.Test

MODULE ContainersTest; (** AUTHOR ""; PURPOSE ""; *)

IMPORT
   Commands, Containers, Random, PreciseTimer;

PROCEDURE HashTest*(context: Commands.Context);
CONST
   SETS = 100000;
   TRIES = 20;
VAR
   r: Random.Generator;
   set: Containers.LongintSet;
   setset1, setset2: Containers.LongintSetSet;
   i, j, n, iTry: LONGINT;
   t: HUGEINT;
BEGIN
   context.out.Ln;

   NEW(r);

   t := PreciseTimer.GetTicks();
   
   FOR iTry := 0 TO TRIES - 1 DO
      NEW(set);
      FOR i := 0 TO SETS - 1 DO
         n := r.Dice(MAX(LONGINT));
         IF ~set.Contains(n) THEN
            set.Add(n)
         END
      END
   END;
   
   t := PreciseTimer.GetTicks() - t;
   
   context.out.String("Count: ");
   context.out.Int(set.GetCount(), 0);
   context.out.Ln;
   context.out.String("Collisions: ");
   context.out.Int(set.dictionary.nCollisions, 0);
   context.out.Ln;
   context.out.String("Time: ");
   context.out.Float(PreciseTimer.GetTime(t) / TRIES, 15);
   context.out.Ln;
   context.out.Update;
   
   NEW(setset1);
   FOR i := 0 TO SETS - 1 DO
      NEW(set);
      FOR j := 0 TO 20 DO
         n := r.Dice(MAX(LONGINT));
         IF ~set.Contains(n) THEN
            set.Add(n)
         END
      END;
      IF ~setset1.Contains(set) THEN
         setset1.Add(set)
      END
   END;
   
   context.out.String("Sets generated");
   context.out.Ln;
   context.out.Update;
   
   t := PreciseTimer.GetTicks();
   
   FOR iTry := 0 TO TRIES - 1 DO
      NEW(setset2);
      setset1.Reset;
      WHILE setset1.HasNext() DO
         set := setset1.GetNext();
         IF ~setset2.Contains(set) THEN
            setset2.Add(set)
         END
      END
   END;

   t := PreciseTimer.GetTicks() - t;

   context.out.String("Count: ");
   context.out.Int(setset2.GetCount(), 0);
   context.out.Ln;
   context.out.String("Collisions: ");
   context.out.Int(setset2.dictionary.nCollisions, 0);
   context.out.Ln;
   context.out.String("Time: ");
   context.out.Float(PreciseTimer.GetTime(t) / TRIES, 15);
   context.out.Ln;
   
END HashTest;

BEGIN
END ContainersTest.

ContainersTest.Test ~
ContainersTest.HashTest ~
SystemTools.Free ContainersTest Containers ~

Count: 99997
Collisions: 232111
Time:   7.291155E-002
Sets generated
Count: 100000
Collisions: 255930
Time:   9.049281E-001