[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...