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