binary tree and files

binary tree and files

[Franck]

hi !

i've got a pb : i don't know how to save a binary tree in a file, and then
load it from the file

here are the type i use

   type T_node;
   type Pt_tree is access T_Node;

   type T_Node is record
      name : T_name;
      G, D : Pt_Arbre;
   end record;

name contain name, surname, birthday etc...

thanks for the help ;o)

P.S :you can send the answer to kribal@caramail.com

Re: binary tree and files

[Franck]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 646 bytes --]

just to correct something in my type
type T_node;
   type Pt_tree is access T_Node;

   type T_Node is record
      name : T_name;
      G, D : Pt_tree;
   end record;

Franck a �crit dans le message <8tuk7l$aq5$1@wanadoo.fr>...
>hi !
>
>i've got a pb : i don't know how to save a binary tree in a file, and then
>load it from the file
>
>here are the type i use
>
>   type T_node;
>   type Pt_tree is access T_Node;
>
>   type T_Node is record
>      name : T_name;
>      G, D : Pt_Arbre;
>   end record;
>
>name contain name, surname, birthday etc...
>
>thanks for the help ;o)
>
>P.S :you can send the answer to kribal@caramail.com
>
>

Re: binary tree and files

[Arthur G. Duncan]

Franck wrote:

  ... question on how to save and restore a binary tree of the 
      form: 

> type T_node;
> type Pt_tree is access T_Node;
> 
> type T_Node is record
>    name : T_name;
>    G, D : Pt_tree;
> end record;
> 

If it is, indeed, a tree (no cycles), you can simply write it out
as a set of nested tuples (LISP list notation is as good a form
as any).

If there are cycles (or the tree is reentrant and you want to save
disk space) you can label the nodes and write out label references
wherever you have a pointer in the original data structure. 

Hope this helps,

- Art Duncan
  aduncan@global2000.net

Re: binary tree and files

[Franck]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1774 bytes --]


Arthur G. Duncan a �crit dans le message <3A02DF9B.2269@global2000.net>...
>Franck wrote:
>
>  ... question on how to save and restore a binary tree of the
>      form:
>
>> type T_node;
>> type Pt_tree is access T_Node;
>>
>> type T_Node is record
>>    name : T_name;
>>    G, D : Pt_tree;
>> end record;
>>
>
>If it is, indeed, a tree (no cycles), you can simply write it out
>as a set of nested tuples (LISP list notation is as good a form
>as any).
>
>If there are cycles (or the tree is reentrant and you want to save
>disk space) you can label the nodes and write out label references
>wherever you have a pointer in the original data structure.
>
>Hope this helps,
>
>- Art Duncan
>  aduncan@global2000.net

thanks for the help Duncan,
but i'm new to Ada and recursivity, and i don't understand all you speek
about ;o)
what is a set of nested tuples??
there is no cycle i think in my program
it s to make a genealogic tree,like this :

father                      father has 2 children : child1 and child2
     /   \
    /      \
null       child1                child1 has no child
              /        \
             /           \
        child2      null           child2 has 2 children : little child1 and
little child2
          /    \
        /        \
    null        little child1             little child1 has no child (right)
and one brother(left)
                    /             \
                  /                 \
            little child2     null          little child2 has no other
brother and no child
               /           \
             /               \
          null            null

i can easily save that in a files with recursive procedure, but i don't see
how to load it from files

still in need of help ;o)

Franck

Re: binary tree and files

[John Cupak]

Check out Streams in Cohen's "Ada as a Second Language, 2nd ed." text.

John

Franck wrote:

> Arthur G. Duncan a �crit dans le message <3A02DF9B.2269@global2000.net>...
> >Franck wrote:
> >
> >  ... question on how to save and restore a binary tree of the
> >      form:
> >
> >> type T_node;
> >> type Pt_tree is access T_Node;
> >>
> >> type T_Node is record
> >>    name : T_name;
> >>    G, D : Pt_tree;
> >> end record;
> >>
> >
> >If it is, indeed, a tree (no cycles), you can simply write it out
> >as a set of nested tuples (LISP list notation is as good a form
> >as any).
> >
> >If there are cycles (or the tree is reentrant and you want to save
> >disk space) you can label the nodes and write out label references
> >wherever you have a pointer in the original data structure.
> >
> >Hope this helps,
> >
> >- Art Duncan
> >  aduncan@global2000.net
>
> thanks for the help Duncan,
> but i'm new to Ada and recursivity, and i don't understand all you speek
> about ;o)
> what is a set of nested tuples??
> there is no cycle i think in my program
> it s to make a genealogic tree,like this :
>
> father                      father has 2 children : child1 and child2
>      /   \
>     /      \
> null       child1                child1 has no child
>               /        \
>              /           \
>         child2      null           child2 has 2 children : little child1 and
> little child2
>           /    \
>         /        \
>     null        little child1             little child1 has no child (right)
> and one brother(left)
>                     /             \
>                   /                 \
>             little child2     null          little child2 has no other
> brother and no child
>                /           \
>              /               \
>           null            null
>
> i can easily save that in a files with recursive procedure, but i don't see
> how to load it from files
>
> still in need of help ;o)
>
> Franck

Re: binary tree and files

[Franck]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 337 bytes --]


John Cupak a �crit dans le message <3A02F502.9956CB25@res.raytheon.com>...
>Check out Streams in Cohen's "Ada as a Second Language, 2nd ed." text.
>
>John
>


thanks john but i'm french and i think it won't be easy for me to find this
book ;o)

i'd like some code exampleif possible

thanks to all who try to help me ;o)

Franck

Re: binary tree and files

[Pascal Obry]

"Franck" <kribal@caramail.com> writes:

> John Cupak a �crit dans le message <3A02F502.9956CB25@res.raytheon.com>...
> >Check out Streams in Cohen's "Ada as a Second Language, 2nd ed." text.
> >
> >John
> >
> 
> 
> thanks john but i'm french and i think it won't be easy for me to find this
> book ;o)

Certainly not !! I'm french too and I can tell you that this book is on any
good book store... Definitly a book to have in anycase. I hope you have some
Ada book around or are you trying to learn Ada yourself with... the help of 
the Ada community :)

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|         http://perso.wanadoo.fr/pascal.obry
--|
--| "The best way to travel is by means of imagination"

Re: binary tree and files

[Franck]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1302 bytes --]


Pascal Obry a �crit dans le message ...
>
>"Franck" <kribal@caramail.com> writes:
>
>> John Cupak a �crit dans le message
<3A02F502.9956CB25@res.raytheon.com>...
>> >Check out Streams in Cohen's "Ada as a Second Language, 2nd ed." text.
>> >
>> >John
>> >
>>
>>
>> thanks john but i'm french and i think it won't be easy for me to find
this
>> book ;o)
>
>Certainly not !! I'm french too and I can tell you that this book is on any
>good book store... Definitly a book to have in anycase. I hope you have
some
>Ada book around or are you trying to learn Ada yourself with... the help of
>the Ada community :)
>
>Pascal.
>
>--
>
>--|------------------------------------------------------
>--| Pascal Obry                           Team-Ada Member
>--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
>--|------------------------------------------------------
>--|         http://perso.wanadoo.fr/pascal.obry
>--|
>--| "The best way to travel is by means of imagination"


i'd like to have this book but... it s too late to buy it i have to finish
my program before tomorow morning... all my genealogic tree program works
BUT save/load file

if someone could give me more precision about how to code it i'd really
appreciate it ;o)
an idea of algorythme or something like that ;o)
thanks

Re: binary tree and files

[Larry Hazel]

I would mimic the tree in a direct access file using record numbers instead of
access numbers.  Then reallocate when you read it back in.

Larry

Franck wrote:
> 
> Pascal Obry a �crit dans le message ...
> >
> >"Franck" <kribal@caramail.com> writes:
> >
> >> John Cupak a �crit dans le message
> <3A02F502.9956CB25@res.raytheon.com>...
> >> >Check out Streams in Cohen's "Ada as a Second Language, 2nd ed." text.
> >> >
> >> >John
> >> >
> >>
> >>
> >> thanks john but i'm french and i think it won't be easy for me to find
> this
> >> book ;o)
> >
> >Certainly not !! I'm french too and I can tell you that this book is on any
> >good book store... Definitly a book to have in anycase. I hope you have
> some
> >Ada book around or are you trying to learn Ada yourself with... the help of
> >the Ada community :)
> >
> >Pascal.
> >
> >--
> >
> >--|------------------------------------------------------
> >--| Pascal Obry                           Team-Ada Member
> >--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
> >--|------------------------------------------------------
> >--|         http://perso.wanadoo.fr/pascal.obry
> >--|
> >--| "The best way to travel is by means of imagination"
> 
> i'd like to have this book but... it s too late to buy it i have to finish
> my program before tomorow morning... all my genealogic tree program works
> BUT save/load file
> 
> if someone could give me more precision about how to code it i'd really
> appreciate it ;o)
> an idea of algorythme or something like that ;o)
> thanks

Re: binary tree and files

[tmoran]

>what is a set of nested tuples??
Your tree diagram can be written as
father(null, child1(child2(null,little child1(little child2(null,null), null)))
where a "(" means "has the children:" and a ")" means "end of this set of
siblings"
You can read that back in and re-create the tree structure.

BTW, your textual description seems to me to indicate
father(child1,child2(little child1, little child2))
which is different than the diagram.

>there is no cycle i think in my program
  You can see that the nested list form could not handle cycles since
at some point a child would have to include one of his ancestors, who
occur to his left, as one of his descendants, who occur to his right.
Absent time travel, this cannot happen in a father, child genealogical tree.
As Oedipus demonstrated, it could happen if you included marriages.

Re: binary tree and files

[David C. Hoos, Sr.]

Here's my approach to this kind of problem:

with Ada.Streams.Stream_IO;
with Ada.Text_IO;
with Ada.Unchecked_Deallocation;
procedure Binary_Tree_Stream
is
   type Node;
   type Node_Access is access Node;

   -- Since writing access values to a stream has no value, we want to
   -- write, instead, the designated object to the stream, or if the
   -- access value is null, an indication that the object is null.
   -- To that end, we override the default stream attributes for the
   -- Node_Access type;
   procedure Read
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :    out Node_Access);
   procedure Write
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   : in     Node_Access);

   for Node_Access'Read use Read;

   for Node_Access'Write use Write;

   type Node is
      record
         Name  : String (1 .. 18);
         Left  : Node_Access;
         Right : Node_Access;
      end record;

   ----------------
   -- Deallocate --
   ----------------

   procedure Deallocate (Item : in out Node_Access)
   is
      procedure Free is new Ada.Unchecked_Deallocation
        (Object => Node,
         Name => Node_Access);
   begin
      Free (Item.Left);
      Free (Item.Right);
      Free (Item);
   end Deallocate;

   ----------
   -- Read --
   ----------

   procedure Read
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :    out Node_Access)
   is
      Is_Non_Null : Boolean;
   begin
      Boolean'Read (Stream, Is_Non_Null);
      if Is_Non_Null then
         Item := new Node'(Node'Input (Stream));
      else
         Item := null;
      end if;
   end Read;

   -----------
   -- Write --
   -----------

   procedure Write
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   : in     Node_Access)
   is
   begin
      Boolean'Write (Stream, Item /= null);
      if Item /= null then
         Node'Output (Stream, Item.all);
      end if;
   end Write;

   -------------
   -- Display --
   -------------

   procedure Display
     (Item  : Node_Access;
      Level : Natural     := 0)
   is
      Indent : String (1 .. 3 * Level) := (others => ' ');
   begin
--      Ada.Text_IO.Put (Indent);
      if Item /= null then
         Ada.Text_IO.Put_Line ("Name  : """ & Item.Name & """");
         if Level /= 0 then
            Ada.Text_IO.Put ("     ");
         end if;
         Ada.Text_IO.Put (Indent & "Left  : ");
         Display (Item.Left, Level + 1);
         if Level /= 0 then
            Ada.Text_IO.Put ("     ");
         end if;
         Ada.Text_IO.Put (Indent & "Right : ");
         Display (Item.Right, Level + 1);
      else
         Ada.Text_IO.Put_Line ("null");
      end if;
   end Display;

   -- Since we haven't defined operations for manipulating the tree, we
   -- declare an initialized tree object, just so we can demonstrate
   -- writing the tree to the stream and reading it back.

   Tree : Node_Access := new Node'
     (Name  => "Parent            ",
      Left  => new Node'
      (Name  => "Child 1           ",
       Left  => null,
       Right => null),
      Right => new Node'
      (Name  => "Child 2           ",
       Left  => new Node'
       (Name  => "Grandchild 1      ",
        Left  => null,
        Right => null),
       Right => new Node'
       (Name  => "Grandchild 2      ",
        Left  => new Node'
        (Name  => "Great-grandchild 1",
         Left  => null,
         Right => null),
        Right => null)
       )
      );

   The_File   : Ada.Streams.Stream_IO.File_Type;
   The_Stream : Ada.Streams.Stream_IO.Stream_Access;

   Reconstructed_Tree : Node_Access;

begin

   -- Display the tree
   Ada.Text_IO.Put_Line ("The tree:");
   Display (Tree);

   -- Create the file
   Ada.Streams.Stream_IO.Create
     (Name => "tree.dat",
      File => The_File,
      Mode => Ada.Streams.Stream_IO.Out_File);
   -- Associate the file with a stream
   The_Stream := Ada.Streams.Stream_IO.Stream (The_File);

   -- Write the tree to the file
   Node_Access'Write (The_Stream, Tree);

   -- Close the file
   Ada.Streams.Stream_IO.Close (The_File);

   -- Deallocate the memory used by the tree
   Deallocate (Tree);

   -- Display the tree after deallocation
   Ada.Text_IO.Put_Line ("The tree after deallocation:");
   Display (Tree);

   -- Open the file
   Ada.Streams.Stream_IO.Open
     (Name => "tree.dat",
      File => The_File,
      Mode => Ada.Streams.Stream_IO.In_File);
   -- Associate the file with a stream
   The_Stream := Ada.Streams.Stream_IO.Stream (The_File);

   -- Read the tree from the file
   Node_Access'Read (The_Stream, Reconstructed_Tree);

   -- Close the file
   Ada.Streams.Stream_IO.Close (The_File);

   -- Display the reconstructed tree
   Ada.Text_IO.Put_Line ("The reconstructed tree:");
   Display (Reconstructed_Tree);

   -- Create a second file to which we will write the reconstructed
   -- tree for comparison of the files
   Ada.Streams.Stream_IO.Create
     (Name => "reconstructed_tree.dat",
      File => The_File,
      Mode => Ada.Streams.Stream_IO.Out_File);
   -- Associate the file with a stream
   The_Stream := Ada.Streams.Stream_IO.Stream (The_File);

   -- Write the tree to the file
   Node_Access'Write (The_Stream, Tree);

   -- Close the file
   Ada.Streams.Stream_IO.Close (The_File);

   -- Deallocate the memory used by the reconstructed tree
   Deallocate (Reconstructed_Tree);

   -- Display the reconstructed tree after deallocation
   Ada.Text_IO.Put_Line ("The reconstructed tree after deallocation:");
   Display (Reconstructed_Tree);
end Binary_Tree_Stream;

Re: binary tree and files

[David C. Hoos, Sr.]

My earlier post had a couple of errors which are
corrected in this version of how I would handle
your problem:

with Ada.Streams.Stream_IO;
with Ada.Text_IO;
with Ada.Unchecked_Deallocation;
procedure Binary_Tree_Stream
is
   type Node;
   type Node_Access is access Node;

   -- Since writing access values to a stream has no value, we want to
   -- write, instead, the designated object to the stream, or if the
   -- access value is null, an indication that the object is null.
   -- To that end, we override the default stream attributes for the
   -- Node_Access type;
   procedure Read
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :    out Node_Access);
   procedure Write
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   : in     Node_Access);

   for Node_Access'Read use Read;

   for Node_Access'Write use Write;

   type Node is
      record
         Name  : String (1 .. 18);
         Left  : Node_Access;
         Right : Node_Access;
      end record;

   ----------------
   -- Deallocate --
   ----------------

   procedure Deallocate (Item : in out Node_Access)
   is
      procedure Free is new Ada.Unchecked_Deallocation
        (Object => Node,
         Name => Node_Access);
   begin
      if Item /= null then
         Deallocate (Item.Left);
         Deallocate (Item.Right);
         Free (Item);
      end if;
   end Deallocate;

   ----------
   -- Read --
   ----------

   procedure Read
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :    out Node_Access)
   is
      Is_Non_Null : Boolean;
   begin
      Boolean'Read (Stream, Is_Non_Null);
      if Is_Non_Null then
         Item := new Node'(Node'Input (Stream));
      else
         Item := null;
      end if;
   end Read;

   -----------
   -- Write --
   -----------

   procedure Write
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   : in     Node_Access)
   is
   begin
      Boolean'Write (Stream, Item /= null);
      if Item /= null then
         Node'Output (Stream, Item.all);
      end if;
   end Write;

   -------------
   -- Display --
   -------------

   procedure Display
     (Item  : Node_Access;
      Level : Natural     := 0)
   is
      Indent : String (1 .. 3 * Level) := (others => ' ');
   begin
--      Ada.Text_IO.Put (Indent);
      if Item /= null then
         Ada.Text_IO.Put_Line ("Name  : """ & Item.Name & """");
         if Level /= 0 then
            Ada.Text_IO.Put ("     ");
         end if;
         Ada.Text_IO.Put (Indent & "Left  : ");
         Display (Item.Left, Level + 1);
         if Level /= 0 then
            Ada.Text_IO.Put ("     ");
         end if;
         Ada.Text_IO.Put (Indent & "Right : ");
         Display (Item.Right, Level + 1);
      else
         Ada.Text_IO.Put_Line ("null");
      end if;
   end Display;

   -- Since we haven't defined operations for manipulating the tree, we
   -- declare an initialized tree object, just so we can demonstrate
   -- writing the tree to the stream and reading it back.

   Tree : Node_Access := new Node'
     (Name  => "Parent            ",
      Left  => new Node'
      (Name  => "Child 1           ",
       Left  => null,
       Right => null),
      Right => new Node'
      (Name  => "Child 2           ",
       Left  => new Node'
       (Name  => "Grandchild 1      ",
        Left  => null,
        Right => null),
       Right => new Node'
       (Name  => "Grandchild 2      ",
        Left  => new Node'
        (Name  => "Great-grandchild 1",
         Left  => null,
         Right => null),
        Right => null)
       )
      );

   The_File   : Ada.Streams.Stream_IO.File_Type;
   The_Stream : Ada.Streams.Stream_IO.Stream_Access;

   Reconstructed_Tree : Node_Access;

begin

   -- Display the tree
   Ada.Text_IO.Put_Line ("The tree:");
   Display (Tree);

   -- Create the file
   Ada.Streams.Stream_IO.Create
     (Name => "tree.dat",
      File => The_File,
      Mode => Ada.Streams.Stream_IO.Out_File);
   -- Associate the file with a stream
   The_Stream := Ada.Streams.Stream_IO.Stream (The_File);

   -- Write the tree to the file
   Node_Access'Write (The_Stream, Tree);

   -- Close the file
   Ada.Streams.Stream_IO.Close (The_File);

   -- Deallocate the memory used by the tree
   Deallocate (Tree);

   -- Display the tree after deallocation
   Ada.Text_IO.Put_Line ("The tree after deallocation:");
   Display (Tree);

   -- Open the file
   Ada.Streams.Stream_IO.Open
     (Name => "tree.dat",
      File => The_File,
      Mode => Ada.Streams.Stream_IO.In_File);
   -- Associate the file with a stream
   The_Stream := Ada.Streams.Stream_IO.Stream (The_File);

   -- Read the tree from the file
   Node_Access'Read (The_Stream, Reconstructed_Tree);

   -- Close the file
   Ada.Streams.Stream_IO.Close (The_File);

   -- Display the reconstructed tree
   Ada.Text_IO.Put_Line ("The reconstructed tree:");
   Display (Reconstructed_Tree);

   -- Create a second file to which we will write the reconstructed
   -- tree for comparison of the files
   Ada.Streams.Stream_IO.Create
     (Name => "reconstructed_tree.dat",
      File => The_File,
      Mode => Ada.Streams.Stream_IO.Out_File);
   -- Associate the file with a stream
   The_Stream := Ada.Streams.Stream_IO.Stream (The_File);

   -- Write the tree to the file
   Node_Access'Write (The_Stream, Reconstructed_Tree);

   -- Close the file
   Ada.Streams.Stream_IO.Close (The_File);

   -- Deallocate the memory used by the reconstructed tree
   Deallocate (Reconstructed_Tree);

   -- Display the reconstructed tree after deallocation
   Ada.Text_IO.Put_Line ("The reconstructed tree after deallocation:");
   Display (Reconstructed_Tree);
end Binary_Tree_Stream;

Re: binary tree and files

[Jeff Carter]

I am aware of French educators who have caramail.com accounts, so I
suspect you have just done this person's homework for him.

-- 
Jeff Carter
"You tiny-brained wipers of other people's bottoms!"
Monty Python & the Holy Grail

Re: binary tree and files

[David C. Hoos, Sr.]

Well, I was not aware of the possible connection of the e-mail address,
and certainly didn't want to deprive a student of the opportunity to figure
it out for himself.

It also, so happens that in my training of some new colleagues in Ada95,
that
we ran across a similar problem (sending record types with access components
between processes distributed on different hosts), just this past week, and
I
prepared the fully-commented version to add to the tutorial examples I use
in
my training activities.

Jeff Carter <jrcarter@acm.org> wrote in message
news:3A04B152.9B437AA3@acm.org...
> I am aware of French educators who have caramail.com accounts, so I
> suspect you have just done this person's homework for him.
>
> --
> Jeff Carter
> "You tiny-brained wipers of other people's bottoms!"
> Monty Python & the Holy Grail