array

array

[Pieter Thysebaert]

Hi,

I've somehow been able to construct a binary tree (using nodes and access
types etc.)

Now I was looking for a function that would allow me to convert the contents
of a tree into an array (and vice versa)
I've found something like arrays with variable range (I mean not fixed at
compile-time)
Well I think that's what I found - does that thing exist ?

And if it does, how would one manipulate it (add/remove elements)

Or are there data structures like C++ STL stuff (vector etc)  available ?

Pieter

Re: array

[Ted Dennison]

In article <5s2B6.32267$ii5.3236241@afrodite.telenet-ops.be>, Pieter Thysebaert
says...
>Now I was looking for a function that would allow me to convert the contents
>of a tree into an array (and vice versa)
>I've found something like arrays with variable range (I mean not fixed at
>compile-time)
>Well I think that's what I found - does that thing exist ?
>
>And if it does, how would one manipulate it (add/remove elements)

Back in the olden days, binary trees were ususally implmented as arrays. I
believe the algorithms for doing so are avilable in "The Art of Computer
Programming, Volume 3" ( http://www-cs-faculty.stanford.edu/~knuth/taocp.html ).
Go find, or preferably purchase yourself, a copy.


>
>Or are there data structures like C++ STL stuff (vector etc)  available ?
The Ada implementation of the Booch Components should have something for
size-limited trees, which I would imagine would be implemented using arrays (but
I haven't examined the code).

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: array

[Des Walker]

Ted Dennison <dennison@telepath.com> wrote in message
news:DpjB6.4297$FY5.303408@www.newsranger.com...
> In article <5s2B6.32267$ii5.3236241@afrodite.telenet-ops.be>, Pieter
Thysebaert
> says...
> >Now I was looking for a function that would allow me to convert the
contents
> >of a tree into an array (and vice versa)
> >I've found something like arrays with variable range (I mean not
fixed at
> >compile-time)
> >Well I think that's what I found - does that thing exist ?
> >
> >And if it does, how would one manipulate it (add/remove elements)
>
> Back in the olden days, binary trees were ususally implmented as
arrays. I
> believe the algorithms for doing so are avilable in "The Art of
Computer
> Programming, Volume 3"
 http://www-cs-faculty.stanford.edu/~knuth/taocp.html ).
> Go find, or preferably purchase yourself, a copy.
>
>
> >
> >Or are there data structures like C++ STL stuff (vector etc)
available ?
> The Ada implementation of the Booch Components should have something
for
> size-limited trees, which I would imagine would be implemented using
arrays (but
> I haven't examined the code).
>
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
>           home email - mailto:dennison@telepath.com

Hi,
  I think the underlying implementation for some of the 'bounded' items
in the Booch Components use arrays, but the array would not be directly
accessible to the user. The BC does provide some useful binary tree
implementations for dynamically changing binary trees, I've used the AVL
tree to good effect.

One method of representing a binary tree in an array is put each node at
the index which corresponds to the order you would obtain it in a
breadth order traversal.
i.e. If you number your binary tree nodes starting at the root node

-------1
---2-------3
4----5--6----7

The numbers correspond to the array index for the element

for an element at index I,
the left child will be at index (I*2)
the right child will be at index (I*2+1)
the parent will be at index (I/2)

If your binary tree has holes in it, you'll need some way of describing
an empty array element, to maintain the correct position of a node in an
array.
In this way you'll know a node doesn't have a child if the index for the
child is greater than the maximum size of the array, or the value at
that index is the empty element.

Sorry I can't be more helpful, I've never used an array implementation
for a binary tree. Binary Trees I have used have been ones which are
dynamically changing and need continuous rebalancing, for which the AVL
tree has been satisfactory.

    Des Walker

Re: array

[Stephen Leake]

"Pieter Thysebaert" <pieter.thysebaert@pandora.be> writes:

><snip>
> Or are there data structures like C++ STL stuff (vector etc)  available ?

http://users.erols.com/leakstan/Stephe/Ada/sal.html


-- 
-- Stephe

Re: array

[Jeffrey Carter]

Pieter Thysebaert wrote:
> 
> Now I was looking for a function that would allow me to convert the contents
> of a tree into an array (and vice versa)
> I've found something like arrays with variable range (I mean not fixed at
> compile-time)
> Well I think that's what I found - does that thing exist ?

Certainly, if you have a function

function Size (Tree : Tree_Type_Name) return Natural;

that returns the number of elements in Tree, you can declare something
like

type Tree_As_Array is array (Positive range <>) of
Tree_Element_Type_Name;

and then declare an array of the right size for a specific tree

Flat : Tree_As_Array (1 .. Size (Tree) );

and then somehow extract the elements of Tree into the components of
Flat.

I'm not sure if this answers your question or not.

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail

Re: array

[Simon Wright]

"Pieter Thysebaert" <pieter.thysebaert@pandora.be> writes:

> I've somehow been able to construct a binary tree (using nodes and
> access types etc.)
> 
> Now I was looking for a function that would allow me to convert the
> contents of a tree into an array (and vice versa) I've found
> something like arrays with variable range (I mean not fixed at
> compile-time) Well I think that's what I found - does that thing
> exist ?
> 
> And if it does, how would one manipulate it (add/remove elements)

It's certainly possible to work with unconstrained array types, you
just need to be aware that the size of an instance of such a type is
*not* variable; it can be fixed at initialization, though:

  type A is array (Integer range <>) of Integer;

  function Fun return A is
    Result : A (12 .. 34) := (others => 42);
  begin
    -- stuff
    return Result;
  end Fun;

  V : A := Fun;

> Or are there data structures like C++ STL stuff (vector etc)
> available ?

The 20010325 release of the Booch Components contains a generic Copy
feature:

  with Bc.Containers;
  generic
    type Item is private;
    with package Source is new BC.Containers (Item);
    type From is new Source.Container with private;
    with package Target is new BC.Containers (Item);
    type To is new Target.Container with private;
    with procedure Clear (The_Container : in out To) is <>;
    with procedure Add (To_The_Container : in out To; I : Item) is <>;
  procedure BC.Copy (Input : From; Output : in out To);

Basically, you have a Source.From container type and a Target.To
container type (clearly both containing the same sort of Item!).  You
need a procedure to Clear the Target.To container, and a procedure
to Add Items to the Target.To container.

  procedure BC.Copy (Input : From; Output : in out To) is
    procedure Ins (I : Item; OK : out Boolean);
    pragma Inline (Ins);
    procedure Cp is new Source.Visit (Ins);
    procedure Ins (I : Item; OK : out Boolean) is
    begin
      Add (Output, I);
      OK := True;
    end Ins;
    It : Source.Iterator'Class := New_Iterator (Input);
  begin
    Clear (Output);
    Cp (It);
  end BC.Copy;

The implementation Clears the the Target.To container and then
iterates over the Source.From container, Adding each Item as it goes.

-Simon

Array...

[BanaN]

Hi
looking to write 83 style, want to know if possible to have dialog boxes,
like window.
This is for the Vax/VMS, so would I have to check their character set?
An array in an array..
whats the possibility of this, sounds very very...
Back soon.
--
BanaN

Re: Array...

[BanaN]

>Hello.
> i am looking into writing in the 83 style, and want to know if it is at
all possible to have dialog >boxes like windows has, for instance on a
386upwards, but this is for the Vax/VMS, so would I >have to check their
character set?
>An array in an array is something else I have to figure out, though I think
I've got the hang of that >from the CD_array and CD_track_array, although
I'm not comfortable with it.
>Please could someone tell me about the Vax stuff if theyre reading, thanks
in advance.

I'm sorry but I don't have a Vax machine, but I would imagine it would be
the same for dos.
Could someone substantiate this claim?
An array within an array?Sorry Im new to this NG myself!