fisheye/src/SortedIndexTable.m3


 Copyright (C) 1992, Digital Equipment Corporation                         
 All rights reserved.                                                      
 See the file COPYRIGHT for a full description.                            
                                                                           
 Last modified on Tue Jun 16 16:46:20 PDT 1992 by muller                   

MODULE SortedIndexTable;

IMPORT SortedHashTable, PrintUtil;

CONST
     NULL_KEY: REAL = -1.0;
     NULL_DATA: INTEGER = -1;

PROCEDURE New(size: INTEGER): T =
  BEGIN
    RETURN NEW(T, number := 0, items := NEW(REF ARRAY OF Item, size));
  END New;

PROCEDURE Clear(table: T) =
  BEGIN
    FOR i := 0 TO NUMBER(table^.items^)-1 DO
      table^.items^[i].key := NULL_KEY;
      table^.items^[i].data := NULL_DATA;
    END;
    table^.number := 0;
  END Clear;

PROCEDURE Insert(table: T; item: Item): BOOLEAN =
  VAR
    i: INTEGER;
    size: INTEGER;
    found: BOOLEAN;
  BEGIN
    size := NUMBER(table^.items^);
    IF table^.number >= size THEN RETURN FALSE; END;

    i := 0;
    found := FALSE;
    WHILE (NOT(found) AND (i < (table^.number-1))) DO
      IF (table^.items^[i].data = item.data) THEN
        found := TRUE;
      ELSE
        i := i + 1;
      END;
    END;

    IF NOT found THEN
      table^.items^[table^.number] := item;
      table^.number := table^.number + 1;
    END;

    RETURN TRUE;
  END Insert;

PROCEDURE CopySortedIndexTable(
     fromSortedIndexTable: T;
     toSortedIndexTable: T;
     n: INTEGER): BOOLEAN =
  BEGIN
    IF ((n <= fromSortedIndexTable^.number) AND
        (n <= NUMBER(toSortedIndexTable^.items^))) THEN
      FOR i := 0 TO (n-1) DO
        toSortedIndexTable^.items^[i] := fromSortedIndexTable^.items^[i];
      END;
      toSortedIndexTable^.number := n;
      RETURN TRUE;
    ELSE
      RETURN FALSE;
    END;
  END CopySortedIndexTable;

PROCEDURE Reverse(table: T) =
  VAR
    item: Item;
    n,j: INTEGER;
  BEGIN
     n := table^.number DIV 2;
     FOR i := 0 TO (n - 1 ) DO
       j := (table^.number - 1) - i;
       item := table^.items[i];
       table^.items[i] := table^.items[j];
       table^.items[j] := item;
     END;
  END Reverse;

PROCEDURE CopySortedHashTable(fromSortedHashTable: SortedHashTable.T;
                            toSortedIndexTable: T; n: INTEGER): BOOLEAN =
  VAR
    i,j: INTEGER;
    bound, buckets: INTEGER;
    head: REF SortedHashTable.ItemNode;
  BEGIN

    bound := NUMBER(toSortedIndexTable^.items^);
    buckets := NUMBER(fromSortedHashTable^);
    IF (n <= bound) THEN
      i := 0;
      j := 0;
      WHILE ((j < buckets) AND (i < n)) DO
        head := fromSortedHashTable^[j];
        WHILE head # NIL DO
          IF (i >= bound) THEN RETURN FALSE; END;
          toSortedIndexTable^.items^[i].key := head^.key;
          toSortedIndexTable^.items^[i].data := head^.data;
          i := i + 1;
          head := head^.next;
        END;
        j := j + 1;
      END;
        toSortedIndexTable^.number := i;
        RETURN TRUE;
    ELSE
      RETURN FALSE;
    END;
  END CopySortedHashTable;

PROCEDURE Print(table: T) =
  BEGIN
    PrintUtil.PrintInt("Total entries ", table^.number);
    PrintUtil.NewLine();
    FOR i := 0 TO table^.number-1 DO
      PrintUtil.PrintInt("Index =", table^.items[i].data);
      PrintUtil.PrintReal(" Value =", table^.items[i].key);
      PrintUtil.NewLine();
    END;
  END Print;

BEGIN
END SortedIndexTable.