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 ?

[The Ghost In The Machine]

In comp.os.linux.a dvocacy, Jeff Relf
<Jeff_Relf_@_NC Plus.NET.Invali d>
wrote
on 3 Aug 2004 10:22:39 GMT
<_J************ ************@NC Plus.NET>:

Hi Karl Heinz Buchegger,

Re: The Ghost In The Machine and me,

You wrote: <<
_______________ ______
/| /| | |
||__|| | Please do not |
/ O O\__ | feed the |
/ \ | Trolls |
/ \ \|_____________ ________|
/ _ \ \ ||
/ |\____\ \ ||
/ | | | |\____/ ||
/ \|_|_|/ | _||
/ / \ |____| ||
/ | | | --|
| | | |____ --|
* _ | |_|_|_| | \-/
*-- _--\ _ \ | ||
/ _ \\ | / `
* / \_ /- | | |
* ___ c_c_c_C/ \C_c_c_c_______ _____

At least we're talking abut C++, doesn't that count ?

I don't think the Ghost is a troll,
I just think he has a different point of view from me.

Very different. :-)

A lot of people have scored me down too,
but that's fine with me...

I'm not entering anyone's popularity contest.

It's even possible that
The Ghost and I could come to a understanding.
I understand you well enough. Admittedly, there are
those out there who think nothing of putting
no comments at all into swamp muck, codeswill, or
execrable crap, then using it as the documentation
basis for whatever the tool is supposed to do.

(The computer has no problem understanding Obfuscated C.
But mere mortals have to take it apart. Code should
be understandable to both man and machine -- ideally.)

Of course part of my position is self-defense. I write
something, come back to it later, and wonder why the
hell I wrote it that particular way. It behooves me
to be able to read my own code -- and presumably that
means others can at least have a chance of decoding
what I scribbled into the computer at some point.

ObLinux: I can get the source code. That is a plus in itself.

There's so much miscommunicatio n on Usenet...

Why not try to resolve some of it ?

--
#191, ew****@earthlin k.net
It's still legal to go .sigless.

[Jeff Relf]

Hi The Ghost In The Machine,

Oops, I showed: <<
FuBar () { int X = -1, Y = -1 ;

Loop ( 6 ) { ++ X ; Loop ( 7 ) ++ Y ; }

// Prints: 5 and 6

printf ( " %d and %d ", X, Y ); }

And you correctly corrected me: <<
The results I get are 5 and 41, before and after conversion.
This is regardless of whether I use 'i' or 'j'
as the inner variable, which shadows the outer one. >>

I meant to write this:

FuBar () { int X = -1, Y = -1 ;

{ Loop ( 6 ) ++ X ; } Loop ( 7 ) ++ Y ;

// Prints: 5 and 6

printf ( " %d and %d ", X, Y ); }
I say that this: { Loop ( 6 ) ++ X ; } Loop ( 7 ) ++ Y ;
is more readable than this:

for(int i = 0; i < 6; i++)
{
x++;
for(int j = 0; j < 7; j++)
y++;
}

You commented: " I'm surprised you can read that gunk. "

That only goes to show that
one man's meat is another man's poison.

I'm into targeting Win XP for personal use,
( I put the personal in personal computer )...

and you're into targeting servers in a large corporation...

As the saying goes:

I'm ok, you're ok,
and Microsoft should give us a 75 billion dollar rebate.

[Jeff Relf]

Hi The Ghost In The Machine,

You showed: <<
it = std::binary_sea rch(
collection.begi n(), collection.end( ), "constant") ;

Yea, my original plan was to :

A. qsort() the unthread list of Usenet messages ( Flat ).
( Flat contains one huge array of pointers to nodes,
as described here
news:_J******** *************** *@NCPlus.NET )

B. Then do a binary search on it.

But then I ran the code... No need for the binary search.

It's already instant,

even with a list of two thousand messages.
( Even more so when compared to how long it takes me
to download those messages using a spotty dial-up service )

In fact, it's much much Much faster than 40Tude Dialog,
the newsreader that I was using before I wrote X.
( Actually, I'm still using Dialog for some things,
because X is still so primitive )

Re: Your code:
typedef std::string itemtype; // or whatever you want
typedef std::xxx<itemty pe> collectiontype;
// xxx = set, vector, or list
collectiontype collection;
collectiontype: :const_iterator it;

You said: " ...it should be fairly clear what I'm doing. "

Yes, it is quite clear ( and quite interesting too ).

You showed: <<
Now, after one's assigned a value to 'it',
one can then test 'it':

if ( it != collection.end( ) ) /* found it */

Of course, I do that all the time...

Only I say this: if ( J < LLL ) // found, i.e. broke out.

after: Loop( 5 ) if ( Eq( "Hello", Line_Array[ J ] ) ) break;

where: #define Eq ! strcmp

#define Loop( N ) int J = -1, LLL = N ; while ( ++ J < LLL )

The main difference is that I'm using J, not " it ",
and LLL, not collection.end( ) .

Re: collection.eras e( it );

With my dynamic arrays of pointers to children and/or lines,
( Using B, P, E, and Inc() described recently:
_J************* ***********@NCP lus.NET )...

...I just free one or more pointers and then
use memmove to overwrite them, the I adjust P,
e.g. -- Ln.P, or -- Forest.P .
( I would show you exactly how I do that,
but it's past 6 am now,
and I usually go to bed at 3 am,
and I have to be on campus by 10 am... uuugh ! )

You wrote: <<
Dereferencing a non-end pointer ( '*it' )
will get the item back. >>

Yea, that's similar to my code here:
LoopC ( & Flat )
if ( Eq ( Par, ( * Arr )->Ln [ _MID ] ) ) break ;
You showed:
collection.eras e( collection.begi n(), collection.end( ) );
saying: << If one wants an explicit forest of items
some work will be required to encapsulate them properly. >>

Right, the STL has no " Forest " type,
especially not one with unlimited children...

So your code above wouldn't work...
forests have to be recursively deleted/printed.

You said: " Enjoy your swamp muck... ".

Oh, of that you can be Quite sure...

I'm loving every minute of it.

But I've got to go now...

[Richard Herring]

In message <sr************ *****@newssvr15 .news.prodigy.c om>, Phlip
<ph*******@yaho o.com> writes

Jeff Relf wrote:

Hi Kelsey Bjarnason,

Re:
#define Loop( N ) int J = -1, LLL = N ; while ( ++ J < LLL )

You commented: << Marvellous; symbol clashes,
just because you use this macro twice in the same scope.
Talk about badly-written. >>

You're worried about compilation errors ?

Real programmers are Never concerned about that.

Real programmers don't piss their colleagues off. They write clear, simple,
robust, and easily-changed code. This helps keep their colleagues in the ...
loop.

They don't change the subject line with every reply, either.

--
Richard Herring

[The Ghost In The Machine]

In comp.os.linux.a dvocacy, Jeff Relf
<Jeff_Relf_@_NC Plus.NET.Invali d>
wrote
on 4 Aug 2004 13:26:28 GMT
<_J************ ************@NC Plus.NET>:

Hi The Ghost In The Machine,

You showed: <<
it = std::binary_sea rch(
collection.begi n(), collection.end( ), "constant") ;

Yea, my original plan was to :

A. qsort() the unthread list of Usenet messages ( Flat ).
( Flat contains one huge array of pointers to nodes,
as described here
news:_J******** *************** *@NCPlus.NET )

B. Then do a binary search on it.

But then I ran the code... No need for the binary search.

It's already instant,

even with a list of two thousand messages.
( Even more so when compared to how long it takes me
to download those messages using a spotty dial-up service )

In fact, it's much much Much faster than 40Tude Dialog,
the newsreader that I was using before I wrote X.
( Actually, I'm still using Dialog for some things,
because X is still so primitive )

Re: Your code:
typedef std::string itemtype; // or whatever you want
typedef std::xxx<itemty pe> collectiontype;
// xxx = set, vector, or list
collectiontype collection;
collectiontype: :const_iterator it;

You said: " ...it should be fairly clear what I'm doing. "

Yes, it is quite clear ( and quite interesting too ).

You showed: <<
Now, after one's assigned a value to 'it',
one can then test 'it':

if ( it != collection.end( ) ) /* found it */

Of course, I do that all the time...

Only I say this: if ( J < LLL ) // found, i.e. broke out.

after: Loop( 5 ) if ( Eq( "Hello", Line_Array[ J ] ) ) break;

where: #define Eq ! strcmp

*hack* *cough*

Try

if(Eq(1, 2))

and see how far you get. I'll be standing way over here...

#define Loop( N ) int J = -1, LLL = N ; while ( ++ J < LLL )

The main difference is that I'm using J, not " it ",
and LLL, not collection.end( ) .
Right. Now replace your list with a red-black tree.

Re: collection.eras e( it );

With my dynamic arrays of pointers to children and/or lines,
( Using B, P, E, and Inc() described recently:
_J************* ***********@NCP lus.NET )...

...I just free one or more pointers and then
use memmove to overwrite them, the I adjust P,
e.g. -- Ln.P, or -- Forest.P .
( I would show you exactly how I do that,
but it's past 6 am now,
and I usually go to bed at 3 am,
and I have to be on campus by 10 am... uuugh ! )

You wrote: <<
Dereferencing a non-end pointer ( '*it' )
will get the item back. >>

Yea, that's similar to my code here:
LoopC ( & Flat )
if ( Eq ( Par, ( * Arr )->Ln [ _MID ] ) ) break ;
You showed:
collection.eras e( collection.begi n(), collection.end( ) );
saying: << If one wants an explicit forest of items
some work will be required to encapsulate them properly. >>

Right, the STL has no " Forest " type,
especially not one with unlimited children...
Don't be so sure. In fact, std::set<> and std::map<>
use a red-black tree.

You're right in that STL has no "Forest" type. I'm not sure
how much of a limitation that is.

So your code above wouldn't work...
forests have to be recursively deleted/printed.

You said: " Enjoy your swamp muck... ".

Oh, of that you can be Quite sure...

I'm loving every minute of it.

But I've got to go now...

--
#191, ew****@earthlin k.net
It's still legal to go .sigless.

[Jeff Relf]

Hi Kelsey Bjarnason,

In news:_J******** *************** *@NCPlus.NET ,
I said to The Ghost: <<
...you and Kelsey Bjarnason were talking about
how much you dislike my AllocN() macro... >>

And you, not remembering what you last wrote, said: <<
Never mentioned it, AFAIK;
although I did make a mention or two about your
Loop and loop macros and your Zero macro. >>

To refresh your memory, see:
news:pa******** *************** *****@xxnospamy y.lightspeed.bc .ca
( Shit, what a verbose Message-ID )

You quoted AllocN() and then commented: <<
Good god. If you're going to do that much work,
use a frippin' function, not a macro. >>

And I said that it was so I could do: { ... continue; }
thus creating fewer ( ugly ) braces in my code.

At any rate, I'm very glad you quoted AllocN(),
as that gave me an excuse to update it...
and to explain to you and the Ghost
how it creates a forest of bushy trees
( i.e. where the number of direct-children per node
is not limited ).

Re: memmove( Dest = malloc( Sz ), Source, Size )

You commented: << If malloc fails, you're hooped. >>

That wasn't my concern ( of course ),
I noticed that that code didn't work in certain places...

So I had to separate out the two calls, like this:
Dest = malloc( Sz ); memmove( Dest , Source, Size )

As I said... I have no idea why.

You quoted: P = ( Lnk_T ) malloc( sizeof NodeT );

And commented: << Okay, look, if you're coding in C,
lose the cast; it is extremely bad practice and hides bugs.
If you're coding in C++,
why are you using malloc at all, when there's new ? >>

I'm obviously coding in C++ ( only without the STL ),

You should've known that by all the binding I was doing,
eg: Line & Inc ( Ln_T & Ln );

So either you don't know C or you aren't reading my code...
Probably both. ( No big deal )

You asked why I use realloc() when there's new...

Compare new and realloc()... ( I'll wait )

Which is better ? ( No cheating )

[Jeff Relf]

Richard Herring,

Re: How I use appropriate titles, in compliance with RFC 1036.

RFC documents employ exact definitions of
these two all-uppercase words: SHOULD and MUST.

Because the title of a message SHOULD describe the message,
RFC 1036 says that when the topic changes:

A. One SHOULD Not use "Re: " at the start of a title.

B. One SHOULD Not delete the References line.

From http://www.usenet-fr.net/fr-chartes/...rfc1036.2.html
<< If the poster determines that
the topic of the followup differs significantly
from what is described in the subject,
a new, more descriptive, subject SHOULD be substituted
( With No Back Reference ). >>
^^^^ ^^ ^^^^ ^^^^^^^^^

The term, " back reference " here is defined as
the " Re: " tag at the start of a title,
( Not the References: line in the headers ).

Google violates RFC 1036 by mandating something more like this:

Because the title of a message MUST define the thread,
One MUST use "Re: " at the start of a title...
Otherwise we MUST delete the References line.

If you were to not side with Google's violation of RFC 1036...

You could " Sort by Thread " ( i.e. the references line ),
( rather than by titles ).

You also might consider unchecking the box that says:
" Start a new thread when the title changes ".

If you simply don't like RFC 1036,
and you choose to violate it...

Please don't complain to me
about the problems it is causing _ You _ .

[JustBoo]

On 31 Jul 2004 08:32:10 GMT, Jeff Relf
<Jeff_Relf_@_NC Plus.NET.Invali d> wrote:

You will never ever catch me telling someone that
his code is hard to maintain ( at least if I'm honest ).
You haven't been around much, have you.
I might well refuse to maintain someone's old code,
as I always prefer total rewrites.
You obviously have never spent a single minute in a commercial
software company, have you. Total rewrites... bwhaahaaaa.
I actually own a 450 dollar copy of MS Fortran for Win98.
( From when I converted some Fortran code to C )
But I never used it, thank God... I refused to.
So you converted from a language you never read about... okay, there's
a clue.
So I know what Fortran code ( and Fortran programmers )
look like ( with their big iron, IBM, and all that ).
But you said you never looked at the book?
I've seen those huge hard disk platters.
Did this excite you in some way?
Hmm... Where they the forerunner to floppies ?
( Not counting tape, of course )

"Never try to teach a pig to sing, it wastes time and annoys the pig."