|
DataMuseum.dkPresents historical artifacts from the history of: Rational R1000/400 Tapes |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about Rational R1000/400 Tapes Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - metrics - downloadIndex: B T
Length: 11810 (0x2e22)
Types: TextFile
Names: »B«
└─⟦180fe333a⟧ Bits:30000405 8mm tape, Rational 1000, SW CATALOG, 10_20_0
└─⟦180fe333a⟧ Bits:30000537 8mm tape, Rational 1000, SW Catalog 10_20_0
└─⟦5cb1d1d7f⟧ »DATA«
└─⟦3b1ee7bd8⟧
└─⟦this⟧
with Unchecked_Deallocation;
package body Singly_Linked_List is
--------------------------------------------------------------------------
-- Abstract : This package provides an abstraction for a singly linked
-- list.
--------------------------------------------------------------------------
-- Assumptions:
-- The lists being manipulated must be in one of the following states
-- both before and after execution of any subprogram in the package:
-- (1) empty-list -- Head = null, Tail = null,
-- Previous = null, Current = null
-- (2) beginning-of-list -- Head /= null, Tail /= null
-- Previous = null, Current = Head
-- (3) inside-of-list -- Head /= null, Tail /= null
-- Previous.Next = Current
-- (4) outside-of-list -- Head /= null, Tail /= null
-- Previous = null, Current = null
----------------------------------------------------------------------
function Empty (List : List_Type) return Boolean is
--------------------------------------------------------------------------
-- Abstract : Indicates whether the list contains any elements.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be queried.
--------------------------------------------------------------------------
begin
return (List.Head = null);
end Empty;
function Null_Node (List : List_Type) return Boolean is
--------------------------------------------------------------------------
-- Abstract : Indicates whether the "current pointer" references an
-- element in the list.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be queried.
--------------------------------------------------------------------------
begin
return (List.Current = null);
end Null_Node;
function Head_Node (List : List_Type) return Boolean is
--------------------------------------------------------------------------
-- Abstract : Indicates whether the "current pointer" references the
-- head of the list.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be queried.
--------------------------------------------------------------------------
begin
return (List.Current = List.Head);
end Head_Node;
function Tail_Node (List : List_Type) return Boolean is
--------------------------------------------------------------------------
-- Abstract : Indicates whether the "current pointer" references the
-- tail of the list.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be queried.
--------------------------------------------------------------------------
begin
return (List.Current = List.Tail);
end Tail_Node;
function Current_Element (List : List_Type) return List_Element is
--------------------------------------------------------------------------
-- Abstract : Returns the value of the element referenced by the
-- "current pointer".
-- Raises END_ERROR if NULL_NODE(LIST) = TRUE.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be queried.
--------------------------------------------------------------------------
begin
if List.Current = null then
raise End_Error;
else
return List.Current.Element;
end if;
end Current_Element;
procedure First (List : in out List_Type) is
--------------------------------------------------------------------------
-- Abstract : Positions the "current pointer" at the head of the list
-- (even if the list is empty).
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
--------------------------------------------------------------------------
begin
List.Previous := null;
List.Current := List.Head;
end First;
procedure Next (List : in out List_Type) is
--------------------------------------------------------------------------
-- Abstract : Positions the "current pointer" at the next element in the
-- list. After the last element in the list NULL_NODE(LIST)
-- becomes true.
-- Raises END_ERROR if NULL_NODE(LIST) = TRUE.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
--------------------------------------------------------------------------
begin
if List.Current = null then
raise End_Error;
else
if List.Current = List.Tail then
List.Previous := null;
else
List.Previous := List.Current;
end if;
List.Current := List.Current.Next;
end if;
end Next;
procedure Insert_After (List : in out List_Type; Element : List_Element) is
--------------------------------------------------------------------------
-- Abstract : Inserts an element after the "current pointer".
-- If NULL_NODE(LIST) = TRUE the element is appended after
-- the tail element of the list.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
-- ELEMENT - is the element to be inserted.
--------------------------------------------------------------------------
begin
if List.Current = null then
List.Current := List.Tail;
end if;
if Empty (List) then
List.Head := new Node'(Element, null);
List.Tail := List.Head;
List.Previous := null;
List.Current := List.Head;
else
declare
New_Node : Node_Access := new Node'(Element, List.Current.Next);
begin
if List.Current = List.Tail then
List.Tail := New_Node;
end if;
List.Previous := List.Current;
List.Previous.Next := New_Node;
List.Current := New_Node;
end;
end if;
end Insert_After;
procedure Insert_Before (List : in out List_Type; Element : List_Element) is
-------------------------------------------------------------------------
-- Abstract : Inserts an element before the "current pointer".
-- If NULL_NODE(LIST) = TRUE the element is prepended before
-- the head element of the list.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
-- ELEMENT - is the element to be inserted.
--------------------------------------------------------------------------
begin
if List.Current = null then
List.Current := List.Head;
end if;
if Empty (List) then
List.Head := new Node'(Element, null);
List.Tail := List.Head;
List.Previous := null;
List.Current := List.Head;
elsif List.Current = List.Head then
List.Head := new Node'(Element, List.Head);
List.Previous := null;
List.Current := List.Head;
else
List.Previous.Next := new Node'(Element, List.Current);
List.Current := List.Previous.Next;
end if;
end Insert_Before;
procedure Delete_Element (List : in out List_Type) is
--------------------------------------------------------------------------
-- Abstract : Deletes the element referenced by the "current pointer"
-- from the list. Upon deletion the "current pointer"
-- references the element after the deleted element.
-- Raises END_ERROR if NULL_NODE(LIST) = TRUE.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
--------------------------------------------------------------------------
procedure Free is new Unchecked_Deallocation (Node, Node_Access);
begin
if List.Current = null then
raise End_Error;
elsif List.Current = List.Head then
declare
Next_Node : Node_Access := List.Head.Next;
begin
Free (List.Head); -- List.Head:=null; --
List.Head := Next_Node;
if List.Head = null then
List.Tail := null;
end if;
List.Current := List.Head;
end;
else
if List.Current = List.Tail then
List.Tail := List.Previous;
end if;
List.Previous.Next := List.Current.Next;
Free (List.Current); -- List.Current:=null; --
List.Current := List.Previous.Next;
if List.Current = null then
List.Previous := null;
end if;
end if;
end Delete_Element;
procedure Modify (List : List_Type) is
--------------------------------------------------------------------------
-- Abstract : Permits modification of the element referenced by the
-- "current pointer" where the modification doesn't require
-- external values (e.g. incrementing a field of the element).
-- Raises END_ERROR if NULL_NODE(LIST) = TRUE.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
--------------------------------------------------------------------------
begin
if List.Current = null then
raise End_Error;
else
Transformation (List.Current.Element);
end if;
end Modify;
procedure Update (List : List_Type; Information : Update_Information) is
--------------------------------------------------------------------------
-- Abstract : Permits modification of the element referenced by the
-- "current pointer" where the modification requires
-- external values (e.g. assigning a value to a field of
-- the element).
-- Raises END_ERROR if NULL_NODE(LIST) = TRUE.
--------------------------------------------------------------------------
-- Parameters : LIST - is the list to be modified.
-- INFORMATION - is the data necessary for the modification.
--------------------------------------------------------------------------
begin
if List.Current = null then
raise End_Error;
else
Transformation (List.Current.Element, Information);
end if;
end Update;
end Singly_Linked_List;