marcap@hercule.cs.concordia.ca (PAWLOWSKY) (02/08/90)
This file consists of two classes. The first is a deferred class which
defines the routines needed, and the second is a class which implements
pattern matching for a FIXED_LIST.
deferred class PATTERN_MATCHER [T]
-- This class will find patterns based on Current.
-- The reciever should inherit from this class.
--
-- These routines are made to find patterns in 1 dimensional collections.
-- Marc Andrew Pawlowsky
-- 1683063
-- Concordia University
-- Dept. Computer Science
-- Montreal, Quebec
-- Canada
-- CLOSED: 08 AUG 89
-- BUGS:
-- Might not work with characters, due to bug in Eiffel 2.1. Known
-- fix is to inherit STD_FILES. (Why this works is unkown.)
export
do_not_care, wild_card, find
feature
i_th(i:INTEGER):T is
-- the i-th member of the collection
require
i_positive: i > 0
deferred
end; -- i_th
count:INTEGER is
-- the number of members in the collection
deferred
ensure
Result >= 0
end; -- count
do_not_care: T;
-- Skip 1 position when this is occurs
wild_card: T;
-- Skip as many positions as needed when this occurs
-- This may be 1 or more positions.
find(match:LIST[T], i:INTEGER):INTEGER is
-- Return the index of where Current cound be found in match
-- Start the search at the i-th position of match
--
-- Return 0 if Current does not occur in match
--
-- test between elements is done with Equal
require
i_positive: i > 0;
local
matches: BOOLEAN;
do
-- try finding match for every position >= i
from
matches := false;
Result := i;
variant
match.count - Result + 1
until
matches or (Result > (match.count - Current.count + 1))
loop
matches := Current.find2(match, 1, Result);
Result := Result + 1;
end; -- loop
if not matches then
Result := 0;
else
Result := Result - 1;
end;
ensure
Result >= 0;
end; -- find
find2(match:LIST[T], start:INTEGER, i:INTEGER):BOOLEAN is
-- Return whether Current[start,Current.length] starts at the i-th position
-- in match
-- test between elements is done with Equal
require
start_positive: start > 0;
i_positive: i > 0;
local
j: INTEGER;
do
if start > Current.count then
Result := true;
-- all items have been matched
else
if (Current.count - start) > (match.count - i) then
-- there are more things to match then there are places
Result := false;
else
if Current.i_th(start) = (do_not_care) then
-- go to next position
Result := Current.find2(match, start+1, i+1);
else
if Current.i_th(start) = (wild_card) then
-- try matching for each position > i
from
Result := false;
j := i + 1;
variant
match.count - j + 1
until
Result or (j > match.count)
loop
Result := Current.find2(match, start+1, j);
j := j + 1;
end; -- loop
else
-- the normal members
if Current.i_th(start) = (match.i_th(i)) then
Result := Current.find2(match, start+1, i+1);
else
Result := false;
end; -- if
end; -- if
end; -- if
end; -- if
end; -- if
end; -- find2
end -- PATTERN_MATCHER
--
-- MODIFICATION HISTORY
--
-- 03 FEB 90 -- updated obsolete features from Eiffel 2.1 to 2.2
class PATTERN_FIXED_LIST[T]
-- A fixed-list that can be searched for patterns with wild cards.
-- Marc Andrew Pawlowsky
-- 1683063
-- Concordia University
-- Dept. Computer Science
-- Montreal, Quebec
-- Canada
-- CLOSED: 08 AUG 89
export
do_not_care, wild_card, find,
count, empty, position, offright, offleft, isfirst,
islast, value, i_th, first, last, change_value, change_i_th,
swap, start, finish, forth, back, go, search, mark, return,
index_of, present, duplicate, wipe_out,
put_i_th
inherit
PATTERN_MATCHER[T] define count;
FIXED_LIST[T] rename i_th as j_th, nb_elements as number_of_elements
feature
Create(n:INTEGER, do_not_care_value, wild_card_value:T) is
-- Allocate list with n elements
require
at_least_one: n >= 1
do
do_not_care := do_not_care_value;
wild_card := wild_card_value;
array_create(1, n);
end; -- Create
-- work arounds to allow the proper functions to come from FIXED_LIST
i_th(i:INTEGER):T is
-- value of the i-th element
require
index_large_enough: i>= 1;
index_small_enough: i <= count;
do
Result := Current.j_th(i);
end; -- i_th
end -- PATTERN_FIXED_LIST
--
-- MODIFICATION HISTORY
--
-- 03 FEB 90 -- updated obsolete features from Eiffel 2.1 to 2.2