(* Copyright (C) 1989, Digital Equipment Corporation           *)
(* All rights reserved.                                        *)
(* See the file COPYRIGHT for a full description.              *)

(* Last modified on Thu Nov  2 18:28:29 1989 by muller         *)
(*      modified on Mon Oct  2 09:19:13 1989 by kalsow         *)
(*      modified on Fri Jun 3 16:21:07 PDT 1988 by luca        *)

INTERFACE Interval;

(* Pair of integers [lo,hi)

   An "interval" is a pair of integers "lo" and "hi" with lo <= hi. It is
   meant to represent the left-closed, right-open segment [lo,hi), i.e. the
   set of integer points between lo (included) and hi (excluded). Note: there
   are many intervals denoting the empty set.

   Index: geometry, intervals; intervals *)

(* NOTATION: An "null interval" is any pair of integers (lo,hi) with lo >= hi.
   A "point-like" interval is any pair of integers (lo,hi) with lo = hi. By
   "empty" we mean an unspecified point-like interval. By <lo,hi> we mean the
   pair (lo,hi) if lo<hi, empty otherwise. By |lo,hi| we mean the pair (lo,hi)
   if lo<hi, (hi,lo) if hi<lo, and empty if lo=hi. *)

(* LAWS: (1) Programs which assume or generate non-point-like null intervals
   are illegal. (2) All empty intervals are identified; programs which
   discriminate between different empty intervals are illegal. *)

TYPE T = RECORD lo, hi: INTEGER END;
TYPE Bound = {Lo, Hi};

CONST Empty = T { 0, 0 }; (* A point-like interval *)
CONST Full  = T {FIRST(INTEGER), LAST(INTEGER)}; (* The biggest interval *)

(* --- Initialization --- *)

PROCEDURE FromBounds (lo, hi: INTEGER): T RAISES {};
(* Returns the interval <lo,hi> *)

PROCEDURE FromAbsBounds (lo, hi: INTEGER): T RAISES {};
(* Returns the interval |lo,hi| *)

PROCEDURE FromBound (lo: INTEGER; s: CARDINAL): T RAISES {};
(* Returns the interval <lo,lo+s> *)

PROCEDURE FromSize (s: CARDINAL): T RAISES {};
(* Returns the interval <0,s> *)

PROCEDURE Center (READONLY a: T; b: INTEGER): T RAISES {};
(* Return an interval congruent to a, with middle at b *)

(* --- Selection --- *)

PROCEDURE Size (READONLY a: T): CARDINAL RAISES {};
(* a.hi - a.lo *)

PROCEDURE Middle (READONLY a: T): INTEGER RAISES {};
(* floor ((a.hi+a.lo)/2); an unspecified integer if empty *)

PROCEDURE PickBound (READONLY a: T; n: INTEGER): Bound RAISES {};
(* Return the bound of a closest to n (one of them if equidistant) *)

PROCEDURE Project (READONLY a: T; n: INTEGER): INTEGER RAISES {};
(* Return the integer in a that is closest to n. a must be non empty *)

(* --- Transformation --- *)

PROCEDURE Move (READONLY a: T; n: INTEGER): T RAISES {};
(* The interval <a.lo+n,a.hi+n> *)

PROCEDURE Inset (READONLY a: T; n: INTEGER): T RAISES {};
(* If a is empty return empty, else return <a.lo+n, a.hi-n> *)

PROCEDURE Change (READONLY a: T; dlo, dhi: INTEGER): T RAISES {};
(* If a is empty return empty, else return <a.lo+dlo, a.hi+dhi> *)

PROCEDURE MoveBound (x: Bound; READONLY a: T; dn: INTEGER): T RAISES {};
(* If r is empty return empty, else add dn to the edge x of a *)

PROCEDURE Join (READONLY a, b: T): T RAISES {};
(* the least interval including the union of the points in a and b *)

PROCEDURE Meet (READONLY a, b: T): T RAISES {};
(* the largest interval included in the intersection of a and b *)

PROCEDURE Chop (READONLY a: T; n: INTEGER; VAR (* out *) b, c: T) RAISES {};
(* Chop an interval in two; b is to the left of c *)

TYPE Partition = ARRAY [0..2] OF T;

PROCEDURE Factor (READONLY a, by: T; VAR (*out*) f: Partition; dn: INTEGER)
  RAISES {};
(* a is partitioned into 3 pieces f[0]..f[2], where f[1] = Meet (a,by). The
   order of f is such that if i<j then f[i] translated by dn doesn't intersect
   f[j]. (Only the sign of dn affects the order, not its magnitude.) *)

PROCEDURE Mod (n: INTEGER; READONLY a: T): INTEGER RAISES {};
(* Return the member of a whose distance from n is a multiple of the size of
   a. a must be non-empty *)

(* --- Test --- *)

PROCEDURE Equal (READONLY a, b: T): BOOLEAN RAISES {};
(* Interval equality; all empty intervals are equal *)

PROCEDURE IsEmpty (READONLY a: T): BOOLEAN RAISES {}; (* Whether a is empty *)

PROCEDURE Member (n: INTEGER; READONLY a: T): BOOLEAN RAISES {};
(* whether an integer is in an interval *)

PROCEDURE Overlap (READONLY a, b: T): BOOLEAN RAISES {};
(* whether two intervals overlap *)

PROCEDURE Subset (READONLY a, b: T): BOOLEAN RAISES {};
(* whether a is a subset of b *)

(* --- Standard type operations --- *)

PROCEDURE New (READONLY value: T): REF T;
(* Allocates and initializes a new heap value *)

PROCEDURE NewArray (size: CARDINAL;  READONLY value := Empty): REF ARRAY OF T;
(* Allocates a new array from the heap
  and initializes all its elements with the given value *)

PROCEDURE UntracedNew (READONLY value: T): UNTRACED REF T;
(* Allocates and initializes a new untraced value *)

PROCEDURE UntracedNewArray (size: CARDINAL;  READONLY value := Empty):
                                                       UNTRACED REF ARRAY OF T;
(* Allocates a new untraced array from the heap
  and initializes all its elements with the given value *)

PROCEDURE Compare (READONLY a, b: T): INTEGER;
(* == RETURN (-1 if Lt (a, b), 0 if Eq (a, b), +1 o. w.) *)

PROCEDURE Lt (READONLY a, b: T): BOOLEAN;
(* == RETURN (a.lo < b.lo) OR ((a.lo = b.lo) AND (a.hi < b.hi)) *)

PROCEDURE Eq (READONLY a, b: T): BOOLEAN;
(* == RETURN (a = b) *)

PROCEDURE Hash (READONLY a: T): INTEGER;
(* == RETURN a suitable hash value  *)

END Interval.