COSC 3319 Data Structures Lab 3 – Containers

Description

Most modern programming languages offer a “container” class for the convenience of users. Containers are typically inefficient with respect to CPU time and memory allocation compared to static types. They may however offer great convenience for the developer. Commonly offered container classes include one for constrained objects and a second for unconstrained objects. These classes typically are further refined to incorporate containers termed “sequence” and “associative.” Sequence classes hold sequences of related items. Associative classes associate a key with each element of the class then manipulate elements based on the keys. You may not utilize container classes in any language for any lab during the semester unless the lab specifically states you must use the container class. Ada provides the following container for “defined/constrained” classes:
a) Ada.Containers.Vectors
b) Ada.Containers.Doubly_lLinked_Lists
c) Ada.Containers.Hashed_Maps
d) Ada.Containers.Ordered_Maps
e) Ada.Containers.Hashed_Sets
f) Ada.Containers.Ordered_Sets
A similar group of classes/packages is provided for undefined/unconstrained types using similar names including Ada.Containers.Indefinite_Vectors with specialized generic procedures such as Ada.Containers.Generic_Array_Sort and Ada.Containers.Generic_Constrained_Sort. The purpose of this lab is to develop the basic technology to implement (program) these capabilities in languages including Ada, C++, Java, Python and Smalltalk using more basic constructs. Implementation of containers, complex numbers, etcetera using code placed in libraries extends the capabilities of languages. This technique is widely used to extend programming language capabilities and convenience for modern languages.

“C” Option: Homogeneous (maximum grade is 75):
Hint: appendix 1, 2 and 3. For the “C” Option remove the generic in appendix 2, replace “item” with Integer and set max to a specific value like 20. Appendix 3 is closest to the lab. Appendix 6 is helpful if you need to pass functions or operator overloads.
Implement package/class Integer_Containers allowing the user to store a list of integers whose meaning is application dependent with respect to the user (a homogeneous list). You must store elements in a doubly linked list (container) with a list head. The following represents a list with 33 inserted first followed by 46 on the right side (front) of the head node. The list head should contain the number of integers currently stored in the list. 

2

46

33
Head

A container (package/class) definition would normally contain procedures and/or functions to insert at the head of the list, insert at the rear of the list, provide the number of items currently in the list, search for an item returning a pointer to it if found (null if not found), print the contents of the item given a pointer to the node containing the item and ask for the next item in the list traversing the list from the front to rear. Finally, you must be able to delete a random item from the doubly linked list given its location (pointer to the item). A partial package/class specification might include the following:
package Integer_Containers is
type Integer_Container is private;
type Integer_Node_Point is access Integer_Container;
procedure InsertFront( list: in out Integer_Container, amt: in Integer, Success: Boolean);
procedure InsertRear( list: in out Integer_Container, amt: in Integer, success: out Boolean);
function listSize( list: in Integer_Container) return Integer;
function findItem( list: in Integer_Container, aValue: Integer) return Integer_Node_point);
procedure delete(list: in out: Integer_Container, Integer_NodePoint);
— Additional functions and procedures as needed.
private
type Integer_Container is record
value: Integer;
next, previous: Integer_Pointer;
end Integer_Container;
— rest of specification.
end Integer_Containers; — followed by the body in another file

–Main program
MyList: Integer_Container; — create an integer container as a doubly linked list.

Process all “C” option transactions in the order specified.
a) Insert 33 in front (right).
b) Insert 57 in front
c) Insert 85 at the rear (left).
d) Insert 62 at the rear.
e) Insert 95 at the front.
f) Print the contents of the list from front to rear.
g) Print the content of the list from rear to front.
h) Find and delete the node containing 57.
i) Find and delete the node containing 33.
j) Find and delete the node containing 33.
k) Find and delete the node containing 62.
l) Insert 22 in front.
m) Delete the node containing 95.
n) Print the contents of the list from front to rear.

“B” Option – Homogeneous (maximum grade is 80):
Hint: Appendix 1,2, 3. Appendix 6 is helpful if you need to pass functions or operator overloads.
You need not do the “C” option. Write a generic/template package/class List_Package allowing the user the ability to store any programmer defined type in a doubly linked list with the operations defined in the “C” option. Use a list head. You will probably wish to provide an overload for the “=” operator as a generic parameter. Implement the package/class List_Package allowing for any user defined in a doubly linked list. Each entry in the list other than the head node may be used to store a user defined transaction. Data fields in the head node may be used or ignored by the implementer. The basic package/class definition will contain at least the following methods:

generic
type ItemsType is private;
package List_Package is
— Methods for previous grading option
— See sample specification/code for similar application below inCompStacg.
end List_Package – followed by the body in another file

— main program
with List_Package;
procedure MainLine is
type ItemType is ( Shoes, Kites, Jacks, Food);
currentItem: ItemType;
price: Float;
amt: Integer;

type InventoryItem is record
itemName: ItemType; unitPrice: Float; inStock: Integer;
end InventoryItem;

temp, theItem: InventoryItem;

package InventoryList is new List_Package (InventoryItem); use InventoryList;

Process the following transactions in the specified order after creating homogeneous containers for cars and planes (two separate lists). You may use the code for cars and planes used in the examples below if desired. Place the cars and planes in the correct lists.
a) Insert a Ford with 4 doors at the rear.
b) Insert a Ford with 2 doors at the front.
c) Insert a GMC with 2 doors at the rear.
d) Insert a RAM with 2 doors at the rear.
e) Insert a Chevy with 3 doors at the front.
f) Print the number of items in the list.
g) Print the contents of the list (front to rear).
h) Find and delete the first Ford in the list (search front to rear).
i) Print the number of items in the list.
j) Print the contents of the list (front to rear).
k) Insert a plane with 3 doors and 6 engines by Boeing at the front.
l) Insert a plane with 2 doors and 1 engine by Piper at the front.
m) Insert a plane with 4 doors and 4 engines by Cessna at the front.
n) Print the list.

Hint: You do not need the “abstract stack (inheritance from a common ancestor) to create the car and plane types in appendix 5. You may use my code for cars and planes in your code.

“A” Option: Heterogeneous Container using Inheritance (maximum grade is 90). Appendix 6 is helpful if you need to pass functions or operator overloads.

Hint: Appendix 1,4 and 5 for all “A” Options.
You need not do the “C” or “B” options. Rather implement a single package/class using inheritance to allow multiple data types/objects in a heterogeneous list.
First: Use your package to process all “C” option transactions! You may have to create a new list element to store integers in your “A” option list.
Second: Use this package/class to implement a single doubly linked list and process all “B” Option transactions placing the cars and planes in a single list using inheritance.
A sample list with one plane and one car follows:

Head
2

Plane

Car

An example of the empty list follows:
Head

0

“A+” Option: Heterogeneous Container using Inheritance (maximum grade is 95):
Complete the “A” option. Allow at least one task to place items in the list and a second task to remove items from the list.

“A Super +” Option: Heterogeneous Container using Inheritance (maximum grade is 100):
Complete the “A” option. Allow multiple tasks to place items in the list and multiple tasks to remove items from the list preventing RACE conditions!

Appendix 1: For all options.
In most industries employee records (inventory records etcetera) appear 20 or more times in applications. Rather than define them in every application it is convenient do define them once then utilize the same definition for the abstraction in every application. Not only is this convenient but increases sharing, consistency across applications, and ease of update for all applications, The following class illustrates the sharing concept for dates.

— in file CompStk1.ads
— Exports IntIO, MonthName, MonthNmaeIO, Date and PrintDate.
with Ada.Text_IO; use Ada.Text_IO;
package CompStk1 is
package IntIO is new Ada.Text_IO.Integer_IO(Integer);
use IntIO;

type MonthName is (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep,
Oct, Nov, Dec); — Enumeration type.

package MonthNameIO is new – Ada generates i/O routines.
Ada.Text_IO.Enumeration_IO(MonthName);
use MonthNameIO;

type Date is record
Month: MonthName;
Day: Integer range 1..31; — Limits range.
Year: Integer; — No limit on range.
end record;

procedure PrintDate(aDate: Date);
end CompStk1;

–in file CompStk1.adb
package body CompStk1 is

procedure PrintDate(aDate: Date) is
begin
put(“mmm/dd/yyyy is “); put(aDate.Month);put(“/”);
put(aDate.Day,2); put(“/”); put(aDate.Year,4);
end PrintDate;
end CompStk1;

Appendix 2: For “C” Option
Sample homogeneous stack for intrinsic data types and programmer data type including task types.

generic — in file Gstack.ads
max:integer; — size of stack
type item is private; — type to stack
package gstack is
procedure push(x: in item);
procedure pop(x: out item);
end gstack;
%%%%%%%%%%%%%%%%%%%%%%%%%%

package body gstack is — in file Gstack.adb
s:array(1..max) of item; — allocate in stack.
top: integer range 0..max;

procedure push(x: in item) is
begin
top := top + 1; s(top) := x;
end push;

procedure pop(x: out item ) is
begin
x := s(top); top := top – 1;
end pop;

begin
top := 0; –initialize top of stack to empty
end gstack;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

with Ada.Text_IO; use Ada.Text_IO; — in file Gusestac.adb
with gstack; — generic stack defined in gstack10.ads /.adb
procedure genstack is
package IIO is new Ada.Text_IO.Integer_IO(integer); use IIO;

package integer_stack is new gstack(100,integer);
use integer_stack;
m: integer;
begin
for i in 1..4 loop
put(“enter an integer “); get(m); push(m);
end loop;

for i in 1..4 loop
put(“result of pop “); pop(m); put(m); new_line;
end loop;
end genstack;

— Consider adding: package intStk is new gstack(10,integer); use intStk;
— Now push(m) will result in a compile time error as “Push” cannot be
–uniquely determined from the context. Use intStk.push(m) or
–integer_stack.push(m), the full object oriented notation.

Now consider using the “date” type. A skeleton follows.
with Ada.Text_IO; use Ada.Text_IO;
with gstack;;
with CompStkg; use CompStkg;

procedure UCmpStkg is — in file UCmpStkg
stackSize: integer := 15;
package DateStack is new gstack(stackSize, Date);
use DateStack;
— rest followed by access, shown 2 ways
push(aDate); –if stack is clearly identifiable (unique0 or to specify using
DateStack.push( aDate ); — DateStac if there are multiple date stacks. 

Appendix 3: Stack implemented as a linked list.
The following creates a homogeneous stack using a linked list. The “C” option does not require the generic as each stack only stores a specific predefined type. The generic allows for the user to store any intrinsic or user defined type (including tasks, protected types, etc.). Replacing “MyType with “integer,” Float,” Character, Date etcetera creates the desired stack type.
generic — in file CompStkg.ads
type MyType is private;
package CompStkg is

procedure Push(X: MyType);
function Pop return MyType; — Note parenthesis are not required if there are no parameters.

private

type Node; — Avoid recursive definition.
type NodePtr is access Node; — Define pointer type to Node.

type Node is record — Allocated in heap at run time.
MyData: MyType;
Next: NodePtr;
end record;
end CompStkg;

with Ada.Unchecked_Deallocation; — in file CompStkg.adb
package body CompStkg is
— Provide opportunity for garbage collection and reuse of Nodes.
function free is new Ada.Unchecked_Deallocation(Node, NodePtr); — reclaim heap storage.
Head, pt: NodePtr := null; — Ada actually sets all pointers to null when they are declared.

procedure Push(X: MyType) is
begin — No check for overflow.
Head := new Node'(X, Head); — Allocated from returned memory, heap is none returned.
end Push; — Most languages return Head = null if out of storage.
 

function Pop return MyType is
X: MyType;
begin
X := Head.MyData; — No check for underflow.
pt := Head;
Head := Head.Next;
free(pt); — Memory hemorraging occurs if forgotten.
return X;
end Pop;

end CompStkg;

— Example of programming by “Composition” (bottom-up, creating whole from parts)
— as opposed to programming by “Classification”
— (top-down) better known as the use of inheritance.

with Ada.Text_IO; use Ada.Text_IO;
with CompStk1; use CompStk1;
with CompStkg;
procedure UCmpStkg is — in file UCmpStkg

package CharStack is new CompStkg(character);
use CharStack;

package DateStack is new CompStkg(CompStk1.Date);
use DateStack;

Char: Character;
ADate: Date;

begin
Push(‘A’); Push(‘B’); Push(‘C’);
put(pop); put(Pop); put(Pop); new_line(2);

Push((Jan, 15, 1992)); Push((Mar, 24, 1994));
Push((Jun, 12, 1999));
ADate := Pop; PrintDate(ADate); new_line;
Adate := Pop; PrintDate(Adate); new_line;
Adate := Pop; PrintDate(ADate); new_line;
end;

Sample Output:
CBA

mmm/dd/yyyy is JUN/12/1999
mmm/dd/yyyy is MAR/24/1994
mmm/dd/yyyy is JAN/15/1992

Appendix 4: “B/A” Option to Implement Containers.
The preceding examples are limited to stacks containing a single data type, i.e., “homogeneous” lists. Industrial grade applications may find it necessary to store more than one type/class item in the container. The assumption is the “heterogeneous” items will have similar operations on the data. The software will select the appropriate version of the method for the user selected operation, i.e., polymorphism. Ada is polymorphic by default. We start with an example of homogeneous inheritance (tagged types) then expand the example to allow heterogeneous data types. The secret in most object oriented languages (Java, C++, SamllTalk, Ada, etc.) is for all children to be derived from a common parent type. Similar operations (methods, procedures, functions) on the data type employ polymorphic methods to implement the behavior for each desired type. The container for the parent type implies the ability to include children derived from the parent.

— Creation of a “cube” type from a “rectangle” type using inheritance.
–in file taged1.adb
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure taged1 is

type Rectangle is tagged — tagged allows inheritance
record
length: Integer;
width: Integer;
end record;

function Size(r: in Rectangle) return Integer is — “intrinsic” method
begin return r.length * r.width; end Size;

— create a cube by inheriting from Rectangle.

type Cube is new Rectangle with – create cube using inheritance
record height: Integer; end record;

— Cube inherits fields length, width, and function Size.
— This size may be redefined as:

function Size(c: Cube) return Integer is — intrinsic function
begin
return Size(Rectangle( C )) * C.height; — cast “Cube” as a rectangle.
end Size;

— Note the type conversion “Rectangle(c)” so that the inherited
— function Size for Rectangle (overload) can be used.

rect1: Rectangle := (6,10);
cube1: Cube := (length => 6, width => 10, height => 20);
begin
put( Size( rect1 ) ); put( Size( cube1 ) );
rect1 := Rectangle( cube1 ); cube1 := ( rect1 with 20 );
end taged1;

— User-written subprograms are classified as primitive operations
— if they are declared in the same package specification as the
— type and have the type as a parameter or result. Derived types
— inherit all primitive operations that belong to the parent type.

Appendix 5: “B/A” HeterogenousAbstract Type taking advantage of inheritance. Ada allows definition/implementation of related types/classes in the same file.
This example uses the object notation for methods as follows to creating intrinsic methods for a package:
“procedures:” (