Loading ...
Sorry, an error occurred while loading the content.

Question to graph theorists - non-recursive binary tree traversal algorithm?

Expand Messages
  • Omer Zak
    I devised an algorithm for traversing a tree, which does not need to maintain a stack. Is the algorithm a familiar one? If not, does it have any flaw? The
    Message 1 of 12 , Aug 25 12:29 AM
    • 0 Attachment
      I devised an algorithm for traversing a tree, which does not need to
      maintain a stack. Is the algorithm a familiar one? If not, does it
      have any flaw?

      The algorithm is as follows.
      1. Initially:
      Node <- pointer to tree's root node
      Direction <- downward
      2. Visit Node.
      If Direction==downward, go to 3.
      Otherwise, go to 4.
      3. If Node has children,
      Node <- Node.OldestChild(), go to 2.
      Otherwise, if Node has a younger sibling,
      Node <- Node.NextSibling(), go to 2.
      Otherwise,
      Direction <- upward, go to 4.
      4. If Node==pointer to tree's root node, terminate.
      Otherwise, Node <- Node.Parent().
      If Node has a younger sibling,
      Node <- Node.NextSibling(), Direction <- downward, go to 2.
      Otherwise, go to 4.

      The above algorithm implements depth-first, prefix order of visiting the
      tree's nodes.
      It may be possible to modify the algorithm to implement infix order or
      postfix order by moving the Visit Node statement to other places in the
      algorithm, but I did not investigate it.

      To implement a breadth-first tree traversal algorithm (i.e. all nodes at
      level N are visited before visiting a node at level N+1), it may be
      sufficient to maintain a counter remembering the current level and
      determine for each visited node which level it belongs to - so only
      nodes at the current level are actually manipulated.
      --- Omer
      --
      Every good master plan involves building a time machine. Moshe Zadka
      My own blog is at http://www.livejournal.com/users/tddpirate/

      My opinions, as expressed in this E-mail message, are mine alone.
      They do not represent the official policy of any organization with which
      I may be affiliated in any way.
      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
    • Arik Baratz
      ... You are relying on the existance of Node.OldestChild(), Node.NextSibling() and Node.Parent(). Implementing these, you ll discover that it s impossible
      Message 2 of 12 , Aug 25 12:39 AM
      • 0 Attachment
        On 25/08/05, Omer Zak <omerz@...> wrote:
        > 3. If Node has children,
        > Node <- Node.OldestChild(), go to 2.
        > Otherwise, if Node has a younger sibling,
        > Node <- Node.NextSibling(), go to 2.
        > Otherwise,
        > Direction <- upward, go to 4.

        You are relying on the existance of Node.OldestChild(),
        Node.NextSibling() and Node.Parent(). Implementing these, you'll
        discover that it's impossible (especially NextSibling() and Parent())
        without some information regarding a node's sibling or at least a
        node's parent in the node. This information replaces the information
        usually found in the stack in the regular recursive DFS.

        There are other ways to DFS without recursion, a notable one is to
        hold a linked list of pointers to the nodes above the current one,
        starting with the lowest, building it as you go by always adding to
        the head, and when you exhaust a node you simply remove the last link
        in the list. This is in fact uses the linked list as a stack.

        Then there's a question of why you want to avoid the recursion in the
        first place. It is more efficient than the methos you suggest - your
        suggestion requires O(n) space in all cases, while the stack, be it
        the language stack or a stack you are implementing, requires O(log n)
        space if the tree is balanced (and O(n) if it is very unbalanced).

        -- Arik
      • Omer Zak
        ... Very true. My algorithm requires each node to have also a pointer to its parent. A pointer to the next sibling is optional (but if it is missing and the
        Message 3 of 12 , Aug 25 1:00 AM
        • 0 Attachment
          On Thu, 2005-08-25 at 11:25 +0300, guy keren wrote:
          > no, except that instead of using a stack, you are storing the information
          > inside the nodes (i.e. how would the 'Node.NextSibling' method work
          > otherwise?).

          Very true. My algorithm requires each node to have also a pointer to its parent.
          A pointer to the next sibling is optional (but if it is missing and the tree is not
          binary, then the algorithm is less efficient).

          > this implies that your algorithm is not re-entrant (can't have to
          > different threads running it simultaneously, for example).

          Not true. The various links are read only, not written. Mutable state is stored
          in the algorithm's process and consists of pointer to current node and traversal
          direction flag.

          On Thu, 2005-08-25 at 00:39 -0700, Arik Baratz wrote:
          > On 25/08/05, Omer Zak <omerz@...> wrote:
          > > 3. If Node has children,
          > > Node <- Node.OldestChild(), go to 2.
          > > Otherwise, if Node has a younger sibling,
          > > Node <- Node.NextSibling(), go to 2.
          > > Otherwise,
          > > Direction <- upward, go to 4.
          >
          > You are relying on the existance of Node.OldestChild(),
          > Node.NextSibling() and Node.Parent(). Implementing these, you'll
          > discover that it's impossible (especially NextSibling() and Parent())
          > without some information regarding a node's sibling or at least a
          > node's parent in the node. This information replaces the information
          > usually found in the stack in the regular recursive DFS.

          Yes. Also Guy Keren pointed this out (see above).

          > There are other ways to DFS without recursion, a notable one is to
          > hold a linked list of pointers to the nodes above the current one,
          > starting with the lowest, building it as you go by always adding to
          > the head, and when you exhaust a node you simply remove the last link
          > in the list. This is in fact uses the linked list as a stack.

          In my book, this is recursion using a different name.

          > Then there's a question of why you want to avoid the recursion in the
          > first place. It is more efficient than the methos you suggest - your
          > suggestion requires O(n) space in all cases, while the stack, be it
          > the language stack or a stack you are implementing, requires O(log n)
          > space if the tree is balanced (and O(n) if it is very unbalanced).

          Guy made an incorrect comment about reentrancy, but since my algorithm
          is reentrant, I can suggest one possible application in which my
          algorithm would be better than a recursive algorithm:

          When you have 2^10 processes running simultaneously, and each one of
          them needs to traverse the tree, then my algorithm requires exactly two
          storage cells per process (one for pointer, one for Boolean flag). The
          various links, being read-only, are shared between all processes.

          In a recursion/linked list based algorithm, each process needs to
          maintain its own stack of pending node pointers.
          --- Omer
          --
          Every good master plan involves building a time machine. Moshe Zadka
          My own blog is at http://www.livejournal.com/users/tddpirate/

          My opinions, as expressed in this E-mail message, are mine alone.
          They do not represent the official policy of any organization with which
          I may be affiliated in any way.
          WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
        • Arik Baratz
          ... No. Recursion is when you use recursion. :-) Recursion is when you use the language s stack to hold data for you. Using a user data structure does not
          Message 4 of 12 , Aug 25 1:16 AM
          • 0 Attachment
            On 25/08/05, Omer Zak <omerz@...> wrote:

            > > There are other ways to DFS without recursion, a notable one is to
            > > hold a linked list of pointers to the nodes above the current one,
            > > starting with the lowest, building it as you go by always adding to
            > > the head, and when you exhaust a node you simply remove the last link
            > > in the list. This is in fact uses the linked list as a stack.
            >
            > In my book, this is recursion using a different name.

            No. Recursion is when you use recursion. :-)

            Recursion is when you use the language's stack to hold data for you.
            Using a user data structure does not constitute (at least in my mind)
            a recursive algorithm. It's an iterative algorithm utilizing a stack.

            > When you have 2^10 processes running simultaneously, and each one of
            > them needs to traverse the tree, then my algorithm requires exactly two
            > storage cells per process (one for pointer, one for Boolean flag). The
            > various links, being read-only, are shared between all processes.

            Then I'll ask another question, if I may: If all those m processes
            need access to the same data in the same order, won't it be easier to
            unroll the tree into a linear structure, which also requires O(n)
            space, such as a linked list, and then traverse it with the processes
            instead of re-traverse the binary tree again and again? Just a
            thought.

            -- Arik
          • guy keren
            ... no, except that instead of using a stack, you are storing the information inside the nodes (i.e. how would the Node.NextSibling method work otherwise?).
            Message 5 of 12 , Aug 25 1:25 AM
            • 0 Attachment
              On Thu, 25 Aug 2005, Omer Zak wrote:

              > I devised an algorithm for traversing a tree, which does not need to
              > maintain a stack.Is the algorithm a familiar one? If not, does it
              > have any flaw?

              no, except that instead of using a stack, you are storing the information
              inside the nodes (i.e. how would the 'Node.NextSibling' method work
              otherwise?).

              this implies that your algorithm is not re-entrant (can't have to
              different threads running it simultaneously, for example). it also implies
              that you rely on extra data stored in the nodes at all times.

              omer, you appear to be in a wierd mood today. i am waiting now for your
              attempt at solving the solvability(?) problem ;)

              --guy

              >
              > The algorithm is as follows.
              > 1. Initially:
              > Node <- pointer to tree's root node
              > Direction <- downward
              > 2. Visit Node.
              > If Direction==downward, go to 3.
              > Otherwise, go to 4.
              > 3. If Node has children,
              > Node <- Node.OldestChild(), go to 2.
              > Otherwise, if Node has a younger sibling,
              > Node <- Node.NextSibling(), go to 2.
              > Otherwise,
              > Direction <- upward, go to 4.
              > 4. If Node==pointer to tree's root node, terminate.
              > Otherwise, Node <- Node.Parent().
              > If Node has a younger sibling,
              > Node <- Node.NextSibling(), Direction <- downward, go to 2.
              > Otherwise, go to 4.
              >
              > The above algorithm implements depth-first, prefix order of visiting the
              > tree's nodes.
              > It may be possible to modify the algorithm to implement infix order or
              > postfix order by moving the Visit Node statement to other places in the
              > algorithm, but I did not investigate it.
              >
              > To implement a breadth-first tree traversal algorithm (i.e. all nodes at
              > level N are visited before visiting a node at level N+1), it may be
              > sufficient to maintain a counter remembering the current level and
              > determine for each visited node which level it belongs to - so only
              > nodes at the current level are actually manipulated.
              > --- Omer
              >

              --
              guy

              "For world domination - press 1,
              or dial 0, and please hold, for the creator." -- nob o. dy
            • Omer Zak
              ... Continuing the argument by shouting match: NO! NO!! NO!!! This is recursion because I am shouting louder than you!!!! ... When the tree is really immutable
              Message 6 of 12 , Aug 25 1:30 AM
              • 0 Attachment
                On Thu, 2005-08-25 at 01:16 -0700, Arik Baratz wrote:
                > On 25/08/05, Omer Zak <omerz@...> wrote:
                >
                > > > There are other ways to DFS without recursion, a notable one is to
                > > > hold a linked list of pointers to the nodes above the current one,
                > > > starting with the lowest, building it as you go by always adding to
                > > > the head, and when you exhaust a node you simply remove the last link
                > > > in the list. This is in fact uses the linked list as a stack.
                > >
                > > In my book, this is recursion using a different name.
                >
                > No. Recursion is when you use recursion. :-)
                >
                > Recursion is when you use the language's stack to hold data for you.
                > Using a user data structure does not constitute (at least in my mind)
                > a recursive algorithm. It's an iterative algorithm utilizing a stack.

                Continuing the argument by shouting match:
                NO! NO!! NO!!!
                This is recursion because I am shouting louder than you!!!!
                :-) :-) :-) :-) :-)

                > > When you have 2^10 processes running simultaneously, and each one of
                > > them needs to traverse the tree, then my algorithm requires exactly two
                > > storage cells per process (one for pointer, one for Boolean flag). The
                > > various links, being read-only, are shared between all processes.
                >
                > Then I'll ask another question, if I may: If all those m processes
                > need access to the same data in the same order, won't it be easier to
                > unroll the tree into a linear structure, which also requires O(n)
                > space, such as a linked list, and then traverse it with the processes
                > instead of re-traverse the binary tree again and again? Just a
                > thought.

                When the tree is really immutable or is modified only rarely, your
                suggestion is indeed easier.

                However, what happens if some (or all) of the assumptions are incorrect:

                - Processes need to access the tree in different orders (prefix vs.
                postfix traversal, for example)?
                - Processes need to skip different parts of the tree while traversing
                it.
                - The tree is dynamically modified by another process (stipulating that
                there are locking mechanisms such that processes in middle of tree
                traversal are not confused by the change) and it is expensive to unroll
                the tree after each modification.

                In short: the tradeoffs of the algorithm, which I suggested, are such
                that is useful under certain circumstances, which are probably rare in
                practice.
                My real question - was this algorithm, or a similar algorithm, already
                proposed by someone else?
                --- Omer
                --
                Every good master plan involves building a time machine. Moshe Zadka
                My own blog is at http://www.livejournal.com/users/tddpirate/

                My opinions, as expressed in this E-mail message, are mine alone.
                They do not represent the official policy of any organization with which
                I may be affiliated in any way.
                WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
              • Arik Baratz
                ... Hm.. I just came back from my thinking place, and it seems to me like Guy may be right after all. Your NextSibling() node method needs to know what you
                Message 7 of 12 , Aug 25 1:51 AM
                • 0 Attachment
                  On 25/08/05, Omer Zak <omerz@...> wrote:
                  > - Processes need to access the tree in different orders (prefix vs.
                  > postfix traversal, for example)?
                  > - Processes need to skip different parts of the tree while traversing
                  > it.
                  > - The tree is dynamically modified by another process (stipulating that
                  > there are locking mechanisms such that processes in middle of tree
                  > traversal are not confused by the change) and it is expensive to unroll
                  > the tree after each modification.

                  Hm.. I just came back from my thinking place, and it seems to me like
                  Guy may be right after all. Your NextSibling() node method needs to
                  know what you mean by 'next', so it has to somehow remember where in
                  relation to other siblings you are now. It has to go to the parent,
                  and look for the 'next' sibling. You need to keep information
                  regarding which is the next sibling somewhere, and that somewhere is
                  different for each process...

                  > My real question - was this algorithm, or a similar algorithm, already
                  > proposed by someone else?

                  If I were you I'd open a good old algorithms reference and look for
                  graph traversal algorithms, you might come across something familiar.

                  -- Arik
                • guy keren
                  ... ofcourse i was right. omer had tried to show that some basic issues of computation theory are wrong, or some very hard problems are actually easy to solve.
                  Message 8 of 12 , Aug 25 6:33 AM
                  • 0 Attachment
                    On Thu, 25 Aug 2005, Arik Baratz wrote:

                    > On 25/08/05, Omer Zak <omerz@...> wrote:
                    > > - Processes need to access the tree in different orders (prefix vs.
                    > > postfix traversal, for example)?
                    > > - Processes need to skip different parts of the tree while traversing
                    > > it.
                    > > - The tree is dynamically modified by another process (stipulating that
                    > > there are locking mechanisms such that processes in middle of tree
                    > > traversal are not confused by the change) and it is expensive to unroll
                    > > the tree after each modification.
                    >
                    > Hm.. I just came back from my thinking place, and it seems to me like
                    > Guy may be right after all. Your NextSibling() node method needs to
                    > know what you mean by 'next', so it has to somehow remember where in
                    > relation to other siblings you are now. It has to go to the parent,
                    > and look for the 'next' sibling. You need to keep information
                    > regarding which is the next sibling somewhere, and that somewhere is
                    > different for each process...

                    ofcourse i was right. omer had tried to show that some basic issues of
                    computation theory are wrong, or some very hard problems are actually
                    easy to solve. what are the chances of him being right about this?

                    you cannot traverse a tree using an O(1) ammount of extra memory - i think
                    if omer looks properly, he'll find proofs for this theorem.

                    as i said, omer's in a very strange mood today - it's not like him to come
                    up with so many fataly flawed ideas. could it be that someone took over
                    omer's email account and is trying to ruin his reputation? :0

                    --
                    guy

                    "For world domination - press 1,
                    or dial 0, and please hold, for the creator." -- nob o. dy
                  • Omer Zak
                    ... If the tree nodes have links to their siblings and parents, and if the memory occupied by the links is not counted as extra memory (reasonable when the
                    Message 9 of 12 , Aug 25 3:11 PM
                    • 0 Attachment
                      On Thu, 2005-08-25 at 16:33 +0300, guy keren wrote:
                      > On Thu, 25 Aug 2005, Arik Baratz wrote:
                      >
                      > > On 25/08/05, Omer Zak <omerz@...> wrote:
                      > > > - Processes need to access the tree in different orders (prefix vs.
                      > > > postfix traversal, for example)?
                      > > > - Processes need to skip different parts of the tree while traversing
                      > > > it.
                      > > > - The tree is dynamically modified by another process (stipulating that
                      > > > there are locking mechanisms such that processes in middle of tree
                      > > > traversal are not confused by the change) and it is expensive to unroll
                      > > > the tree after each modification.
                      > >
                      > > Hm.. I just came back from my thinking place, and it seems to me like
                      > > Guy may be right after all. Your NextSibling() node method needs to
                      > > know what you mean by 'next', so it has to somehow remember where in
                      > > relation to other siblings you are now. It has to go to the parent,
                      > > and look for the 'next' sibling. You need to keep information
                      > > regarding which is the next sibling somewhere, and that somewhere is
                      > > different for each process...
                      >
                      > ofcourse i was right. omer had tried to show that some basic issues of
                      > computation theory are wrong, or some very hard problems are actually
                      > easy to solve. what are the chances of him being right about this?
                      >
                      > you cannot traverse a tree using an O(1) ammount of extra memory - i think
                      > if omer looks properly, he'll find proofs for this theorem.

                      If the tree nodes have links to their siblings and parents, and if the
                      memory occupied by the links is not counted as extra memory (reasonable
                      when the trees are read-only accessed by several processes, each of
                      which needs to maintain its own traversal state) - then you can consider
                      the tree as a maze (each vertex is a corridor and each node is a meeting
                      place of few corridors). You then follow the maze using the right hand
                      law. When using the right hand law, you do not need more than O(1)
                      read-write memory.

                      Of course, when only a single process needs to traverse the tree at the
                      same time, it is more economical to maintain the O(log N) read-write
                      memory than to spend space on redundant links in the tree.

                      > as i said, omer's in a very strange mood today - it's not like him to come
                      > up with so many fataly flawed ideas. could it be that someone took over
                      > omer's email account and is trying to ruin his reputation? :0

                      Thanks for the belated compliment on my past ideas.
                      If you feel bored by my flawed but nevertheless interesting (at least to
                      my ego) ideas, which were publicized in an attempt to wake up the
                      Hackers-IL mailing list, can you post your own speculative (translation:
                      flawed) but interesting ideas?
                      --- Omer
                      --
                      Jara Cimrman! He is one of the unsung geniuses--scientist, engineer,
                      inventor and literary critic.
                      My own blog is at http://www.livejournal.com/users/tddpirate/

                      My opinions, as expressed in this E-mail message, are mine alone.
                      They do not represent the official policy of any organization with which
                      I may be affiliated in any way.
                      WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
                    • Omer Zak
                      [... snipped ...] If the tree nodes have links to their siblings and parents, and if the memory occupied by the links is not counted as extra memory
                      Message 10 of 12 , Aug 25 3:14 PM
                      • 0 Attachment
                        [... snipped ...]
                        If the tree nodes have links to their siblings and parents, and if the
                        memory occupied by the links is not counted as extra memory (reasonable
                        when the trees are read-only accessed by several processes, each of
                        which needs to maintain its own traversal state) - then you can consider
                        the tree as a maze (each vertex is a corridor and each node is a meeting
                        ^^^^^^ should be "edge"
                        place of few corridors). You then follow the maze using the right hand
                        law. When using the right hand law, you do not need more than O(1)
                        read-write memory.

                        Of course, when only a single process needs to traverse the tree at the
                        same time, it is more economical to maintain the O(log N) read-write
                        memory than to spend space on redundant links in the tree.
                        [... snipped ...]
                        --- Omer
                        --
                        Jara Cimrman! He is one of the unsung geniuses--scientist, engineer,
                        inventor and literary critic.
                        My own blog is at http://www.livejournal.com/users/tddpirate/

                        My opinions, as expressed in this E-mail message, are mine alone.
                        They do not represent the official policy of any organization with which
                        I may be affiliated in any way.
                        WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
                      • guy keren
                        ... aha, but you are forgetting that you do not have an upper-bound on the number of children for a given node. consider this: [ P ] [C1] [C2] [C3] [C4]
                        Message 11 of 12 , Aug 25 4:13 PM
                        • 0 Attachment
                          On Fri, 26 Aug 2005, Omer Zak wrote:

                          > If the tree nodes have links to their siblings and parents, and if the
                          > memory occupied by the links is not counted as extra memory (reasonable
                          > when the trees are read-only accessed by several processes, each of
                          > which needs to maintain its own traversal state) - then you can consider
                          > the tree as a maze (each vertex is a corridor and each node is a meeting
                          > place of few corridors).You then follow the maze using the right hand
                          > law.When using the right hand law, you do not need more than O(1)
                          > read-write memory.

                          aha, but you are forgetting that you do not have an upper-bound on the
                          number of children for a given node. consider this:


                          [ P ]


                          [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]


                          lets say we were in C2, and are now returning to P. we now need to find
                          which is the next node we should visit. the only way to make this in O(1),
                          is that each node will keep a link to its sibling. add these links too,
                          then. (if this operation is not O(1), it makes your scanning algorithm
                          less efficient then O(N)).

                          if you'll want to scan the tree in reverse order, you'll need the siblings
                          list to be bidirectional.

                          if you'll want to make a BFS scan, rather then DFS.....

                          so, you see, you're creating a tree that lends itself to one manner of
                          traversal, and does not work for other types of traversals.

                          this could be useful for specific types of problems, ofcourse, but this is
                          not the generic issue of traversing a tree structure.

                          > Of course, when only a single process needs to traverse the tree at the
                          > same time, it is more economical to maintain the O(log N) read-write
                          > memory than to spend space on redundant links in the tree.

                          log N is relevant assuming a balanced tree. in fact, it's not log N, but
                          log (largest number of children of a single parent).

                          > > as i said, omer's in a very strange mood today - it's not like him to come
                          > > up with so many fataly flawed ideas. could it be that someone took over
                          > > omer's email account and is trying to ruin his reputation? :0
                          >
                          > Thanks for the belated compliment on my past ideas.
                          > If you feel bored by my flawed but nevertheless interesting (at least to
                          > my ego) ideas, which were publicized in an attempt to wake up the
                          > Hackers-IL mailing list, can you post your own speculative (translation:
                          > flawed) but interesting ideas?

                          if you can't bring up something useful - it's better to keep the list
                          quiet. would you like me to bring up my mission-imposible project of
                          devising an algorithm that automatically translates C programs into C++
                          programs while introducing classes based on usage relations between data
                          and functions in the original C program?

                          --
                          guy

                          "For world domination - press 1,
                          or dial 0, and please hold, for the creator." -- nob o. dy
                        • Omer Zak
                          ... How about that what-is-its-name transformation, which establishes an equivalence relationship between general and binary trees? Then you need to deal only
                          Message 12 of 12 , Aug 25 5:02 PM
                          • 0 Attachment
                            On Fri, 2005-08-26 at 02:13 +0300, guy keren wrote:

                            > aha, but you are forgetting that you do not have an upper-bound on the
                            > number of children for a given node. consider this:
                            >
                            >
                            > [ P ]
                            >
                            >
                            > [C1] [C2] [C3] [C4] [C5] [C6] [C7] [C8] [C9] [C10] [C11]
                            >
                            >
                            > lets say we were in C2, and are now returning to P. we now need to find
                            > which is the next node we should visit. the only way to make this in O(1),
                            > is that each node will keep a link to its sibling. add these links too,
                            > then. (if this operation is not O(1), it makes your scanning algorithm
                            > less efficient then O(N)).

                            How about that what-is-its-name transformation, which establishes an
                            equivalence relationship between general and binary trees?

                            Then you need to deal only with two children per node.

                            > if you'll want to scan the tree in reverse order, you'll need the siblings
                            > list to be bidirectional.
                            >
                            > if you'll want to make a BFS scan, rather then DFS.....
                            >
                            > so, you see, you're creating a tree that lends itself to one manner of
                            > traversal, and does not work for other types of traversals.
                            >
                            > this could be useful for specific types of problems, ofcourse, but this is
                            > not the generic issue of traversing a tree structure.

                            OK, I give up.
                            I propose a bicycle as a transportation vehicle, pointing out that it is
                            the best solution for some specialized transportation situations.
                            You reply by reminding us that most of the transportation needs of
                            humans are better served by cars and airplanes.

                            > if you can't bring up something useful - it's better to keep the list
                            > quiet. would you like me to bring up my mission-imposible project of
                            > devising an algorithm that automatically translates C programs into C++
                            > programs while introducing classes based on usage relations between data
                            > and functions in the original C program?

                            Sounds cool and interesting. Can you tell us more about it?
                            How do you avoid the trivial solution of enclosing function declarations
                            by extern "C" { ... } declarations?
                            --- Omer
                            --
                            Every good master plan involves building a time machine. Moshe Zadka
                            My own blog is at http://www.livejournal.com/users/tddpirate/

                            My opinions, as expressed in this E-mail message, are mine alone.
                            They do not represent the official policy of any organization with which
                            I may be affiliated in any way.
                            WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
                          Your message has been successfully submitted and would be delivered to recipients shortly.