PACKAGE BODY Stack_Package IS
TYPE Nodes;
TYPE Pointers IS ACCESS Nodes;
TYPE Nodes IS
RECORD
Data: Elements;
Previous: Pointers;
END RECORD;
Top: Pointers;
FUNCTION Empty RETURN Boolean IS
BEGIN
RETURN Top = NULL;
END Empty;
PROCEDURE Push(Item: IN Elements) IS
This: Nodes;
BEGIN
This.Data := Item;
This.Previous := Top;
Top := NEW Nodes'(This);
EXCEPTION
WHEN Storage_Error =>
RAISE Full_Stack;
END Push;
PROCEDURE Pop(Item: OUT Elements) IS
SEPARATE;
END Stack_Package;
WITH Unchecked_Deallocation;
SEPARATE (Stack_Package)
PROCEDURE Pop(Item: OUT Elements) IS
Old_Top: Pointers;
PROCEDURE Deallocate_Node IS NEW
Unchecked_Deallocation(Nodes,Pointers);
BEGIN
IF Top = NULL THEN
RAISE Empty_Stack;
ELSE
Old_Top := Top;
Item := Top.Data;
Top := Top.Previous;
Deallocate_Node(Old_Top);
END IF;
END Pop;

GENERIC
TYPE Elements IS PRIVATE;
TYPE Keys IS PRIVATE;
WITH FUNCTION Get_Key(Element: Elements)
RETURN Keys;
WITH FUNCTION ">"(Left,Right: Keys) RETURN
Boolean IS <>;
PACKAGE Sorted_List_Package IS
TYPE Lists IS PRIVATE;
PROCEDURE Insert(List: IN OUT Lists;
Element: IN Elements);
PROCEDURE Delete(List: IN OUT Lists;
Key: IN Keys);
PROCEDURE Find(List: IN Lists;
Key: IN Keys; Element: OUT Elements;
Found: OUT Boolean);
Full_List,Duplicate_Key: EXCEPTION;
PRIVATE
TYPE Tables IS ARRAY(1..100) OF Elements;
TYPE Lists IS
RECORD
Count: Natural := 0;
Table: Tables;
END RECORD;
END Sorted_List_Package;
PACKAGE BODY Sorted_List_Package IS
PROCEDURE Search(List: IN Lists;
Key: IN Keys; Location: OUT Positive;
Found: OUT Boolean) IS SEPARATE;
PROCEDURE Insert(List: IN OUT Lists;
Element: IN Elements) IS
Key: Keys := Get_Key(Element);
Location: Natural;
Found: Boolean;
BEGIN
Search(List,Key,Location,Found);
IF Found THEN
RAISE Duplicate_Key;
END IF;
IF List.Count = Tables'Last THEN
RAISE Full_List;
END IF;
List.Count := List.Count + 1;
List.Table(Location+1..List.Count) :=
List.Table(Location..List.Count-1);
List.Table(Location) := Element;
END Insert;
--Package Body Continues On Next Page
PROCEDURE Delete(List: IN OUT Lists;
Key: IN Keys) IS
Location: Natural;
Found: Boolean;
BEGIN
Search(List,Key,Location,Found);
IF Found THEN
List.Table(Location..List.Count-1) :=
List.Table(Location+1..List.Count);
List.Count := List.Count - 1;
END IF;
END Delete;
PROCEDURE Find(List: IN Lists;
Key: IN Keys; Element: OUT Elements;
Found: OUT Boolean) IS
Location: Natural;
In_List: Boolean;
BEGIN
Search(List,Key,Location,In_List);
IF In_List THEN
Element := List.Table(Location);
END IF;
Found := In_List;
END Find;
END Sorted_List_Package;
SEPARATE (Sorted_List_Package)
PROCEDURE Search(List: IN Lists;
Key: IN Keys; Location: OUT Positive;
Found: OUT Boolean) IS
Index: Positive := 1;
BEGIN
WHILE Index <= List.Count LOOP
EXIT WHEN
Get_Key(List.Table(Index)) = Key OR
Get_Key(List.Table(Index)) > Key;
Index := Index + 1;
END LOOP;
Found := Index <= List.Count AND THEN
Get_Key(List.Table(Index)) = Key;
Location := Index;
END Search;
1. The Efficiency Of The Linear Search Procedure Is O(n), It Does Not Take Advantage Of The Sorted Order, It Will Work On Unsorted Lists As Well
2. A Binary Search Utilizes The Divide And Conquer Approach That Greatly Improves The Efficiency Of The Search, Its Efficiency Is O(log2 n )
SEPARATE (Sorted_List_Package)
PROCEDURE Search(List: IN Lists;
Key: IN Keys; Location: OUT Positive;
Found: OUT Boolean) IS
Lower,Mid: Positive := 1;
Upper: Positive := List.Count;
BEGIN
IF List.Count = 0 THEN
Location := 1; Found := FALSE; RETURN;
END IF;
WHILE Lower <= Upper LOOP
Mid := (Lower + Upper) / 2;
EXIT WHEN Key=Get_Key(List.Table(Mid));
IF Key > Get_Key(List.Table(Mid)) THEN
Lower := Mid + 1;
ELSE
Upper := Mid - 1;
END IF;
END LOOP;
Found := Get_Key(List.Table(Mid)) = Key;
IF Key > Get_Key(List.Table(Mid)) THEN
Location := Mid + 1;
ELSE
Location := Mid;
END IF;
END Search;
1. A Linked Keyed Table Can Be Built By Adding A Layer Of Abstraction On Top Of The Basic Linked List Package And Creating A Linked Sorted List
2. The Basic Linked List Package Can Be Instantiated For Any Private Type, The Linked Sorted List Requires That The Type Have A > Function Defined
3. The Linked Sorted List Package Maintains A Sorted List By Searching The List Before Insertion Or Deletion

WITH Linked_List_Package;
GENERIC
TYPE Elements IS PRIVATE;
TYPE Keys IS PRIVATE;
WITH FUNCTION ">"(Left,Right: Keys) RETURN
Boolean IS <>;
WITH PROCEDURE Put(Item: Elements) IS <>;
WITH FUNCTION Get_Key(Element: Elements)
RETURN Keys;
PACKAGE Sorted_List_Package IS
TYPE Lists IS PRIVATE;
PROCEDURE Insert(List: IN OUT Lists;
Element: IN Elements);
PROCEDURE Delete(List: IN OUT Lists;
Key: IN Keys);
PROCEDURE Find(List: IN OUT Lists;
Key: IN Keys; Element: OUT Elements;
Found: OUT Boolean);
Full_List,Duplicate_Key: EXCEPTION;
PRIVATE
PACKAGE LL IS NEW Linked_List_Package
(Elements);
TYPE Lists IS NEW LL.Lists;
END Sorted_List_Package;
PACKAGE BODY Sorted_List_Package IS
PROCEDURE Search(List: IN Lists;
Key: IN Keys; Last,This: IN OUT Lists;
Found: OUT Boolean) IS
BEGIN
Last := NULL;
This := List;
WHILE This /= NULL LOOP
EXIT WHEN Key > Get_Key(This.Data)
OR Key = Get_Key(This.Data);;
Last := This;
This := Lists(This.Next);
END LOOP;
Found := Last /= NULL AND THEN
Key = Get_Key(Last.Data);
END Search;
PROCEDURE Find(List: IN OUT Lists;
Key: IN Keys; Element: OUT Elements;
Found: OUT Boolean) IS
Last,This: Lists; In_List: Boolean;
BEGIN
Search(List,Key,Last,This,In_List);
IF In_List THEN
Element := This.Data;
END IF;
Found := In_List;
END Find;
PROCEDURE Insert(List: IN OUT Lists;
Element: IN Elements) IS
Key: Keys := Get_Key(Element);
Last,This: Lists;
Found: Boolean;
BEGIN
Search(List,Key,Last,This,Found);
IF Found THEN
RAISE Duplicate_Key;
END IF;
LL.Insert(LL.Lists(List),
LL.Lists(Last), Element);
EXCEPTION
WHEN Storage_Error =>
RAISE Full_List;
END Insert;
PROCEDURE Delete(List: IN OUT Lists;
Key: IN Keys) IS
Last,This: Lists;
Found: Boolean;
BEGIN
Search(List,Key,Location,Found);
IF Found THEN
LL.Delete(LL.Lists(List),
LL.Lists(Last));
END IF;
END Delete;
END Sorted_List_Package;
Advantage
1. A Binary Search Is Possible, The Efficiency Of A Binary Search Is O(log2 n)
Disadvantages
1. The Size Of The Table Must Be Fixed At Compile Time
2. The Efficiency Of Insertion And Deletion, Excluding The Search Is Linear, O(n), Because Of The Need To Move Data
Advantages
1. The Size Of The Table Is Limited Only By The Memory Available In The Heap
2. Excluding The Search, The Efficiency For Insertion And Deletion Is O(1)
Disadvantage
1. The Only Possible Search Algorithm Is A Linear Search With Efficiency O(n)
/ Top of Page /