-- integer set (linked list in decreasing order) by R J Botting, CSUSB
with Text_io; use Text_io;
package body INTEGER_SETS is
  -- The elements are kept in decreasing order with no duplicates
  -- For all S, S=empty or S.first>S.rest.first>S.rest.rest.first>...
  -- by R J Botting, CSUSB
 
 -- INTEGER_SET is access DATA and NULL_SET=INTEGER_SET(NULL).
 -- In this package "=" is often the Package's own "=" operation!
 
  package IIO is new Text_IO.Integer_io(integer); --need integer output
  use iio;
 
  type DATA is record
	FIRST:INTEGER;
	REST:INTEGER_SET:=NULL;
  end record;
 
  function Empty(ISIN:INTEGER_SET) return boolean is
	DUMMY:INTEGER;
  begin 
	--notice that we can NOT use `ISIN=NULL` since this uses "=".
	DUMMY:=ISIN.FIRST; --exception if empty
	return false;
  exception
	when CONSTRAINT_ERROR=>return true;
  end Empty;
 
 
  function EQ(I:INTEGER; T:INTEGER_SET) return boolean is
		 -- T.first exists and equals I
  begin
    return not Empty(T) and then T.FIRST=I;
  end EQ;
 
  function FIND(I:INTEGER; S:INTEGER_SET) return INTEGER_SET is
		--find position in S, just  before place for I
    T1: INTEGER_SET; T2: INTEGER_SET;
  begin  --AFTER: if Empty(S) then T1=NULL
    --  if S={J} then T1=(FIRST=>J, rest=>NULL)
    --       else T1/=NULL/=T1.rest and 
    --          T1.FIRST > I >= T1.rest.FIRST 
    T1:=S; T2:=T1;
    while not Empty(T2) and then I<T2.FIRST loop --I<T2.FIRST
      T1:=T2; -- I<T1.FIRST
      T2:=T2.REST;  -- I<T1.FIRST and T1.REST=T2
    end loop;-- T2=NULL or I>=T2.rest.first and I<T1.FIRST and T1.rest=T2
    return T1;
  end FIND;
 
 
  function Member(I:INTEGER; ISIN:INTEGER_SET) return boolean is
	T:INTEGER_SET;
  begin
    if Empty(ISIN) then return false; 
    else T:=ISIN; T:=Find(I, T);
      if Empty(T.REST) then return I=T.FIRST;
      else return EQ(I,T.REST);
      end if;
    end if;
  end Member;
 
  function "="(LEFT,RIGHT:INTEGER_SET) return Boolean is
		-- L empty	R empty		L=R
		-------------------------------------
		-- True		True		True
		-- True		False		False
		-- False	True		False
		-- False	False		???
		-------------------------------------
	LE:Boolean:=Empty(LEFT); RE:BOOLEAN:=Empty(RIGHT);
  begin 
	if LE or RE then return LE and RE;
	else return LEFT.FIRST=RIGHT.FIRST 
		and then LEFT.REST=RIGHT.REST; --recursion!
	end if;
  end;
 
  function Full(ISIN:INTEGER_SET) return boolean is
  begin return false;
  end Full;
 
  procedure Make_Empty(S:out INTEGER_SET) is -- after S=NULL_SET
  begin S:=NULL;
  end;
 
  procedure Getmax(I:out INTEGER; FROM:in out INTEGER_SET) is
  begin 
    if Empty(FROM) then raise EMPTY_GET;
    end if;
    I:=FROM.FIRST;  FROM:=FROM.REST;
  end Getmax;
 
 
  procedure Get(I:out INTEGER; FROM:in out INTEGER_SET) is
  begin Getmax(I,FROM);
  end GET;
 
  procedure Getmin(I:out INTEGER; FROM:in out INTEGER_SET) is
    T1,T2:INTEGER_SET;
  begin 
    if Empty(FROM) then raise EMPTY_GET;
    end if;
 
    T1:=FROM; 
    if Empty(T1.REST) then
      I:=T1.FIRST; FROM:=NULL_SET;
    else
      T2:=T1.REST;
      while not Empty(T2.REST) loop T1:=T2;  T2:=T2.REST;
      end loop;
      I:=T2.FIRST;  T1.REST:=null;
    end if;
  end Getmin;
 
  procedure Put(S:in INTEGER_SET) is
    T:INTEGER_SET;
  begin
    Put("{");
    if not Empty(S) then
      T:=S;
      while Not Empty(T) loop
        Put(T.FIRST);
        if not Empty(T.REST) then Put(", ");
        end if;
        T:=T.REST;
      end loop;
    end if;
    Put("}");
  end Put;
 
 
  procedure Put(I:INTEGER; INTO:in out INTEGER_SET) is
    T1,T2:INTEGER_SET;
  begin
    if empty(INTO) then
      INTO:=new DATA'(FIRST=>I, REST=>null);
    elsif INTO.FIRST = I then null; -- I is already in the set
    elsif INTO.FIRST < I then       -- I belongs at the start of the set
      INTO:=new DATA'(FIRST=>I, REST=>INTO);
    else 		      	    -- need to find T1 before place for I
      T1:=INTO; T1:=FIND(I,T1);  T2:=T1.REST;
      if not EQ(I,T2) then
        T1.REST:=new DATA'(FIRST=>I, REST=>T2);
      end if;
    end if;
  end;
 
  procedure Take(I:INTEGER; FROM:in out INTEGER_SET) is
    T1,T2:INTEGER_SET;
  begin if Empty(FROM) then null;
    elsif FROM.FIRST=I then
      FROM:=INTEGER_SET(FROM.REST);
    else
      T1:=FROM; T2:=T1.REST;
      while not Empty(T2) and then I<T2.FIRST loop
        T1:=T2; T2:=T2.REST;
      end loop; -- T1.REST=T2 and (T2=NULL or T2.FIRST<=I)
 
      if EQ(I, T2) then
        T1.REST:=T2.REST;
      end if;
    end if;
  end Take;
 
 
  function Max(S:INTEGER_SET) return INTEGER is
  begin if Empty(S) then raise EMPTY_GET; end if;
 
    return S.FIRST;
  end Max;
 
  function Min(S:INTEGER_SET) return INTEGER is
    T:INTEGER_SET;
  begin if Empty(S) then raise EMPTY_GET; end if;
    T:=S;
 
    while not Empty(T.REST) loop
      T:=T.REST;
    end loop;
 
    return T.FIRST;
  end Min;
 
 
end INTEGER_SETS;