unit TrSortNC;
//*******************************************************
// Sorted tree node class.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
    Windows, Graphics, Math, SysUtils;

type
    TSortNode = class(TObject)
        private
        public
            Id                    : Integer;
            LeftChild, RightChild : TSortNode;
            Position              : TPoint;

            constructor Create;
            destructor Destroy; override;
            class function NumAllocated : Integer;
            procedure SetPosition(var xmin : Integer; ymin : Integer);
            procedure DrawNode(cvs : TCanvas);
            procedure DrawSubtree(cvs : TCanvas);
            function NodeAtPoint(X, Y : Integer) : TSortNode;
    end;

implementation

const
    WID = 40;
    HGT = 16;
    HGAP = 2;
    VGAP = 6;

var
    NodesAllocated : Integer;

// Keep count of nodes allocated.
constructor TSortNode.Create;
begin
    NodesAllocated := NodesAllocated + 1;
    inherited Create;
end;

// Free any children.
destructor TSortNode.Destroy;
begin
    NodesAllocated := NodesAllocated - 1;

    LeftChild.Free;
    RightChild.Free;
    inherited Destroy;
end;

// Return the number of nodes currently allocated.
class function TSortNode.NumAllocated : Integer;
begin
    Result := NodesAllocated;
end;

// Set the position for the node and its descendants.
// Update xmin so it indicates the rightmost position
// used by the node and its descendants.
procedure TSortNode.SetPosition(var xmin : Integer; ymin : Integer);
var
    x1, x2 : Integer;
begin
    Position.Y := ymin;

    // If there are no children, take the easy way out.
    if ((LeftChild = nil) and (RightChild = nil)) then
    begin
        Position.X := xmin;
        xmin := xmin + WID;
    end else begin
        // Position the left child.
        if (LeftChild = nil) then
        begin
            x1 := xmin;
            xmin := xmin + WID;
        end else begin
            LeftChild.SetPosition(xmin, ymin + HGT + VGAP);
            x1 := LeftChild.Position.X;
        end;

        // Put a little space inbetween.
        xmin := xmin + HGAP;

        // Position the right child.
        if (RightChild = nil) then begin
            x2 := xmin;
            xmin := xmin + WID;
        end else begin
            RightChild.SetPosition(xmin, ymin + HGT + VGAP);
            x2 := RightChild.Position.X;
        end;

        // Center this node over its children.
        Position.X := (x1 + x2) div 2;
    end;
end;

// Draw this node.
procedure TSortNode.DrawNode(cvs : TCanvas);
var
    rect      : TRect;
    text_size : TSize;
begin
    // Erase the spot and draw a box around it.
    rect.Left   := Position.X;
    rect.Right  := Position.X + WID;
    rect.Top    := Position.Y;
    rect.Bottom := Position.Y + HGT;
    cvs.FillRect(rect);
    cvs.Rectangle(rect.Left, rect.Top, rect.Right, rect.Bottom);

    // Draw the label.
    text_size := cvs.TextExtent(IntToStr(Id));
    cvs.TextOut(
        (rect.Left + rect.Right - text_size.cx) div 2,
        (rect.Top + rect.Bottom - text_size.cy) div 2,
        IntToStr(Id));
end;

// Draw the subtree rooted at this node.
procedure TSortNode.DrawSubtree(cvs : TCanvas);
begin
    // Draw this node.
    DrawNode(cvs);

    // Draw the children.
    if (LeftChild <> nil) then
    begin
        LeftChild.DrawSubtree(cvs);
        cvs.MoveTo(
            Position.X + WID div 2,
            Position.Y + HGT);
        cvs.LineTo(
            LeftChild.Position.X + WID div 2,
            LeftChild.Position.Y);
    end;
    if (RightChild <> nil) then
    begin
        RightChild.DrawSubtree(cvs);
        cvs.MoveTo(
            Position.X + WID div 2,
            Position.Y + HGT);
        cvs.LineTo(
            RightChild.Position.X + WID div 2,
            RightChild.Position.Y);
    end;
end;

// Find the descendant node containing this point.
// Note that this is not a very sophisticated method.
// A quadtree would be much faster.
function TSortNode.NodeAtPoint(X, Y : Integer) : TSortNode;
begin
    Result := nil;

    // Check this node.
    if ((Position.X <= X) and (X <= Position.X + WID) and
        (Position.Y <= Y) and (Y <= Position.Y + HGT))
    then
        Result := Self;

    // Check the left child.
    if ((Result = nil) and (LeftChild <> nil)) then
        Result := LeftChild.NodeAtPoint(X, Y);

    // Check the right child.
    if ((Result = nil) and (RightChild <> nil)) then
        Result := RightChild.NodeAtPoint(X, Y);
end;

end.
