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

interface

uses
    Graphics, Dialogs, SysUtils,
    TrSortNC;

type
    TSortTree = class(TObject)
        private
            Root : TSortNode;
        public
            destructor Destroy; override;
            function NotEmpty : Boolean;
            procedure SetPositions(xmin : Integer; ymin : Integer);
            procedure DrawTree(cvs : TCanvas);
            function NodeAtPoint(X, Y : Integer) : TSortNode;
            procedure Add(new_id : Integer);
            procedure AddNode(var node : TSortNode; new_id : Integer);
            procedure Remove(target_value : Integer);
            procedure RemoveNode(var node : TSortNode; target_value : Integer);
            procedure ReplaceRightmost(var target, repl : TSortNode);
    end;

implementation

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

// Free the nodes.
destructor TSortTree.Destroy;
begin
    Root.Free;
    inherited Destroy;
end;

// Return True if the tree is not empty.
function TSortTree.NotEmpty : Boolean;
begin
    Result := (Root <> nil);
end;

// Set the positions for the nodes.
procedure TSortTree.SetPositions(xmin : Integer; ymin : Integer);
begin
    if (Root <> nil) then Root.SetPosition(xmin, ymin);
end;

// Draw the tree.
procedure TSortTree.DrawTree(cvs : TCanvas);
begin
    if (Root <> nil) then Root.DrawSubtree(cvs);
end;

// Find the descendant node containing this point.
function TSortTree.NodeAtPoint(X, Y : Integer) : TSortNode;
begin
    if (Root = nil) then
        Result := nil
    else
        Result := Root.NodeAtPoint(X, Y);
end;

// Add a new value to the tree.
procedure TSortTree.Add(new_id : Integer);
begin
    AddNode(Root, new_id);
end;

// Add a new value below the indicated node.
procedure TSortTree.AddNode(var node : TSortNode; new_id : Integer);
begin
    if (node = nil) then
    begin
        // Create the new node.
        node := TSortNode.Create;
        node.Id := new_id;
    end else if (new_id <= node.Id) then
        AddNode(node.LeftChild, new_id)
    else
        AddNode(node.RightChild, new_id)
end;

// Remove a value from the tree.
procedure TSortTree.Remove(target_value : Integer);
begin
    RemoveNode(Root, target_value);
end;

// Remove a value from below the indicated node.
procedure TSortTree.RemoveNode(var node : TSortNode; target_value : Integer);
var
    target : TSortNode;
begin
    // If we cannot find the item, say so.
    if (node = nil) then
    begin
        ShowMessage(Format('Item %d is not in the tree.',
            [target_value]));
        exit;
    end;

    if (target_value < node.Id) then
        // Continue down left subtree.
        RemoveNode(node.LeftChild, target_value)
    else if (target_value > node.Id) then
        // Continue down right subtree.
        RemoveNode(node.RightChild, target_value)
    else begin
        // This is the target.
        if (node.LeftChild = nil) then
        begin
            // Replace target with its right child.
            target := node;
            node := node.RightChild;
            target.RightChild := nil;
            target.Free;
        end else if (node.RightChild = nil) then
        begin
            // Replace target with its left child.
            target := node;
            node := node.LeftChild;
            target.LeftChild := nil;
            target.Free;
        end else begin
            // Use ReplaceRightmost to replace the target
            // with the rightmost descendant to its left.
            ReplaceRightmost(node, node.LeftChild);
        end; // End replacing the target.
    end; // End if left ... else if right ... else ...
end;

// Replace the target node with the rightmost descendant
// to its left.
procedure TSortTree.ReplaceRightmost(var target, repl : TSortNode);
var
    old_repl, tmp : TSortNode;
begin
    if (repl.RightChild <> nil) Then
    begin
        // Move farther down to the right.
        ReplaceRightmost(target, repl.RightChild);
    end else begin
        // We've reached the bottom. Remember node repl.
        old_repl := repl;

        // Replace repl with its left child.
        repl := repl.LeftChild;

        // Replace the target with repl.
        old_repl.LeftChild := target.LeftChild;
        old_repl.RightChild := target.RightChild;
        tmp := target;
        target := old_repl;
        tmp.LeftChild := nil;
        tmp.RightChild := nil;
        tmp.Free;
    end;
end;

end.
