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 that I wrote in Java and ported to C# for a few other projects. I'd be 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:
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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:

 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:


 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