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

Fabian Buske <f.buske@uq.edu.au> · Wed, 24 Nov 2010 07:47:31 +1000

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