[comp.lang.eiffel] Error in library class TWO_WAY_TREE

jos@cs.vu.nl (11/10/89)

Version: ISE Eiffel, version 2.2, level A, SUN4/sparc

The library class TWO_WAY_TREE contains an erorror in the function
`search_child'.  As it is, the cursor will never be altered and
the routine is actually a NO-OP.
This becomes clear when reading the code.

The routine will work correctly when the calls to `child_mark'
and `child_return' are removed.
This is the library version of `search_child', with the lines to
be removed flagged:

    search_child (sought: like parent; i: INTEGER) is
	-- Move cursor under `i'-th occurence of `sought' if
	-- exists among children; go child_offright if none.
    require
	arguments_not_void: not sought.Void
    local
	j: INTEGER
    do
	child_mark;                      -- remove this line
	from
	    go_offleft
	invariant
	    child_position >= 0
	variant
	    arity - child_position
	until
	    child_offright or else (j = i)
	loop
	    child_forth;
	    if (sought = child) then
		j := j + 1
	    end -- if
	end;
	child_return                      -- remove this line
    end; -- search_child


========================================================================
If the above is still not clear, here is an example of a class
using `search_child', with its output:

class TREE_ERROR export

feature
    t : TWO_WAY_TREE[STRING];
    s1, s2, s3 : STRING;
    ch : TWO_WAY_TREE[STRING];

    Create is
    do
	s1.Create(10);
	s2.Create(10);
	s3.Create(10);

        s1.append("aap");
        s2.append("noot");
        s3.append("mies");

	t.Create(s1);
	t.child_put_right(s2);
	t.child_start;
	t.child_put_right(s3);

	from  t.child_start;
	      ch := t.child;
	      t.child_back;
	until ch.Void
	loop
	    if t.child_offleft then
		io.putstring("t is offleft"); io.new_line;
	    end;
	    io.putstring("search child: "); io.putstring( ch.item ); io.new_line;
	    -- `ch' is a child of `t', so it should be found.
	    t.search_child(ch, 1);
	    if t.child_offleft then
		io.putstring("Error: child of `t' not found"); io.new_line;
	    else
		io.putstring("Ok   : child of `t' found"); io.new_line;
	    end;
	    ch := ch.right_sibling;
	end;
    end;

end;
======== output ============
t is offleft
search child: noot
Error: child of `t' not found
t is offleft
search child: mies
Error: child of `t' not found
============================