More on (not moron) Linked Lists
Just like we did for tables, we can make a Lists_Generic package for manipulating different element types using the same code
Here is the spec:
Go through the body on your own, and make sure you understand what is going on


Managing Your Own Memory
Recall that when you allocate a new piece of memory, what you are actually doing is grabbing memory form the heap
This is an expensive operation
The system needs to find a block in the heap of the appropriate size for the new block
We can improve performance by maintaining our own list of “discarded” blocks
Managing Your Own Memory (cont.)
Because we will be allocating blocks of the same size each time, we know that the size of discarded blocks matches what we need
Now, instead of simply calling Dispose, we take the block, and add it to another list which contains discarded blocks
Then when we need to allocate a new block, we first check see if there is a block in our discarded list, and if not, we call NEW
So How Does This Look?
Linked Lists have the following general structure:
Disposing of an Element
Implementing Queues and Stacks with Lists
The Queue and Stack implementations we introduced before were limited to a given capacity
We can implement the Queue and Stack ADTs using Linked Lists to remove this constraint
This is the nice thing about encapsulating the implementation of an ADT in a package!
Tables_Generic
We can do the same thing with Tables_Generic
In order to REALLY understand the new Tables_Generic (Program 9.6), you need to understand the function Locate

Analysis of Runtime Complexity
Using Unordered Lists, what is the runtime complexity of a search?
Using Ordered Lists, what is the runtime complexity of a search?
Passive vs. Active Iteration
Using Traverse, we can apply a given function (e.g. Put) to each element
Sometimes this isn’t enough, and we want more control over each “visit”
StartTraversal( T );
E := RetrieveCurrentElement( T );
MoreElements( T );
MoveToNextELement( T );
Now we can perform our manipulations on E
Sparse Vectors and Matrices
For large vectors and matrices, many of the cells are empty
This wastes a lot of space!
We can implement them using dynamic linked structures instead of as static arrays
For example, store:
V := ( 0.0, 1.5, -3.7, 0.0, 0.0, 0.0, 2.4, 0.0 );
as a list of  <subscript,value> pairs:
<2,1.5>, <3,-3.7>, <7,2.4>
Sparse Vectors and Matrices (cont.)
Vector/Matrix operations:
Store/Retrieve:

V( 5 ) := 23.7;
X := V( k );

Can be recoded as:

Store(Vector => V,Subscript => 5,Value => 23.7 );
X := Retrieve( Vector => V, Subscript => k );
Operations (cont.)
To Retrieve for a given subscript:
Search the list for an element with the desired subscript
If the search is successful, return the associated value
Otherwise, return 0
Operations (cont.)
To Store a value with a given subscript:
If the element value is 0, delete it from the list
Otherwise, search the table for an element with the desired subscript
If the search is successful, replace the value with the new value
Otherwise, insert a new element with the given <subscript,value> pair

To Add Two Vectors...

. . .
FOR Which IN LowBound..HighBound LOOP
  Store( Result, Which,
    Retrieve( Left, Which ) +
    Retrieve( Right, Which );
END LOOP;
. . .
General Access Types
We have seen how to implement “pointers” to heap data in Ada:
TYPE NodePtr IS ACCESS Node;
MyPtr : NodePtr;
MyPtr := NEW Node;
Ada 95 relaxes the restriction that ACCESS variables only point to heap memory:
Pool-specific access types (the familiar ones)
General access types (new ones)
General Access Types
TYPE IntegerPtr IS ACCESS Integer;
TYPE IntegerPtr IS ACCESS ALL Integer;
TYPE IntegerPtr IS ACCESS CONSTANT Integer;
Variables must explicitly allow themselves to be pointed to
P : IntegerPtr;      -- ACCESS ALL type
X : Integer;
Y : ALIASED Integer;
P := X’Access;       -- Will cause error
P := Y’Access;       -- Okay
Okay, now we go OO!
Say it with me:


OOOOOOOOOOOOOOOO!


Class-Wide Types
Tagged types takes us part of the way towards Object Orientation:
Derive records from other records
Inherit data fields
Inherit operators
Add data fields
Add operators
. . .
Class-Wide Types (cont.)
Given that T is a tagged type, the attribute:
T’Class
represents the entire hierarchy of which T is the parent.
This is known as a class-wide type
Combining class-wide types with general access types allows more freedom (p. 371-372)