digitalmars.D - TreeSet

Toki (5/5) Aug 02 2008 Hi,

Moritz Warning (4/10) Aug 02 2008 You can use an associative array with a boolean dummy key, e.g.:

Moritz Warning (4/12) Aug 02 2008 sorry I meant you can use an associative array with a boolean dummy

Benji Smith (12/15) Aug 02 2008 It's not *quite* the same.

Toki (5/26) Aug 02 2008 Thnak you,

Koroskin Denis (2/28) Aug 02 2008 It is available for both.

Steven Schveighoffer (5/8) Aug 02 2008 I highly recommend Tango's new containers, as they offer the best

toki (12/24) Aug 03 2008 Thank you, dcollections is much easier to install.

Koroskin Denis (3/36) Aug 03 2008 I think you should build dcollections into a library and link with it or...
Steven Schveighoffer (12/45) Aug 04 2008 Sorry about that. The reason is because dcollections is not built as a

Steven Schveighoffer (5/47) Aug 04 2008 In addition to releasing version 0.02 (which includes the new allocator)...

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

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

You can use an associative array with a boolean dummy key, e.g.:
uint[bool] myset;

or you can use the Tango library, it has tango.util.container.HashSet.

Aug 02 2008

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


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

Aug 02 2008

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

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

"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

"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

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

"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

"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

"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

D Programming

C/C++ Programming

Other

digitalmars.D - TreeSet