indexing
description: "Deterministic finite automata"
legal: "See notice at end of class."
status: "See notice at end of class."
date: "$Date: 2006-01-22 18:25:44 -0800 (Sun, 22 Jan 2006) $"
revision: "$Revision: 56675 $"
class interface
FIXED_DFA
create
make (i, s: INTEGER_32)
`i'
`s'
feature
make (i, s: INTEGER_32)
`i'
`s'
fixed_make (i, s: INTEGER_32)
`s'
`i'
FIXED_AUTOMATON
require FIXED_AUTOMATON
s_large_enough: s > 0
i_large_enough: i >= 0
array_make (min_index, max_index: INTEGER_32)
`min_index'`max_index'
`min_index'`max_index'
ARRAY
require ARRAY
valid_bounds: min_index <= max_index + 1
ensure ARRAY
lower_set: lower = min_index
upper_set: upper = max_index
items_set: all_default
make_from_array (a: ARRAY [STATE_OF_DFA])
`a'
`ARRAY'
ARRAY
require ARRAY
array_exists: a /= Void
make_from_cil (na: NATIVE_ARRAY [like item])
`na'
ARRAY
require ARRAY
is_dotnet: {PLATFORM}.is_dotnet
na_not_void: na /= Void
feature
area: SPECIAL [STATE_OF_DFA]
TO_SPECIAL
entry (i: INTEGER_32): STATE_OF_DFA
`i'
ARRAY
require ARRAY
valid_key: valid_index (i)
find_successor (source, input_doc: INTEGER_32): STATE_OF_DFA
`input_doc'
require DFA
True
require else
source_in_automaton: source >= 1 and source <= nb_states
possible_input_doc: input_doc >= 0 and input_doc <= greatest_input
generating_type: STRING_8
ANY
generator: STRING_8
ANY
greatest_input: INTEGER_32
AUTOMATON
has (v: STATE_OF_DFA): BOOLEAN
`v'
object_comparison
ARRAY
ensure CONTAINER
not_found_in_empty: Result implies not is_empty
possible_tokens (l: LINKED_LIST [INTEGER_32]): ARRAY [INTEGER_32]
`final_array'
`l'
DFA
recognize (l: LINKED_LIST [INTEGER_32]): INTEGER_32
`final'
`l'
DFA
start_number: INTEGER_32
AUTOMATON
infix "@" (i: INTEGER_32): STATE_OF_DFA assign put
`i'
ARRAYitem
ARRAY
require TABLE
valid_key: valid_index (i)
require TO_SPECIAL
valid_index: valid_index (i)
feature {ANY}
item alias "[]" (i: INTEGER_32): STATE_OF_DFA assign put
`i'
ARRAYinfix "@"
ARRAY
require TABLE
valid_key: valid_index (i)
require TO_SPECIAL
valid_index: valid_index (i)
last_position: INTEGER_32
FIXED_AUTOMATON
feature
additional_space: INTEGER_32
RESIZABLE
ensure RESIZABLE
at_least_one: Result >= 1
capacity: INTEGER_32
ARRAYcount
ARRAY
require BOUNDED
True
ensure then ARRAY
consistent_with_bounds: Result = upper - lower + 1
count: INTEGER_32
ARRAYcapacity
ARRAY
require FINITE
True
ensure then ARRAY
consistent_with_bounds: Result = upper - lower + 1
growth_percentage: INTEGER_32 is 50
RESIZABLE
index_set: INTEGER_INTERVAL
ARRAY
require INDEXABLE
True
ensure INDEXABLE
not_void: Result /= Void
ensure then ARRAY
same_count: Result.count = count
same_bounds: ((Result.lower = lower) and (Result.upper = upper))
minimal_increase: INTEGER_32 is 5
RESIZABLE
nb_states: INTEGER_32
AUTOMATON
occurrences (v: STATE_OF_DFA): INTEGER_32
`v'
ARRAY
ensure BAG
non_negative_occurrences: Result >= 0
feature {ANY}
lower: INTEGER_32
ARRAY
feature {ANY}
upper: INTEGER_32
ARRAY
feature
frozen deep_equal (some: ANY; other: like arg #1): BOOLEAN
`some'`other'
ANY
ensure ANY
shallow_implies_deep: standard_equal (some, other) implies Result
both_or_none_void: (some = Void) implies (Result = (other = Void))
same_type: (Result and (some /= Void)) implies some.same_type (other)
symmetric: Result implies deep_equal (other, some)
frozen equal (some: ANY; other: like arg #1): BOOLEAN
`some'`other'
ANY
ensure ANY
definition: Result = (some = Void and other = Void) or else ((some /= Void and other /= Void) and then some.is_equal (other))
is_equal (other: like Current): BOOLEAN
`other'
ARRAY
require ANY
other_not_void: other /= Void
ensure ANY
symmetric: Result implies other.is_equal (Current)
consistent: standard_is_equal (other) implies Result
frozen standard_equal (some: ANY; other: like arg #1): BOOLEAN
`some'`other'
ANY
ensure ANY
definition: Result = (some = Void and other = Void) or else ((some /= Void and other /= Void) and then some.standard_is_equal (other))
frozen standard_is_equal (other: like Current): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
ensure ANY
same_type: Result implies same_type (other)
symmetric: Result implies other.standard_is_equal (Current)
feature
all_default: BOOLEAN
ARRAY
ensure ARRAY
definition: Result = (count = 0 or else ((item (upper) = Void or else item (upper) = item (upper).default) and subarray (lower, upper - 1).all_default))
changeable_comparison_criterion: BOOLEAN
object_comparison
CONTAINER
conforms_to (other: ANY): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
extendible: BOOLEAN
ARRAY
full: BOOLEAN
ARRAY
require BOX
True
is_empty: BOOLEAN
FINITE
require CONTAINER
True
is_inserted (v: STATE_OF_DFA): BOOLEAN
`v'
`has (v)'
COLLECTION
object_comparison: BOOLEAN
equal`='
`='
CONTAINER
prunable: BOOLEAN
ARRAY
resizable: BOOLEAN
capacity
RESIZABLE
same_items (other: like Current): BOOLEAN
`other'
ARRAY
require ARRAY
other_not_void: other /= Void
ensure ARRAY
definition: Result = ((count = other.count) and then (count = 0 or else (item (upper) = other.item (other.upper) and subarray (lower, upper - 1).same_items (other.subarray (other.lower, other.upper - 1)))))
same_type (other: ANY): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
ensure ANY
definition: Result = (conforms_to (other) and other.conforms_to (Current))
valid_index (i: INTEGER_32): BOOLEAN
`i'
ARRAY
require TABLE
True
require TO_SPECIAL
True
ensure then INDEXABLE
only_if_in_index_set: Result implies ((i >= index_set.lower) and (i <= index_set.upper))
valid_index_set: BOOLEAN
ARRAY
feature
compare_objects
equal
`='
CONTAINER
require CONTAINER
changeable_comparison_criterion: changeable_comparison_criterion
ensure CONTAINER
object_comparison
compare_references
`='
equal
CONTAINER
require CONTAINER
changeable_comparison_criterion: changeable_comparison_criterion
ensure CONTAINER
reference_comparison: not object_comparison
f_set_final (state, f: INTEGER_32)
`state'`final'`f'
FIXED_AUTOMATON
require FIXED_AUTOMATON
is_in_automaton: state <= upper and state >= lower
set_final (state, f: INTEGER_32)
`state'`f'
set_start (n: INTEGER_32)
`n'
AUTOMATON
require AUTOMATON
no_other_start: start_number = 0 or start_number = n
is_in_automaton: n <= nb_states and n >= 1
set_state
set_transition (source, input_doc, target: INTEGER_32)
`source'`target'`input_doc'
require AUTOMATON
True
require else DFA
source_in_automaton: source >= 1 and source <= nb_states
target_in_automaton: target >= 1 and target <= nb_states
possible_input_doc: input_doc >= 0 and input_doc <= greatest_input
require else
source_in_automaton: source >= 1 and source <= nb_states
target_in_automaton: target >= 1 and target <= nb_states
possible_input_doc: input_doc >= 0 and input_doc <= greatest_input
feature {ANY}
add_right (s: STATE_OF_DFA)
`s'
FIXED_AUTOMATON
require FIXED_AUTOMATON
not_full: last_position < count
put (v: like item; i: INTEGER_32)
`i'`v'
ARRAY
require TABLE
valid_key: valid_index (i)
require TO_SPECIAL
valid_index: valid_index (i)
ensure then INDEXABLE
insertion_done: item (i) = v
ensure TO_SPECIAL
inserted: item (i) = v
feature
enter (v: like item; i: INTEGER_32)
`i'`v'
ARRAY
require ARRAY
valid_key: valid_index (i)
fill (other: CONTAINER [STATE_OF_DFA])
`other'
`other'
COLLECTION
require COLLECTION
other_not_void: other /= Void
extendible: extendible
force (v: like item; i: INTEGER_32)
`v'`i'
`i'
ARRAY
ensure ARRAY
inserted: item (i) = v
higher_count: count >= old count
subcopy (other: ARRAY [like item]; start_pos, end_pos, index_pos: INTEGER_32)
`other'`start_pos'`end_pos'
`index_pos'
ARRAY
require ARRAY
other_not_void: other /= Void
valid_start_pos: other.valid_index (start_pos)
valid_end_pos: other.valid_index (end_pos)
valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
valid_index_pos: valid_index (index_pos)
enough_space: (upper - index_pos) >= (end_pos - start_pos)
feature
clear_all
ARRAY
ensure ARRAY
stable_lower: lower = old lower
stable_upper: upper = old upper
default_items: all_default
discard_items
ARRAY
ensure ARRAY
default_items: all_default
prune_all (v: STATE_OF_DFA)
`v'
object_comparison
COLLECTION
require COLLECTION
prunable: prunable
ensure COLLECTION
no_more_occurrences: not has (v)
feature
automatic_grow
Growth_percentage
RESIZABLE
ensure RESIZABLE
increased_capacity: capacity >= old capacity + old capacity * growth_percentage // 100
conservative_resize (min_index, max_index: INTEGER_32)
`min_index'`max_index'
ARRAY
require ARRAY
good_indices: min_index <= max_index
ensure ARRAY
no_low_lost: lower = min_index or else lower = old lower
no_high_lost: upper = max_index or else upper = old upper
grow (i: INTEGER_32)
`i'
ARRAY
ensure RESIZABLE
new_capacity: capacity >= i
feature
linear_representation: LINEAR [STATE_OF_DFA]
ARRAY
to_c: ANY
ARRAY
require ARRAY
not_is_dotnet: not {PLATFORM}.is_dotnet
to_cil: NATIVE_ARRAY [STATE_OF_DFA]
ARRAY
require ARRAY
is_dotnet: {PLATFORM}.is_dotnet
ensure ARRAY
to_cil_not_void: Result /= Void
to_special: SPECIAL [STATE_OF_DFA]
ARRAY
ensure ARRAY
to_special_not_void: Result /= Void
feature
copy (other: like Current)
`other'
clone
ARRAY
require ANY
other_not_void: other /= Void
type_identity: same_type (other)
ensure ANY
is_equal: is_equal (other)
ensure then ARRAY
equal_areas: area.is_equal (other.area)
frozen deep_copy (other: like Current)
copy`other'deep_twin
ANY
require ANY
other_not_void: other /= Void
ensure ANY
deep_equal: deep_equal (Current, other)
frozen deep_twin: like Current
ANY
ensure ANY
deep_equal: deep_equal (Current, Result)
frozen standard_copy (other: like Current)
`other'
ANY
require ANY
other_not_void: other /= Void
type_identity: same_type (other)
ensure ANY
is_standard_equal: standard_is_equal (other)
frozen standard_twin: like Current
`other'
ANY
ensure ANY
standard_twin_not_void: Result /= Void
equal: standard_equal (Result, Current)
subarray (start_pos, end_pos: INTEGER_32): ARRAY [STATE_OF_DFA]
`start_pos'`end_pos'
ARRAY
require ARRAY
valid_start_pos: valid_index (start_pos)
valid_end_pos: end_pos <= upper
valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
ensure ARRAY
lower: Result.lower = start_pos
upper: Result.upper = end_pos
frozen twin: like Current
`Current'
twincopycopy
ANY
ensure ANY
twin_not_void: Result /= Void
is_equal: Result.is_equal (Current)
feature
frozen default: like Current
ANY
frozen default_pointer: POINTER
`POINTER'
`p'default
`p'`POINTER'
ANY
default_rescue
ANY
frozen do_nothing
ANY
feature
do_all (action: PROCEDURE [ANY, TUPLE [STATE_OF_DFA]])
`action'
`action'
ARRAY
require ARRAY
action_not_void: action /= Void
do_if (action: PROCEDURE [ANY, TUPLE [STATE_OF_DFA]]; test: FUNCTION [ANY, TUPLE [STATE_OF_DFA], BOOLEAN])
`action'`test'
`action'`test'
ARRAY
require ARRAY
action_not_void: action /= Void
test_not_void: test /= Void
for_all (test: FUNCTION [ANY, TUPLE [STATE_OF_DFA], BOOLEAN]): BOOLEAN
`test'
ARRAY
require ARRAY
test_not_void: test /= Void
there_exists (test: FUNCTION [ANY, TUPLE [STATE_OF_DFA], BOOLEAN]): BOOLEAN
`test'
ARRAY
require ARRAY
test_not_void: test /= Void
feature
io: STD_FILES
ANY
out: STRING_8
ANYtagged_out
ANY
print (some: ANY)
`some'
ANY
frozen tagged_out: STRING_8
ANYout
ANY
trace
feature
operating_environment: OPERATING_ENVIRONMENT
ANY
invariant
ANY
reflexive_equality: standard_is_equal (Current)
reflexive_conformance: conforms_to (Current)
ARRAY
area_exists: area /= Void
consistent_size: capacity = upper - lower + 1
non_negative_count: count >= 0
index_set_has_same_count: valid_index_set
RESIZABLE
increase_by_at_least_one: minimal_increase >= 1
BOUNDED
valid_count: count <= capacity
full_definition: full = (count = capacity)
FINITE
empty_definition: is_empty = (count = 0)
non_negative_count: count >= 0
INDEXABLE
index_set_not_void: index_set /= Void
indexing
copyright: "Copyright (c) 1984-2006, Eiffel Software and others"
license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
source: "[
Eiffel Software
356 Storke Road, Goleta, CA 93117 USA
Telephone 805-685-1006, Fax 805-685-6869
Website http://www.eiffel.com
Customer support http://support.eiffel.com
]"
end FIXED_DFA