-- 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
--
class LINK_LIST[E]
   -- 
   -- One way linked list with internal automatic memorization of
   -- the last access.
   --

inherit LINKED_COLLECTION[E];

creation
   make, from_collection

feature

feature -- Creation and Modification :
   
   make is
      -- Make an empty list;
      do
	 first_link := Void;
	 upper := 0;
	 last_link := Void;
	 mem_idx := 0;
	 mem_lnk := Void;
      ensure
	 count = 0
      end;

feature -- Implementation of deferred :

   add_first(element: like item) is
      do
	 if first_link = Void then
	    !!first_link.make(element,Void);
	    upper := 1;
	    last_link := first_link;
	    mem_idx := 1;
	    mem_lnk := first_link;
	 else 
	    !!first_link.make(element,first_link);
	    upper := upper + 1;
	    mem_idx := mem_idx + 1;
	 end;
      end;

   add_last(element: like item) is
      local
	 lnk: like first_link;
      do
	 if first_link = Void then
	    !!first_link.make(element,Void);
	    upper := 1;
	    last_link := first_link;
	    mem_idx := 1;
	    mem_lnk := first_link;
	 else
	    !!lnk.make(element,Void);
	    last_link.set_next(lnk);
	    upper := upper + 1;
	    last_link := lnk;
	 end;
      end;
   
   add(element: like item; index: INTEGER) is
      local
	 link: like first_link;
      do
	 if index = 1 then
	    add_first(element);
	 elseif index = upper + 1 then
	    add_last(element);
	 else
	    if (index - 1) /= mem_idx then
	       go_item(index - 1);
	    end;
	    !!link.make(element,mem_lnk.next);
	    mem_lnk.set_next(link);
	    upper := upper + 1;
	 end;
      end;

   remove_first is
      do
	 if upper = 1 then
	    make;
	 else
	    mem_lnk := first_link;
	    first_link := first_link.next;
	    mem_lnk := first_link;
	    mem_idx := 1;
	    upper := upper - 1;
	 end;
      end;

   remove(index: INTEGER) is
      local
	 link: like first_link;
      do
	 if index = 1 then
	    remove_first;
	 elseif index = upper then
	    remove_last;
	 else
	    if (index - 1) /= mem_idx then
	       go_item(index - 1);
	    end;
	    link := mem_lnk.next;
	    mem_lnk.set_next(link.next);
	    upper := upper - 1;
	 end;
      end;

feature {NONE}

   go_item(i: INTEGER) is
      do
	 if mem_idx > i then
	    mem_idx := 1;
	    mem_lnk := first_link;
	 end;
	 from
	 until
	    i = mem_idx
	 loop
	    mem_lnk := mem_lnk.next;
	    mem_idx := mem_idx + 1;
	 end;
      end;

end -- LINK_LIST[E]