indexing
description: "[
Sets whose items may be compared according to a partial order relation
implemented as sorted two-way lists.
]"
legal: "See notice at end of class."
status: "See notice at end of class."
names: sorted_set, set, two_way_list
representation: linked
access: membership, min, max
contents: generic
date: "$Date: 2006-01-22 18:25:44 -0800 (Sun, 22 Jan 2006) $"
revision: "$Revision: 56675 $"
class interface
PART_SORTED_SET [G -> PART_COMPARABLE]
create
make
LINKED_LIST
ensure LINKED_LIST
is_before: before
create {PART_SORTED_SET}
make_sublist (first_item, last_item: like first_element; n: INTEGER_32)
TWO_WAY_LIST
feature
generating_type: STRING_8
ANY
generator: STRING_8
ANY
has (v: G): BOOLEAN
`v'
object_comparison
PART_SORTED_LIST
require CONTAINER
True
ensure CONTAINER
not_found_in_empty: Result implies not is_empty
index: INTEGER_32
LINKED_LIST
require LINEAR
True
require LINEAR_SUBSET
True
item: G
LINKED_LIST
require TRAVERSABLE
not_off: not off
require ACTIVE
readable: readable
require TRAVERSABLE_SUBSET
not_off: not off
feature
count: INTEGER_32
LINKED_LIST
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)
disjoint (other: TRAVERSABLE_SUBSET [G]): BOOLEAN
`other'
TRAVERSABLE_SUBSET
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
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'
LIST
require ANY
other_not_void: other /= Void
ensure ANY
symmetric: Result implies other.is_equal (Current)
consistent: standard_is_equal (other) implies Result
ensure then LIST
indices_unchanged: index = old index and other.index = old other.index
true_implies_same_size: Result implies count = other.count
is_subset (other: TRAVERSABLE_SUBSET [G]): BOOLEAN
`other'
TRAVERSABLE_SUBSET
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
is_superset (other: SUBSET [G]): BOOLEAN
`other'
SUBSET
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
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
after: BOOLEAN
LINKED_LIST
before: BOOLEAN
LINKED_LIST
changeable_comparison_criterion: BOOLEAN
object_comparison
CONTAINER
ensure then SET
only_on_empty: Result = is_empty
conforms_to (other: ANY): BOOLEAN
`other'
ANY
require ANY
other_not_void: other /= Void
extendible: BOOLEAN is True
DYNAMIC_CHAIN
is_empty: BOOLEAN
FINITE
require CONTAINER
True
is_inserted (v: G): BOOLEAN
`v'
`has (v)'
COLLECTION
islast: BOOLEAN
TWO_WAY_LIST
require CHAIN
True
require LINEAR_SUBSET
True
ensure CHAIN
valid_position: Result implies not is_empty
object_comparison: BOOLEAN
equal`='
`='
CONTAINER
off: BOOLEAN
LINKED_LIST
require TRAVERSABLE
True
require TRAVERSABLE_SUBSET
True
prunable: BOOLEAN
DYNAMIC_CHAIN
require COLLECTION
True
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'
CHAIN
require TABLE
True
require LINEAR_SUBSET
True
ensure then INDEXABLE
only_if_in_index_set: Result implies ((i >= index_set.lower) and (i <= index_set.upper))
ensure LINEAR_SUBSET
index_valid: 0 <= i and i <= count + 1
ensure then CHAIN
valid_index_definition: Result = ((i >= 1) and (i <= count))
feature {ANY}
readable: BOOLEAN
LINKED_LIST
require ACTIVE
True
valid_cursor_index (i: INTEGER_32): BOOLEAN
`i'
CHAIN
ensure CHAIN
valid_cursor_index_definition: Result = ((i >= 0) and (i <= count + 1))
writable: BOOLEAN
SEQUENCE
require ACTIVE
True
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
feature
forth
TWO_WAY_LIST
require LINEAR
not_after: not after
require TRAVERSABLE_SUBSET
not_after: not after
ensure then LIST
moved_forth: index = old index + 1
go_i_th (i: INTEGER_32)
`i'
LINKED_LIST
require CHAIN
valid_cursor_index: valid_cursor_index (i)
require LINEAR_SUBSET
valid_index: valid_index (i)
ensure CHAIN
position_expected: index = i
ensure LINEAR_SUBSET
cursor_moved: index = i
start
LINKED_LIST
require TRAVERSABLE
True
require TRAVERSABLE_SUBSET
True
ensure then CHAIN
at_first: not is_empty implies isfirst
ensure then LINKED_LIST
empty_convention: is_empty implies after
feature {ANY}
finish
TWO_WAY_LIST
require LINEAR
True
ensure then CHAIN
at_last: not is_empty implies islast
ensure then LINKED_LIST
empty_convention: is_empty implies before
ensure then TWO_WAY_LIST
not_after: not after
feature
extend (v: G)
`v'
PART_SORTED_SETput
require COLLECTION
extendible: extendible
ensure COLLECTION
item_inserted: is_inserted (v)
ensure then SET
in_set_already: old has (v) implies (count = old count)
added_to_set: not old has (v) implies (count = old count + 1)
fill (other: CONTAINER [G])
`other'
`other'
CHAIN
require COLLECTION
other_not_void: other /= Void
extendible: extendible
merge (other: TRAVERSABLE_SUBSET [G])
`other'
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
move_item (v: G)
`v'
LINEAR_SUBSET
require LINEAR_SUBSET
item_exists: v /= Void
item_in_set: has (v)
put (v: G)
`v'
PART_SORTED_SETextend
require COLLECTION
extendible: extendible
ensure COLLECTION
item_inserted: is_inserted (v)
ensure then SET
in_set_already: old has (v) implies (count = old count)
added_to_set: not old has (v) implies (count = old count + 1)
put_left (v: like item)
`v'
TWO_WAY_LIST
require DYNAMIC_CHAIN
extendible: extendible
not_before: not before
require LINEAR_SUBSET
item_exists: v /= Void
not_before: not before
ensure DYNAMIC_CHAIN
new_count: count = old count + 1
new_index: index = old index + 1
ensure then LINKED_LIST
previous_exists: previous /= Void
item_inserted: previous.item = v
ensure LINEAR_SUBSET
cursor_position_unchanged: index = old index + 1
feature
prune (v: like item)
`v'
require COLLECTION
prunable: prunable
ensure then SET
removed_count_change: old has (v) implies (count = old count - 1)
not_removed_no_count_change: not old has (v) implies (count = old count)
item_deleted: not has (v)
prune_all (v: like item)
`v'
object_comparison
off
PART_SORTED_TWO_WAY_LIST
require COLLECTION
prunable: prunable
ensure COLLECTION
no_more_occurrences: not has (v)
ensure then DYNAMIC_CHAIN
is_exhausted: exhausted
remove
after
TWO_WAY_LIST
require ACTIVE
prunable: prunable
writable: writable
require TRAVERSABLE_SUBSET
not_off: not off
ensure then DYNAMIC_LIST
after_when_empty: is_empty implies after
wipe_out
TWO_WAY_LIST
require COLLECTION
prunable: prunable
ensure COLLECTION
wiped_out: is_empty
ensure then DYNAMIC_LIST
is_before: before
feature
linear_representation: LINEAR [G]
LINEAR
require CONTAINER
True
feature
copy (other: like Current)
`other'
LINKED_LIST
require ANY
other_not_void: other /= Void
type_identity: same_type (other)
ensure ANY
is_equal: is_equal (other)
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)
duplicate (n: INTEGER_32): like Current
`n'countindex
require CHAIN
not_off_unless_after: off implies after
valid_subchain: n >= 0
require SUBSET
non_negative: n >= 0
ensure SUBSET
correct_count_1: n <= count implies Result.count = n
correct_count_2: n >= count implies Result.count = count
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)
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
intersect (other: TRAVERSABLE_SUBSET [G])
`other'
`other'is_empty
TRAVERSABLE_SUBSET
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
ensure SUBSET
is_subset_other: is_subset (other)
subtract (other: TRAVERSABLE_SUBSET [G])
`other'
TRAVERSABLE_SUBSET
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
ensure SUBSET
is_disjoint: disjoint (other)
symdif (other: TRAVERSABLE_SUBSET [G])
`other'
`other'
TRAVERSABLE_SUBSET
require SUBSET
set_exists: other /= Void
same_rule: object_comparison = other.object_comparison
feature
io: STD_FILES
ANY
out: STRING_8
ANYtagged_out
ANY
print (some: ANY)
`some'
ANY
frozen tagged_out: STRING_8
ANYout
ANY
feature
operating_environment: OPERATING_ENVIRONMENT
ANY
invariant
LINEAR_SUBSET
before_definition: before = (index = 0)
TRAVERSABLE_SUBSET
empty_definition: is_empty = (count = 0)
count_range: count >= 0
ANY
reflexive_equality: standard_is_equal (Current)
reflexive_conformance: conforms_to (Current)
TWO_WAY_LIST
non_empty_list_has_two_endpoints: not is_empty implies (first_element /= Void and last_element /= Void)
first_element_constraint: first_element /= Void implies first_element.left = Void
last_element_constraint: last_element /= Void implies last_element.right = Void
LINKED_LIST
prunable: prunable
empty_constraint: is_empty implies ((first_element = Void) and (active = Void))
not_void_unless_empty: (active = Void) implies is_empty
before_constraint: before implies (active = first_element)
after_constraint: after implies (active = last_element)
LIST
before_definition: before = (index = 0)
after_definition: after = (index = count + 1)
CHAIN
non_negative_index: index >= 0
index_small_enough: index <= count + 1
off_definition: off = ((index = 0) or (index = count + 1))
isfirst_definition: isfirst = ((not is_empty) and (index = 1))
islast_definition: islast = ((not is_empty) and (index = count))
item_corresponds_to_index: (not off) implies (item = i_th (index))
index_set_has_same_count: index_set.count = count
ACTIVE
writable_constraint: writable implies readable
empty_constraint: is_empty implies (not readable) and (not writable)
INDEXABLE
index_set_not_void: index_set /= Void
BILINEAR
not_both: not (after and before)
before_constraint: before implies off
LINEAR
after_constraint: after implies off
TRAVERSABLE
empty_constraint: is_empty implies off
FINITE
empty_definition: is_empty = (count = 0)
non_negative_count: count >= 0
DYNAMIC_CHAIN
extendible: extendible
indexing
library: "EiffelBase: Library of reusable components for Eiffel."
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 PART_SORTED_SET