Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15856 > unrolled thread

Tree implementation, ideas for keyboard input method needed

Back to article view | Back to comp.lang.c

Contents

  Tree implementation, ideas for keyboard input method needed Bubba <nickname@banelli.biz.invalid> - 2012-01-16 22:01 +0000
    Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 14:27 -0800
      Re: Tree implementation, ideas for keyboard input method needed Bubba <nickname@banelli.biz.invalid> - 2012-01-16 22:36 +0000
        Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-16 22:53 +0000
        Re: Tree implementation, ideas for keyboard input method needed James Kuyper <jameskuyper@verizon.net> - 2012-01-16 18:06 -0500
        Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 16:41 -0800
      Re: Tree implementation, ideas for keyboard input method needed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-16 23:01 +0000
        Re: Tree implementation, ideas for keyboard input method needed Shao Miller <sha0.miller@gmail.com> - 2012-01-16 19:49 -0500
          Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 17:46 -0800
    Re: Tree implementation, ideas for keyboard input method needed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-16 22:29 +0000
      Re: Tree implementation, ideas for keyboard input method needed Bubba <nickname@banelli.biz.invalid> - 2012-01-16 22:38 +0000
      Re: Tree implementation, ideas for keyboard input method needed William Ahern <william@wilbur.25thandClement.com> - 2012-01-16 15:30 -0800
        Re: Tree implementation, ideas for keyboard input method needed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-17 00:03 +0000
        Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 16:35 -0800
          Re: Tree implementation, ideas for keyboard input method needed cri@tiac.net (Richard Harter) - 2012-01-17 02:00 +0000
            Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 19:16 -0800
              Re: Tree implementation, ideas for keyboard input method needed cri@tiac.net (Richard Harter) - 2012-01-17 05:15 +0000
                Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-17 00:00 -0800
            Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-17 04:04 +0000
    Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-16 22:44 +0000
    Re: Tree implementation, ideas for keyboard input method needed Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-16 17:58 -0500
    Re: Tree implementation, ideas for keyboard input method needed ImpalerCore <jadill33@gmail.com> - 2012-01-16 19:36 -0800
      Re: Tree implementation, ideas for keyboard input method needed Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-16 23:33 -0500
        Re: Tree implementation, ideas for keyboard input method needed ImpalerCore <jadill33@gmail.com> - 2012-01-17 07:18 -0800
      Re: Tree implementation, ideas for keyboard input method needed "BartC" <bc@freeuk.com> - 2012-01-17 13:54 +0000
        Re: Tree implementation, ideas for keyboard input method needed ImpalerCore <jadill33@gmail.com> - 2012-01-17 07:39 -0800
      Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-17 19:01 +0000
    Re: Tree implementation, ideas for keyboard input method needed jgk@panix.com (Joe keane) - 2012-01-18 21:21 +0000

Page 2 of 2 — ← Prev page 1 [2]

#15864

On 1/16/2012 5:01 PM, Bubba wrote:
> Greetings,
>
> nodes of my ordered tree are implemented like this:
>
>      typedef struct __celltype {

     A minor point: `__celltype' is a reserved identifier, and if
the implementation decides to use the identifier for its own
purposes (which it's at liberty to do without warning you), chaos
is likely to ensue.  Use an identifier from the name space belonging
to the programmer -- `celltype' is fine, yes, even though you're also
going to use `celltype' as a typedef alias for `struct celltype'.

>            labeltype label;
>            struct __celltype *first_child;
>            struct __celltype *next_sib;
>            struct __celltype *last_child;
>            int zadnji;
>      } celltype;
>      typedef celltype *node;
>      typedef celltype *TREE;

     Another minor point: It's been my experience that typedef aliases
for pointer types usually cause confusion.  "Usually" is not "always,"
but I think you'd be better off without these aliases.  The fact that
you have two identical aliases suggests that a certain amount of
confusion may already have crept in: When would you use `node' and
when would you use `TREE', and what difference are you trying to
express by choosing one or the other?

> where first_child points to first sibling of the node, next_sib points to
> next sibling and last_child points to last sibling in the node.

     I'll assume you mean that `first_child' and `last_child' point
to the first and last *children* of the node, not to its first and
last siblings.

> next sibling and last_child points to last sibling in the node. Data
> zadnji is true if the node is last child of any other node.
>
> Labeltype is char.
>
> Here's the whole implementation:
>
> #include<stdlib.h>
> #include<stdio.h>
> #define LAMBDA NULL
> #define labeltype char
>
> typedef struct __celltype {
>            labeltype label;
>            struct __celltype *first_child;
>            struct __celltype *next_sib;
>            struct __celltype *last_child;
>            int zadnji; /*last*/
>      } celltype;
>
> typedef celltype *node;
> typedef celltype *TREE;
>
> node MAKE_ROOT(labeltype l, TREE *T) {
>       if (!(*T = (celltype*) malloc(sizeof(celltype)))) {

     Yet more minor points: First, it's not necessary to cast the
result of malloc().  Second, the code relies on `TREE' being an
alias for `celltype*', which means you're not actually getting any
value out of the `TREE' alias.  Here's a better paradigm, no matter
what type of data `T' points to:

	if (!(*T = malloc(sizeof(**T))) ...

>      printf("Nema dovoljno memorije.");
>      exit(1);

     Minor points: Put a newline '\n' at the end of the message,
and use exit(EXIT_FAILURE) instead of exit(1).

     As a matter of design, it is usually not a good idea for a
"low-level" function to make such a drastic decision about the
fate of the entire program.  Normally, it's better to indicate
failure in some other way, and let the higher-level caller decide
how to deal with it; the higher-level caller has more "knowledge"
of the state of the entire program.  Even if the eventual action
is to exit(), the caller might want to do something else first.
Observe that malloc() does not terminate your program when it
fails, but instead reports the failure and lets the program make
its own choice; consider following that pattern in your own code,
especially in functions near the "leaves."

>    }
>       (*T)->label=l;
>       (*T)->first_child=NULL;
>       (*T)->next_sib=NULL;
>       (*T)->last_child=NULL;
>       (*T)->zadnji=0;
>       return *T;

     Yet another confusion of aliases: This line relies on
`TREE' being the same as `node'.  In one function you've used
three different names for exactly the same type!  Do you think
this makes the code easier or harder to read?

     There's also a design oddity.  The function returns its
result via two different channels: It stores the new pointer
at the location pointed to by `T', and it also returns the
same pointer as the function value.  There's nothing actually
"wrong" with this, but it's unusual enough to raise an eyebrow.
Usually, you'll want to use just one channel to export a result;
functions like time() are the exception, not the rule.

>       }
>
> node INSERT_CHILD(labeltype l, node i, TREE *T){
>       node temp;
>         if (!i) {
>      printf("Nema tog cvora.");
>      exit(1);
>    }
>    if (!(i->first_child= (celltype*) malloc(sizeof(celltype)))) {
>      printf("Nema dovoljno memorije.");
>      exit(1);
>    }
>    if (i->first_child==NULL)  {

     Okay, here's an actual problem: Observe that (1) the code in
this part of the `if' statement will never execute, and (2) if it
somehow did execute you'd be trying to store data where the NULL
pointer points!

>        i->first_child->label=l;
>        i->first_child->first_child=NULL;
>        i->first_child->next_sib=NULL;
>        i->first_child->last_child=NULL;
>        i->first_child->zadnji=1;
>        }
>      if (i->first_child!=NULL)  {

     ... and here's another part of the same problem: This code
will always execute, and will wind up producing an endless loop
in your data structure: That is, `i->first_child->next_sib' will
point back to `i->first_child' again.  Any siblings that might
already have existed are now lost forever.

>        temp=i->first_child;
>        i->first_child->label=l;
>        i->first_child->first_child=NULL;
>        i->first_child->next_sib=temp;
>        i->first_child->last_child=NULL;
>        i->first_child->zadnji=0;
>        }
>        return i->first_child;
> }
>
> node ROOT(TREE T){
>       return T;
>       }
>
> node INSERT_SIBLING(labeltype l, node i, TREE *T){
>       node temp;
>         if (!i) {
>      printf("Nema tog cvora.");
>      exit(1);
>    }
>    if (!(i->next_sib= (celltype*) malloc(sizeof(celltype)))) {
>      printf("Nema dovoljno memorije.");
>      exit(1);
>    }
>    if (i==ROOT(*T)) {
>               printf("Taj cvor je korijen.");
>      exit(1);
>    }
>    if(i->zadnji==1){
>       i->zadnji=0;
>       i->next_sib->label=l;
>       i->next_sib->first_child=NULL;
>       i->next_sib->next_sib=NULL;
>       i->next_sib->last_child=NULL;
>       i->next_sib->zadnji=1;
>       }
>      if(i->zadnji==0){
>        temp=i->next_sib;
>        i->next_sib->label=l;
>       i->next_sib->first_child=NULL;
>       i->next_sib->next_sib=temp;
>       i->next_sib->last_child=NULL;
>       i->next_sib->zadnji=0;
>       }
>       return i->next_sib;
>       }
>
> node PARENT(node i,TREE T){

     If you expect to navigate from child to parent, wouldn't it
be easier to store that link directly in the node than to do a
recursive search for it?

>         node c, d;
>         if (i==ROOT(T)) return LAMBDA;
>         if (!i) {
> 	   printf("Nema tog cvora.");
> 		exit(1);
> 		}
>         for (c=T->first_child; c!=NULL; c=c->next_sib)
>         if (c==i) return T;
>         for (c=T->first_child; c!=NULL; c=c->next_sib){
> 	   d=PARENT(i,c);
> 		if (d!=NULL) return d;
> 	}
> return NULL;
> }

     I'm running out of energy, and won't say much more; absence
of commentary should not be construed as approval!  One thing that
stands out is that you've duplicated the node-building operation
(allocate memory and initialize the struct) in about five places;
it would be much simpler (and easier!) to write just one function
to do this job, and to call it from wherever it's needed.  You've
got three functions whose job is to create a new struct and attach
it in various ways; consider separating the "create" and "attach"
operations, and I think you'll have shorter and cleaner code.

> void DELETE(node i, TREE *T) {
>       node c,d,e,f,temp;
>      if (i==ROOT(*T)) {
>      printf("Taj cvor je korijen."); /*is root*/
>      exit(1);
>      }
> 	if (!i) {
>      printf("Nema tog cvora."); /*no node*/
>      exit(1);
>    }
>    if (i->first_child!=NULL) {
>      printf("Taj cvor ima djece."); /*has sib*/
>      exit(1);
>   }
>   c=PARENT(i,*T);
>   if (c->first_child==c->last_child) {
>       free(i);
>       c->first_child=NULL;
>       c->last_child=NULL;
>       }
>   if (i==c->first_child) {
>       temp=i->next_sib;
>       free(i);
>       c->first_child=temp;
>       }
>    if(i==c->last_child) {
>        d=c->first_child;
>       while(d!=c->last_child) {
>          if (d->next_sib==i) {
>            d->next_sib=NULL;
>            d->zadnji=1;
>            break;
>            }
>      d=d->next_sib;
>    }
>    free(i);
>    c->last_child=d;
>    }
> if ((i!=c->first_child)&&  (i!=c->last_child)){
>
>      for (d=c->first_child; d!=NULL; d=d->next_sib){
>          if(d->next_sib==i) e=d;
>          if(i->next_sib==d) f=d;
>          }
>     free(i);
>     e->next_sib=f;
>    }
> }
>
> node FIRST_CHILD(node i, TREE T){
>       if (i->first_child==NULL) return NULL;
>       if (!i) {
>      printf("Nema tog cvora.");
>      exit(1);
>    }
>    return i->first_child;
> }
>
> node NEXT_SIBLING(node i, TREE T){
>       if (i->next_sib==NULL) return NULL;
>       if (!i) {
>      printf("Nema tog cvora.");
>      exit(1);
>    }
>    return i->next_sib;
> }
>
> labeltype LABEL(node i, TREE T) {
>     if (!i) {
>      printf("Nema tog cvora.");
>      exit(1);
>    }
>    return i->label;
> }
>
> void CHANGE_LABEL(labeltype l, node i, TREE *T){
>         if (!i) {
>      printf("Nema tog cvora.");
>      exit(1);
>    }
>    i->label=l;
> }
>
> void POSTORDER(node i, TREE T) {
>       node c;
>       for(c=FIRST_CHILD(i,T); c!=LAMBDA; c=NEXT_SIBLING(c,T))
>         POSTORDER(c,T);
>      printf("%c ", LABEL(i,T));
> }
>
>
> int main(void)
> {
>       return 0;
> }
>
>
>
> Now I need a sane way to input a tree from keyboard. What would be the
> easiest one?

     You could use parentheses to enclose groups of siblings:

	(A(B,C),D,E(F(G,H),I),J)

could encode a tree that might also be diagrammed as

	A
	+- B
	+- C
	D
	E
	+- F
	   +- G
	   +- H
	+- I
	J

     But first, fix your code!

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15876

On Jan 16, 5:01 pm, Bubba <nickn...@banelli.biz.invalid> wrote:
> Greetings,
>
[snip]
>
> Now I need a sane way to input a tree from keyboard. What would be the
> easiest one?
>
> Thanks in advance!

The simplest is probably to leverage an existing XML parser and write
your own XML format to populate your own custom "DOM" structure.  The
expat and libxml2 are fairly popular, and there are some varying
implementations of DOM floating around.

If you want to input a tree from the keyboard, you could type in the
tree data in XML format, feed it to one of the parsers, and use its
events to trigger using your interface to populate your tree.  It'll
take some work, but learning how to use an XML parser can be quite
useful.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#15878

On 1/16/2012 10:36 PM, ImpalerCore wrote:
> On Jan 16, 5:01 pm, Bubba<nickn...@banelli.biz.invalid>  wrote:
>> Greetings,
>>
> [snip]
>>
>> Now I need a sane way to input a tree from keyboard. What would be the
>> easiest one?
>>
>> Thanks in advance!
>
> The simplest is probably to leverage an existing XML parser and write
> your own XML format to populate your own custom "DOM" structure.  The
> expat and libxml2 are fairly popular, and there are some varying
> implementations of DOM floating around.

     Angels and ministers of grace defend us!  The O.P. is trying
to build a tree in which each node carries a payload of

	ONE

	LONESOME

	`CHAR'

	VALUE

... and you want to inflict XML on him?!?!

     Whereabouts do you live, ImpalerCore?  I want to be about five
hundred miles away, and upwind, when you find a cockroach in your
cupboard and exterminate it with nuclear armaments.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15889

On Jan 16, 11:33 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 1/16/2012 10:36 PM, ImpalerCore wrote:
>
> > On Jan 16, 5:01 pm, Bubba<nickn...@banelli.biz.invalid>  wrote:
> >> Greetings,
>
> > [snip]
>
> >> Now I need a sane way to input a tree from keyboard. What would be the
> >> easiest one?
>
> >> Thanks in advance!
>
> > The simplest is probably to leverage an existing XML parser and write
> > your own XML format to populate your own custom "DOM" structure.  The
> > expat and libxml2 are fairly popular, and there are some varying
> > implementations of DOM floating around.
>
>      Angels and ministers of grace defend us!  The O.P. is trying
> to build a tree in which each node carries a payload of
>
>         ONE
>
>         LONESOME
>
>         `CHAR'
>
>         VALUE
>
> ... and you want to inflict XML on him?!?!
>
>      Whereabouts do you live, ImpalerCore?  I want to be about five
> hundred miles away, and upwind, when you find a cockroach in your
> cupboard and exterminate it with nuclear armaments.

S/He doesn't need to use to entire subset that is XML.  The XML file
format represents a hierarchical structure that directly maps to a
tree.  What's wrong with this?

<a>
  <b>
    <c/>
    <d/>
  </b>
  <e>
    <f/>
  </e>
</a>

---Corresponding tree---

     a
    / \
   b   e
  / \   \
 c   d   f

If one is uncomfortable with using a XML parser, one could devise his
own scheme/parser.  The XML file format is just one popular model for
how to read and write information in a hierarchical tree-based
structure.

One could use a simple 'child:parent' format string like
'a,b:a,c:b,d:b,e:a,f:e', tokenize it, and using appropriate searches
and inserts, and would probably work fine for small trees.

I guess I've had too much XML on the mind lately.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#15886

"ImpalerCore" <jadill33@gmail.com> wrote in message
news:bd91005a-17a3-486b-b2e5-3f7466e439c3@d8g2000vbb.googlegroups.com...
> On Jan 16, 5:01 pm, Bubba <nickn...@banelli.biz.invalid> wrote:
>> Greetings,
>>
> [snip]
>>
>> Now I need a sane way to input a tree from keyboard. What would be the
>> easiest one?

> If you want to input a tree from the keyboard, you could type in the
> tree data in XML format, feed it to one of the parsers, and use its
> events to trigger using your interface to populate your tree.  It'll
> take some work, but learning how to use an XML parser can be quite
> useful.

It'll take quite some work on the part of the user as well, who will also
need to be an expert on XML.  (As well as needing to be prepared for quite a 
lot of typing..)

XML I would have thought was more suitable for file rather than keyboard
input, and would be best for machine-generated data.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15888

On Jan 17, 8:54 am, "BartC" <b...@freeuk.com> wrote:
> "ImpalerCore" <jadil...@gmail.com> wrote in message
>
> news:bd91005a-17a3-486b-b2e5-3f7466e439c3@d8g2000vbb.googlegroups.com...
>
> > On Jan 16, 5:01 pm, Bubba <nickn...@banelli.biz.invalid> wrote:
> >> Greetings,
>
> > [snip]
>
> >> Now I need a sane way to input a tree from keyboard. What would be the
> >> easiest one?
> > If you want to input a tree from the keyboard, you could type in the
> > tree data in XML format, feed it to one of the parsers, and use its
> > events to trigger using your interface to populate your tree.  It'll
> > take some work, but learning how to use an XML parser can be quite
> > useful.
>
> It'll take quite some work on the part of the user as well, who will also
> need to be an expert on XML.  (As well as needing to be prepared for quite a
> lot of typing..)

If you have a document that has a well defined structure, and you have
decent 'sed' or 'perl' skills, one can construct an XML document, or
at least a document fragment.  I'm currently tasked to create an XML
representation of a document from an approximate 2000+ PDF file, and
yes it is a lot of work, but 'sed' can provide some of the fine
document structure for data elements that have a uniform format.  I
still have to stitch the fragments together manually into a cohesive
XML document, and flesh out any format problems my script stumbles
across.

> XML I would have thought was more suitable for file rather than keyboard
> input, and would be best for machine-generated data.

We have web forms that people fill out that get translated into an XML
document, so while the content is user-entered, the XML structure is
computer generated.  People rarely have to manually encode raw XML
text files except for testing.

I agree that XML format is probably too much for toy tree input.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#15890

On 2012-01-17, ImpalerCore <jadill33@gmail.com> wrote:
> On Jan 16, 5:01 pm, Bubba <nickn...@banelli.biz.invalid> wrote:
>> Greetings,
>>
> [snip]
>>
>> Now I need a sane way to input a tree from keyboard. What would be the
>> easiest one?
>
> The simplest is probably to leverage an existing XML parser and write

XML ... keyboard ... no.

[toc] | [prev] | [next] | [standalone]

#15922

In article <Xns9FDCEA347419Bbubbachipsetone@130.133.4.11>,
Bubba  <nickname@banelli.biz.invalid> wrote:
>Now I need a sane way to input a tree from keyboard. What would be the 
>easiest one?

Like this?

int user_edit(struct tree *tree)
{
    ...
    for (;;)
    {
	...
	fputs("Command? [acdlsq] ");
	fflush(stdout);
	fgetstnl(cmd, sizeof cmd, stdin);
	c = cmd[0];

	switch (c)
	{
	  case 'a':

	    fputs("Key? ", stdout);
	    fflush(stdout);
	    fgetstnl(key, sizeof key, stdin);
	    fputs("Data1? ", stdout);
	    fflush(stdout);
	    fgetstnl(data1, sizeof data1, stdin);
	    err = add_node(tree, key, data1);
	    break:
	    ...
	  case 'l':
	    fputs("Filename? ", stdout);
	    fflush(stdout);
	    fgetstnl(filename, sizeof filename, stdin);
	    err = load_tree(tree, filename);
	    break;
	    ...
	  case 'q':
	    goto done;
	}

	if (err != 0)
	    fprintf(stdout, "Error: your command failed (%d)\n", err);
	...
    }
    ...
}

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web