File : bc-containers-trees-avl-validate.adb
-- Copyright (C) 1999 Simon Wright.
-- All Rights Reserved.
--
-- This program is free software; you can redistribute it
-- and/or modify it under the terms of the Ada Community
-- License which comes with this Library.
--
-- This program is distributed in the hope that it will be
-- useful, but WITHOUT ANY WARRANTY; without even the implied
-- warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
-- PURPOSE. See the Ada Community License for more details.
-- You should have received a copy of the Ada Community
-- License with this library, in the file named "Ada Community
-- License" or "ACL". If not, contact the author of this library
-- for a copy.
--
-- $Id: bc-containers-trees-avl-validate.adb,v 1.1.2.2 1999/12/30 14:59:14 simon Exp $
with Ada.Text_Io;
procedure BC.Containers.Trees.AVL.Validate (T : AVL_Tree) is
use Ada.Text_Io;
use type Nodes.Avl_Node_Ref;
use type Nodes.Node_Balance;
function Depth (N : Nodes.Avl_Node_Ref) return Natural is
begin
if N = null then
return 0;
else
return 1 + Natural'Max (Depth (N.Left), Depth (N.Right));
end if;
end Depth;
procedure Validate (N : Nodes.AVL_Node_Ref) is
Left_Depth : constant Natural := Depth (N.Left);
Right_Depth : constant Natural := Depth (N.Right);
begin
if N.Left /= null then
Validate (N.Left);
end if;
if N.Right /= null then
Validate (N.Right);
end if;
if Left_Depth = Right_Depth then
if N.Balance /= Nodes.Middle then
Put_Line ("depths equal but balance "
& Nodes.Node_Balance'Image (N.Balance));
end if;
elsif Left_Depth > Right_Depth then
if Left_Depth - Right_Depth /= 1 then
Put_Line ("left depth is"
& Natural'Image (Left_Depth - Right_Depth)
& " greater than right depth");
end if;
if N.Balance /= Nodes.Left then
Put_Line ("left deeper than right but balance "
& Nodes.Node_Balance'Image (N.Balance));
end if;
else
if Right_Depth - Left_Depth /= 1 then
Put_Line ("right depth is"
& Natural'Image (Right_Depth - Left_Depth)
& " greater than left depth");
end if;
if N.Balance /= Nodes.Right then
Put_Line ("right deeper than left but balance "
& Nodes.Node_Balance'Image (N.Balance));
end if;
end if;
end Validate;
begin
if T.Rep /= null then
Validate (T.Rep);
end if;
end BC.Containers.Trees.AVL.Validate;