Craig Black wrote:
>> If you're testing against VS 2005 that may be somewhat related to checked iterators, depending on how you're doing the testing.  The checking occurs even in release builds.
> 
> Is there an option to turn it off?

Not that I know of.  MS wanted the checking in no matter what, and Dinkumware complied.  But it's worth checking the headers to be sure.


Sean

clayasaurus wrote:
> clayasaurus wrote:
>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>
>>
>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>
>> ~ Clay
>>
> 
> RBTree is public domain.

But the redblacktree.d code says it's copyrighted.

Walter Bright wrote:
> clayasaurus wrote:
>> clayasaurus wrote:
>>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>>
>>>
>>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>>
>>> ~ Clay
>>>
>>
>> RBTree is public domain.
> 
> But the redblacktree.d code says it's copyrighted.

I just explicitly put it under public domain. :)

clayasaurus wrote:
> Walter Bright wrote:
>> clayasaurus wrote:
>>> clayasaurus wrote:
>>>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>>>
>>>>
>>>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>>>
>>>> ~ Clay
>>>>
>>>
>>> RBTree is public domain.
>>
>> But the redblacktree.d code says it's copyrighted.
> 
> I just explicitly put it under public domain. :)

Thank you!

clayasaurus wrote:
> Walter Bright wrote:
>> clayasaurus wrote:
>>> clayasaurus wrote:
>>>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>>>
>>>>
>>>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>>>
>>>> ~ Clay
>>>>
>>>
>>> RBTree is public domain.
>>
>> But the redblacktree.d code says it's copyrighted.
> 
> I just explicitly put it under public domain. :)

I hate to be pedantic about this, but this is very important.

If this is based on "Original code and author" at http://eternallyconfuzzled.com/tuts/redblack.html then that needs to be public domain, too. The page, at the bottom, says it's copyrighted.

Walter Bright wrote:
> clayasaurus wrote:
>> Walter Bright wrote:
>>> clayasaurus wrote:
>>>> clayasaurus wrote:
>>>>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>>>>
>>>>>
>>>>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>>>>
>>>>> ~ Clay
>>>>>
>>>>
>>>> RBTree is public domain.
>>>
>>> But the redblacktree.d code says it's copyrighted.
>>
>> I just explicitly put it under public domain. :)
> 
> I hate to be pedantic about this, but this is very important.
> 
> If this is based on "Original code and author" at http://eternallyconfuzzled.com/tuts/redblack.html then that needs to be public domain, too. The page, at the bottom, says it's copyrighted.

I emailed the author about it, and the author said to me...

"All of the code is PD unless otherwise stated. I believe each tutorial mentions this at the start, and including it in the code snippets would be redundant and waste space."

His email is ' happyfrosty at hotmail.com ' if you want to double check.  I told him that the words public domain never appear on the red black tree page and that he should add it.

~ Clay

clayasaurus wrote:
> Walter Bright wrote:
>> clayasaurus wrote:
>>> Walter Bright wrote:
>>>> clayasaurus wrote:
>>>>> clayasaurus wrote:
>>>>>> My templated red black tree version: http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d 
>>>>>>
>>>>>>
>>>>>> I've have only done minimal testing with it, but it hasn't broken on me yet.
>>>>>>
>>>>>> ~ Clay
>>>>>>
>>>>>
>>>>> RBTree is public domain.
>>>>
>>>> But the redblacktree.d code says it's copyrighted.
>>>
>>> I just explicitly put it under public domain. :)
>>
>> I hate to be pedantic about this, but this is very important.
>>
>> If this is based on "Original code and author" at http://eternallyconfuzzled.com/tuts/redblack.html then that needs to be public domain, too. The page, at the bottom, says it's copyrighted.
> 
> I emailed the author about it, and the author said to me...
> 
> "All of the code is PD unless otherwise stated. I believe each tutorial mentions this at the start, and including it in the code snippets would be redundant and waste space."
> 
> His email is ' happyfrosty at hotmail.com ' if you want to double check.  I told him that the words public domain never appear on the red black tree page and that he should add it.
> 
> ~ Clay
> 

I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...

0) Touch up code, fix up indenting.

1) Change 'merge' name to 'union', add 'intersect' function, and add any other standard tree functions that are missing

2) Add option to allow duplicate data in tree (thinking a simple counter to count how many of the same type there are in a node)

3) Create another version that will allow the user to specify the key type to sort by (could try to match STL set/map naming scheme, or use RedBlackTree and RedBlackTreeKey or RBTree RBTreeKey)

4) Heavy testing

5) Have members of the community review and test it for themselves (only those that want to ;) )

I wouldn't want anything 'rushed' into phobos.

~ Clay

clayasaurus wrote:
> I'd also like to add, that if you do give me the heads up that you would like to see this to phobos, give me time to...
> 
> 0) Touch up code, fix up indenting.
> 
> 1) Change 'merge' name to 'union', add 'intersect' function, and add any other standard tree functions that are missing
> 
> 2) Add option to allow duplicate data in tree (thinking a simple counter to count how many of the same type there are in a node)

Better to just add nodes. opEquals may not test all the data in the type, and even if it does object identity may still matter.

> 3) Create another version that will allow the user to specify the key type to sort by (could try to match STL set/map naming scheme, or use RedBlackTree and RedBlackTreeKey or RBTree RBTreeKey)

Maybe also non-modifiable versions or adaptors?

> 4) Heavy testing

Always a good idea.

> 5) Have members of the community review and test it for themselves (only those that want to ;) )
> 
> I wouldn't want anything 'rushed' into phobos.

Some other things you may want to think about:

'D-ify' the code some more
* in/out contracts
* invariant { assert(isValid()); } (or is this ever invalid when a public member is called internally?)
* Some ints --> bools (at least Node.red, isRed(), isValid(), some parameters). The original code was in C which doesn't have bools, but D does, so you might as well use them. Actually, on a quick search through the code, it looks like almost all ints are used as bools. size, getSize() and assertNode() seem to be the only exceptions.

Also:
* It looks like your createCopy does an in-order traversal and adds copies of nodes to the tree. Doesn't this incur a lot of balancing overhead that's totally unnecessary since the tree being copied is balanced already? I'd just add a Node constructor that copies a given node (and recurses on its non-null children). --- Wait, createCopy is also used for merge(). In that case, just keep it for that (maybe rename it addAll?) but duplicate() can be done more efficiently, I think.
* Doesn't opIn_r typically return a T*? I think it at least does for AAs. Might be something to think about since you've already looked up that data anyway and the user might want it (and if not, no big deal).
* Overload some Object functions? opEquals at least, and maybe override toString and toHash as well.

clayasaurus wrote:
>> If this is based on "Original code and author" at http://eternallyconfuzzled.com/tuts/redblack.html then that needs to be public domain, too. The page, at the bottom, says it's copyrighted.
> 
> I emailed the author about it, and the author said to me...
> 
> "All of the code is PD unless otherwise stated. I believe each tutorial mentions this at the start, and including it in the code snippets would be redundant and waste space."

That's a little frustrating, because the page itself says it's copyrighted, so it's a tad ambiguous. I could assume from his email that the code is pd and the copyright only refers to the text, but I'd really rather have an *explicit* statement that the code on that page is pd.

> His email is ' happyfrosty at hotmail.com ' if you want to double check.
> I told him that the words public domain never appear on the red black tree page
> and that he should add it.

Yes. This merry-go-round is important, otherwise at some arbitrary future date we could get the rug pulled out from under us.

Walter Bright wrote:
> Yes. This merry-go-round is important, otherwise at some arbitrary future date we could get the rug pulled out from under us.

I've dealt with lawyers, judges, and contract disputes before. Nothing works better than EXPLICIT and DIRECT statements about the status. Any ambiguousness winds up costing one plenty in legal fees. Something like:

I, <your name here>, am the author of this and I place it into the Public Domain.

is pretty hard to argue with.