Power-Programmierung/CD1.mdf/pascal/library/dos/arrays/generics/genlist/genlist.doc

Text File | 1989-07-28 | 11.7 KB | 277 lines

{
******  The List and L_Heap Objects (and Descendants) *****


Design and Implementation ---  Eric C. Wentz

                               1-703-860-3807

                               2374 Antiqua Court
                               Reston, Va. 22091


Last Modification Date : 7-28-89


********************************************************************


Design Objective(s):

       (1) {List}

           Implementation of a fully Generic Doubly-Linked List Object,
           Capable of all List functions, for any DataType.

       (2) {L_Heap}

           Implementation of a fully Dynamic Generic Heap Object, capable
           of all Heap functions for any Datatype.

Limitations:

           Individual Nodes in both are limited to the maximum size which
           GetMem can allocate to a single variable, or 65521 bytes.

***************************************************************************
Implementation {GenList} :
***************************************************************************

Unit GenList;  {Generic Fully Dynamic Doubly-Linked List w/ArrayLike extras}

{ Unit GenList introduces the LinkedList equivalent of the FlexArray datatype }
{ Lists are allocated dynamically on the Heap, but as they are allocated on a }
{ node-by-node basis, they can grow to occupy the entire Heap.  This is their }
{ only superiority over the FlexArray type.  FlexArray's will perform quite a }
{ bit faster for all operations, and take up much less overhead (since there  }
{ are TWO pointers associated with each element in a List).  Nevertheless,    }
{ for Lists/Arrays of LARGE data structures, or simply huge lists of smaller  }
{ structures, Lists should prove quite handy.                                 }

{ All Lists (and descendant objects) MUST be CREATEd before any other         }
{ operations are performed upon them.  Using CREATE to re-initialize          }
{ may well lead to system crashes, so DON'T do it!  By using DESTROY and      }
{ then INITting again, you can re-use the List type for whatever purpose      }
{ deemed appropriate.  As ListS use Untyped Variables to achieve Genericity,  }
{ you MUST tell the List how many bytes to expect -- use SizeOf.              }
{ Procedures RESETELEMENT_N and GETELEMENT_N provide Array-like access to     }
{ Established Lists, and DO check current bounds of List.  Attempting to      }
{ Access beyond these bounds is an error and will terminate the program!      }
{ Procedures APPEND, DELETE and INSERTAFTER_N are more ListSpecific .         }
{ APPEND is used to add new elements to the "end" of the List.  Insertion at  }
{ a particular index is accomplished with INSERTAFTER_N, and deletion of a    }
{ given element is similarly handled by DELETE.  REMEMBER: For DELETE and     }
{ methods ending in "_N", it is a program-terminating error to attempt to     }
{ access the List outside of it's (Current) boundaries!! Procedure LISTCOPY   }
{ will copy one list to another (if enough memory) and is of necessity very   }
{ slow. Finally, Functions ElemSize and CurrentLength provide important info  }
{ as to (Current) List status.  Procedure ReWind is provided only to speed up }
{ those List Accesses which will be sequential, starting from the "Top", and  }
{ is generally not particularly useful or needed.  It merely goes directly to }
{ the "Top", where the "_N" methods must run down the pointers to reach the   }
{ "Top".  Calling it once will suffice to speed up sequential accesses.       }
{ Note, here I am using Top in the sense of a FIFO Queue, NOT as in a Stack!  }

{ LAST MOD: Added Function Node_N for more direct access to Nodes, as needed  }
{ in Unit GenHeap, which defines the Heap structured variant of this List.    }

{ NOTE: Lists (as defined here) are "indexed" 1..CurrentLength }
{       CurrentLength = 0 equates to Empty List                }

INTERFACE  {NOT complete, but all needed information is here}

Type
  List = Object
    (**********************************************************************)
    { GENERAL NOTE: Every time the parameter "Size" is specified, you MUST }
    {               use SizeOf(<inputvariable>) to ensure correctness!!    }
    (**********************************************************************)

    Procedure Create;{ List Must be CREATEd EXACTLY once, and before all else }

    Procedure Init (Size : Word);  { Once CREATEd, you may Re-Use a List }
    Procedure Destroy;             { by DESTROYing and then Re-INITting  }

    Function CurrentLength : LongInt;   { Report Current Length of List }
    Function ElemSize : Word;           { Report Size of List Elements  }
    Function Current : LongInt;         { Where is "Cursor" ?           }
    Procedure ReWind;                   { Go To the "Top" of the List   }

    Procedure Append (Var InData; Size : Word); { Add InData to END of List  }
                                                { automatically "grows" List }

    Procedure GetElement_N (Var OutData; N : LongInt; Size : Word);

                           { Return value of Nth member of List    }
                           { legal N's are from 1..CurrentLength   }
                           { Only legal size is equal to ElemSize. }

    Procedure ReSetElement_N (Var InData; N : LongInt; Size : Word);

                           { Re-Assign value of Nth member of List }
                           { legal N's are form 1..CurrentLength   }
                           { Only legal size is equal to ElemSize. }

    Procedure Delete (N : LongInt); { Delete Nth Element }

    Procedure InsertAfter_N (Var InData; N : LongInt; Size : Word);

                           { Insert new value into list AFTER Nth element }

    Procedure Copy (L : List); { Target List MUST be CREATEd or DESTROYed }

    Function Node_N (N : LongInt) : DPtr; { Returns a Pointer to the Nth Node }
                                        { See Unit LGenHeap for correct usage }
  End;


IMPLEMENTATION { Not Reproduced }

***************************************************************************
Implementation {LGenHeap} :
***************************************************************************

Unit LGenHeap; {Generic Fully Dynamic Doubly-Linked Heap}

INTERFACE { NOT the entire Interface, but all needed definitions are here }

{Introduces the Heap variant of the List Object}

Type
  L_Heap = Object (List)

                Greater : NodeSortFunc;

                Procedure Init (SortBy : NodeSortFunc; Size : Word);

                                   { Size refers to ElementSize! }

                Procedure SiftDown (I,J : LongInt);

                                   { While I can think of No reason to  }
                                   { Use SiftDown externally, there may }
                                   { be a reason, so I have exported it }

                Procedure SiftUp (Var Elem; Size : Word);

                                 { SiftUp can be used in place of Append }
                                 { In order to Create/Maintain a Heap as }
                                 { a Heap while adding elements, thus    }
                                 { allowing the use of Sort instead of   }
                                 { HeapSort which structures a Heap by   }
                                 { using BuildHeap.                      }

                Procedure BuildHeap;

                                 { Creates the Heap structure from }
                                 { the ground up.                  }

                Procedure ChangeSort (NewSort : NodeSortFunc);

                          { Permits redefinition of collating sequence }
                          { for already established Heaps.             }

                Procedure Sort;

                          { Sorts a Heap into Ascending order    }
                          { Assumes HEAP is built or maintained. }

                Procedure HeapSort;

                          { Sorts a Heap into Ascending order     }
                          { Assumes nothing about Heap structure. }

                Procedure Copy (H : L_Heap)

             End;


IMPLEMENTATION { Not Reproduced }

**************************************************************************
 { UNIT DEPENDENCIES }
**************************************************************************

        FlexPntr
           |    \
           |     \
           |      \
           |       \
        GenDatum    \
           |        |
           |        |
           |        |
           |        |
        DoubLink____|___
           |\\      |   \
           | \\     |    \
           |  \\    |     \
           |   \\   |      \
           |    \\  |       \
        GenList  \\ |        \
        /     \   \\|         \
       /       \  | \  /----NodeSort
      /         \ | |\/      |
     /           \| |/\      |
  Lists        LGenHeap\     |
                    \   \    |
                     \   \   |
                      \   \  |
                       \   \ |
                        L_Heaps


****************************************************************************
 { ERROR MESSAGES }
****************************************************************************

POSSIBLE ERROR MESSAGES: (Unit GenList)

           Attempted to Insert wrong size data Element.
           Attempted GetElement with wrong size variable.
           Attempted to index past current end of List.
           Attempted ReSetElement with wrong size variable.
           Attempted to delete past current bounds of List.
           Attempted to insert past current bounds of List.
           Attempted InsertAfter with wrong size data Element.
           Attempted Function Node_N beyond Current Length.
           **** OUT OF MEMORY ERROR ****


POSSIBLE ERROR MESSAGES: (Unit GenDatum)

           Attempted Set_Data with Incompatible Data Size.
           Attempted Get_Data with Incompatible Data Size.
           Attempted Destroy on Non-Initialized Datum.
           Attempted Init on Initialized or UnCREATEd Datum.
           **** OUT OF MEMORY ****


  { To be honest, I must add that I may very easily have overlooked something.
    If you find such an error, please write and let me know!!! }


******************************************************************************
 { PROPRIETARY CODE }
******************************************************************************

The FlexPntr Unit.

ALL the code in it was either directly taken from an article in
PROGRAMMERS JOURNAL by Tom Swann or inspired by the same article
(Programming on the Variant Express PJ V6.5 Sept/Oct 1988), and is of such a
fundamental nature that no changes are really possible or desireable in ANY
context.  I have distributed it as a TPU simply because Turbo has no other
method available for PRIVATE declarations (ala ADA).  Therefore, since I did
not really originate the code, and since there is no reason to ever change
any of it, I will NOT distribute the source code for any reason.  Those
incureably interested individuals should look up the above article, paying
particular attention to Mr. Swann's definitions of IntPtr and IntRec, which
I have renamed "FlexPtr" and "FlxArray" respectively. NOTE: the array which
Mr. Swann defines within the IntRec is referenced with field name "Flex" in
my version of the construct, and is an array of Bytes, not Integers.

******************************************************************************
******************************************************************************
******************************************************************************
}