MODULE SortedHashTable;

PROCEDURE New(size: INTEGER): T =
  BEGIN
    RETURN NEW(T, size);
  END New;

PROCEDURE Clear(table: T) =
  BEGIN
    FOR i := 0 TO NUMBER(table^)-1 DO
      table^[i] := NIL;
    END;
  END Clear;

PROCEDURE Insert(table: T; new_key: REAL; new_data: INTEGER): BOOLEAN =
  VAR
    head, tail, node: REF ItemNode;
    index: INTEGER;
    done: BOOLEAN;
  BEGIN
    index := FLOOR(new_key * FLOAT(NUMBER(table^) - 1));
    IF index > NUMBER(table^) - 1 THEN
      RETURN FALSE;
    ELSIF index < 0 THEN
      RETURN FALSE;
    END;
    head := table^[index];
    tail := head;
    node := NEW(REF ItemNode, key:=new_key, data:=new_data, next:=NIL);

    done := FALSE;
    WHILE (head # NIL) AND (NOT done) DO
      IF head^.key >= new_key THEN
        IF tail = head THEN
          table^[index] := node;
          node^.next := tail;
        ELSE
            tail^.next := node;
            node^.next := head;
        END;
        done := TRUE;             (* to make sure the loop terminates *)
      ELSE
        tail := head;
        head := head^.next
      END
    END;

    IF (NOT done) THEN
      IF tail = NIL THEN
        table^[index] := node;
      ELSE
        tail^.next := node;
      END;
    END;
    RETURN TRUE;
  END Insert;

BEGIN
END SortedHashTable.