Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/TOTDOC.ZIP/CHAPT19.TXT

Text File | 1991-02-11 | 19.6 KB | 456 lines

                                                                     Customizing
                                                                          Linked
                                                                           Lists





         "As we acquire knowledge, things do not become more comprehensible, but
         more mysterious."

                                                                     Will Durant





         Doubly-linked lists are ideal for managing large lists of data, they
         are memory efficient and fast. The only problem is they are compli-
         cated! Fortunately, the Toolkit provides a very easy to use doubly-
         linked list object called DLLOBJ. DLLOBJ is an abstract object designed
         specifically to simplify the task of extending the object. In this
         chapter, techniques for developing a custom doubly-linked list for
         managing records is discussed.

         You might want to consider re-reading the section on linked list theory
         (page 9-1) before proceeding.



DLLOBJ

         Unlike many objects, you do not need to understand very much about
         DLLOBJ to create descendant objects. All the following methods (which
         were described in chapter 9) are unaffected by the type of data stored
         in the list, and do not need to be modified in descendant objects:

         procedure   Advance(Amount:longint);
         procedure   Retreat(Amount:longint);
         function    NodePtr(NodeNumber:longint): DLLNodePtr;
         procedure   Jump(NodeNumber:longint);
         procedure   ShiftActiveNode(NewNode: DLLNodePtr; NodeNumber: longint);
         procedure   DelNode(Node:DLLNodePtr);
         procedure   DelAllStatus(BitPos:byte;On:boolean);
         function    TotalNodes: longint;
         function    ActiveNodeNumber: longint;
         function    ActiveNodePtr: DLLNodePtr;
         function    StartNodePtr: DLLNodePtr;
         function    EndNodePtr: DLLNodePtr;
         procedure   EmptyList;
         procedure   Sort(SortID:shortint;Ascending:boolean);
         procedure   SwapNodes(Node1,Node2:DLLNodePtr);


         The DLLOBJ stores un-typed data in binary format. You can literally
         stored any type of data in a DLLOBJ list. The following methods add and
         modify data in a list:


19-2                                                       Extending the Toolkit

--------------------------------------------------------------------------------

         function Add(var TheData;Size:longint): integer;
         function Change(Node:DLLNodePtr;var TheData;Size:longint): integer;
         function InsertBefore(Node:DLLNodePtr;var TheData;Size:longint): inte-
         ger;


         Each of these three methods are passed an untyped parameter and a lon-
         gint indicating the size of the data. In descendant objects, you will
         call these methods to manipulate the data in the list. The following
         methods return information about the data stored in the list:

         procedure   Get(var TheData);
         procedure   GetNodeData(Node:DLLNodePtr;Var TheData);
         function    GetNodeDataSize(Node:DLLNodePtr):longint;
         function    GetMaxNodeSize: longint;


         The most used method is GetNodeData, which will update a passed un-
         typed parameter with the data stored in the list. It is the fundamental
         way for a descendant object to get data from the list.



Extending DLLOBJ

         The main reason for extending DLLOBJ is to make the new object manage a
         specific type of data. The Toolkit includes the descendant StrDLLOBJ,
         which is specifically designed to store strings, and FileDLLOBJ, which
         stores DOS file details.

         In this section, DLLOBJ will be extended and customized to store a
         record. To illustrate the principles involved, we will create a new
         object RecordDLLOBJ to store the following record data:

         RecordInfo = record
            FirstName: string[15];
            LastName: string[15];
            Company: string[20];
            Tel: string[10];
            CumDollarsSpent: real;
            LastOrder: longint;
            Comments: string[40];
         end;


         The main methods that need to be customized are the data manipulation
         methods, i.e. Add, Change and InsertBefore. If you want to display the
         object in a Browse or List window you must also customize the GetStr
         virtual method. GetStr is called by the browse and list objects, and is
         simply a function which returns the data stored at a node in string
         form. The fifth method which usually needs to be customized is Wron-



Customizing Linked Lists                                                    19-3

--------------------------------------------------------------------------------

         gOrder. This method provides the Sort method with the information
         needed to sort the data, and is discussed in a later section. The new
         object would therefore be declared as follows:

         RecordListOBJ = object (DLLOBJ)
            constructor Init;
            function    Add(Rec:RecordInfo): integer;
            function    Change(Node:DLLNodePtr;Rec:RecordInfo): integer;
            function    InsertBefore(Node:DLLNodePtr;Rec:RecordInfo): integer;
            function    WrongOrder(Node1,Node2:DLLNodePtr;
                                   Asc:boolean): boolean;        VIRTUAL;
            function    GetStr(Node:DLLNodePtr;
                               Start,Finish: longint):string;    VIRTUAL;
            destructor  Done;                                    VIRTUAL;
         end; {RecordListOBJ}


         Notice that Add, Change and InsertBefore are each passed a variable of
         type RecordInfo. All these methods need to do is call their correspond-
         ing DLLOBJ method and pass the record as an untyped parameter together
         with the record size. The three methods would be implemented as
         follows:

         function RecordDLLOBJ.Add(Rec:RecordInfo): integer;
         begin
            Add := DLLOBJ.Add(Rec,sizeof(Rec));
         end; {RecordDLLOBJ.Add}

         function RecordDLLOBJ.Change(Node:DLLNodePtr;
                                       Rec:RecordInfo): integer;
         begin
            Change := DLLOBJ.Change(Node,Rec,sizeof(Rec));
         end; {RecordDLLOBJ.Change}

         function RecordDLLOBJ.InsertBefore(Node:DLLNodePtr;
                                             Rec:RecordInfo): integer;
         {}
         begin
            InsertBefore := DLLOBJ.InsertBefore(Node,Rec,sizeof(Rec));
         end; {RecordDLLOBJ.InsertBefore}


         It's really as simple as that.

         The function method GetStr is passed three parameters; a node pointer
         indicating which data to access, and the Start and Finish parameters of
         type longint. Start and Finish identify the first and last character
         positions of the sub-string to be returned by the function. The DLLOBJ
         method GetNodeData can be used to retrieve the node data, and then the
         data must be converted into string form. The requested portion of this
         string can then be returned. GetStr could be implemented as follows:



19-4                                                       Extending the Toolkit

--------------------------------------------------------------------------------

         function RecordDLLOBJ.GetStr(Node:DLLNodePtr;Start,Finish: lon-
         gint):string;
         {Returns string representation of record}
         var
           Temp: string;
           Rec: RecordInfo;
         begin
            if Node = nil then
               GetStr := 'Not found'
            else
            begin
               GetNodeData(Node,Rec);  {inherited method}
               with Rec do
               begin
                  Temp := inttostr(ActiveNodeNumber)+': '+
                          FirstName+
                          LastName+
                          Company;
                  if Finish > 53 then
                     Temp := Temp + PicFormat(Tel,'(###) ###-####',' ')+' ';
                  if Finish > 68 then
                     Temp := Temp + JultoStr(LastOrder,MMDDYY)+' ';
                  if Finish > 77 then
                     Temp := Temp + FmtNumberTOT.FormattedReal
                                    (CumDollarsSpent,2,10)+' ';
                  if Finish > 88 then
                     Temp := Temp + Comments;
                end;
                GetStr := copy(Temp,Start,succ(Finish-start));
             end;
         end; {RecordDLLOBJ.GetStr}


         GetStr will never be called with Start and Finish parameters that are
         more than 255 characters apart. In this case example, the entire record
         can be represented by a string, so GetStr builds a string and returns
         the requested sub-string. In cases where the record is larger than will
         fit in a 255 string, the method should only convert the requested por-
         tion of the record in string form. Note that the Browse object calls
         GetStr many times during a browse session, and that GetStr needs to
         respond quickly to avoid sluggishness. If you find that browsing is too
         slow, try the program with range checking, stack checking etc. turned
         off. These compiler directives slow down string-related activity con-
         siderably.


         The file EXTLINK.PAS contains the entire code for the customized
         RecordDLLOBJ object, and is only about 100 lines long. Use this unit as
         a template for your own specific record types.




Customizing Linked Lists                                                    19-5

--------------------------------------------------------------------------------

Displaying RecordListOBJ Records

         The List and Browse objects automatically support any descendant of
         DLLOBJ, and so the new object RecordDLLOBJ can be easily displayed in a
         List or Browse window.

         The key method controlling what information is displayed in the window
         is the GetStr method. Thanks to polymorphism, the List and Browse
         objects don't need to know the specifics of GetStr. When they need a
         node in string form, they simply call the DLLOBJ (or descendant) GetStr
         method, and use whichever string is returned.

         Listed below is the demo program, EXTDEM5.PAS, which displays the list
         contents in a browse window. Figure 19.1 shows the resultant output.

         Program ExtendedDemoFive;

         Uses DOS,CRT,
              totFAST, totINPUT, totList, extLINK, totSTR;

         var
           RecList: RecordDLLOBJ;
           ListWin: BrowseLinkOBJ;

         procedure BuildTheList(Filename:string);
         {loads in the data from disk - could also be from d/b}
         var
           F: file of RecordInfo;
           Rec: RecordInfo;
           Ecode: integer;
         begin
            assign(F,filename);
            {$I-}
            reset(F);
            {$I+}
            if ioresult <> 0 then
            begin
               writeln('The file ',filename,' cannot be located.');
               writeln('Demo aborting');
               halt(1);
            end;
            Ecode := 0;
            RecList.Init;
            while not eof(F) and (Ecode = 0) do
            begin
               Read(F,Rec);
               with Rec do
               begin
                  FirstName:= padleft(FirstName,15,' ');
                  LastName:= padleft(LastName,15,' ');
                  Company:= padleft(Company,20,' ');
               end;



19-6                                                       Extending the Toolkit

--------------------------------------------------------------------------------

               Ecode := RecList.Add(Rec);
            end;
            close(F);
         end; {BuildtheList}

         begin {Main program}
            BuildTheList('EXTDEM5.DBF');
            Screen.Clear(white,'░'); {paint the screen}
            Key.SetFast;
            with ListWin do
            begin
               Init;
               AssignList(RecList);
               Go;
            end;
         end.


Figure 19.1                                                             [SCREEN]
Browsing
RecordDLLOBJ



         As it stands, the string returned by GetStr is not really suited for
         displaying in a list. Each item in the list would be wider than the
         list display! A quick solution is to build a descendant of RecordDLLStr
         and replace the GetStr method with a method which only returns a short
         string, e.g. last name. The on-disk example EXTDEM6.PAS illustrates
         this technique. In this example, ListLinkOBJ is also extended and cus-
         tomized to show the full record in the message box at the bottom of the
         list. This technique was described on page 9-30. Figure 19.2 shows the
         output generated by EXTDEM6.



Figure 19.2                                                             [SCREEN]
Listing
RecordDLLOBJ



Sorting

         It is very easy to make your custom linked lists sortable. To make a
         list sortable, the inherited virtual method WrongOrder must be com-
         pleted. Behind the scenes, the Toolkit sort routines repeatedly call
         WrongOrder to determine whether two nodes are in the correct order.

         The WrongOrder method is declared as follows:

            function WrongOrder(Node1,Node2:DLLNodePtr;Asc:boolean): boolean;




Customizing Linked Lists                                                    19-7

--------------------------------------------------------------------------------

         WrongOrder is a boolean function method which should return TRUE if the
         data in the two nodes are in the wrong order. The method is passed
         three parameters; two DLLNodePtr pointers to identify the nodes to be
         compared, and a boolean to indicate whether the list is being sorted in
         ascending (true) or descending (false) order.

         The WrongOrder method must therefore get the data from the two nodes,
         and decide if they are in the appropriate order for the sort. All
         DLLOBJ objects include a shortint vSortID. This variable can be used to
         provide multiple sorting capabilities. When you call the Sort method,
         you must pass two parameters; a Sort ID, and a boolean to indicate
         whether the sort order is ascending or descending. The Toolkit automat-
         ically updates vSortID with the parameter passed to Sort. WrongOrder
         should therefore check vSortID to determine what data to use in
         deciding whether the order is correct.

         In the RecordDLLOBJ example, the following codes might be appropriate:

                   1      sort on LastName
                   2      sort on Company
                   3      sort on Tel
                   4      sort on CumDollarsSpent
                   5      sort on LastOrder

         The actual codes you select are not important. You decide which fields
         you want to be able to sort on, and which codes to use. Using the
         listed codes, the WrongOrder method for the RecordDLLOBJ object would
         be as follows:

         function RecordDLLOBJ.WrongOrder(Node1,Node2:DLLNodePtr;Asc:boolean):
         boolean;
         var
           S1,S2: string;
           Rec1,Rec2: RecordInfo;
           R1,R2: real;
           D1,D2: longint;
         begin
            GetNodeData(Node1,Rec1);
            GetNodeData(Node2,Rec2);
            if vSortID in [1,2,3] then
            begin
               case vSortID of
                  1:begin      {LastName}
                     S1 := Rec1.LastName;
                     S2 := Rec2.LastName;
                  end;
                  2: begin     {Company}
                     S1 := Rec1.Company;
                     S2 := Rec2.Company;
                  end;
                  3: begin     {Tel}



19-8                                                       Extending the Toolkit

--------------------------------------------------------------------------------

                     S1 := Rec1.Tel;
                     S2 := Rec2.Tel;
                  end;
               end; {case}
               if Asc then
                  WrongOrder := (S1 > S2)
               else
                  WrongOrder := (S2 > S1);
            end
            else if vSortID = 4 then  {CumDollars}
            begin
               R1 := Rec1.CumDollarsSpent;
               R2 := Rec2.CumDollarsSpent;
               if Asc then
                  WrongOrder := (R1 > R2)
               else
                  WrongOrder := (R2 > R1);
            end
            else                       {LastOrder}
            begin
               D1 := Rec1.LastOrder;
               D2 := Rec2.LastOrder;
               if Asc then
                  WrongOrder := (D1 > D2)
               else
                  WrongOrder := (D2 > D1);
            end;
         end; {RecordDLLOBJ.WrongOrder}


         To sort the list, call the method Sort, e.g. MyList.Sort(1,true). The
         demo file EXTDEM6.PAS includes a sort statement.



Using Status Codes

         List status codes are used internally by the Toolkit to support the
         displaying of lists in windows. In some circumstances, you may be able
         to use this facility in your custom lists.

         All items stored in a DLLOBJ, or descendant object, include a Status
         byte. Each of the eight bits in the Status byte can be used for a
         different purpose. Chapter 9: Managing Lists (page 9-27), describes how
         the first two bits are used by the List display object. You may recall
         that bit 0 is used to identify whether the item is tagged, and bit 1
         identifies which items to display in an alternate color. The remaining
         six bits can be used for your own custom needs. For example, you might
         use bit 2 to identify all customers with a delinquent account, and bit
         3 might identify whether the customer is international or domestic, or




Customizing Linked Lists                                                    19-9

--------------------------------------------------------------------------------

         you might extend ListOBJ to use a three-color list, and use bit 2 to
         identify items to show in the third color. Whatever the reason, they
         are there if you need them.

         To access the Status bits, you need to know how data is stored at each
         node. Each node in a list actually points to a DLLNodeOBJ. This object
         manages the storage of data at the node, as well as the node status
         byte. The following four DLLNodeOBJ methods support the Status byte:

                  GetStatus(Bitpos:byte): boolean;
                  SetStatus(BitPos:byte;On:boolean);
                  GetStatusByte:byte;
                  SetStatusByte(Val:byte);

         To call these methods use the syntax MyList.NodePtr(number)^.method.
         Use the Set methods to change a status bit, and the get methods to
         check the current status. For example, to set the fourth bit to true
         for the 12th entry in the list MyList, you would use the following
         statement:

                  MyList.NodePtr(12).SetStatus(3,true);