www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.dtl - MinTL, SortedSet and searching

reply Paul Findlay <r.lph50+d gmail.com> writes:
Hello,

I'm new to programming and to D.

I 'inherited' some C code (a small library I want to port to D) that 
used an array to store in sorted order pointers to structs. I thought it 
would be nice fit for the MinTL SortedSet. But how does one go about 
doing a (<= O(n)) search on a MinTL SortedSet that returns a value? The 
value I would search using is a struct with only some of its members 
set. The opCmp on the struct allows for this. I'm using SortedSet.values 
but I'm balking at it..

Perhaps I should just keep using an array of pointers with reallocations 
and binary search. Or is there room in the MinTL for something else? Or 
am I missing something?

- Paul Findlay
P.S. I'm sorry if this is the wrong newsgroup..
Jun 29 2006
parent "Ben Hinkle" <bhinkle mathworks.com> writes:
"Paul Findlay" <r.lph50+d gmail.com> wrote in message 
news:e80htr$2jtd$1 digitaldaemon.com...
 Hello,

 I'm new to programming and to D.

 I 'inherited' some C code (a small library I want to port to D) that used 
 an array to store in sorted order pointers to structs. I thought it would 
 be nice fit for the MinTL SortedSet. But how does one go about doing a (<= 
 O(n)) search on a MinTL SortedSet that returns a value? The value I would 
 search using is a struct with only some of its members set. The opCmp on 
 the struct allows for this. I'm using SortedSet.values but I'm balking at 
 it..

 Perhaps I should just keep using an array of pointers with reallocations 
 and binary search. Or is there room in the MinTL for something else? Or am 
 I missing something?

 - Paul Findlay
 P.S. I'm sorry if this is the wrong newsgroup..

I'm not sure what the problem is but here's an exmaple usage from the unittests: // test SortedSet SortedSet!(char[]) s2; s2.add("hello","world"); assert( s2["world"] ); assert( s2["hello"] ); assert( !s2["worldfoo"] ); foreach(char[] val ; s2) { printf("%.*s\n",val); } assert( !s2.isEmpty ); Lookups should be O(log(n)). If you never need to traverse the set in order you could also use a HashAA instead of a SortedAA and get O(1) lookups. -Ben
Jul 05 2006