-- 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 COLLECTION[E]
-- 
-- Common abstract definition of a sequentiable collection of 
-- objects. Such a collection is traversable using a simple 
-- INTEGER index from `lower' to `upper'. Items can be added,
-- changed or removed.
-- 
-- The SmallEiffel standard library (lib_std) provides four
-- implementations : ARRAY[E], FIXED_ARRAY[E], LINK_LIST[E] 
-- and LINK2_LIST[E]. All implementations have exactly the 
-- same behavior. Switching from one implementation to another 
-- only change the memory used and the execution time.
--

inherit
   ANY
      undefine copy, is_equal
      redefine fill_tagged_out_memory
      end;

feature -- Indexing :

   lower: INTEGER is
	 -- Lower index bound.
      deferred
      end;

   upper: INTEGER is
	 -- Upper index bound.
      deferred
      end;

   frozen valid_index(index: INTEGER): BOOLEAN is
	 -- True when `index' is valid (ie. inside actual 
	 -- bounds of the collection).
      do
	 Result := lower <= index and then index <= upper;
      ensure      
	 Result = (lower <= index and then index <= upper);
      end;

feature -- Counting :

   count: INTEGER is
	 -- Number of elements actually stored in the collection.
      deferred
      ensure
	 Result = upper - lower + 1
      end;

   empty: BOOLEAN is
	 -- Is collection empty?
      do
	 Result := (count = 0);
      end;

feature -- Accessing :

   item, infix "@" (index: INTEGER): E is
	 -- Item at position `index'.
      require
	 valid_index(index)
      deferred
      end;

   first: like item is
	 -- The `first' item.
      require
	 count >= 1
      do
	 Result := item(lower);
      end;
   
   last: like item is
	 -- The `last' item.
      require
	 count >= 1
      do
	 Result := item(upper);
      end;

feature -- Writing :

   put(element: like item; index: INTEGER) is
	 -- Put `element' at position `index'.
      require
	 valid_index(index)
      deferred
      ensure
	 item(index) = element;
	 count = old count
      end;

   swap(i1, i2: INTEGER) is
	 -- Swap item at index `i1' with item at index `i2'.
      require
	 valid_index(i1);
	 valid_index(i2)
      local
	 tmp: like item;
      do
	 tmp := item(i1);
	 put(item(i2),i1);
	 put(tmp,i2);
      ensure
	 item(i1) = old item(i2);
	 item(i2) = old item(i1);
	 count = old count
      end;
   	 
   set_all_with(v: like item) is
	 -- Set all items with value `v'.
      deferred
      ensure
	 count = old count
      end;
   
   set_slice_with(v: like item; lower_index, upper_index: INTEGER) is
	 -- Set all items in range [`lower_index' .. `upper_index'] with `v'.
      require
	 lower_index <= upper_index;
	 valid_index(lower_index);
	 valid_index(upper_index)
      local
	 i: INTEGER;
      do
	 from  
	    i := lower_index;
	 until
	    i > upper_index
	 loop
	    put(v,i);
	    i := i + 1;
	 end;      
      ensure
	 count = old count
      end;
   
   clear_all is
	 -- Set all items to default values.
	 -- The `count' is not affected (see also `clear').
      local
	 value: like item;
      do
	 set_all_with(value);
      ensure
	 count = old count;
	 all_cleared
      end;
   
feature -- Adding :

   add_first(element: like item) is
	 -- Add a new item in first position : `count' is increased by 
	 -- one and all other items are shifted right.
      deferred
      ensure
	 first = element;
	 count = 1 + old count;
	 lower = old lower;
	 upper = 1 + old upper
      end;

   add_last(element: like item) is
	 -- Add a new item at the end : `count' is increased by one.
      deferred
      ensure
	 last = element;
	 count = 1 + old count;
	 lower = old lower;
	 upper = 1 + old upper
      end;

   add(element: like item; index: INTEGER) is
	 -- Add a new `element' at rank `index' : `count' is increased 
	 -- by one and range [`index' .. `upper'] is shifted right
	 -- by one position.
      require
	 lower <= index;
         index <= upper + 1
      deferred
      ensure
	 item(index) = element;
         count = 1 + old count;
	 upper = 1 + old upper
      end;

feature -- Modification :

   force(element: E; index: INTEGER) is
	 -- Put `element' at position `index'. Collection is
	 -- resized if `index' is not inside current bounds.
	 -- New bounds are initialized with default values.
      require
	 index >= lower
      deferred
      ensure
	 valid_index(index); 
	 item(index) = element
      end;

   from_collection(model: COLLECTION[like item]) is
      -- Initialize the current object with the contents of `model'.
      require
	 model /= Void
      deferred
      ensure
	 count = model.count;
      end;

feature -- Removing :

   remove_first is
	 -- Remove the `first' element of the collection.
      require
	 not empty
      deferred
      ensure
	 count = (old count) - 1;
         (lower = (old lower) + 1) xor (upper = (old upper) - 1) 
      end;

   remove(index: INTEGER) is
	 -- Remove the item at position `index'. Followings items
	 -- are shifted left by one position.
      require
	 valid_index(index)
      deferred
      ensure
	 count = (old count) - 1;
	 upper = (old upper) - 1;
      end;

   remove_last is
	 -- Remove the `last' item.
      require
	 not empty;
      deferred
      ensure
	 count = (old count) - 1;
	 upper = (old upper) - 1
      end;

   clear is
	 -- Discard all items in order to make it `empty'.
	 -- See also `clear_all'.
      deferred
      ensure
	 empty;
      end;

feature -- Looking and Searching :

   has(x: like item): BOOLEAN is
	 -- Look for `x' using `equal' for comparison.
	 -- Also consider `fast_has' to choose the most appropriate.
      do
	 Result := valid_index(index_of(x));
      end;
   
   fast_has(x: like item): BOOLEAN is
	 -- Look for `x' using basic `=' for comparison.
	 -- Also consider `has' to choose the most appropriate.
      do
	 Result := valid_index(fast_index_of(x));
      end;
   
   index_of(element: like item): INTEGER is
	 -- Give the index of the first occurrence of `element' using
	 -- `is_equal' for comparison.
	 -- Answer `upper + 1' when `element' is not inside.
	 -- Also consider `fast_index_of' to choose the most appropriate.
      deferred
      ensure
	 lower <= Result;
	 Result <= upper + 1;
	 Result <= upper implies equal(element,item(Result));
      end;
   
   fast_index_of(element: like item): INTEGER is
	 -- Give the index of the first occurrence of `element' using
	 -- basic `=' for comparison.
	 -- Answer `upper + 1' when `element' is not inside.
	 -- Also consider `index_of' to choose the most appropriate.
      deferred
      ensure
	 lower <= Result;
	 Result <= upper + 1;
	 Result <= upper implies element = item(Result);
      end;
   
feature -- Looking and comparison :

   all_cleared: BOOLEAN is
	 -- Are all items set to the default value ?
      deferred
      end;

   nb_occurrences(element: like item): INTEGER is
	 -- Number of occurrences of `element' using `equal' for comparison.
	 -- Also consider `fast_nb_occurences' to choose the most appropriate.
      deferred
      ensure
	 Result >= 0
      end;
      
   fast_nb_occurrences(element: like item): INTEGER is
	 -- Number of occurrences of `element' using basic `=' for comparison.
	 -- Also consider `nb_occurences' to choose the most appropriate.
      deferred
      ensure
	 Result >= 0;
      end;
      
feature -- Printing :

   frozen fill_tagged_out_memory is
      local
	 i: INTEGER;
	 v: like item;
      do
	 tagged_out_memory.append("lower: "); 
	 lower.append_in(tagged_out_memory);
	 tagged_out_memory.append(" upper: "); 
	 upper.append_in(tagged_out_memory);
	 tagged_out_memory.append(" [");
	 from  
	    i := lower;
	 until
	    i > upper or else tagged_out_memory.count > 2048
	 loop
	    v := item(i);
	    if v = Void then
	       tagged_out_memory.append("Void");
	    else
	       v.out_in_tagged_out_memory;
	    end;
	    if i < upper then
	       tagged_out_memory.extend(' ');
	    end;
	    i := i + 1;
	 end;
	 if i <= upper then
	    tagged_out_memory.append(" ..."); 
	 end;
	 tagged_out_memory.extend(']'); 
      end;

feature -- Other Features :

   replace_all(old_value, new_value: like item) is
      	 -- Replace all occurences of the element `old_value' by `new_value' 
	 -- using `equal' for comparison.
	 -- See also `fast_replace_all' to choose the apropriate one.
      deferred
      ensure
	 count = old count;
	 nb_occurrences(old_value) = 0
      end;
   
   fast_replace_all(old_value, new_value: like item) is
      	 -- Replace all occurences of the element `old_value' by `new_value' 
	 -- using operator `=' for comparison.
	 -- See also `replace_all' to choose the apropriate one.
      deferred
      ensure
	 count = old count;
	 fast_nb_occurrences(old_value) = 0
      end;

   move(lower_index, upper_index, distance: INTEGER) is
	 -- Move range `lower_index' .. `upper_index' by `distance' 
	 -- positions. Negative distance moves towards lower indices.
	 -- Free places get default values.
      require
	 lower_index <= upper_index;
	 valid_index(lower_index);
	 valid_index(lower_index + distance);
	 valid_index(upper_index);
	 valid_index(upper_index + distance)
      local
	 default_value: like item;
	 i: INTEGER;
      do
	 if distance = 0 then
	 elseif distance < 0 then
	    from  
	       i := lower_index;
	    until
	       i > upper_index
	    loop
	       put(item(i),i + distance);
	       put(default_value,i);
	       i := i + 1;
	    end;
	 else
	    from  
	       i := upper_index;
	    until
	       i < lower_index
	    loop
	       put(item(i),i + distance);
	       put(default_value,i);
	       i := i - 1;
	    end;
	 end;
      ensure
	 count = old count
      end;

   slice(low, up: INTEGER): like Current is
	 -- Create a new collection initialized with elements of
	 -- range `low'..`up'. Result has the same dynamic type 
	 -- as Current collection. The `lower' index of the new 
	 -- collection is the same as `lower' of Current.
      require
	 valid_index(low);
	 valid_index(up);
	 low <= up
      deferred
      ensure
	 same_type(Result);
	 Result.count = up - low + 1;
	 Result.lower = lower
      end;

feature -- The Guru section :

   free is
	 -- Free the memory used by the Current COLLECTION (objects
	 -- pointed by the Current COLLECTION are not affected). 
	 -- Assume you don't use Current any more. 
      obsolete "Replaced by automatic Garbage Collection. %
             %Will be removed in the next release."
      deferred
      end;
   
feature {NONE}

   frozen equal_like(e1, e2: like item): BOOLEAN is
	 -- Note: this feature is called to avoid calling `equal'
	 -- on expanded types (no automatic conversion to 
	 -- corresponding reference type).
      do
	 if e1.is_basic_expanded_type then
	    Result := e1 = e2;
	 elseif e1.is_expanded_type then
	    Result := e1.is_equal(e2);
	 elseif e1 = e2 then
	    Result := true;
	 elseif e1 = Void or else e2 = Void then
	 else
	    Result := e1.is_equal(e2);
	 end;
      end;

end -- COLLECTION[E]