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

structure.dispenser

Class DS_LINKED_QUEUE


Direct ancestors

DS_QUEUE, KL_IMPORTED_ANY_ROUTINES

Creation

Features

Invariants

indexing

description

Queues (First-In, First-Out) implemented with linked cells

library

Gobo Eiffel Structure Library

copyright

Copyright (c) 1999, Eric Bezault and others

license

Eiffel Forum License v2 (see forum.txt)

date

$Date: 2005/07/13 17:50:23 $

revision

$Revision: 1.9 $

class

DS_LINKED_QUEUE [G]

inherit

DS_QUEUE

create

make

-- Create an empty queue.
-- Use = as comparison criterion.

ensure
empty: is_empty
make_equal

-- Create an empty queue.
-- Use equal as comparison criterion.

ensure
empty: is_empty
make_default

-- Create an empty queue.
-- Use = as comparison criterion.

-- (From DS_CONTAINER)

ensure
empty: is_empty

feature -- Access

any_: KL_ANY_ROUTINES

-- Routines that ought to be in class ANY

-- (From KL_IMPORTED_ANY_ROUTINES)

ensure
any_routines_not_void: Result /= Void
equality_tester: KL_EQUALITY_TESTER [G]

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

-- (From DS_SEARCHABLE)

item: G

-- Item at front of queue

-- (From DS_DISPENSER)

require
not_empty: not is_empty

feature -- Measurement

count: INTEGER

-- Number of items in queue

-- (From DS_CONTAINER)

occurrences (v: G): INTEGER

-- Number of times v appears in queue
-- (Use equality_tester's comparison criterion
-- if not void, use = criterion otherwise.)

-- (From DS_SEARCHABLE)

ensure
positive: Result >= 0
has: has (v) implies Result >= 1

feature -- Comparison

is_equal (other: like Current): BOOLEAN

-- Is current queue equal to other?

-- (From ANY)

require
other_not_void: other /= Void
ensure
symmetric: Result implies other.is_equal (Current)
consistent: standard_is_equal (other) implies Result

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 container?
-- (Default answer: True.)

-- (From DS_SEARCHABLE)

extendible (n: INTEGER): BOOLEAN

-- May queue be extended with n items?

-- (From DS_EXTENDIBLE)

require
positive_n: n >= 0
ensure then
definition: Result = True
has (v: G): BOOLEAN

-- Does queue include v?
-- (Use equality_tester's comparison criterion
-- if not void, use = criterion otherwise.)

-- (From DS_SEARCHABLE)

ensure
not_empty: Result implies not is_empty
is_empty: BOOLEAN

-- Is container empty?

-- (From DS_CONTAINER)

same_equality_tester (other: DS_SEARCHABLE [G]): BOOLEAN

-- Does container use the same comparison
-- criterion as other?

-- (From DS_SEARCHABLE)

require
other_not_void: other /= Void
same_items (v, u: G): BOOLEAN

-- Are v and u considered equal?
-- (Use equality_tester's comparison criterion
-- if not void, use = criterion otherwise.)

-- (From DS_SEARCHABLE)

feature -- Element change

append (other: DS_LINEAR [G])

-- Add items of other to back of queue.
-- Add other.first first, etc.

-- (From DS_EXTENDIBLE)

require
other_not_void: other /= Void
ensure then
new_count: count = old count + other.count
extend (other: DS_LINEAR [G])

-- Add items of other to back of queue.
-- Add other.first first, etc.

-- (From DS_EXTENDIBLE)

require
other_not_void: other /= Void
extendible: extendible (other.count)
ensure then
new_count: count = old count + other.count
force (v: G)

-- Add v to back of queue.

-- (From DS_EXTENDIBLE)

ensure
added: has (v)
ensure then
one_more: count = old count + 1
put (v: G)

-- Add v to back of queue.

-- (From DS_EXTENDIBLE)

require
extendible: extendible (1)
ensure
added: has (v)
ensure then
one_more: count = old count + 1

feature -- Removal

keep (n: INTEGER)

-- Keep n items in queue.

-- (From DS_DISPENSER)

require
valid_n: 0 <= n and n <= count
ensure
new_count: count = n
prune (n: INTEGER)

-- Remove n items from queue.

-- (From DS_DISPENSER)

require
valid_n: 0 <= n and n <= count
ensure
new_count: count = old count - n
remove

-- Remove from item from queue.

-- (From DS_DISPENSER)

require
not_empty: not is_empty
ensure
one_less: count = old count - 1
wipe_out

-- Remove all items from queue.

-- (From DS_CONTAINER)

ensure
wiped_out: is_empty

feature -- Duplication

cloned_object: like Current

-- Clone of current object

-- (From KL_CLONABLE)

ensure
cloned_not_void: Result /= Void
same_type: ANY_.same_types (Result, Current)
is_equal: Result.is_equal (Current)
copy (other: like Current)

-- Copy other to current queue.

-- (From ANY)

require
other_not_void: other /= Void
type_identity: same_type (other)
ensure
is_equal: is_equal (other)

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_SEARCHABLE)

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

feature {DS_LINKED_QUEUE} -- Implementation

first_cell: DS_LINKABLE [G]

-- First cell in queue

last_cell: like first_cell

-- Last cell in queue

invariant

first_cell: is_empty = (first_cell = Void)
last_cell: is_empty = (last_cell = Void)

-- From DS_CONTAINER
positive_count: count >= 0
empty_definition: is_empty = (count = 0)

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

end