note description: "Unbounded queues implemented as linked lists" legal: "See notice at end of class." status: "See notice at end of class." names: linked_queue, dispenser, linked_list; representation: linked; access: fixed, fifo, membership; contents: generic; date: "$Date$" revision: "$Revision$" class LINKED_QUEUE [G] inherit QUEUE [G] undefine is_empty, copy, is_equal redefine linear_representation, prune_all, extend select item, put, extend end LINKED_LIST [G] rename item as ll_item, remove as ll_remove, make as ll_make, remove_left as remove, put as ll_put, extend as ll_extend export {NONE} all {LINKED_QUEUE} cursor, valid_cursor, start, forth, go_to, first_element, last_element, ll_item {ANY} writable, extendible, wipe_out, readable, off, before, after, index undefine fill, append, prune, readable, writable, prune_all, force, is_inserted redefine duplicate, linear_representation, copy select remove end create make create {LINKED_QUEUE} ll_make feature -- Initialization make -- Create linked queue. do after := True end feature -- Access item: G -- Oldest item do Result := active.item ensure then last_element_if_not_empty: not is_empty implies (active = last_element) end feature -- Element change put, extend, force (v: G) -- Add `v' as newest item. do put_front (v) before := False after := True ensure then single_item_constraint: (old is_empty) implies (item = v) end feature -- Conversion linear_representation: ARRAYED_LIST [G] -- Representation as a linear structure -- (order is same as original order of insertion) do create Result.make_filled (count) from start Result.finish until after loop Result.replace (ll_item) forth Result.back end end feature -- Duplication duplicate (n: INTEGER): like Current -- New queue containing the `n' oldest items in current queue. -- If `n' is greater than `count', identical to current queue. local l_cur: like cursor do l_cur := cursor from create Result.make start until after or Result.count = n loop Result.extend (ll_item) forth end go_to (l_cur) end copy (other: like Current) -- Update current object using fields of object attached -- to `other', so as to yield equal objects. local cur: like cursor obj_comparison: BOOLEAN do obj_comparison := other.object_comparison standard_copy (other) if not other.is_empty then internal_wipe_out cur ?= other.cursor from other.start until other.off loop ll_extend (other.ll_item) -- For speeding up next insertion, we go -- to the end, that way `extend' does not -- need to traverse the list completely. forth other.forth end other.go_to (cur) end object_comparison := obj_comparison after := True before := False end feature {NONE} -- Not applicable prune (v: like item) -- Remove one occurrence of `v'. -- Not available. do -- Do nothing end prune_all (v: like item) -- Remove all occurrences of `v'. -- Not available do -- Do nothing end invariant is_always_after: not is_empty implies after note 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 -- class LINKED_QUEUE