home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
AmigActive 3
/
AACD03.BIN
/
AACD
/
Programming
/
sofa
/
archive
/
SmallEiffel.lha
/
SmallEiffel
/
lib_std
/
collection.e
< prev
next >
Wrap
Text File
|
1999-06-05
|
13KB
|
472 lines
-- 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://SmallEiffel.loria.fr
--
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 very `first' item.
require
count >= 1
deferred
ensure
Result = item(lower)
end;
last: like item is
-- The `last' item.
require
count >= 1
deferred
ensure
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 "Since release -0.81, the Garbage Collector is %
%implemented. This feature will be soon removed."
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]