indexing
description: "Priority queues implemented as heaps"
names: sorted_priority_queue, dispenser, heap
representation: heap
access: fixed, membership
contents: generic
class interface
HEAP_PRIORITY_QUEUE [G -> COMPARABLE]
create
make (n: INTEGER)
-- Allocate heap space.
feature -- Initialization
make (n: INTEGER)
-- Allocate heap space.
setup (other: like Current)
-- Perform actions on a freshly created object so that
-- the contents of other can be safely copied onto it.
-- (from ARRAY)
ensure -- from GENERAL
consistent (other)
feature -- Access
has (v: G): BOOLEAN
-- Does v appear in array?
-- (Reference or object equality,
-- based on object_comparison.)
-- (from ARRAY)
ensure -- from CONTAINER
not_found_in_empty: Result implies not empty
item: G
-- Entry at top of heap.
require -- from ACTIVE
readable: readable
feature -- Measurement
count: INTEGER
occurrences (v: G): INTEGER
-- Number of times v appears in structure
-- (from ARRAY)
ensure -- from BAG
non_negative_occurrences: Result >= 0
feature -- Comparison
is_equal (other: like Current): BOOLEAN
-- Is array made of the same items as other?
-- (from ARRAY)
require -- from GENERAL
other_not_void: other /= void
ensure -- from GENERAL
symmetric: Result implies other.is_equal (Current);
consistent: standard_is_equal (other) implies Result
feature -- Status report
changeable_comparison_criterion: BOOLEAN
-- May object_comparison be changed?
-- (Answer: yes by default.)
-- (from CONTAINER)
consistent (other: like Current): BOOLEAN
-- Is object in a consistent state so that other
-- may be copied onto it? (Default answer: yes).
-- (from ARRAY)
empty: BOOLEAN
-- Is structure empty?
-- (from FINITE)
extendible: BOOLEAN
-- May items be added?
full: BOOLEAN
-- Is structure filled to capacity?
object_comparison: BOOLEAN
-- Must search operations use equal rather than =
-- for comparing references? (Default: no, use =.)
-- (from CONTAINER)
Prunable: BOOLEAN is true
-- May items be removed? (Answer: yes.)
readable: BOOLEAN
-- Is there a current item that may be read?
-- (from DISPENSER)
writable: BOOLEAN
-- Is there a current item that may be modified?
-- (from DISPENSER)
feature -- Status setting
compare_objects
-- Ensure that future search operations will use equal
-- rather than = for comparing references.
-- (from CONTAINER)
require -- from CONTAINER
changeable_comparison_criterion
ensure -- from CONTAINER
object_comparison
compare_references
-- Ensure that future search operations will use =
-- rather than equal for comparing references.
-- (from CONTAINER)
require -- from CONTAINER
changeable_comparison_criterion
ensure -- from CONTAINER
reference_comparison: not object_comparison
feature -- Element change
append (s: SEQUENCE [G])
-- Append a copy of s.
-- (Synonym for fill)
-- (from DISPENSER)
fill (other: CONTAINER [G])
-- Fill with as many items of other as possible.
-- The representations of other and current structure
-- need not be the same.
-- (from COLLECTION)
require -- from COLLECTION
other_not_void: other /= void;
extendible
force (v: like item)
-- Insert item v at its proper position.
-- Was declared in HEAP_PRIORITY_QUEUE as synonym of force and put.
put (v: like item)
-- Insert item v at its proper position.
-- Was declared in HEAP_PRIORITY_QUEUE as synonym of force and put.
require -- from COLLECTION
extendible: extendible
ensure -- from COLLECTION
item_inserted: has (v)
feature -- Removal
prune_all (v: G)
-- Remove all occurrences of v.
-- (Reference or object equality,
-- based on object_comparison.)
-- (from COLLECTION)
require -- from COLLECTION
prunable
ensure -- from COLLECTION
no_more_occurrences: not has (v)
remove
-- Remove item of highest value.
require -- from ACTIVE
prunable: prunable;
writable: writable
wipe_out
-- Make array empty.
-- (from ARRAY)
require -- from COLLECTION
prunable
ensure -- from COLLECTION
wiped_out: empty
feature -- Conversion
linear_representation: ARRAYED_LIST [G]
-- Representation as a linear structure
-- (Sorted according to decreasing priority)
feature -- Duplication
copy (other: like Current)
-- Reinitialize by copying all the items of other.
-- (This is also used by clone.)
-- (from ARRAY)
require -- ARRAY
precursor: True
require -- from GENERAL
other_not_void: other /= void;
type_identity: same_type (other)
ensure -- from GENERAL
is_equal: is_equal (other)
duplicate (n: INTEGER): like Current
-- New priority queue containing the n greatest items
feature -- Inapplicable
extend (v: G)
-- Add v to structure.
-- (Precondition is false.)
-- (from ARRAY)
require -- from COLLECTION
extendible: extendible
ensure -- from COLLECTION
item_inserted: has (v)
ensure then -- from BAG
one_more_occurrence: occurrences (v) = old (occurrences (v)) + 1
prune (v: G)
-- Remove first occurrence of v if any.
-- (Precondition is false.)
-- (from ARRAY)
require -- from COLLECTION
prunable: prunable
invariant
-- from GENERAL
reflexive_equality: standard_is_equal (Current);
reflexive_conformance: conforms_to (Current);
-- from DISPENSER
readable_definition: readable = not empty;
writable_definition: writable = not empty;
-- from ACTIVE
writable_constraint: writable implies readable;
empty_constraint: empty implies (not readable) and (not writable);
-- from FINITE
empty_definition: empty = (count = 0);
non_negative_count: count >= 0;
-- from ARRAY
non_negative_count: count >= 0;
end -- class HEAP_PRIORITY_QUEUE