www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Set class for D

reply Bill Baxter <dnewsgroup billbaxter.com> writes:
There was some discussion a while back about a Set class.
I think Tango has one, but unfortunately I'm not on Tango yet.
Anyone have a link for a Phobos-compatible set class?
I checked dsource and scrapple, and tried searching the NG, but "set" 
gets a lot of bogus hits :-(.

--bb
Apr 25 2007
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.


BTW.  -- the thin wrapper around an AA (a.k.a. bool[T]) implementation 
is ok with me, though one without the bool baggage would naturally be 
better.

--bb
Apr 25 2007
parent Benji Smith <dlanguage benjismith.net> writes:
Bill Baxter wrote:

 Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.


 
 BTW.  -- the thin wrapper around an AA (a.k.a. bool[T]) implementation 
 is ok with me, though one without the bool baggage would naturally be 
 better.
 
 --bb


This is one of those areas where the awkwardness of built-in AA's (as 
opposed to a library implementation) becomes evident. Ideally, calling 
the .keys property of an AA should return a Set, and calling .values 
should return a Bag.

The fact that D essentially has Map and List as built-in types means 
that any collection API will have a lot of weird boundaries and edge-cases.

Inevitably, people will want Map implementations that preserve 
key-ordering and/or value-ordering, using custom comparators. At that 
point, it'll be painful to draw the line between AA's and other Map 
implementations.

The same thing is true for dynamic arrays and other sequentially-ordered 
data structures (queues, linked lists, etc).

Anyhow, to get back to the OP's point, I think the reason why there's no 
good implementation of Set is that D makes it difficult to design a good 
collections API by putting some things into the language (and making 
their implementations opaque) that should have been in libraries.

For example, I have a pretty mature Map, Set, and Bag implementation 

happy to port it to D as well, but I'd want to publish a well-designed 
API for all collections, and it's not obvious to me how that should be 
done in D.

--benji
Apr 26 2007
prev sibling next sibling parent reply torhu <fake address.dude> writes:
Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.
 
 --bb


Maybe you can check out Indigo's Set?  I haven't really looked closely 
at it myself, but it might be an option.  I just uploaded it to dsource 
yesterday.  It's based on Qt 4's QSet, but also mimicks the STL 
container interface.  The license is GPL.

http://indigo.dsource.org/files/tools/set-d.html

http://www.dsource.org/projects/indigo
Apr 25 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
torhu wrote:

 Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.

 --bb


 
 Maybe you can check out Indigo's Set?  I haven't really looked closely 
 at it myself, but it might be an option.  I just uploaded it to dsource 
 yesterday.  It's based on Qt 4's QSet, but also mimicks the STL 
 container interface.  The license is GPL.
 
 http://indigo.dsource.org/files/tools/set-d.html
 
 http://www.dsource.org/projects/indigo


Thanks.  I should have specified that I can't use GPL.

--bb
Apr 25 2007
next sibling parent Justin C Calvarese <technocrat7 gmail.com> writes:
Bill Baxter wrote:

 torhu wrote:

 Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.

 --bb


 Maybe you can check out Indigo's Set?  I haven't really looked closely 
 at it myself, but it might be an option.  I just uploaded it to 
 dsource yesterday.  It's based on Qt 4's QSet, but also mimicks the 
 STL container interface.  The license is GPL.

 http://indigo.dsource.org/files/tools/set-d.html

 http://www.dsource.org/projects/indigo


 
 Thanks.  I should have specified that I can't use GPL.
 
 --bb


Is GPL Lessor a problem, too?

I looked a little deeper into the Set and Range template announced at: 
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=4254

Ddoc documentation:
    http://peylow.no-ip.org/~peylow/set.html
Actual implementation:
    http://peylow.no-ip.org/~peylow/set.d

Since I realized that the links for Set and Range template had gone 
dead, so I've attached the source that I happened to have downloaded 
previously.

-- 
jcc7
Apr 25 2007
prev sibling parent reply torhu <fake address.dude> writes:
Bill Baxter wrote:

 torhu wrote:


<snip>

 Maybe you can check out Indigo's Set?  I haven't really looked closely 
 at it myself, but it might be an option.  I just uploaded it to dsource 
 yesterday.  It's based on Qt 4's QSet, but also mimicks the STL 
 container interface.  The license is GPL.
 
 http://indigo.dsource.org/files/tools/set-d.html
 
 http://www.dsource.org/projects/indigo


 
 Thanks.  I should have specified that I can't use GPL.


The author of Indigo wasn't interested in switching to another license, 
I'm afraid.

There's another set here, no idea how polished it is:

http://pr.stewartsplace.org.uk/d/sutil/
Apr 26 2007
parent reply "Stewart Gordon" <smjg_1998 yahoo.com> writes:
"torhu" <fake address.dude> wrote in message 
news:f0qsei$2a1$1 digitalmars.com...

 Bill Baxter wrote:

 torhu wrote:




<snip>

 http://www.dsource.org/projects/indigo


 Thanks.  I should have specified that I can't use GPL.


 The author of Indigo wasn't interested in switching to another license, 
 I'm afraid.


It was changed to LGPL at some point.  What's the evidence that it was 
changed back?

Stewart.
May 02 2007
parent torhu <fake address.dude> writes:
Stewart Gordon wrote:

 It was changed to LGPL at some point.  What's the evidence that it was 
 changed back?


My mistake, it's indeed LGPL.  It's still pretty restricted, but it 
seems to allow dynamic linking with code under non-compatible licenses, 
at least.

And if I recall correctly, you can link statically, providing you make 
available the object files needed to link the full app.  So you can keep 
the source to yourself, but not your object files.  Sounds odd, I know.
May 02 2007
prev sibling next sibling parent reply Justin C Calvarese <technocrat7 gmail.com> writes:
Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.
 
 --bb



I'm not sure what you're looking for (probably because I'm getting 
sleepy), but I'll offer some suggestions.

Set and Ranges template
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=4254

I found it listed on: http://www.prowiki.org/wiki4d/wiki.cgi?AllLibraries#S


Also, I found these links in my personal bookmarks:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=7399
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=7401

(And you're certainly right. It is tricky searching for "set" since it's 
such a common word.)

-- 
jcc7
Apr 25 2007
parent reply BCS <BCS pathlink.com> writes:
Justin C Calvarese wrote:

 Bill Baxter wrote:
 

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.




[...]

 
 Also, I found these links in my personal bookmarks:
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.anno
nce&article_id=7399 
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.anno
nce&article_id=7401 
 


Thanks :b, I'd forgotten I'd written that, (they are still some of the 
stranger code I worked on).


That aside, I also am looking for a set implementation. I'm going to 
need light weight (struct not class, can't hammer the heap), fast (O[1] 
for most ops), and I'll need add, remove and contains check. really 
void[T] AA's would do everything I need, if the performance is good 
enough. Oh and it must allow closed source use.
Apr 26 2007
parent reply Dan <murpsoft hotmail.com> writes:
BCS Wrote:


 Justin C Calvarese wrote:

 Bill Baxter wrote:
 

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.




 [...]

 
 Also, I found these links in my personal bookmarks:
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.anno
nce&article_id=7399 
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.anno
nce&article_id=7401 
 


 
 Thanks :b, I'd forgotten I'd written that, (they are still some of the 
 stranger code I worked on).
 
 
 That aside, I also am looking for a set implementation. I'm going to 
 need light weight (struct not class, can't hammer the heap), fast (O[1] 
 for most ops), and I'll need add, remove and contains check. really 
 void[T] AA's would do everything I need, if the performance is good 
 enough. Oh and it must allow closed source use.


AA's are good for that - they use a hash lookup, keep buffer size and occupied
size separate and such.  The hash algorithm uses sub-optimal operators, but it
is O(k) and performs rather well.  AA's are also rather convenient for closed
source as they tend to be internally less legible.

Sincerely,
Dan
Apr 26 2007
parent BCS <BCS pathlink.com> writes:
Dan wrote:

 BCS Wrote:
 
 

Justin C Calvarese wrote:


Bill Baxter wrote:



There was some discussion a while back about a Set class.
I think Tango has one, but unfortunately I'm not on Tango yet.




[...]


Also, I found these links in my personal bookmarks:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.anno
nce&article_id=7399 
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.anno
nce&article_id=7401 


Thanks :b, I'd forgotten I'd written that, (they are still some of the 
stranger code I worked on).


That aside, I also am looking for a set implementation. I'm going to 
need light weight (struct not class, can't hammer the heap), fast (O[1] 
for most ops), and I'll need add, remove and contains check. really 
void[T] AA's would do everything I need, if the performance is good 
enough. Oh and it must allow closed source use.


 
 
 AA's are good for that - they use a hash lookup, keep buffer size and occupied
size separate and such.  The hash algorithm uses sub-optimal operators, but it
is O(k) and performs rather well.  AA's are also rather convenient for closed
source as they tend to be internally less legible.
 
 Sincerely,
 Dan


However the data payload that can't be dropped could be a killer.
Apr 26 2007
prev sibling parent reply Clay Smith <clayasaurus gmail.com> writes:
Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.
 
 --bb


Here's a RedBlack tree implementation in D.

http://www.dsource.org/projects/arclib/browser/trunk/arc/templates/redblacktree.d

It's in public domain, and based on this (now explicitly said ;) ) 
public domain C code.

http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

I used it to convert a C++ 2D physics engine --> D , replacing C++ set 
with this red black tree.

~ Clay
Apr 26 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Clay Smith wrote:

 Bill Baxter wrote:

 There was some discussion a while back about a Set class.
 I think Tango has one, but unfortunately I'm not on Tango yet.
 Anyone have a link for a Phobos-compatible set class?
 I checked dsource and scrapple, and tried searching the NG, but "set" 
 gets a lot of bogus hits :-(.

 --bb


 
 Here's a RedBlack tree implementation in D.
 
 http://www.dsource.org/projects/arclib/browser/trunk/arc/temp
ates/redblacktree.d 
 
 
 It's in public domain, and based on this (now explicitly said ;) ) 
 public domain C code.
 
 http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
 
 I used it to convert a C++ 2D physics engine --> D , replacing C++ set 
 with this red black tree.


Great.  Thanks.  I do remember you posting that now.  I see that file is 
in a directory in arclib sitting right next to my FlexSignal code. ;-)

--bb
Apr 26 2007