Nodes with unlimited children.

[Jeff Relf]

Hi All,

I plan on using the following C++ code
to create nodes with unlimited children:

// I would like to declare NodeT like this,
// but it won't compile because Lnk_T is not defined yet.

struct NodeT { Lnk_T Lnk ; };

So I have to declare NodeT like this instead:

struct NodeT {
struct { NodeT * * B, * * E, * * Room ; } Lnk ; };
typedef NodeT * Link ;

typedef Link * Link_P ;

// B is the Beginning of an array of pointers.
// E is the End of an array of pointers that are in use.
// Room the end of an array of all pointers, used or not.

struct Lnk_T { Link_P B, E, Room ; };

Lnk_T Lnk ;

enum { Chunk = 4,
Sz_Ptr = sizeof Link, Sz_Node = sizeof NodeT };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link_P ) realloc( Lnk.B, Room * Sz_Ptr );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Ptr ); }
// Below is an example of is how the above might be used,
// I know that it works.

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

GrowList ( Lnk ); // Lnk is a global, so it's initialized.

Link & P = * Lnk.E ++ ;

P = ( Link ) realloc( P, Sz_Node );

memset ( P, 0, Sz_Node );

GrowList ( ( Lnk_T & ) P->Lnk );

{ Link Passed = P, & P = * Passed->Lnk.E ++ ;

P = ( Link ) realloc( P, Sz_Node );

memset ( P, 0, Sz_Node );

GrowList ( ( Lnk_T & ) P->Lnk );

// etc.
}

But is there any way to declare NodeT so that
I don't have to use that ( Lnk_T & ) cast ?

[Jumpin' Jehosephat]

Jeff Relf wrote:

Hi All,

I plan on using the following C++ code
to create nodes with unlimited children:

// I would like to declare NodeT like this,
// but it won't compile because Lnk_T is not defined yet.

struct NodeT { Lnk_T Lnk ; };

So I have to declare NodeT like this instead:

struct NodeT {
struct { NodeT * * B, * * E, * * Room ; } Lnk ; };
typedef NodeT * Link ;

typedef Link * Link_P ;

// B is the Beginning of an array of pointers.
// E is the End of an array of pointers that are in use.
// Room the end of an array of all pointers, used or not.

struct Lnk_T { Link_P B, E, Room ; };

Lnk_T Lnk ;

enum { Chunk = 4,
Sz_Ptr = sizeof Link, Sz_Node = sizeof NodeT };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link_P ) realloc( Lnk.B, Room * Sz_Ptr );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Ptr ); }
// Below is an example of is how the above might be used,
// I know that it works.

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

GrowList ( Lnk ); // Lnk is a global, so it's initialized.

Link & P = * Lnk.E ++ ;

P = ( Link ) realloc( P, Sz_Node );

memset ( P, 0, Sz_Node );

GrowList ( ( Lnk_T & ) P->Lnk );

{ Link Passed = P, & P = * Passed->Lnk.E ++ ;

P = ( Link ) realloc( P, Sz_Node );

memset ( P, 0, Sz_Node );

GrowList ( ( Lnk_T & ) P->Lnk );

// etc.
}

But is there any way to declare NodeT so that
I don't have to use that ( Lnk_T & ) cast ?

That doesn't sound type safe.

And modern computing demands type safety.

--
incognito @ http://kentpsychedelic.blogspot.com

[General Protection Fault]

On 29 Jul 2004 11:06:12 GMT, Jeff Relf wrote:

Hi All,

I plan on using the following C++ code
to create nodes with unlimited children:

// I would like to declare NodeT like this,
// but it won't compile because Lnk_T is not defined yet.

struct NodeT { Lnk_T Lnk ; };

So I have to declare NodeT like this instead:

struct NodeT {
struct { NodeT * * B, * * E, * * Room ; } Lnk ; };
typedef NodeT * Link ;

typedef Link * Link_P ;

// B is the Beginning of an array of pointers.
// E is the End of an array of pointers that are in use.
// Room the end of an array of all pointers, used or not.

struct Lnk_T { Link_P B, E, Room ; };

Lnk_T Lnk ;

enum { Chunk = 4,
Sz_Ptr = sizeof Link, Sz_Node = sizeof NodeT };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link_P ) realloc( Lnk.B, Room * Sz_Ptr );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Ptr ); }
// Below is an example of is how the above might be used,
// I know that it works.

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

GrowList ( Lnk ); // Lnk is a global, so it's initialized.

Link & P = * Lnk.E ++ ;

P = ( Link ) realloc( P, Sz_Node );

memset ( P, 0, Sz_Node );

GrowList ( ( Lnk_T & ) P->Lnk );

{ Link Passed = P, & P = * Passed->Lnk.E ++ ;

P = ( Link ) realloc( P, Sz_Node );

memset ( P, 0, Sz_Node );

GrowList ( ( Lnk_T & ) P->Lnk );

// etc.
}

But is there any way to declare NodeT so that
I don't have to use that ( Lnk_T & ) cast ?

Good lord, that's the worst code I've ever seen. I hope I don't ever
have to maintain something of yours.

It's considered polite, when incrementing a pointer value, to bracket to
explicity show what you're intending, i.e.
(*p)++ return the value at the pointer, then increment the value
*(p++) return the value at the pointer, then increment the pointer

Maybe I got those backwards. Which is why you really want to be explicit.

--
FreeBSD 4.8-RELEASE i386
11:20AM up 130 days, 3:23, 1 user, load averages: 0.00, 0.01, 0.00

[Jeff Relf]

Karl Heinz Buchegger

Re: Nodes with unlimited children,

You wrote,
" Start the whole thing with a forward declaration of NodeT. "

Oh, how so very sweet, thank you much !

By the way,
I just realized that the code that I showed in my original
post was really designed for a NodeT of varying length,
which I don't think I really need.

So this is how it looks now ( and it works ),

struct NodeT ;

typedef NodeT * Link ;

// B is the Beginning of an array of NodeT's.
// E is the End of an array of NodeT's that are in use.
// Room the end of an array of all NodeT's, used or not.

struct Lnk_T { Link B, E, Room ; };

struct NodeT { Lnk_T Lnk ; };

Lnk_T Lnk ;

enum { Sz_Node = sizeof NodeT, Chunk_Lnk = 4 };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk_Lnk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link ) realloc( Lnk.B, Room * Sz_Node );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Node ); }

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

// Lnk is a global, so it's initialized.
// This creates a child for Lnk.
// There is no limit to the number of children.
GrowList ( Lnk );

// This creates a grandchild for Lnk.
GrowList ( ( * Lnk.E ++ ).Lnk );

// etc
}

You wrote,
" BTW: I consider your formatting style horrible. "

Everyone employs whitespace differently,
I even change my own style from time to time.

So I don't see how it's worth commenting on.

[Joe Gottman]

"Jeff Relf" <Jeff_Relf_@_NC Plus.NET.Invali d> wrote in message
news:_J******** *************** **@NCPlus.NET.. .

Hi All,

I plan on using the following C++ code
to create nodes with unlimited children:

<code snipped>

There's a clever way to get this effect with only two Node *'s per Node:

class Node
{
/* put data here */
Node *firstChild;
Node *nextSibling;
};

Then, to get all the children of a node, you just do
for (Node *child = myNode->firstChild; child != 0; child =
child->nextSibling) {
// whatever
}

This works great as long as you don't need constant-time access to the
nth child of a Node.

Joe Gottman

[Jeff Relf]

Hi General Protection Fault,

Re: Precedence vs. overused parentheses,
such as: ( * Lnk.E ++ ).Lnk in the following code,

struct NodeT ;

typedef NodeT * Link ;

// B is the Beginning of an array of NodeT's.
// E is the End of an array of NodeT's that are in use.
// Room the end of an array of all NodeT's, used or not.

struct Lnk_T { Link B, E, Room ; };

struct NodeT { Lnk_T Lnk ; };

Lnk_T Lnk ;

enum { Sz_Node = sizeof NodeT, Chunk_Lnk = 4 };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk_Lnk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link ) realloc( Lnk.B, Room * Sz_Node );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Node ); }

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

// Lnk is a global, so it's initialized.
// This creates a child for Lnk.
// There is no limit to the number of children.
GrowList ( Lnk );

// This creates a grandchild for Lnk.
GrowList ( ( * Lnk.E ++ ).Lnk );

// etc
}

If you're asking me,
it's much better to know the precedence of operators
than to overuse parentheses.

For example:
( * Lnk.E ++ ).Lnk is better than ( * ( Lnk.E ++ ) ).Lnk

But it's subjective, so why quibble ?

As for you maintaining my code,
I wouldn't worry about that if I were you.

Here is the order of precedence, highest first:
++ Post-increment, Left to right
-- Post-decrement
( ) Function call
[ ] Array element
-> Pointer to structure member
.. Structure or union member
++ Pre-increment, Right to left
-- Pre-decrement
! Logical NOT
~ Bitwise NOT
- Unary minus
+ Unary plus
& Address
* Indirection
sizeof Size in bytes
new Allocate program memory
delete Deallocate program memory
( type ) Type cast [ for example, ( float ) i ]
..* Pointer to member ( objects ), Left to right
->* Pointer to member ( pointers )
* Multiply, Left to right
/ Divide
% Remainder
+ Add, Left to right
- Subtract
<< Left shift, Left to right

Right shift

< Less than, Left to right
<= Less than or equal to Greater than
= Greater than or equal to

== Equal, Left to right
!= Not equal
& Bitwise AND, Left to right
^ Bitwise exclusive OR, Left to right
| Bitwise OR, Left to right
&& Logical AND, Left to right
|| Logical OR, Left to right
? : Conditional, Right to left
= Assignment, Right to left
*=, /=, %=, +=, -=, <<=, >>=, &=, ^=, |= Compound assignment
, Comma, Left to right

[International All-Star Cast]

Jeff Relf wrote:

Hi General Protection Fault,

Re: Precedence vs. overused parentheses,
such as: ( * Lnk.E ++ ).Lnk in the following code,

struct NodeT ;

What a bunch of boring bullshit.

Here's something more interesting. I was writing a c# service and that
created a file that would then be transferred somewhere else. Originally I
coded some meta-data in the file name, but then because that had specific
size requirements, I had to use something else. How about File Properties
( right click on a text file, and look at the Properties ( third ) tab. It
has stuff like Author, Title, Subject.

I figure those nice m$ people created a cool assembly that would let me
set/get those. Well there is a class with get methods but not set methods.
So, I had to use a COM object that M$ supplies called DFOfile.dll

Yeah, so, when you dig a little beneath the pretty surface of .NET -- it's
all COM.

typedef NodeT * Link ;

// B is the Beginning of an array of NodeT's.
// E is the End of an array of NodeT's that are in use.
// Room the end of an array of all NodeT's, used or not.

struct Lnk_T { Link B, E, Room ; };

struct NodeT { Lnk_T Lnk ; };

Lnk_T Lnk ;

enum { Sz_Node = sizeof NodeT, Chunk_Lnk = 4 };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk_Lnk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link ) realloc( Lnk.B, Room * Sz_Node );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Node ); }

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

// Lnk is a global, so it's initialized.
// This creates a child for Lnk.
// There is no limit to the number of children.
GrowList ( Lnk );

// This creates a grandchild for Lnk.
GrowList ( ( * Lnk.E ++ ).Lnk );

// etc
}

If you're asking me,
it's much better to know the precedence of operators
than to overuse parentheses.

For example:
( * Lnk.E ++ ).Lnk is better than ( * ( Lnk.E ++ ) ).Lnk

But it's subjective, so why quibble ?

As for you maintaining my code,
I wouldn't worry about that if I were you.

Here is the order of precedence, highest first:
++ Post-increment, Left to right
-- Post-decrement
( ) Function call
[ ] Array element
-> Pointer to structure member
. Structure or union member
++ Pre-increment, Right to left
-- Pre-decrement
! Logical NOT
~ Bitwise NOT
- Unary minus
+ Unary plus
& Address
* Indirection
sizeof Size in bytes
new Allocate program memory
delete Deallocate program memory
( type ) Type cast [ for example, ( float ) i ]
.* Pointer to member ( objects ), Left to right
->* Pointer to member ( pointers )
* Multiply, Left to right
/ Divide
% Remainder
+ Add, Left to right
- Subtract
<< Left shift, Left to right

Right shift

< Less than, Left to right
<= Less than or equal to

Greater than
= Greater than or equal to

== Equal, Left to right
!= Not equal
& Bitwise AND, Left to right
^ Bitwise exclusive OR, Left to right
| Bitwise OR, Left to right
&& Logical AND, Left to right
|| Logical OR, Left to right
? : Conditional, Right to left
= Assignment, Right to left
*=, /=, %=, +=, -=, <<=, >>=, &=, ^=, |= Compound assignment
, Comma, Left to right

--
http://kentpsychedelic.blogspot.com

[Jeff Relf]

Oops, I should've said:

I prefer Lnk.E ++ -> Lnk over ( Lnk.E ++ ) -> Lnk

[Jeff Relf]

Hi Joe Gottman,

You showed something similar this:

class Node_Type {
Node * firstChild ;
Node * nextSibling ; };

for ( Node_Type * child = myNode->firstChild ;
child != 0 ;
child = child->nextSibling ) ...
For what I'm doing, I prefer my dynamic array of nodes.

such as: Lnk.E ++ -> Lnk ( defined below ),

That allows me to do things like: Lnk.B [ 4 ]
which directly references the fifth node.

My NodeT is very small and has a fixed size,
if NodeT was large or if it had a dynamic size
I'd use the code that I originally posted in this thread:
news:_J******** *************** **@NCPlus.NET

To loop though all the child nodes I define this:
( Lnk is a global, see below )

#define LoopChildren \
Link _Lnk = Lnk.B - 1 ; while ( ++ _Lnk < Lnk.E )

Which is then called like this:

LoopChildren _Lnk->Whatever ;

Here's how I declared those variables:

struct NodeT ;

typedef NodeT * Link ;

// B is the Beginning of an array of NodeT's.
// E is the End of an array of NodeT's that are in use.
// Room the end of an array of all NodeT's, used or not.

struct Lnk_T { Link B, E, Room ; };

struct NodeT { int Whatever ; Lnk_T Lnk ; };

Lnk_T Lnk ; // This is a global variable, so it's initialized.

enum { Sz_Node = sizeof NodeT, Chunk_Lnk = 4 };

GrowList ( Lnk_T & Lnk ) {
if ( Lnk.E + 1 < Lnk.Room ) return;
int Room = Lnk.Room - Lnk.B + Chunk_Lnk, E = Lnk.E - Lnk.B ;
Lnk.B = ( Link ) realloc( Lnk.B, Room * Sz_Node );
Lnk.Room = Lnk.B + Room ; Lnk.E = Lnk.B + E ;
memset( Lnk.E, 0, ( Lnk.Room - Lnk.E ) * Sz_Node ); }

__stdcall WinMain( HINSTANCE, HINSTANCE, LPSTR, int ) {

// This creates a child for Lnk.
// There is no limit to the number of children.
GrowList ( Lnk );

// This creates a grandchild for Lnk.
GrowList ( Lnk.E ++ -> Lnk );

// etc
}

[Jeff Relf]

Hi International All-Star Cast,

Win XP's File Properties is... well... specific to Win XP,
and therefore it can't be part of the main C# framework.

I'm sure that there is
plenty of C# code that only runs on Win XP.

To be sure that your C# code _ Shines _
on dual 64-bit PowerPCs as well as on some arcane cell phone,
you'd better damn well test it on all of those devices.