• Paul Findlay <r.lph50+d gmail.com> Jun 29 2006
• "Ben Hinkle" <bhinkle mathworks.com> Jul 05 2006

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..

"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