 |  | limited_lists |  |
 |  | limi_lists.ads |  |
 | limi_lists.adb |
|  | lists | |
| | limited_lists | |
| lists | ||
| string_lists | ||
| test_lists.adb | ||
| test_stri_list |
| | util | |
|  | hash_tables/ | |
| heaps/ | ||
| images/ | ||
| lists/ | ||
| maths/ | ||
| messages/ | ||
| pipes/ | ||
| primes/ | ||
| readers/ | ||
| strings/ | ||
| writers/ |
| | ada | |
| | bin/ | |
| engine/ | ||
| fonts/ | ||
| internal/ | ||
| text/ | ||
| util/ |
|  | Home | |
|  | Showcase | |
 | Snapshots | ||
 | Ada Source | ||
 | PHP Source | ||
 | Fonts |
|  | Sourceforge | |
|  | Summary | |
 | Downloads | ||
 | Browse CVS | ||
 | Donate | ||
 | Activity |
Hosted by
-- $Date: 2004/02/14 09:51:42 $
-- $Revision: 1.4 $
-- $Author: jcrocholl $
generic
-- Generic type of the items to be stored.
type Content_Type is limited private;
-- Linked list with some nice features.
-- - Private implementation: can't mess around with this.
-- - Small memory footprint: only one extra pointer per item.
-- - Built-in iterator for simple loops.
-- - Modify while iterating: insert, remove, update.
-- - Item direct iteration: unlimited parallel independent iterators.
-- - Direct access to first and last item: can add items at both ends.
-- - Cached item count.
package Limited_Lists is
-- Instance of a list, needs to be created before it can be used.
type List is limited private;
type List_Access is access List;
-- Instance of a list item. Most useful if you need multiple iterators.
type Item;
type Item_Access is access Item;
type Item is limited record
Next : Item_Access := null;
Content : Content_Type;
end record;
--------------------
-- List construction
--------------------
-- Create a list.
function Create
return List_Access;
-- Append a list at the end of another list. This is done by simply
-- linking from the last item to the first item of the tail, not by
-- copying the items of the tail. This means that if you modify the
-- tail list later, the modifications will appear in the appended
-- list as well.
procedure Append
(This : access List; -- Append to this list.
Tail : access List); -- Append these items at the end.
---------------
-- Adding items
---------------
-- Insert an item at the end of the list.
function Push
(This : access List) -- Push into this list.
return Item_Access; -- The newly created item.
-- Insert an item at the beginning of the list.
function Unshift
(This : access List) -- Unshift into this list.
return Item_Access; -- The newly created item.
-----------------
-- Removing items
-----------------
-- Remove an item at the end of the list.
function Pop
(This : access List) -- Pop out of this list.
return Item_Access; -- The removed item.
-- Remove an item at the beginning of the list.
function Shift
(This : access List) -- Shift out of this list.
return Item_Access; -- The removed item.
----------------
-- Item indexing
----------------
-- Count items in this list. This operation is not O(n) but O(1)
-- because the result comes straight from a counter variable.
function Count
(This : access List) -- Get information about this list.
return Natural; -- The number of items in the list.
-- Is the list empty? Returns True if and only if there are no
-- items in the list.
function Empty
(This : access List) -- Get information about this list.
return Boolean; -- This list empty?
-- Read the current iteration position as a number, starting with 1
-- at the first item. An index of 0 means: no current item, so
-- either we're not currently iterating or the iteration has
-- finished.
function Index
(This : access List) -- Get information about this list.
return Natural; -- Iteration index of this list.
----------------------
-- First and last item
----------------------
-- Read the first item in the list.
function First
(This : access List) -- Read from this list.
return Content_Type; -- The first item.
-- Read the last item in the list.
function Last
(This : access List) -- Read from this list.
return Content_Type; -- The last item.
------------------------
-- Iterating over a list
------------------------
-- Reset the iteration index to 0. This starts a new
-- iteration. There must be a call to Next before the first item
-- can be read from the function Current.
procedure Reset
(This : access List); -- The list to iterate over.
-- Go to the next item.
procedure Next
(This : access List); -- The list to iterate over.
-- Go to the next item. Returns False if and only if we reached the
-- end of the list.
function Next
(This : access List) -- The list to iterate over.
return Boolean; -- Successfully moved to next item?
-- Is the a next item available? Returns False if the current item
-- is the last one in the list.
function Next_Available
(This : access List) -- The list to iterate over.
return Boolean; -- Next item available?
-- Get the content of the next item.
function Next_Content
(This : access List) -- The list to iterate over.
return Content_Type; -- The content of the next item.
-- End of list reached? Returns True if and only if the current
-- item pointer is null. This also occurs after calling Reset but
-- before calling Next.
function End_Of_List
(This : access List) -- The list to iterate over.
return Boolean; -- Reached end of list?
-- Read the item at the current iteration pointer.
function Current
(This : access List) -- The list to iterate over.
return Content_Type; -- Current item.
--------------------------------------
-- Manipulating a list while iterating
--------------------------------------
-- Remove the item at the current iteration pointer from the list.
procedure Remove_Current
(This : access List); -- The list to modify.
-- Insert an item directly before the item at the current iteration
-- pointer.
function Insert_Before_Current
(This : access List) -- The list to modify.
return Item_Access; -- The newly created item.
-- Insert an item directly after the item at the current iteration
-- pointer.
function Insert_After_Current
(This : access List) -- The list to modify.
return Item_Access; -- The newly created item.
------------------------
-- Item direct iteration
------------------------
-- Get the first item of the list.
function First_Item
(This : access List) -- Read from this list.
return Item_Access; -- The first item.
-- Get the last item of the list.
function Last_Item
(This : access List) -- Read from this list.
return Item_Access; -- The last item.
-- Get the current iteration item of the list.
function Current_Item
(This : access List) -- Read from this list.
return Item_Access; -- The last item.
-- Go to the next item.
procedure Next_Item
(This : in out Item_Access); -- Advance this item.
-- Get the next item.
function Next_Item
(This : access Item) -- Get this item's successor.
return Item_Access; -- The successor of the input item.
-- Returns True if and only if the item pointer is null. This
-- happens after the last item in the list.
function Item_Invalid
(This : in Item_Access) -- The iterating list item.
return Boolean; -- Reached end of list?
-- Compare two items (not the contents but the pointers).
function Item_Equals
(This : in Item_Access; -- Compare this item.
Other : in Item_Access) -- To that other item.
return Boolean; -- True if the pointers are the same.
-- Read an item's content.
function Item_Content
(This : access Item) -- Read content from this item.
return Content_Type; -- Content of this item.
-- Remove an item from the list and advance the item pointer.
procedure Remove_Item
(Previous : in Item_Access; -- May be null if removing first.
This : in out Item_Access; -- Remove and advance this item.
Context : access List); -- Remove the item from this list.
private
type List is record
Count : Natural := 0; -- Number of items in the list.
Index : Natural := 0; -- Index of current item while iterating.
First : Item_Access; -- First item in the list.
Last : Item_Access; -- Last item in the list.
Prev : Item_Access; -- Previous item while iterating.
Current : Item_Access; -- Current item while iterating.
Next : Item_Access; -- Next item while iterating.
end record;
end Limited_Lists;