digitalmars.D.learn - How to remove the key from the `redBlackTree` with comparator" a <= b
- Dennis Ritchie (10/12) Jun 07 2015 I understand that `removeKey` works only with the comparator "a <
- anonymous (5/10) Jun 07 2015 Do not use '<=' as a comparison function with RedBlackTree. It
- Dennis Ritchie (9/19) Jun 07 2015 OK. But I want to return a `upperBound` segment with the included
- anonymous (3/11) Jun 07 2015 Use equalRange to get the elements that equal 3, too:
- Dennis Ritchie (2/9) Jun 07 2015 Thank you!
- "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> (2/9) Jun 08 2015 Could we add a static check for this?
- Steven Schveighoffer (4/15) Jun 08 2015 How would a static check generate a and b generically?
I understand that `removeKey` works only with the comparator "a < b":Removes elements from the container that are equal to the given values according to the less comparator.How do I remove the key from the `redBlackTree` with comparator "a <= b" ? auto rbt = redBlackTree!("a <= b", int)(1, 2, 3, 4, 5, 6, 7); rbt.removeKey(6); foreach (key; rbt) write(key); // prints 1234567
Jun 07 2015
On Sunday, 7 June 2015 at 18:42:58 UTC, Dennis Ritchie wrote:How do I remove the key from the `redBlackTree` with comparator "a <= b" ?Do not use '<=' as a comparison function with RedBlackTree. It doesn't meet the requirements. Quoting the documentation [1]:Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false.This doesn't hold for '<='.
Jun 07 2015
On Sunday, 7 June 2015 at 18:50:47 UTC, anonymous wrote:On Sunday, 7 June 2015 at 18:42:58 UTC, Dennis Ritchie wrote:OK. But I want to return a `upperBound` segment with the included `key`. It does not suit me: auto rbt = redBlackTree!("a < b", int)(1, 2, 3, 4, 5); writeln(rbt.upperBound(3)); // prints [4, 5] I want it to be so: auto rbt = redBlackTree!("a <= b", int)(1, 2, 3, 4, 5); writeln(rbt.upperBound(3)); // prints [3, 4, 5] How do I do with the comparator "a < b" ?How do I remove the key from the `redBlackTree` with comparator "a <= b" ?Do not use '<=' as a comparison function with RedBlackTree. It doesn't meet the requirements. Quoting the documentation [1]:Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false.This doesn't hold for '<='.
Jun 07 2015
On Sunday, 7 June 2015 at 19:04:08 UTC, Dennis Ritchie wrote:OK. But I want to return a `upperBound` segment with the included `key`. It does not suit me: auto rbt = redBlackTree!("a < b", int)(1, 2, 3, 4, 5); writeln(rbt.upperBound(3)); // prints [4, 5] I want it to be so: auto rbt = redBlackTree!("a <= b", int)(1, 2, 3, 4, 5); writeln(rbt.upperBound(3)); // prints [3, 4, 5] How do I do with the comparator "a < b" ?Use equalRange to get the elements that equal 3, too: writeln(std.range.chain(rbt.equalRange(3), rbt.upperBound(3)));
Jun 07 2015
On Sunday, 7 June 2015 at 19:11:25 UTC, anonymous wrote:On Sunday, 7 June 2015 at 19:04:08 UTC, Dennis Ritchie wrote:Thank you!auto rbt = redBlackTree!("a <= b", int)(1, 2, 3, 4, 5); writeln(rbt.upperBound(3)); // prints [3, 4, 5] How do I do with the comparator "a < b" ?Use equalRange to get the elements that equal 3, too: writeln(std.range.chain(rbt.equalRange(3), rbt.upperBound(3)));
Jun 07 2015
On Sunday, 7 June 2015 at 18:50:47 UTC, anonymous wrote:Do not use '<=' as a comparison function with RedBlackTree. It doesn't meet the requirements. Quoting the documentation [1]:Could we add a static check for this?Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false.This doesn't hold for '<='.
Jun 08 2015
On 6/8/15 6:53 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com>" wrote:On Sunday, 7 June 2015 at 18:50:47 UTC, anonymous wrote:How would a static check generate a and b generically? -SteveDo not use '<=' as a comparison function with RedBlackTree. It doesn't meet the requirements. Quoting the documentation [1]:Could we add a static check for this?Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false.This doesn't hold for '<='.
Jun 08 2015