[Tutor] Re: One other thing·... (and more)
Stephen L Arnold
sarnold@earthling.net
Sat, 12 May 2001 17:30:37 -0700
On 12 May 01, at 12:09, Bruce Sass wrote:
> On Fri, 11 May 2001, VanL wrote:
>
[snip]
> > That last operation would test that the two types were compatible, and,
> > where applicable, perform the tree merge. All this stuff would be hard
> > to do, if not impossible, if I can't figure out what I've got when I am
> > passed in an object.
>
> Hmmm, could it be that you, "can't see the forest for the trees"
> (sorry).
[snip]
I'm just starting with Python, so I'd also like to know how this
works too. Sorry it's kinda long, but I inserted some example code
from a binary search tree. I'd like to know (in general) how this
kind of thing works in Python. The syntax of the code below is
very readable (though a bit more verbose than Python). Comments
are preceded by two dashes.
Whether you want to think in terms of objects and methods or
generic packages and generic formal parameters (it least that's the
way I understand it) there must be some way to define the set of
valid operations, arguments, etc. In Ada, this is defined in the
package specification. You don't need (or want) to know how the
code in the package body is implemented, unless of course, you're
the one doing the implementing (it just needs to conform to the
spec).
Using the binary search tree example, in the package spec I would
define the data types, overloaded operators, and the first
procedure like this:
-- This is the package spec --
generic
type Element_Type is private;
type Key_Type is private;
with function Key(Item : in Element_Type) return Key_Type;
with function "="(Left, Right : in Key_Type) return Boolean is <>;
with function "<"(Left, Right : in Key_Type) return Boolean is <>;
package Binary_Search_Tree is
type BST is limited private;
type Traversal is (In_Order, Pre_Order, Post_Order);
Overflow : exception; -- Raised when tree space runs out.
Key_Error : exception; -- Raised for bogus key operations.
State_Error : exception; -- Raised for more than one concurrent
-- traversal, or state change during
-- a traversal.
-------------------------------------------------------------------------
procedure Insert(Item : in Element_Type; Tree : in out BST);
-- Adds Item to Tree.
-- Exceptions:
-- Overflow Item could not be added to Tree.
-- Key_Error Key(Item) already exists.
-- State_Error Tree is in a traversal.
-------------------------------------------------------------------------
The above tells you all you need to know about data types, valid
operators, and procedures/functions and their arguments (of course,
there are more than just Insert). It even tells you which kinds of
exceptions to expect from each function or procedure. If I were
writing this package (or just curious) I might find something like
this implementation in the package body:
-- This is the package body --
with Ada.Exceptions ;
with Ada.Unchecked_Deallocation ;
package body Binary_Search_Tree is
procedure Free is new Ada.Unchecked_Deallocation(Tree_Node, Tree_Node_Ptr);
-------------------------------------------------------------------------
procedure Insert(Item : in Element_Type; Tree : in out BST) is
-- Adds Item to Tree.
-- Exceptions:
-- Overflow Item could not be added to Tree.
-- Key_Error Key(Item) already exists.
-- State_Error Tree is in a traversal.
New_item : Tree_Node_Ptr := null;
Parent : Tree_Node_Ptr := null;
Target : Tree_Node_Ptr := Tree.Root;
begin -- Insert
if Tree.Traversing then
Ada.Exceptions.Raise_Exception (State_Error'identity,
"Error using Insert. Tree is already in a traversal.");
end if;
-- Find the insert spot.
while Target /= null loop
Parent := Target;
if Key(Item) = Key(Target.Data) then
Ada.Exceptions.Raise_Exception (Key_Error'identity,
"Error using Insert. Key already exists.");
elsif Key(Item) < Key(Target.Data) then
Target := Target.Child(Left);
else
Target := Target.Child(Right);
end if;
end loop;
begin
New_Item := new Tree_Node'(Item, (others => null));
exception
when Storage_Error =>
Ada.Exceptions.Raise_Exception (Overflow'identity,
"Error using Insert. Not enough free memory.");
end;
-- Insert new item
if Parent = null then
Tree.Root := New_Item;
elsif Key(Item) < Key(Parent.Data) then
Parent.Child(Left) := New_Item;
else
Parent.Child(Right) := New_Item;
end if;
Tree.Count := Natural'Succ(Tree.Count);
end Insert;
-------------------------------------------------------------------------
But I still can't do anything with it unless I 'with' this package
in some other code (such as a test driver). Part of such a driver
might look like this:
-- First I have to 'with' my bst package (and a few others)
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Exceptions; use Ada.Exceptions;
with Ada.Numerics.Discrete_Random;
with Ada.Unchecked_Deallocation;
with Binary_Search_Tree;
-- Then I can instantiate a tree like this:
procedure BST_Test is
package BT is new Binary_Search_Tree(Integer, Integer, Identity, "=","<"); use BT;
package Boolean_IO is new Ada.Text_IO.Enumeration_IO (enum => Boolean);
-- and create some trees and integers to fill them:
A, B, C, D : aliased BST;
m : Integer := 0;
ns : array(1..8) of Integer := (11, 8, 10, 17, 3, 1, 4, 13);
na : array(1..8) of Integer := (12, 9, 11, 16, 5, 18, 7, 14);
I hope that's enough to give a fairly clear picture of what's going
on (and isn't too confusing). The rest of the code is available on
my webserver (it's just the homework problems from the data
structures class I took last year):
http://arnolds.dhs.org/cgi-bin/viewcvs.cgi/Ada/CS-152/
How does this kind of thing work in Python? I guess you would
define a binary_search_tree class, with methods like insert,
delete, etc, exceptions, what parameters can be passed to the
methods, any overloaded operators, etc. You would also have to
specify (perhaps when you instantiate a tree object) what types are
contained in the tree. As a user of the tree class library, how do
I find out what methods/parameters are valid, what the exception
names are, etc?
Any one care to give it a go? (sorry about the Ada code, but I
can't do it in Python yet...)
Steve
*************************************************************
Steve Arnold http://arnolds.dhs.org
Things go better with Linux and King Crimson.