Skip Lists
==========

This file contains some notes related to the implementation of Skip Lists (Homework #2)

 1. At the top of the body file you will want to do:

      with Ada.Numerics.Float_Random;

    and then declare, inside the package body itself, a variable representing a random number
    generator. I suggest using:

      Gen : Ada.Numerics.Float_Random.Generator;

    To generate a random floating point value call the following function:

      Ada.Numerics.Float_Random.Random(Gen)

    This returns a random value between 0.0 and 1.0 (not including 1.0). You can use a 'use'
    statement if you want to avoid typing the full package name of Ada.Numerics.Float_Random,
    but since there are only two places you need to do that, it might not be worth it.

 2. The pseudo-code in the skip lists paper is flawed. Consider the pseudo-code for Search.
    Notation such as x := list->header makes 'x' reference the header (an array of node
    pointers) at the start of the list. However, latter expressions such as x->key then make no
    sense because the array does not contain a component 'key'. For that matter x->forward[1]
    doesn't make sense either because the array does not contain an array named forward.

    The usage of 'x' in the pseudo-code makes it appear as if 'x' references an entire node...
    some kind of sentinel node at the beginning of the list. Thus, contrary to the text of the
    paper, 'header' really is an entire node where the key and value components are just being
    ignored.

    In Ada terms that means the key and value components of that header node are being default
    initialized (if there is any default initialization) which could potentially be expensive in
    space and time depending on the actual types for Key_Type and Value_Type (See the Skip_Lists
    procedure Initialize). There are ways to avoid this extra default initializations, but they
    are complicated so don't worry about it. In most cases the default initializations would be
    a minor or insignificant issue.

 3. The paper shows nodes with variable sized arrays of pointers in them. Doing this in Ada is
    complicated because each instance of a record type has to have the same size. What would be
    necessary would be to store an access value in the record that points at a dynamically
    allocated array of the appropriate size. This complicates the creation and destruction of
    the nodes.

    To simplify, I recommend just using a fixed size array of size Max_Level in every node. Then
    just process all the pointers in every node as appropriate. In many cases, most of those
    pointers would be null. This increases the space/time overhead of the implementation. It
    remains to be seen how problematic that will be.

 4. Don't forget to use 'for I in reverse ...' in Ada to make a loop that counts backwards. This
    is how to handle the 'downto' in the pseudo-code.

 5. Don't forget to protect against X.Forward(I) being null. The pseudo-code doesn't do this.
    You may need to use 'and then' to ensure an appropriate order of evaluation of subexpressions
    in a conditional expression.

 6. Instead of returning 'failure' in Search, do 'raise Not_Found' to raise an exception.

 7. The Random_Level function is only needed by Insert so it can (and probably should) be nested
    inside of Insert.

 8. In the Insert pseudo-code, the part where it extends the list's level can be removed. In
    this implementation the list stays at Max_Level. After computing the newLevel, you can go
    directly into making a new node. The syntax for doing so looks like:

      X := new Node'(Key, Value, (others => null));

 9. Our implementation tracks the number of elements in the list (the pseudo-code doesn't do
    that. Don't forget to manage that count at the end of Insert and Delete.

10. Call Deallocate_Node to free a node. Deallocate_Node is an instance of
    Unchecked_Deallocation (see the top of the body file).

11. At the end of Delete the pseudo-code adjusts the list's level if necessary. Since we aren't
    changing the list's level, that can be removed.

12. When compiling the test program you will see two warnings. One warns about a possible
    infinite loop. This arises because the compiler doesn't realize Gen returns a different
    random number each time it is called. The Float_Random function has an 'in' parameter and
    the compiler assumes calling the function doesn't change the parameter. It gets changed
    anyway because internally there are pointers involved. This weirdness is one of the reasons
    Ada 2012 started allowing functions to have 'out' and 'in out' parameters... preventing side
    effects by restricting to just 'in' doesn't really work. Float_Random should have been
    defined with an 'in out' parameter, but at the time it was standardized that wasn't an
    option.

    The second warning is about a possible use of an uninitialized variable. I believe the code
    is correct, however.