Eiffel Media API
Overview Cluster Class Classes Index      Previous Next      Top Features

structure.sort

Class DS_HASH_TOPOLOGICAL_SORTER


Direct ancestors

DS_TOPOLOGICAL_SORTER

Creation

Features

Invariants

indexing

description

Topological sorters of hashable items

remark

Use the algorithm described by D. Knuth in 'The Art of %
%Computer Programming', Vol.1 3rd ed. p.265. The detection %
%of cycles is described in exercise 23 p.271 and p.548.

library

Gobo Eiffel Structure Library

copyright

Copyright (c) 2001, Eric Bezault and others

license

Eiffel Forum License v2 (see forum.txt)

date

$Date: 2005/07/13 17:52:51 $

revision

$Revision: 1.8 $

class

DS_HASH_TOPOLOGICAL_SORTER [G -> HASHABLE]

inherit

DS_TOPOLOGICAL_SORTER

create

make (nb: INTEGER)

-- Create a new topological sorter.
-- Set initial capacity to nb.

-- (From DS_TOPOLOGICAL_SORTER)

require
nb_positive: nb >= 0
ensure
capacity_set: capacity = nb
make_default

-- Create a new topological sorter.
-- Set initial capacity to a default value.

-- (From DS_TOPOLOGICAL_SORTER)

feature -- Access

cycle: DS_ARRAYED_LIST [G]

-- Items involved in a cycle if any
-- (Note: the items in cycle are stored in reverse order
-- and the first item is repeated at the end of the list.)

-- (From DS_TOPOLOGICAL_SORTER)

equality_tester: KL_EQUALITY_TESTER [G]

-- Equality tester to compare items to be sorted;
-- A void equality tester means that = will be
-- used as comparison criterion.

-- (From DS_TOPOLOGICAL_SORTER)

index_of (v: G): INTEGER

-- Index of v in the list of items to be sorted;
-- Return 'count + 1' if v is not in the list yet

-- (From DS_TOPOLOGICAL_SORTER)

ensure
index_large_enough: Result >= 1
index_small_enough: Result <= count + 1
sorted_items: DS_ARRAYED_LIST [G]

-- Sorted items

-- (From DS_TOPOLOGICAL_SORTER)

feature -- Measurement

capacity: INTEGER

-- Maximum number of items to be sorted

-- (From DS_TOPOLOGICAL_SORTER)

ensure
capacity_large_enough: Result >= count
count: INTEGER

-- Number of items to be sorted

-- (From DS_TOPOLOGICAL_SORTER)

ensure
count_positive: Result >= 0

feature -- Status report

equality_tester_settable (a_tester: like equality_tester): BOOLEAN

-- Can set_equality_tester be called with a_tester
-- as argument in current state of the sorter?

-- (From DS_TOPOLOGICAL_SORTER)

ensure
definition: Result = is_empty
has (v: G): BOOLEAN

-- Is v included in the list of items to be sorted?

-- (From DS_TOPOLOGICAL_SORTER)

has_cycle: BOOLEAN

-- Has a cycle been detected?

-- (From DS_TOPOLOGICAL_SORTER)

ensure
definition: Result = (cycle /= Void and then not cycle.is_empty)
is_empty: BOOLEAN

-- Are there no items yet to be sorted?

-- (From DS_TOPOLOGICAL_SORTER)

ensure
definition: Result = (count = 0)
is_sorted: BOOLEAN

-- Have items been sorted?

-- (From DS_TOPOLOGICAL_SORTER)

ensure
definition: Result = (sorted_items /= Void)

feature -- Element change

force (v: G)

-- Add v to the list of items to be sorted.
-- Resize the list of items if needed.

-- (From DS_TOPOLOGICAL_SORTER)

require
not_has: not has (v)
ensure
one_more: count = old count + 1
inserted: has (v)
last: index_of (v) = count
force_relation (u, v: G)

-- Specify that item u should appear
-- before item v in the sorted list.
-- Insert u and v in the list of items
-- to be sorted if not already done.

-- (From DS_TOPOLOGICAL_SORTER)

put (v: G)

-- Add v to the list of items to be sorted.

-- (From DS_TOPOLOGICAL_SORTER)

require
not_has: not has (v)
not_full: count < capacity
ensure
one_more: count = old count + 1
inserted: has (v)
last: index_of (v) = count
put_indexed_relation (i, j: INTEGER)

-- Specify that item at index i should
-- appear before item at index j in
-- the sorted list.

-- (From DS_TOPOLOGICAL_SORTER)

require
i_large_enough: i >= 1
i_small_enough: i <= count
j_large_enough: j >= 1
j_small_enough: j <= count
put_relation (u, v: G)

-- Specify that item u should appear
-- before item v in the sorted list.

-- (From DS_TOPOLOGICAL_SORTER)

require
has_u: has (u)
has_v: has (v)

feature -- Removal

remove (v: G)

-- Remove v to the list of items to be sorted.
-- Keep the order relation for the sorting though.

-- (From DS_TOPOLOGICAL_SORTER)

require
has: has (v)
ensure
one_less: count = old count - 1
removed: not has (v)
reset

-- Discard result of last sort.

-- (From DS_TOPOLOGICAL_SORTER)

ensure
not_sorted: not is_sorted
no_cycle: not has_cycle
wipe_out

-- Wipe out items.

-- (From DS_TOPOLOGICAL_SORTER)

ensure
not_sorted: not is_sorted
no_cycle: not has_cycle
empty: count = 0

feature -- Setting

set_equality_tester (a_tester: like equality_tester)

-- Set equality_tester to a_tester.
-- A void equality tester means that =
-- will be used as comparison criterion.

-- (From DS_TOPOLOGICAL_SORTER)

require
equality_tester_settable: equality_tester_settable (a_tester)
ensure
equality_tester_set: equality_tester = a_tester

feature -- Sort

sort

-- Sort items held in items according to the
-- relations which have been recorded.

-- (From DS_TOPOLOGICAL_SORTER)

ensure
sorted: is_sorted
cycle: (sorted_items.count /= count) implies has_cycle

invariant

indexes_not_void: indexes /= Void
indexes_count: indexes.count = items.count
indexes_capacity: indexes.capacity = items.capacity

items_not_void: items /= Void
counts_not_void: counts /= Void
counts_count: counts.count = items.count
counts_capacity: counts.capacity = items.capacity
successors_not_void: successors /= Void
successors_count: successors.count = items.count
successors_capacity: successors.capacity = items.capacity
has_cycle: has_cycle implies cycle.count >= 2 and then cycle.first = cycle.last

-- From ANY
reflexive_equality: standard_is_equal (Current)
reflexive_conformance: conforms_to (Current)

end