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

["Weese, David" <weese@campus.fu-berlin.de>]

Hi Fabian,

VectorSets need a mapping from keys to ordinal numbers (function ordValue) to work. They are designed for small or medium size alphabets and an efficient alternative to binary search based sets. They are not going to work on your key set.

ANFSCD, can you test cmake again on your machine. I hope I fixed the CUDA issue.

Cheers,
David

--
David Weese				weese@inf.fu-berlin.de
Freie Universität Berlin		http://www.inf.fu-berlin.de/
Institut für Informatik			Phone: +49 30 838 75246
Takustraße 9					Algorithmic Bioinformatics
14195 Berlin					Room 021 

Am 23.11.2010 um 22:47 schrieb Fabian Buske:

> 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
> 
> 
> _______________________________________________
> seqan-dev mailing list
> seqan-dev@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/seqan-dev