-- This file is  free  software, which  comes  along  with  SmallEiffel. This
-- software  is  distributed  in the hope that it will be useful, but WITHOUT 
-- ANY  WARRANTY;  without  even  the  implied warranty of MERCHANTABILITY or
-- FITNESS  FOR A PARTICULAR PURPOSE. You can modify it as you want, provided
-- this header is kept unaltered, and a notification of the changes is added.
-- You  are  allowed  to  redistribute  it and sell it, alone or as a part of 
-- another product.
--          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
--            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr 
--                       http://www.loria.fr/SmallEiffel
--
deferred class LINKED_COLLECTION[E]
   -- 
   -- Common root for LINK_LIST[E] and LINK2_LIST[E].
   --

inherit COLLECTION[E] redefine first, last end;

feature

   lower: INTEGER is 1;
	 -- Lower index bound is frozen.
   
feature {LINKED_COLLECTION}
   
   first_link: LINK[E];
	 -- Void when empty or gives access to the first element.

   last_link: like first_link; 
	 -- Void when empty or gives access to the last element.

   mem_idx: INTEGER; mem_lnk: like first_link; 
	 -- To speed up accessing, `mem_idx' and `mem_lnk' is the 
	 -- memory of the last access done. For example, after 
	 -- item(1), `mem_idx' is 1 and `mem_lnk' is `first_link'.
	 -- When list is empty, `first_link' is Void as well as 
	 -- `mem_lnk' and `mem_idx' is 0;
	 -- 
feature
   
   upper: INTEGER;
	 -- Memorized upper index bound.

feature -- Creation and Modification :

   make is
      -- Make an empty list;
      deferred
      end;

feature
   
   first: like item is
      do
	 Result := first_link.item;
      end;
   
   last: like item is
      do
	 Result := last_link.item;
      end;

feature -- Implementation of deferred :

   item, infix "@" (index: INTEGER): E is
      do
	 if index /= mem_idx then
	    go_item(index);
	 end;
	 Result := mem_lnk.item;
      end;
   
   put(element: like item; index: INTEGER) is
      do
	 if index /= mem_idx then
	    go_item(index);
	 end;
	 mem_lnk.set_item(element);
      end;

   count: INTEGER is
      do
	 Result := upper;
      end;

   set_all_with(v: like item) is
      do
	 if first_link /= Void then
	    first_link.set_all_with(v);
	 end;
      end;

   copy(other: like Current) is
      do
	 from_collection(other);
      end;

   is_equal(other: like Current): BOOLEAN is
      local
	 lnk1, lnk2: like first_link;
      do
	 if Current = other then
	    Result := true;
	 elseif upper = other.upper then
	    from
	       Result := true;
	       lnk1 := first_link;
	       lnk2 := other.first_link;
	    until
	       lnk1 = Void or not Result
	    loop
	       Result := equal_like(lnk1.item,lnk2.item);
	       lnk1 := lnk1.next;
	       lnk2 := lnk2.next;
	    end;	    
	 end;
      end;

   index_of(x: like item): INTEGER is
      do
	 from  
	    Result := lower;
	 until
	    (Result > upper) or else equal_like(x,item(Result))
	 loop
	    Result := Result + 1;
	 end;
      end;
   
   fast_index_of(x: like item): INTEGER is
      local
	 u: like upper;
      do
	 from
	    Result := lower;
	    u := upper;
	 until
	    (Result > u) or else x = item(Result)
	 loop
	    Result := Result + 1;
	 end;
      end;
   
   clear is
      do
	 if first_link /= Void then
	    first_link := Void;
	    mem_idx := 0;
	    mem_lnk := Void;
	    upper := 0;
	    last_link := Void;
	 end;
      ensure then
	 upper = 0
      end;

   from_collection(model: COLLECTION[like item]) is
      local
	 i, up: INTEGER;
	 lnk: like first_link;
      do
	 if first_link = Void then
	    from
	       i := model.lower;
	       up := model.upper;
	    until
	       i > up
	    loop
	       add_last(model.item(i));
	       i := i + 1;
	    end;
	 else
	    from
	       lnk := first_link;
	       i := model.lower;
	       up := model.upper;
	    until
	       i > up
	    loop
	       if lnk = Void then
		  add_last(model.item(i));
	       else
		  lnk.set_item(model.item(i));
		  lnk := lnk.next;
	       end;
	       i := i + 1;
	    end;
	    if lnk = first_link then
	       check
		  model.count = 0
	       end;
	       clear;
	    elseif lnk /= Void then
	       i := model.count;
	       if mem_idx /= i then
		  go_item(i);
	       end;
	       check
		  lnk = mem_lnk.next
	       end;
	       mem_lnk.set_next(Void);
	       upper := i;
	       last_link := mem_lnk;
	    end;
	 end;
      end;

   slice(low, up: INTEGER): like Current is
      local
	 lnk: like first_link;
	 i: INTEGER;
      do
	 from
	    !!Result.make;
	    if mem_idx /= low then
	       go_item(low);
	    end;
	    lnk := mem_lnk;
	    i := up - low + 1;
	 until
	    i = 0
	 loop
	    Result.add_last(lnk.item);
	    lnk := lnk.next;
	    i := i - 1;
	 end;
      end;

   nb_occurrences(element: like item): INTEGER is
      local
	 lnk: like first_link;
      do
	 from
	    lnk := first_link;
	 until
	    lnk = Void
	 loop
	    if equal_like(element,lnk.item) then
	       Result := Result + 1;
	    end;
	    lnk := lnk.next;
	 end;
      end;

   frozen free is 
      obsolete "Replaced by automatic Garbage Collection. %
             %Will be removed in the next release."
      do
      end;

   force(element: E; index: INTEGER) is
      local
	 v: like element;
      do
	 from
	 until
	    index <= upper
	 loop
	    add_last(v);
	 end;
	 put(element,index);
      end;

   all_cleared: BOOLEAN is
      local
	 l: like first_link;
	 d: like item;
      do
	 from
	    Result := true;
	    l := first_link;
	 until
	    not Result or else l = Void
	 loop
	    Result := d = l.item;
	    l := l.next;
	 end;
      end;

   remove_last is
      do
	 if upper = 1 then
	    make;
	 else
	    if upper - 1 /= mem_idx then
	       go_item(upper - 1);
	    end;
	    upper := upper - 1;
	    last_link := mem_lnk;
	    last_link.set_next(Void);
	 end;
      end;

   replace_all(old_value, new_value: like item) is
      local
	 i: INTEGER;
      do
	 from
	    i := lower;
	 until 
	    i > upper
	 loop
	    if equal_like(item(i),old_value) then
	       put(new_value,i);
	    end;
	    i := i + 1;
	 end;
      end;
   
   fast_replace_all(old_value, new_value: like item) is
      local
	 i: INTEGER;
      do
	 from 
	    i := lower;
	 until
	    i > upper
	 loop
	    if item(i) = old_value then
	       put(new_value, i);
	    end;
	    i := i + 1;
	 end;
      end;

feature {NONE}

   go_item(index: INTEGER) is
      require
	 valid_index(index);
	 mem_idx /= index;
      	 mem_idx > 0;
	 mem_lnk /= Void
      deferred
      ensure
	 mem_idx = index;
	 mem_lnk /= Void
      end;

invariant

   empty_status:
      first_link = Void implies 
         (last_link = Void and upper = 0 and mem_idx = 0 
	  and mem_lnk = Void);

   not_empty_status:
      first_link /= Void implies 
         (last_link /= Void and upper > 0 and mem_idx > 0 
	  and mem_lnk /= Void);
   
end -- LINKED_COLLECTION[E]