-- ordered sets (linked list in decreasing order) by R J Botting, CSUSB
with Text_io; use Text_io;
with IIO; use IIO;
--generic type ELEMENT is private; with "<" and Put.
package body ORDERED_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
 
 -- OSET is access DATA and NULL_SET=OSET(NULL).
 
  type DATA is record
	FIRST:ELEMENT;
	REST:OSET:=NULL;
  end record;
 
  procedure Empty(S:out OSET) is
  begin S:=NULL;
  end;
 
  function EQ(I:ELEMENT; T:OSET) return boolean is
  begin
    return T/=null and then T.FIRST=I;
  end EQ;
 
  function FIND(I:ELEMENT; S:OSET) return OSET is--before place for I
    T1: OSET; T2: OSET;
  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 T2/=null 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 Empty(ISIN:OSET) return boolean is
  begin 
	return ISIN=NULL;
  end Empty;
 
  function Member(I:ELEMENT; ISIN:OSET) return boolean is
	T:OSET;
  begin
    if Empty(ISIN) then return false; 
    else T:=ISIN; T:=Find(I, T);
      if T.REST=NULL then return I=T.FIRST;
      else return EQ(I,T.REST);
      end if;
    end if;
  end Member;
 
 
  function Full(ISIN:OSET) return boolean is
  begin return false;
  end Full;
 
 
  procedure Getmax(I:out ELEMENT; FROM:in out OSET) is
  begin 
    if Empty(FROM) then raise EMPTY_GET;
    end if;
    I:=FROM.FIRST;  FROM:=FROM.REST;
  end Getmax;
 
 
  procedure Get(I:out ELEMENT; FROM:in out OSET) is
  begin Getmax(I,FROM);
  end GET;
 
  procedure Getmin(I:out ELEMENT; FROM:in out OSET) is
    T1,T2:OSET;
  begin 
    if Empty(FROM) then raise EMPTY_GET;
    end if;
 
    T1:=FROM; 
    if T1.REST=null then
      I:=T1.FIRST; FROM:=NULL_SET;
    else
      T2:=T1.REST;
      while T2.REST/=null loop T1:=T2;  T2:=T2.REST;
      end loop;
      I:=T2.FIRST;  T1.REST:=null;
    end if;
  end Getmin;
 
  procedure Put(S:in OSET) is
    T:OSET;
  begin
    Put("{");
    if S/=NULL then
      T:=S;
      while T/=null loop
        Put(T.FIRST);
        if T.REST/=null then Put(", ");
        end if;
        T:=T.REST;
      end loop;
    end if;
    Put("}");
  end Put;
 
 
  procedure Put(I:ELEMENT; INTO:in out OSET) is
    T1,T2:OSET;
  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:ELEMENT; FROM:in out OSET) is
    T1,T2:OSET;
  begin if Empty(FROM) then null;
    elsif FROM.FIRST=I then
      FROM:=OSET(FROM.REST);
    else
      T1:=FROM; T2:=T1.REST;
      while T2/=null 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:OSET) return ELEMENT is
  begin if Empty(S) then raise EMPTY_GET; end if;
 
    return S.FIRST;
  end Max;
 
  function Min(S:OSET) return ELEMENT is
    T:OSET;
  begin if Empty(S) then raise EMPTY_GET; end if;
    T:=S;
 
    while T.REST/=null loop
      T:=T.REST;
    end loop;
 
    return T.FIRST;
  end Min;
 
 
end ORDERED_SETS;