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

inherit LINKED_COLLECTION[E] redefine first_link end;

creation
   make, from_collection

feature {LINKED_COLLECTION}
   
   first_link: LINK2[E];

feature -- Creation and Modification :
   
   make is
      -- Make an empty list;
      do
	 first_link := Void;
	 last_link := Void;
	 upper := 0;
	 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,Void);
	    last_link := first_link;
	    upper := 1;
	    mem_idx := 1;
	    mem_lnk := first_link;
	 else
	    !!first_link.make(element,Void,first_link);
	    first_link.next.set_previous(first_link);
	    upper := upper + 1;
	    mem_idx := mem_idx + 1;
	 end;
      ensure then
	 upper = 1 + old upper 
      end;

   add_last(element: like item) is
      do
	 if first_link = Void then
	    !!first_link.make(element,Void,Void);
	    last_link := first_link;
	    upper := 1;
	    mem_idx := 1;
	    mem_lnk := first_link;
	 else
	    !!last_link.make(element,last_link,Void);
	    last_link.previous.set_next(last_link);
	    upper := upper + 1;
	 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,mem_lnk.next);
	    link.next.set_previous(link);
	    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;
	    first_link.set_previous(Void);
	    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);
	    link.next.set_previous(mem_lnk);
	    upper := upper - 1;
	 end;
      end;

feature {NONE}

   go_item(index: INTEGER) is
      do
	 if index > mem_idx then
	    if (upper - index) < (index - mem_idx) then
	       from
		  mem_idx := upper;
		  mem_lnk := last_link;
	       until
		  index = mem_idx
	       loop
		  mem_lnk := mem_lnk.previous;
		  mem_idx := mem_idx - 1;
	       end;
	    else
	       from
	       until
		  index = mem_idx
	       loop
		  mem_lnk := mem_lnk.next;
		  mem_idx := mem_idx + 1;
	       end;
	    end
	 elseif (mem_idx - index) < (index - 1) then
	    from
	    until
	       index = mem_idx
	    loop
	       mem_lnk := mem_lnk.previous;
	       mem_idx := mem_idx - 1;
	    end;
	 else
	    from
	       mem_idx := 1;
	       mem_lnk := first_link;
	    until
	       index = mem_idx
	    loop
	       mem_lnk := mem_lnk.next;
	       mem_idx := mem_idx + 1;
	    end;
	 end;
      end;

end -- LINK2_LIST[E]