-- This file is  free  software, which  comes  along  with  SmartEiffel. 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-2002 LORIA - INRIA - U.H.P. Nancy 1 - FRANCE
--          Dominique COLNET and Suzanne COLLIN - SmartEiffel@loria.fr
--                       http://SmartEiffel.loria.fr
--
class ARRAY[E]
   --
   -- General purpose resizable ARRAYs.
   --

inherit ARRAYED_COLLECTION[E]

creation make, with_capacity, from_collection

feature

   lower: INTEGER
         -- Lower index bound.

feature -- Creation and Modification:

   make(min_index, max_index: INTEGER) is
         -- Prepare the array to hold values for indexes in range
	 -- [`min_index' .. `max_index']. Set all values to default.
         -- When `max_index' = `min_index' - 1, the array `is_empty'.
      require
         valid_bounds: min_index <= max_index + 1
      local
         needed: INTEGER
      do
         lower := min_index
         upper := max_index
         needed := max_index - min_index + 1
         if needed > 0 then
            if capacity < needed then
               storage := storage.calloc(needed)
               capacity := needed
            else
               clear_all
            end
         end
      ensure
         lower_set: lower = min_index
         upper_set: upper = max_index
         items_set: all_default
      end

   with_capacity(needed_capacity, low: INTEGER) is
         -- Create an empty array with `capacity' initialized
         -- at least to `needed_capacity' and `lower' set to `low'.
      require
         needed_capacity >= 0
      do
         if capacity < needed_capacity then
            storage := storage.calloc(needed_capacity)
            capacity := needed_capacity
         end
         lower := low
         upper := low - 1
      ensure
         is_empty
         needed_capacity <= capacity
         lower = low
      end

feature -- Modification:

   resize(min_index, max_index: INTEGER) is
         -- Resize to bounds `min_index' and `max_index'. Do not lose any
         -- item whose index is in both [`lower' .. `upper'] and
         -- [`min_index' .. `max_index']. New positions if any are
         -- initialized with the appropriate default value.
      require
         min_index <= max_index + 1
      local
         needed, offset, intersize: INTEGER
      do
         needed := max_index - min_index + 1
         if needed > 0 then
            if needed > capacity then
               if capacity = 0 then
                  storage := storage.calloc(needed)
                  capacity := needed
               else
                  storage := storage.realloc(capacity, needed)
                  capacity := needed
               end
            end
            offset := lower - min_index
            intersize := max_index.min(upper) - min_index.max(lower) + 1
            if intersize > 0 then
               if offset = 0 then
                  if intersize < capacity then
                     storage.clear(intersize, capacity - 1)
                  end
               elseif offset < 0 then
                  storage.move(-offset, intersize - offset - 1, offset)
                  if intersize < capacity then
                     storage.clear(intersize, capacity - 1)
                  end
               else
                  storage.move(0, intersize - 1, offset)
                  storage.clear(0, offset - 1)
                  if intersize + offset < capacity then
                     storage.clear(intersize + offset, capacity - 1)
                  end
               end
            else
	       storage.clear(0, capacity - 1)
            end
         end
         lower := min_index
         upper := max_index
      ensure
	 lower = min_index
	 upper = max_index
      end

   reindex(new_lower: INTEGER) is
	 -- Change indexing to take in account the expected `new_lower'
	 -- index. The `upper' index is translated accordingly.
      local
	 i: INTEGER
      do
	 i := new_lower - lower
	 lower := lower + i
	 upper := upper + i
      ensure
	 lower = new_lower
	 count = old count
      end


feature -- Implementation of deferred:

   subarray(min, max: INTEGER): like Current is
      do
	 Result := slice(min,max)
	 Result.reindex(min)
      ensure then
         Result.lower = min
      end

   is_empty: BOOLEAN is
      do
         Result := upper < lower
      end

   count: INTEGER is
      do
         Result := upper - lower + 1
      end

   item, infix "@" (i: INTEGER): E is
      do
         Result := storage.item(i - lower)
      end

   put(element: like item; i: INTEGER) is
      do
         storage.put(element,i - lower)
      end

   force(element: like item; index: INTEGER) is
      require else
         true
      do
         if upper < index then
            if index = upper + 1 then
               add_last(element)
            else
               resize(lower,index)
               put(element,index)
            end
         elseif index < lower then
            resize(index,upper)
            put(element,index)
         else
            put(element,index)
         end
      ensure then
	 lower = index.min(old lower)
      end

   copy(other: like Current) is
      local
         needed_capacity: INTEGER
      do
         lower := other.lower
         upper := other.upper
         needed_capacity := upper - lower + 1
         if capacity < needed_capacity then
            storage := storage.calloc(needed_capacity)
            capacity := needed_capacity
         end
         if needed_capacity > 0 then
            storage.copy_from(other.storage,needed_capacity - 1)
         end
      end

   set_all_with(v: like item) is
      do
         storage.set_all_with(v,upper - lower)
      end

   remove_first is
      do
         storage.remove_first(upper - lower)
         lower := lower + 1
      ensure then
         upper = old upper
      end

   remove(index: INTEGER) is
      do
         storage.remove(index - lower,upper - lower)
         upper := upper - 1
      end

   clear is
      do
         upper := lower - 1
      ensure then
         capacity = old capacity
      end

   add_first(element: like item) is
      do
         if upper < lower then
            add_last(element)
         else
            add_last(element)
            move(lower,upper - 1,1)
            put(element,lower)
         end
      end

   add_last(element: like item) is
      local
         new_capacity: INTEGER
      do
         if capacity < count + 1 then
            if capacity = 0 then
               new_capacity := 16
               storage := storage.calloc(new_capacity)
               capacity := new_capacity
            else
               new_capacity := 2 * capacity
               storage := storage.realloc(capacity,new_capacity)
               capacity := new_capacity
            end
         end
         upper := upper + 1
         put(element,upper)
      end

   from_collection(model: COLLECTION[like item]) is
      local
         i, up: INTEGER
      do
         from
            with_capacity(model.count,model.lower)
            i := model.lower
            up := model.upper
            upper := up
         until
            i > up
         loop
            put(model.item(i),i)
            i := i + 1
         end
      ensure then
         lower = model.lower
         upper = model.upper
      end

   all_default: BOOLEAN is
      do
         Result := storage.all_default(upper - lower)
      end

   occurrences(element: like item): INTEGER is
      do
         Result := storage.occurrences(element,upper - lower)
      end

   fast_occurrences(element: like item): INTEGER is
      do
         Result := storage.fast_occurrences(element,upper - lower)
      end

   index_of(element: like item): INTEGER is
      do
         Result := lower + storage.index_of(element,upper - lower)
      end

   fast_index_of(element: like item): INTEGER is
      do
         Result := lower + storage.fast_index_of(element,upper - lower)
      end

   is_equal(other: like Current): BOOLEAN is
      do
         if Current = other then
            Result := true
         elseif lower = other.lower and then upper = other.upper then
            Result := storage.fast_memcmp(other.storage,count)
         end
      end

   is_equal_map(other: like Current): BOOLEAN is
      do
         if Current = other then
            Result := true
         elseif lower = other.lower and then upper = other.upper then
            Result := storage.memcmp(other.storage,count)
         end
      end

   slice(min, max: INTEGER): like Current is
      do
	 !!Result.make(lower,lower + max - min)
	 Result.storage.copy_slice(0,storage,min - lower,max - lower)
      end

   get_new_iterator: ITERATOR[E] is
      do
         !ITERATOR_ON_COLLECTION[E]!Result.make(Current)
      end

end -- ARRAY[E]