python-markdown-discuss

[Python-markdown-discuss] Bug in Treap??

[Waylan L. <wa...@gm...>]

I think I found a bug in Treap when using the "<key" syntax but I'm
not sure. My understanding is that a node assigned such a priority
would be inserted *before* the "key" node. However it never is. In
fact, the last test in treap_test.py displays this same behavior. I
was confused at first thinking the test was right, but it is obviously
wrong.

    print ".. Change priority test."
    r.link('seventh', '<third')
    test('.... vals', r.heapsorted() == ['This', 'a', 'self', 'CRAZY', 'test'])
    test('.... keys', r.heapsorted(keys=1) == ['first', 'third',
'fourth','seventh', 'fifth'])
    test('.... items', r.heapsorted(items=1) == [('first', 'This'),
('third', 'a'), ('fourth', 'self'), ('seventh','CRAZY'), ('fifth',
'test')])

If "seventh" is linked *before* "third", then the keys should be
['first', 'seventh 'third', 'fourth', 'fifth'].

I think there may be a clue in ``r._tree`` (I added
``pprint(r._etree)`` to the end of treap_test.py:

    {'_begin': {'heap': ('_begin', 'B'), 'kids': {'first': '='}, 'prio': 'B'},
     '_end': {'heap': ('_end', 'E'), 'kids': {'seventh': '='}, 'prio': 'E'},
     'fifth': {'heap': ('fifth', 'B=>>'), 'kids': {}, 'prio': '>fourth'},
     'first': {'heap': ('first', 'B='),
               'kids': {'fourth': '>', 'third': '>'},
               'prio': '_begin'},
     'fourth': {'heap': ('fourth', 'B=>'),
                'kids': {'fifth': '>'},
                'prio': '>first'},
     'seventh': {'heap': ('seventh', 'B=><'), 'kids': {}, 'prio': '<third'},
     'third': {'heap': ('third', 'B=>'),
               'kids': {'seventh': '<'},
               'prio': '>first'}}

Notice that "seventh" has ``'B=><'`` and 'fifth' has ``'B=>>'``. In
further testing, I've noted this same pattern in each instance I can't
get Treap to sort the way I want.

If I understand things correctly, line 1667 is the problem. It currently is:

    self._tree[parn]['heap'][1]+brace

and should be:

    self._tree[parn]['heap'][1].strip('<>')+brace

The problem is, that takes "second" out of order (in the first test)
which makes me wonder if ``B=>>`` has special meaning. If so, then
line 1667 needs to be more sophisticated and do something different
depending on the value of ``brace``.

Or am I missing something obvious?
-- 
----
Waylan Limberg
wa...@gm...

Re: [Python-markdown-discuss] Bug in Treap??

[Waylan L. <wa...@gm...>]

On Mon, Oct 20, 2008 at 9:53 PM, Waylan Limberg <wa...@gm...> wrote:
[snip]
>
> If I understand things correctly, line 1667 is the problem. It currently is:
>
>    self._tree[parn]['heap'][1]+brace
>
> and should be:
>
>    self._tree[parn]['heap'][1].strip('<>')+brace
>
> The problem is, that takes "second" out of order (in the first test)
> which makes me wonder if ``B=>>`` has special meaning. If so, then
> line 1667 needs to be more sophisticated and do something different
> depending on the value of ``brace``.
>

Now that I've had time to sleep on it, I think that my patch might be
correct. "second" isn't really out of order. Both "second" and "third"
were set to come after "first", but they were never set in relation to
each other so "second" coming after "third" is not wrong, especially
considering that "second" was added later than "third".

If we really want "second" to come before "third", then we should tell
is so with "<third". As "third" is already set to come after "first",
this will force "second" to fall between "first" and "third". That
should provide enough control.

What this essentially means is that when adding items in order (as in
the Markdown class), they should be added using ">the_last_item"
(which is the default when no priority is set on add). However
whenever later inserting nodes, they should be added using
"<some_item" for precision placement.

Is this understanding correct? or am I crazy?

If I'm not crazy (at least with respect to this point), then I'll
commit the patch, update the tests and add a more polished version of
the above explanation to the docs so future users don't get surprised
like I did.


-- 
----
Waylan Limberg
wa...@gm...