Re: [Seqan-dev] Skiplist does not find existing key

["Reinert, Knut" <Knut.Reinert@fu-berlin.de>]

Dear Fabian,

The skip lists are OK.
Your operator< is wrong. For (4,3,2) < (2,4,4) it yields true, which is
not what you intend.

Here is the fixed version with which your test works.


template <typename TKey>
bool TestKey<TKey>::operator<(const TestKey<TKey> & b) const {
    if (value1 < b.value1) return true;
 if (value1 > b.value1) return false;
    if (value2 < b.value2) return true;
    if (value2 > b.value2) return false; 
    if (value3 < b.value3) return true;
 if (value3 > b.value3) return false; 
    return false;
}


Cheers,

Knut




Am 11/23/10 8:46 AM schrieb "Reinert, Knut" unter
<Knut.Reinert@fu-berlin.de>:

>Hm
>So beim direkten compilieren gibt es Fehler (s.u.)
>
>Compiliert das test file mit dem SVN head bei Dir?
>
>
>
>Building CXX object
>tests/CMakeFiles/test_map.dir/Users/reinert/seqan/projects/tests/map/test_
>m
>ap.cpp.o
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h: In function
>Œvoid Test_Map_Complex_Key() [with TMap = seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >]¹:
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:502:
>instantiated from here
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:470: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue3¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:470: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue2¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:470: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue1¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:502:
>instantiated from here
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:471: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue3¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:471: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue2¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:471: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue1¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:472: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue3¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:472: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue2¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:472: error:
>Œstruct 
>seqan::Proxy<seqan::IteratorProxy<seqan::Iter<seqan::Map<TestKey<long long
>int>, seqan::VectorSet<seqan::Alloc<void> > >, seqan::VectorSetIterator> >
>>¹ has no member named Œvalue1¹
>/Users/reinert/seqan/projects/library/seqan/basic/basic_alphabet_interface
>.
>h: At global scope:
>/Users/reinert/seqan/projects/library/seqan/basic/basic_alphabet_interface
>.
>h: In instantiation of Œseqan::ValueSize<TestKey<long long int> >¹:
>/Users/reinert/seqan/projects/library/seqan/map/map_vector.h:103:
>instantiated from Œseqan::Map<TElement, seqan::VectorSet<TSpec> >::Map()
>[with TValue = TestKey<long long int>, TSpec = seqan::Alloc<void>]¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:452:
>instantiated from Œvoid Test_Map_Complex_Key() [with TMap =
>seqan::Map<TestKey<long long int>, seqan::VectorSet<seqan::Alloc<void> >
>>]¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:502:
>instantiated from here
>/Users/reinert/seqan/projects/library/seqan/basic/basic_alphabet_interface
>.
>h:963: warning: left shift count >= width of type
>/Users/reinert/seqan/projects/library/seqan/sequence/lexical.h: In
>function Œunsigned int seqan::ordValue(const TValue&) [with TValue =
>TestKey<long long int>]¹:
>/Users/reinert/seqan/projects/library/seqan/map/map_vector.h:328:
>instantiated from Œtypename seqan::Iterator<seqan::Map<TKey2,
>seqan::VectorSet<TSpec> >, typename
>seqan::DefaultIteratorSpec<seqan::Map<TKey2, seqan::VectorSet<TSpec> >
>>::Type>::Type seqan::find(seqan::Map<TKey2, seqan::VectorSet<TSpec> >&,
>>const TKey&) [with TKey = TestKey<long long int>, TKey2 = TestKey<long
>>long int>, TSpec = seqan::Alloc<void>]¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:464:
>instantiated from Œvoid Test_Map_Complex_Key() [with TMap =
>seqan::Map<TestKey<long long int>, seqan::VectorSet<seqan::Alloc<void> >
>>]¹
>/Users/reinert/seqan/projects/tests/map/test_map_extended.h:502:
>instantiated from here
>/Users/reinert/seqan/projects/library/seqan/sequence/lexical.h:787: error:
>cannot convert Œconst TestKey<long long int>¹ to Œunsigned int¹ in return
>make[3]: *** 
>[tests/CMakeFiles/test_map.dir/Users/reinert/seqan/projects/tests/map/test
>_
>map.cpp.o] Error 1
>make[2]: *** [tests/CMakeFiles/test_map.dir/all] Error 2
>make[1]: *** [tests/CMakeFiles/test_map.dir/rule] Error 2
>
>
>
>Am 11/23/10 4:43 AM schrieb "Fabian Buske" unter <f.buske@uq.edu.au>:
>
>>Hi,
>>
>>I observed a rather peculiar phenomenon for the Skiplist map
>>specialisation, a data type I use quite extensively.
>>
>>Using a custom key class and comparator the skiplist sometimes does not
>>find a key that has been inserted into the map. Since the skiplist is a
>>randomised data structure this behaviour occurs by chance.
>>
>>When using the iterator to go through the Skiplist the element will
>>actually be output. I observed that the order of the objects (keys) in
>>the output is not the ordered lists of keys according to the comparator
>>(which I was expecting) but to the order in which the keys where
>>inserted into the map. I'm not sure if this is intended.
>>
>>I created a ticket for this phenomenon, which has an extended test_map
>>class attached demonstrating this behaviour:
>>http://trac.mi.fu-berlin.de/seqan/ticket/589
>>
>>This phenomenon may have serious consequences on any application relying
>>on Skiplists.
>>
>>Best,
>>Fabian
>>
>>-- 
>>
>>Fabian Buske
>>Institute for Molecular Bioscience
>>The University of Queensland
>>Brisbane, Qld. 4072 Australia
>>Phone: (61)-(7)-334-62608
>>
>>
>>_______________________________________________
>>seqan-dev mailing list
>>seqan-dev@lists.fu-berlin.de
>>https://lists.fu-berlin.de/listinfo/seqan-dev

Attachment: smime.p7s
Description: S/MIME cryptographic signature