MODULE Triangulate;

IMPORT 
  Wr, Threads;
  
CONST 
  MaxSegs = 2000;

TYPE
  Vertex = CARDINAL;
  Segment = CARDINAL;
  
TYPE
  EKind = {Start, Stop};

  Event = RECORD
      kind: EKind;
      s: Segment;
    END;
    
  EventCmpProc = PROCEDURE (a, b: Event): [-1..+1];
    (* "-1" means "a" is earlier than "b". *)

  EventAgenda = OBJECT
      ne: CARDINAL;                 (* Number of events in agenda *)
      e: ARRAY [0..MaxSegs] OF Event;  (* Earliest event is "e[ne-1]". *)
    METHODS
      empty: PROCEDURE (): BOOLEAN := EA_empty;
      add: PROCEDURE (e: Event; cmp: EventCmpProc) := EA_add;
      pop: PROCEDURE (): event := EA_pop; (* Pops the smallest *)
    END;
  
PROCEDURE EA_empty(ea: EventAgenda): BOOLEAN =
  BEGIN
    RETURN ea.ne = 0
  END EA_empty;
  
PROCEDURE EA_add(ea: EventAgenda; e: Event; cmp: EventCmpProc) =
  VAR i: CARDINAL;
  BEGIN
    i := ea.ne;
    WHILE i>0 AND cmp(ea.e[i-1], e) = -1 DO 
      ea.e[i] := ea.e[i-1]; DEC(i)
    END;
    ea.e[i] := e;
    INC(ea.ne)
  END EA_add;
  
PROCEDURE EA_pop(ea: EventAgenda): Event =
  BEGIN
    DEC(ea.ne);
    RETURN ea.e[ne]
  END EA_pop;

CONST
  NoSegment: INTEGER = FIRST(Segment) - 1;

TYPE
  SegmentOrNil = [NoSegment .. LAST(Segment)];  
  Gap = RECORD above, below: SegmentOrNil END;
  
  VSCmpProc = PROCEDURE (v: Vertex; s: Segment): [-1..+1];  
    (* "-1" means "v" is below "s". *)

  SSCmpProc = PROCEDURE (a, b: Segment): [-1..+1];
    (* "-1" means "a" is below "b". *)
  
  ActiveList = OBJECT
      ns: CARDINAL;                       (* Number of active Edges *)
      e: ARRAY [0..MaxEdges-1] OF EdgeId; (* Lowest edge is "e[0]". *)
    METHODS
      (* For these, "e" must be active: *)
      nextUp: PROCEDURE (e: EdgeOrNil): EdgeOrNil := AL_nextUp;
      nextDn: PROCEDURE (e: EdgeOrNil): EdgeOrNil := AL_nextDn;
      (* For these, "e" or "v" must fall strictly inside a gap: *) 
      findS: PROCEDURE (e: Edge; cmp: SSCmpProc): Gap := AL_findS;
    END;

PROCEDURE AL_nextUp(al: ActiveList; e: EdgeOrNil): EdgeOrNil =
  VAR i: CARDINAL;
  BEGIN
    i := 0;
    IF e # NoEdge THEN 
      WHILE i < al.ns AND al.e[i] # e DO INC(i) END;
      <* ASSERT i < al.ns *>
      INC(i)
    END;
    IF i = al.ns THEN 
      RETURN NoEdge
    ELSE
      RETURN sl.e[i]
    END
  END AL_nextUp;
    
PROCEDURE AL_nextDn(al: ActiveList; e: EdgeOrNil): EdgeOrNil =
  VAR i: INTEGER;
  BEGIN
    i := al.ns - 1;
    IF e # NoEdge THEN 
      WHILE i >= 0 AND al.e[i] # e DO DEC(i) END;
      <* ASSERT i >= 0 *>
      DEC(i)
    END;
    IF i = -1 THEN 
      RETURN NoEdge
    ELSE
      RETURN sl.e[i]
    END
  END AL_nextDn;
    
PROCEDURE AL_findS(al: ActiveList; e: Edge; cmp: SSCmpProc): Gap =
  VAR g: Gap;
  BEGIN
    g.below := NoEdge;
    FOR i := 0 TO al.ns-1 DO
      CASE cmp(e, al.e[i]) < 0 OF
      | -1: g.above := al.e[i]; RETURN g;
      | 00: <* ASSERT FALSE *>
      | +1: g.below := al.e[i]
      END;
    END;
    g.above := NoEdge;
  END AL_findS;


END Triangulate.