[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]

{

Peterborough, Ontario, CANADA

Hi !

  If any of you boys have been reading BYTE magazine, you may have
  noticed an article in the Dec/93 issue on Directory objects (in
  C++ however). I was keenly interested in this article, because it
  showed a quick and easy way to handle directory recursion - which
  was necessary for a project I was doing.

  While the complete code listings weren't given, they were in C so
  I couldn't use them directly anyways, so I just wrote my own
  object in TP. (Works great, btw)

  I've decided to wake this conference up a bit so I'm going to post
  this stuff over the next couple of days. The first installment is
  the SORT unit which implements a binary-tree sorting object for
  the sort method of the directory object. This object is completely
  re-usable and extendable (designed so from the ground up) and
  helps demonstrate more uses for OOP.
----------------------------------------------------------------------
}
Unit SORT;

INTERFACE

TYPE
   comparefunc = function(d1, d2 :pointer):integer;
                             { function returns sort value for data  }
   ptree    = ^treenode;
   treenode = record
      data  :pointer;
      left,
      right :ptree;
   end;
                              { ****** Abstract sort object ******
                                         Must be inherited
                              }
   pSortTree = ^oSortTree;
   oSortTree = OBJECT
      root    :ptree;
      comp    :comparefunc;

      constructor Init(cf :comparefunc);
      destructor  Done;

      procedure   InsertNode(n :pointer);
      procedure   DeleteNode(var Node); virtual; { abstract }
      function    ReadLeftNode:pointer;
   end;

IMPLEMENTATION

constructor  oSortTree.Init(cf :comparefunc);
begin
   FillChar(self, SizeOf(self), #0); { zero out object data }
   comp := cf; { set "compare" function to user defined far-local }
end;

destructor   oSortTree.Done;

   procedure disposetree(var t :ptree);
   begin
      if t=NIL then
         EXIT;
      disposetree(t^.left);
      disposetree(t^.right);
      DeleteNode(t^.data);
      dispose(t);
   end;

begin
   disposetree(root);
end;

procedure    oSortTree.InsertNode(n :pointer);
   { Insert the data pointer in sorted order, as defined by the
     passed "compare" function
   }
   procedure recursetree(var t :ptree);

      procedure PutNode(node :ptree);
      begin
         node^.right := NIL;
         node^.left  := NIL;
         node^.data  := n;
      end;

   begin
      if comp(n, t^.data)>0 then
      begin
         if t^.right<>NIL then
            recursetree(t^.right)
         else
         begin
            New(t^.right);
            PutNode(t^.right);
         end;
      end
      else
      begin
         if t^.left<>NIL then
            recursetree(t^.left)
         else
         begin
            New(t^.left);
            PutNode(t^.left);
         end;
      end;
   end;

begin
   if n<>NIL then
      if root=NIL then
      begin
         New(root);
         root^.left  := NIL;
         root^.right := NIL;
         root^.data  := n;
      end
      else
         recursetree(root);
end;

procedure    oSortTree.DeleteNode(var Node);
   { The calling code must define how to dispose of the data field
     by inheritance }
begin
   Halt(255); {abstract method}
end;

function     oSortTree.ReadLeftNode:pointer;
   { This function is intended to be called one-at-a-time to recover
     data in sorted order. The data is returned as an untyped
     pointer. It is assumed that the calling code will type the
     pointer as required. The data pointer is set to NIL after being
     passed to the caller. }
var
   ln :pointer;

   procedure recurseTree(var t :pTree;var result :pointer);
   begin
      if t^.left<>NIL then
      begin
         recurseTree(t^.left, result);
         if result=NIL then
         begin
            result  := t^.data;
            t^.data := NIL;
         end;
      end
      else
      begin
         if t^.data<>NIL then
         begin
            result  := t^.data;
            t^.data := NIL;
         end
         else
            if t^.right<>NIL then
            begin
               recurseTree(t^.right, result);
               if result=NIL then
               begin
                  dispose(t);
                  t := NIL;
               end
            end
            else
            begin
               dispose(t);
               t := NIL;
               result := NIL;
            end;
      end;
   end;

begin
   if root<>NIL then
   begin
      recurseTree(root, ln);
      ReadLeftNode := ln;
   end
   else
      ReadLeftNode := NIL;
end;

END.

[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]