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

Searching a BINARY_SEARCH_TREE

Expand Messages
  • brucemount
    ...sigh...I m sure this is easy, but Ive spent a lot of time on this and I have not figured it out yet. How do you search in a BINARY_SEARCH_TREE? I know that
    Message 1 of 8 , Sep 24, 2007
      ...sigh...I'm sure this is easy, but Ive spent a lot of time on this
      and I have not figured it out yet. How do you search in a
      BINARY_SEARCH_TREE?

      I know that for HASH_TABLE you can do a a_hash_table.search and then
      refer to a_hash_table.found_item to use the item found by the search.
      I'm trying to do the same thing with a BINARY_SEARCH_TREE. I have
      the code fragment of...

      bin_tree : BINARY_SEARCH_TREE[FOO]

      if (bin_tree.has(a_foo)) then
      -- HOW THE HECK DO I REFER TO THE "found" ITEM?
      repair_groups.item.add_repair(a_repair)
      else
      bin_tree.extend(a_foo)
      end


      Where FOO has < defined as a simple string compare of a field inside FOO.

      From what I can tell 'has' does not position the cursor of the
      BINARY_SEARCH_TREE such that 'item' is the found object. Can someone
      please tell me how to do this?

      [RANT: by the way, why don't the comments in the BINARY_SEARCH_TREE
      class tell me how to do this?????]

      Thanks in advance,

      --Bruce
      (feeling dumb, but it's after midnight so it's time to ask someone
      else who will probably tell me what I'm doing wrong in 30 seconds.)
    • brucemount
      Hmmm, nearly 24 hours since I posted this and not a single response. I guess I should change my questions to: does anyone use BINARY_SEARCH_TREE at all?
      Message 2 of 8 , Sep 25, 2007
        Hmmm, nearly 24 hours since I posted this and not a single response.
        I guess I should change my questions to: does anyone use
        BINARY_SEARCH_TREE at all?

        --Bruce
        ============================
        --- In eiffel_software@yahoogroups.com, "brucemount" wrote:
        > ...sigh...I'm sure this is easy, but Ive spent a lot of time on this
        > and I have not figured it out yet. How do you search in a
        > BINARY_SEARCH_TREE?

        > I know that for HASH_TABLE you can do a a_hash_table.search and then
        > refer to a_hash_table.found_item to use the item found by the search.
        > I'm trying to do the same thing with a BINARY_SEARCH_TREE. I have
        > the code fragment of...
        >
        > bin_tree : BINARY_SEARCH_TREE[FOO]
        >
        > if (bin_tree.has(a_foo)) then
        > -- HOW THE HECK DO I REFER TO THE "found" ITEM?
        > repair_groups.item.add_repair(a_repair)
        > else
        > bin_tree.extend(a_foo)
        > end
        >
        >
        > Where FOO has < defined as a simple string compare of a field inside
        FOO.
        >
        > From what I can tell 'has' does not position the cursor of the
        > BINARY_SEARCH_TREE such that 'item' is the found object. Can someone
        > please tell me how to do this?
        >
        > [RANT: by the way, why don't the comments in the BINARY_SEARCH_TREE
        > class tell me how to do this?????]
        >
        > Thanks in advance,
        >
        > --Bruce
        > (feeling dumb, but it's after midnight so it's time to ask someone
        > else who will probably tell me what I'm doing wrong in 30 seconds.)
        >
      • Peter Gummer
        ... I don t, but I ll be really interested to read the answer when it comes; it might encourage me to use it. Once you ve figured it out, maybe you could blog
        Message 3 of 8 , Sep 25, 2007
          brucemount wrote:

          > Hmmm, nearly 24 hours since I posted this and not a single response.
          > I guess I should change my questions to: does anyone use
          > BINARY_SEARCH_TREE at all?

          I don't, but I'll be really interested to read the answer when it comes; it
          might encourage me to use it. Once you've figured it out, maybe you could
          blog about it on eiffelroom :-)

          - Peter Gummer
        • Emmanuel Stapf [ES]
          ... There is no query to give you the item you looked for. For the moment, you may need to extend BINARY_SEARCH_TREE to add this feature. Regards, Manu
          Message 4 of 8 , Sep 26, 2007
            > From what I can tell 'has' does not position the cursor of
            > the BINARY_SEARCH_TREE such that 'item' is the found object.
            > Can someone please tell me how to do this?

            There is no query to give you the item you looked for. For the moment, you
            may need to extend BINARY_SEARCH_TREE to add this feature.

            Regards,
            Manu
          • brucemount
            [Manu said] ... Uhhh, say what? Oh, I get it....it s a SEARCH-only tree. Not a search-and-use-what-you-find tree. I mean, like, ya know, who would want to do
            Message 5 of 8 , Sep 26, 2007
              [Manu said]
              >There is no query to give you the item you looked for.
              >For the moment, you may need to extend BINARY_SEARCH_TREE
              >to add this feature.

              Uhhh, say what?

              Oh, I get it....it's a SEARCH-only tree. Not a
              search-and-use-what-you-find tree. I mean, like, ya know, who would
              want to do that? :-)

              I guess on the plus side, I don't feel quite as stupid for not being
              able to figure it out.

              Seriously, Manu, thanks for the response. It's not the response I
              expected (or even conceived of), but it's very useful to know I should
              stop looking and either use a different class or extend this one.

              Thanks,

              --Bruce
            • holworth
              ... When I used to write C I wrote a multi-dimensional sparse matrix using trees of trees ... and it worked (and still does) very well. Recently I wanted to
              Message 6 of 8 , Sep 27, 2007
                --- In eiffel_software@yahoogroups.com, "brucemount" <brucemount@...>
                wrote:
                > Seriously, Manu, thanks for the response. It's not the response I
                > expected (or even conceived of), but it's very useful to know I should
                > stop looking and either use a different class or extend this one.

                When I used to write C I wrote a multi-dimensional sparse matrix using
                trees of trees ... and it worked (and still does) very well.

                Recently I wanted to obtain the same functionality in Eiffel so I too
                tried BINARY_TREEs - and got nowhere.

                So I thought it all out again and did it using SORTED_TWO_WAY_LISTs of
                SORTED_TWO_WAY_LISTs ... and that worked.

                But I's still like to understand how I should be using BINARY_TREES.
                Perhaps it's time to read the book again.
              • Manvinder Singh
                ... using ... too ... of ... I havn t used sparse matrix since long but thinking from top of my head this could be another solution:- HASH_TABLE [HASH_TABLE
                Message 7 of 8 , Sep 27, 2007
                  "holworth" wrote:

                  > When I used to write C I wrote a multi-dimensional sparse matrix
                  using
                  > trees of trees ... and it worked (and still does) very well.
                  >
                  > Recently I wanted to obtain the same functionality in Eiffel so I
                  too
                  > tried BINARY_TREEs - and got nowhere.
                  >
                  > So I thought it all out again and did it using SORTED_TWO_WAY_LISTs
                  of
                  > SORTED_TWO_WAY_LISTs ... and that worked.

                  I havn't used sparse matrix since long but thinking from top of my
                  head this could be another solution:-
                  HASH_TABLE [HASH_TABLE [MY_OBJECT, INTEGER], INTEGER]

                  ..which would facilitate quick lookup of queries like
                  sparse_matrix.search (x, y)
                  Of course, it would work only for 2-dim matrices.

                  > But I's still like to understand how I should be using
                  BINARY_TREES.

                  I did use Binary-tree once. This is how I extended it :-

                  class
                  MY_BINARY_SEARCH_TREE [G -> COMPARABLE]

                  inherit
                  BINARY_SEARCH_TREE [G]
                  redefine
                  parent
                  end

                  create
                  make

                  feature -- Access

                  parent: MY_BINARY_SEARCH_TREE [G]
                  -- Parent of current node

                  tree_item (v: like item): like Current is
                  --
                  do
                  if item.is_equal (v) then
                  Result := Current
                  else
                  if v < item then
                  if left_child /= Void then
                  Result := left_child.tree_item (v)
                  end
                  else
                  if right_child /= Void then
                  Result := right_child.tree_item
                  (v)
                  end
                  end
                  end
                  end

                  end -- class MY_BINARY_SEARCH_TREE

                  hope that helps,
                  --Manvinder Singh
                • Emmanuel Stapf [ES]
                  Just taking the opportunity to remind everyone that we are open source and that EiffelBase is now based on FreeELKS yet another open source project. The
                  Message 8 of 8 , Sep 28, 2007
                    Just taking the opportunity to remind everyone that we are open source and
                    that EiffelBase is now based on FreeELKS yet another open source project.
                    The FreeELKS development page is at http://sourceforge.net/projects/freeelks
                    and we will welcome additions/suggestions/corrections.

                    Regards,
                    Manu

                    > -----Original Message-----
                    > From: eiffel_software@yahoogroups.com
                    > [mailto:eiffel_software@yahoogroups.com] On Behalf Of Manvinder Singh
                    > Sent: Thursday, September 27, 2007 3:59 AM
                    > To: eiffel_software@yahoogroups.com
                    > Subject: [eiffel_software] Re: Searching a BINARY_SEARCH_TREE
                    >
                    > "holworth" wrote:
                    >
                    > > When I used to write C I wrote a multi-dimensional sparse matrix
                    > using
                    > > trees of trees ... and it worked (and still does) very well.
                    > >
                    > > Recently I wanted to obtain the same functionality in Eiffel so I
                    > too
                    > > tried BINARY_TREEs - and got nowhere.
                    > >
                    > > So I thought it all out again and did it using SORTED_TWO_WAY_LISTs
                    > of
                    > > SORTED_TWO_WAY_LISTs ... and that worked.
                    >
                    > I havn't used sparse matrix since long but thinking from top
                    > of my head this could be another solution:- HASH_TABLE
                    > [HASH_TABLE [MY_OBJECT, INTEGER], INTEGER]
                    >
                    > ..which would facilitate quick lookup of queries like
                    > sparse_matrix.search (x, y) Of course, it would work only for
                    > 2-dim matrices.
                    >
                    > > But I's still like to understand how I should be using
                    > BINARY_TREES.
                    >
                    > I did use Binary-tree once. This is how I extended it :-
                    >
                    > class
                    > MY_BINARY_SEARCH_TREE [G -> COMPARABLE]
                    >
                    > inherit
                    > BINARY_SEARCH_TREE [G]
                    > redefine
                    > parent
                    > end
                    >
                    > create
                    > make
                    >
                    > feature -- Access
                    >
                    > parent: MY_BINARY_SEARCH_TREE [G]
                    > -- Parent of current node
                    >
                    > tree_item (v: like item): like Current is
                    > --
                    > do
                    > if item.is_equal (v) then
                    > Result := Current
                    > else
                    > if v < item then
                    > if left_child /= Void then
                    > Result :=
                    > left_child.tree_item (v)
                    > end
                    > else
                    > if right_child /= Void then
                    > Result :=
                    > right_child.tree_item
                    > (v)
                    > end
                    > end
                    > end
                    > end
                    >
                    > end -- class MY_BINARY_SEARCH_TREE
                    >
                    > hope that helps,
                    > --Manvinder Singh
                    >
                    >
                    >
                    >
                    >
                    > Yahoo! Groups Links
                    >
                    >
                    >
                    >
                  Your message has been successfully submitted and would be delivered to recipients shortly.