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

[Fabian Buske <f.buske@uq.edu.au>]

Doh! Thanks for the heads up, Knut.

The VectorSet version still won't compile though even when the output 
via the iterator is removed from the test. Would be nice to get that one 
working just as well.

Best,
Fabian


On 23/11/10 7:06 PM, Reinert, Knut wrote:
> 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


--
Fabian Buske
Institute for Molecular Bioscience
The University of Queensland
Brisbane, Qld. 4072 Australia
Phone: (61)-(7)-334-62608