www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - TreeSet

reply Toki <thorstenkiefer gmx.de> writes:
Hi,
I want to port my Java app to D.
Is there sometinhg like a TreeSet in D?

Best Regards
Thorsten
Aug 02 2008
next sibling parent reply Moritz Warning <moritzwarning web.de> writes:
On Sat, 02 Aug 2008 09:06:42 -0400, Toki wrote:

 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?
 
 Best Regards
 Thorsten

uint[bool] myset; or you can use the Tango library, it has tango.util.container.HashSet.
Aug 02 2008
parent reply Moritz Warning <moritzwarning web.de> writes:
On Sat, 02 Aug 2008 17:26:34 +0000, Moritz Warning wrote:

 On Sat, 02 Aug 2008 09:06:42 -0400, Toki wrote:
 
 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?
 
 Best Regards
 Thorsten


value, e.g.: bool[uint] myset;
Aug 02 2008
parent reply Benji Smith <dlanguage benjismith.net> writes:
 sorry I meant you can use an associative array with a boolean dummy 
 value, e.g.:
 bool[uint] myset;

It's not *quite* the same. A java TreeSet<T> uses a red-black tree implementation rather than a hashtable implementation (like the java HashSet<T> class). Consequently, a TreeSet<T>.ValueIterator will always iterate the values in their natural ordering, whereas a HashSet<T>.ValueIterator makes no guarantees about its iteration ordering. I don't know whether Tango provides any equivalent containers. Tango definitely has TreeMap and TreeBag implementations, but there doesn't seem to be a TreeSet. http://dsource.org/projects/tango/docs/current/ Someone with more Tango expertise could probably clarify... --benji
Aug 02 2008
parent reply Toki <thorstenkiefer gmx.de> writes:
Benji Smith Wrote:

 sorry I meant you can use an associative array with a boolean dummy 
 value, e.g.:
 bool[uint] myset;

It's not *quite* the same. A java TreeSet<T> uses a red-black tree implementation rather than a hashtable implementation (like the java HashSet<T> class). Consequently, a TreeSet<T>.ValueIterator will always iterate the values in their natural ordering, whereas a HashSet<T>.ValueIterator makes no guarantees about its iteration ordering. I don't know whether Tango provides any equivalent containers. Tango definitely has TreeMap and TreeBag implementations, but there doesn't seem to be a TreeSet. http://dsource.org/projects/tango/docs/current/ Someone with more Tango expertise could probably clarify... --benji

Thnak you, that's what I was looking for. But the next question: is tango available for dmd, or only for gdc ? -Toki
Aug 02 2008
parent "Koroskin Denis" <2korden gmail.com> writes:
On Sun, 03 Aug 2008 03:00:35 +0400, Toki <thorstenkiefer gmx.de> wrote:

 Benji Smith Wrote:

 sorry I meant you can use an associative array with a boolean dummy
 value, e.g.:
 bool[uint] myset;

It's not *quite* the same. A java TreeSet<T> uses a red-black tree implementation rather than a hashtable implementation (like the java HashSet<T> class). Consequently, a TreeSet<T>.ValueIterator will always iterate the values in their natural ordering, whereas a HashSet<T>.ValueIterator makes no guarantees about its iteration ordering. I don't know whether Tango provides any equivalent containers. Tango definitely has TreeMap and TreeBag implementations, but there doesn't seem to be a TreeSet. http://dsource.org/projects/tango/docs/current/ Someone with more Tango expertise could probably clarify... --benji

Thnak you, that's what I was looking for. But the next question: is tango available for dmd, or only for gdc ? -Toki

It is available for both.
Aug 02 2008
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Toki" wrote
 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?

I highly recommend Tango's new containers, as they offer the best performance. But if you have to stick with the default D library (Phobos), consider dcollections: http://www.dsource.org/projects/dcollections -Steve
Aug 02 2008
parent reply toki <thorstenkiefer gmx.de> writes:
Steven Schveighoffer Wrote:

 "Toki" wrote
 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?

I highly recommend Tango's new containers, as they offer the best performance. But if you have to stick with the default D library (Phobos), consider dcollections: http://www.dsource.org/projects/dcollections -Steve

Thank you, dcollections is much easier to install. But when i compile my program, I gat the following errors : main.o: In function `_D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x1e): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10isLeftNodeMFZb': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10i LeftNodeMFZb+0x1b): undefined reference to `_D12dcollections6RBTree8__assertFiZv' -TK
Aug 03 2008
next sibling parent "Koroskin Denis" <2korden gmail.com> writes:
On Sun, 03 Aug 2008 18:14:45 +0400, toki <thorstenkiefer gmx.de> wrote:

 Steven Schveighoffer Wrote:

 "Toki" wrote
 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?

I highly recommend Tango's new containers, as they offer the best performance. But if you have to stick with the default D library (Phobos), consider dcollections: http://www.dsource.org/projects/dcollections -Steve

Thank you, dcollections is much easier to install. But when i compile my program, I gat the following errors : main.o: In function `_D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x1e): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10isLeftNodeMFZb': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10i LeftNodeMFZb+0x1b): undefined reference to `_D12dcollections6RBTree8__assertFiZv' -TK

I think you should build dcollections into a library and link with it or include all the dcollection source files into your project.
Aug 03 2008
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"toki" <thorstenkiefer gmx.de> wrote in message 
news:g74egl$2f07$1 digitalmars.com...
 Steven Schveighoffer Wrote:

 "Toki" wrote
 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?

I highly recommend Tango's new containers, as they offer the best performance. But if you have to stick with the default D library (Phobos), consider dcollections: http://www.dsource.org/projects/dcollections -Steve

Thank you, dcollections is much easier to install. But when i compile my program, I gat the following errors : main.o: In function `_D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x1e): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10isLeftNodeMFZb': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10i LeftNodeMFZb+0x1b): undefined reference to `_D12dcollections6RBTree8__assertFiZv' -TK

Sorry about that. The reason is because dcollections is not built as a library, so you must actually compile the dcollections modules in addition to your modules. Or make it a library. I probably should do this... What I do when using dcollections is: dmd mymodule1.d mymodule2.d path/to/dcollections/*.d You don't have to build the model directory. Note that the above might add more size to your executable than you need, but it's easy to type. If you just want TreeSet, compile RBTree.d, TreeSet.d, (and if you used the svn trunk, DefaultAllocator.d). -Steve
Aug 04 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer"wrote
 "toki" <thorstenkiefer gmx.de> wrote in message 
 news:g74egl$2f07$1 digitalmars.com...
 Steven Schveighoffer Wrote:

 "Toki" wrote
 Hi,
 I want to port my Java app to D.
 Is there sometinhg like a TreeSet in D?

I highly recommend Tango's new containers, as they offer the best performance. But if you have to stick with the default D library (Phobos), consider dcollections: http://www.dsource.org/projects/dcollections -Steve

Thank you, dcollections is much easier to install. But when i compile my program, I gat the following errors : main.o: In function `_D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBTreeTiZ6RBTree6removeMFC12dcollections6RBTree13__T6RBNodeTiZ6RBNodeZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x1e): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateRMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBNodeTiZ6RBNode': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode7rotateLMFZC12dcollections6RBTree13__T6RBN deTiZ6RBNode+0x17): undefined reference to `_D12dcollections6RBTree8__assertFiZv' main.o: In function `_D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10isLeftNodeMFZb': satsolver.d:(.text._D12dcollections6RBTree13__T6RBNodeTiZ6RBNode10i LeftNodeMFZb+0x1b): undefined reference to `_D12dcollections6RBTree8__assertFiZv' -TK

Sorry about that. The reason is because dcollections is not built as a library, so you must actually compile the dcollections modules in addition to your modules. Or make it a library. I probably should do this...

In addition to releasing version 0.02 (which includes the new allocator), I have included build scripts which should build libraries for you. Please download the new version, and follow the README instructions. -Steve
Aug 04 2008