www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - We need to rethink remove in std.container

reply Jonathan M Davis <jmdavisProg gmx.com> writes:
Okay, removing elements from a container sucks right now. You can do stuff like 
removeAny (generally pretty useless IMHO) or removeFront just fine, but
removing 
an arbitrary range from a container just plain sucks.

remove takes a range type which is the range type for the container that it's 
on. That makes sense. It's obviously not going to be able to a take an
arbitrary 
range and remove that from itself. How would it know which elements in that 
range corresponded to which elements in itself - especially when it could be a 
range which skips elements or something similar? So, _that_ part makes sense.

But have you actually tried to get a range of the appropriate type to remove 
from a container? It seems like almost ever function in std.range and 
std.algorithm returns a new range type, making them completely useless for 
processing a range to be removed from a container.

I was looking to remove a single element for a RedBlackTree. The best function 
that I could think to get the proper range was findSplit. The middle portion of 
the return value would be the portion that I was looking for. I'd take that and 
pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its 
implementation and the first two portions of the result of findSplit aren't the 
right range type.

So, what do I do? The _only_ thing that I can think of at the moment is to use 
find to locate the beginning of the range that I want, take the length of the 
range with walkLength and then use popBackN to pop of the elements I don't
want. 
e.g.

======
import std.algorithm, std.container, std.conv,
       std.range, std.stdio;

void main()
{
    auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
    assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");

    auto found = find(rbt[], 5);
    assert(to!string(found) == "[5, 12, 22, 59]");

    popBackN(found, walkLength(found) - 1);
    assert(to!string(found) == "[5]");

    rbt.remove(found);
    assert(to!string(rbt[]) == "[0, 2, 12, 22, 59]");
}
======

That's disgusting. All that just to remove one element? And what if the range 
isn't bidirectional (e.g. SList)? Well, then you have no popBack, and as far as 
I can tell, you're screwed, since you can't use either take or takeExactly, 
because both of them return new range types.

In particular, the fact that you can't take a range and create a new one of the 
same type from its first n elements is highly problematic. Maybe we need to add
a 
function to ForwardRange which returns a new range with the first n elements
(it 
certainly looks like that's the key element that's missing here). I don't know 
if that would be reasonable, but the fact that you can't create a range of the 
same type as the original range when taking just its first n elements seems 
crippling in this situation.

I don't know what the proper solution to this is, but the current situation 
strikes me as untenable. I had to think through this problem for a while before 
I came to a solution that came even close to working, let alone get one that 
actually works. Removing elements from a container should _not_ be this hard. 
The situation with remove _needs_ to be improved.

- Jonathan M Davis
Feb 21 2011
next sibling parent reply %u <wfunction hotmail.com> writes:
 remove takes a range type which is the range type for the
container that it's on. That makes sense. It's obviously not going to be able to a take an arbitrary range and remove that from itself. How would it know which elements in that range corresponded to which elements in itself - especially when it could be a range which skips elements or something similar? So, _that_ part makes sense. I'm wondering, what was the reason for making a "remove range X from Y" method in the first place? To me, that's not a "remove" operation; if anything, it's the "removeAll" operation, but I'd actually call it "subtract" (because it's the set subtraction operation... although there can be duplicates). If we change remove to only take in a single element, wouldn't its implementation then be trivial? (For a range, just return a filter that removes the element. For a container, actually remove the element. For ranges that also behave like containers -- like arrays -- I have no idea.) Does this sound like a good idea?
Feb 21 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 21 February 2011 21:04:47 %u wrote:
 remove takes a range type which is the range type for the
container that it's on. That makes sense. It's obviously not going to be able to a take an arbitrary range and remove that from itself. How would it know which elements in that range corresponded to which elements in itself - especially when it could be a range which skips elements or something similar? So, _that_ part makes sense. I'm wondering, what was the reason for making a "remove range X from Y" method in the first place? To me, that's not a "remove" operation; if anything, it's the "removeAll" operation, but I'd actually call it "subtract" (because it's the set subtraction operation... although there can be duplicates). If we change remove to only take in a single element, wouldn't its implementation then be trivial? (For a range, just return a filter that removes the element. For a container, actually remove the element. For ranges that also behave like containers -- like arrays -- I have no idea.) Does this sound like a good idea?
Removing a range is not necessarily related to removing an element with a particular value. Sure, a method could be added to the various container types which takes a value and removes the first instance of that value from the container, but that's not what remove is necessarily trying to do. It's like erase in C++'s standard library which takes two iterators. There are plenty of situations where removing a range makes sense. The odd bit with remove in Phobos vs erase in the STL is that with iterators, you can give a single iterator to indicate a single element whereas you can't do that with a range. So, remove takes a range, and if you want to remove a single element, that range only has one element in it. It's a bit weird, but that's fine. The typical way to remove an element in the STL is to use find to find an element and then erase to remove it. remove in std.container is doing the same thing. The problem is that you can't give the result of find to remove, because instead of a single iterator, find gives you a whole range, and you probably don't want to remove that whole range. You generally either want to remove the first element or some set of elements at the front of the range. So, you need to able to remove the other elements from the range so that you can give that range to the remove method on the container. That's fine in principle, but since so many of the range-based algorithms give you a new type back and you need the exact type that that container uses for its ranges, it's very hard to get a range of the correct type with the correct elements in it. So, while find will give you the beginning of the range you want, there's not an easy way to remove the end of that range. Functions like take and takeExactly return new types, so they don't work. The more I look at it, the more I'm convinced that we really need to add a primitive to forward ranges that returns the first n elements of that range. Without that, I don't see how you can get a range of the correct type with only those elements in it unless it's also a bidirectional range, which some ranges (like SList's range) aren't. - Jonathan M Davis
Feb 21 2011
next sibling parent %u <wfunction hotmail.com> writes:
 The more I look at it, the more I'm convinced that we really need to
add a primitive to forward ranges that returns the first n elements of that range. Without that, I don't see how you can get a range of the correct type with only those elements in it unless it's also a bidirectional range, which some ranges (like SList's range) aren't. Huh, yeah I think I agree. It seems like ranges are just delayed evaluation, and that, at some point, we need to be able to force their evaluation -- otherwise, it's like combining Scheme's (delay X) and (force Y) operations with mutation, which just doesn't work sensibly in non-functional programming.
Feb 21 2011
prev sibling next sibling parent reply %u <wfunction hotmail.com> writes:
You know, I'm actually now questioning whether STL did the right thing
with requiring iterators for the erase() method. It actually seems
quite pointless -- there's no reason why integer indices wouldn't
work. I don't think we really need to follow suit with STL here... is
there some situation with erase() that I'm missing that can't be
covered with plain integer (or rather, size_t) indices, and that
requires ranges?
Feb 21 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 21 February 2011 21:51:51 %u wrote:
 You know, I'm actually now questioning whether STL did the right thing
 with requiring iterators for the erase() method. It actually seems
 quite pointless -- there's no reason why integer indices wouldn't
 work. I don't think we really need to follow suit with STL here... is
 there some situation with erase() that I'm missing that can't be
 covered with plain integer (or rather, size_t) indices, and that
 requires ranges?
Some of them do take indices, but you can't generally operate on indices. To do that, you need the original container. But you can operate on an iterate just fine. So, it's generally easier to deal with iterators. However, the big thing would be that it actually doesn't make sense to use indices in many cases. Think about RedBlackTree for a moment. If you remove something from it or add something to it, that doesn't invalidate any range that you have which points to it (assuming that the end points haven't changed). You can still take that range and use it any any algorithm that you want - including remove (assuming that the algorithm takes the appropriate kind of range of course), and it will work. But using indices wouldn't work. They would have changed. Adding or removing anything to a container at or before an index that you have would make it so that that index no longer points to the same element. However, for many containers (though not all), any iterators or ranges would still be valid. So, on the whole, using iterators or ranges makes great sense. I have no problem with how the STL does that. The problem is transitioning that to ranges. The STL doesn't go and change your iterator types on you when you feed them to algorithms, but std.range and std.algorithm typically do. So, the result is sub- optimal in this case, to say the least. - Jonathan M Davis
Feb 21 2011
parent reply %u <wfunction hotmail.com> writes:
Hm... so the entire issue here seems to be the capability to do
iteration and modification in a concurrent manner, right?

IMHO that may not be worth the costs we're paying -- I would argue
that you normally shouldn't be modifying a collection that you're
iterating over in the first place; it just doesn't make any sense
when you're delaying everything. Sure, it would work fine if you
couldn't have more than one reference to any container (since every
range would would then have the same view of the container), but
when we're introducing delayed evaluation with ranges, I just don't
see how (or even why) it should be combinable with modification.
It's like trying to read from a database and concurrently modifying
the underlying storage by hand, bypassing the database... it just
doesn't work that way, outside of functional programming. So is it
really worth paying the price?
Feb 21 2011
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 21 February 2011 22:51:25 %u wrote:
 Hm... so the entire issue here seems to be the capability to do
 iteration and modification in a concurrent manner, right?
 
 IMHO that may not be worth the costs we're paying -- I would argue
 that you normally shouldn't be modifying a collection that you're
 iterating over in the first place; it just doesn't make any sense
 when you're delaying everything. Sure, it would work fine if you
 couldn't have more than one reference to any container (since every
 range would would then have the same view of the container), but
 when we're introducing delayed evaluation with ranges, I just don't
 see how (or even why) it should be combinable with modification.
 It's like trying to read from a database and concurrently modifying
 the underlying storage by hand, bypassing the database... it just
 doesn't work that way, outside of functional programming. So is it
 really worth paying the price?
_Of course_, it's worth it. Do you never alter anything in a range? Functions like sort need to be able to alter the elements that the range refers to. Not to mention, there's generally no other way to alter elements in a container other than through a range to it unless you remove them and add new ones to replace them. The one exception would be if the container is random access, and then you can use the subscript operator to get at its elements. Ranges definitely need to be able to alter the elements that they contain. Sure, there are plenty of times when you don't need to do that, but there are times when you definitely do. And really, the problem here isn't really the concept of ranges - it's their implementation. The fact that you can't get the right type of range with the right elements in it is the problem. Doing something like building the take functionality into forward ranges would fix that problem. - Jonathan M Davis
Feb 21 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/21/11 11:27 PM, Jonathan M Davis wrote:
 The typical way to remove an element in the STL is to use find to find an
element
 and then erase to remove it. remove in std.container is doing the same thing.
 The problem is that you can't give the result of find to remove, because
instead
 of a single iterator, find gives you a whole range, and you probably don't want
 to remove that whole range. You generally either want to remove the first
element
 or some set of elements at the front of the range.
This is the exact insight that made me recognize take() is an essential range type. Andrei
Feb 22 2011
prev sibling next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 22 Feb 2011 05:55:20 +0300, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 Okay, removing elements from a container sucks right now. You can do  
 stuff like
 removeAny (generally pretty useless IMHO) or removeFront just fine, but  
 removing
 an arbitrary range from a container just plain sucks.

 remove takes a range type which is the range type for the container that  
 it's
 on. That makes sense. It's obviously not going to be able to a take an  
 arbitrary
 range and remove that from itself. How would it know which elements in  
 that
 range corresponded to which elements in itself - especially when it  
 could be a
 range which skips elements or something similar? So, _that_ part makes  
 sense.

 But have you actually tried to get a range of the appropriate type to  
 remove
 from a container? It seems like almost ever function in std.range and
 std.algorithm returns a new range type, making them completely useless  
 for
 processing a range to be removed from a container.

 I was looking to remove a single element for a RedBlackTree. The best  
 function
 that I could think to get the proper range was findSplit. The middle  
 portion of
 the return value would be the portion that I was looking for. I'd take  
 that and
 pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
 implementation and the first two portions of the result of findSplit  
 aren't the
 right range type.

 So, what do I do? The _only_ thing that I can think of at the moment is  
 to use
 find to locate the beginning of the range that I want, take the length  
 of the
 range with walkLength and then use popBackN to pop of the elements I  
 don't want.
 e.g.

 ======
 import std.algorithm, std.container, std.conv,
        std.range, std.stdio;

 void main()
 {
     auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
     assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");

     auto found = find(rbt[], 5);
     assert(to!string(found) == "[5, 12, 22, 59]");

     popBackN(found, walkLength(found) - 1);
     assert(to!string(found) == "[5]");

     rbt.remove(found);
     assert(to!string(rbt[]) == "[0, 2, 12, 22, 59]");
 }
 ======

 That's disgusting. All that just to remove one element? And what if the  
 range
 isn't bidirectional (e.g. SList)? Well, then you have no popBack, and as  
 far as
 I can tell, you're screwed, since you can't use either take or  
 takeExactly,
 because both of them return new range types.

 In particular, the fact that you can't take a range and create a new one  
 of the
 same type from its first n elements is highly problematic. Maybe we need  
 to add a
 function to ForwardRange which returns a new range with the first n  
 elements (it
 certainly looks like that's the key element that's missing here). I  
 don't know
 if that would be reasonable, but the fact that you can't create a range  
 of the
 same type as the original range when taking just its first n elements  
 seems
 crippling in this situation.

 I don't know what the proper solution to this is, but the current  
 situation
 strikes me as untenable. I had to think through this problem for a while  
 before
 I came to a solution that came even close to working, let alone get one  
 that
 actually works. Removing elements from a container should _not_ be this  
 hard.
 The situation with remove _needs_ to be improved.

 - Jonathan M Davis
I believe remove operation is better expressed in terms of a Cursor (iterator in C++). It also doesn't make much sense (at least of me) for a find to return a subrange of the source range. While it does generalize well, it's not really what most people expect. What I'd love to have instead is something like this: int[] arr = [1, 2, 3, 4, 5]; auto cursor = arr.find(3); // either points to 3 or null int[] before = arr[0..cursor]; int value = arr[cursor]; // for consistency, C++ uses *cursor int[] after = arr[arr.advance(cursor)..$]; Note that typeof(cursor) could/should actually be int*, but I don't use arr[cursor+1..$] because cursor doesn't know about range bounds, and as such it can't advance on it's own. For dynamic arrays: V[K] dynamicArray; V* cursor = key in dynamicArray; dynamicArray.remove(key); // requires an additional lookup, which is sub-optimal // dynamicArray.remove(cursor); // optimal but doesn't work atm. I think it should I think it's also worth noting that "find" for trees makes even less sense (to me). You can't "slice" a tree arbitrarily, yet find tries to do that:
     auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
     assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");

     auto found = find(rbt[], 5);
     assert(to!string(found) == "[5, 12, 22, 59]");
What is the type of "found"? It's clearly not a tree anymore. Don't know why, but it's still a range. How is it implemented? Without looking at the source I can tell it's implemented as an original tree + a cursor. And I believe the two are better be separated. As a side note, in my own code I have 2 version of remove - remove and removeUnstable, which work differently. Simple example: // swaps current element with last one and pops last void removeUnstable(T)(ref T[] array, T* cursor) { auto length = array.length; assert(length > 0); --length; T* last = array.ptr + length; assert(array.ptr <= cursor && cursor <= last); *cursor = *last; array.length = length; } // Moves elements T* remove(T)(ref T[] array, T* cursor) { auto length = array.length; assert(length > 0); --length; assert(array.ptr <= cursor && cursor <= array.ptr + length); auto numElementsToMove = length - (cursor - array.ptr); memmove(cursor, cursor + 1, numElementsToMove * T.sizeof); array.length = length; return cursor; }
Feb 22 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Feb 2011 03:43:25 -0500, Denis Koroskin <2korden gmail.com>  
wrote:

 I believe remove operation is better expressed in terms of a Cursor  
 (iterator in C++). It also doesn't make much sense (at least of me) for  
 a find to return a subrange of the source range. While it does  
 generalize well, it's not really what most people expect.

 What I'd love to have instead is something like this:

 int[] arr = [1, 2, 3, 4, 5];
 auto cursor = arr.find(3); // either points to 3 or null

 int[] before = arr[0..cursor];
 int value = arr[cursor]; // for consistency, C++ uses *cursor
 int[] after = arr[arr.advance(cursor)..$];
This is exactly how dcollections works.
 Note that typeof(cursor) could/should actually be int*, but I don't use  
 arr[cursor+1..$] because cursor doesn't know about range bounds, and as  
 such it can't advance on it's own.
Here is how dcollections solves this. A cursor in dcollections is actually a zero or one element range. It can only reference exactly one element. Since it has no references to other elements, it is immune to operations that use the surrounding elements. In contrast, a red black tree range contains references to the begin and the end node. This means operations on these nodes (i.e. removing the end node, or inserting an element between the two) can affect the range. So essentially, your code would look like this in dcollections: auto arr = new ArrayList!int(1,2,3,4,5); auto cursor = arr.find(3); int[] before = arr[0..cursor]; int value = arr[cursor]; cursor.popFront(); int[] after = arr[cursor..arr.end]; // note, $ overrides don't currently work, so we can't get the sugar here...
 I think it's also worth noting that "find" for trees makes even less  
 sense (to me). You can't "slice" a tree arbitrarily, yet find tries to  
 do that:

     auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
     assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");

     auto found = find(rbt[], 5);
     assert(to!string(found) == "[5, 12, 22, 59]");
What is the type of "found"? It's clearly not a tree anymore. Don't know why, but it's still a range. How is it implemented? Without looking at the source I can tell it's implemented as an original tree + a cursor. And I believe the two are better be separated.
Actually, find is probably not the correct thing to use for this. Use upperBound (or lowerBound, I can never remember which one does what) to get all the elements >= 5. The range is not a tree, and this is intentional. Containers are *not* ranges. Think of a range as a 'view' into a container, but not a container itself. You can't add/remove elements from the tree using a range, you can just traverse it. If it helps, think of the range as a pair of iterators. -Steve
Feb 22 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/22/11 7:58 AM, Steven Schveighoffer wrote:
 A cursor in dcollections is actually a zero or one element range. It can
 only reference exactly one element. Since it has no references to other
 elements, it is immune to operations that use the surrounding elements.
At this exact point I had what would be either a good idea or a brainfart. I've been thinking for a good while to define a "singleton range", a range that has at most one element. I had the intuition that a singleton range is a useful concept, but I felt it was a bit tenuous to argue in its favor (mostly because one could easily simulate it with repeat(x, 1)), so I never put it in std.range. The definition would go like this: auto singletonRange(T)(T element) { static struct Result { private T _element; private bool _done; property bool empty() { return _done; } property auto front() { assert(!empty); return _element; } void popFront() { assert(!empty); _done = true; } auto save() { return this; } } return Result(element, false); } But now I realized that singleton ranges are your cursors, so I'll definitely add them. And you also made me realize that a singleton range is very different from other ranges in the same way 1 is different from other numbers. Great. This may as well be The Great Unification that was needed to converge std.container with dcollections in a harmonious whole. Andrei
Feb 22 2011
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/22/11 7:58 AM, Steven Schveighoffer wrote:
 A cursor in dcollections is actually a zero or one element range. It can
 only reference exactly one element. Since it has no references to other
 elements, it is immune to operations that use the surrounding elements.
At this exact point I had what would be either a good idea or a brainfart. I've been thinking for a good while to define a "singleton range", a range that has at most one element. I had the intuition that a singleton range is a useful concept, but I felt it was a bit tenuous to argue in its favor (mostly because one could easily simulate it with repeat(x, 1)), so I never put it in std.range. The definition would go like this: auto singletonRange(T)(T element) { static struct Result { private T _element; private bool _done; property bool empty() { return _done; } property auto front() { assert(!empty); return _element; } void popFront() { assert(!empty); _done = true; } auto save() { return this; } } return Result(element, false); }
This is almost the same as a dcollections cursor. The only difference is, popFront in a cursor not only sets the '_done' member, but also moves to the next element. This distinction is necessary with node-based containers that have an end marker node. So the cursor that is returned from 'end()' (or from find where the element was not found, etc.) is an already-empty cursor. I hadn't thought of just setting the empty variable, but I think it wouldn't work properly. You could possibly say "a cursor that points to an element but is empty is actually pointing *after* the element." But then I'm not sure how to construct an end cursor. It's advantageous to point at the end of a container, where there is no true node to point at. Is there another way to think about this?
 But now I realized that singleton ranges are your cursors, so I'll  
 definitely add them. And you also made me realize that a singleton range  
 is very different from other ranges in the same way 1 is different from  
 other numbers. Great.
Yes, that distinction is really important, I'm glad you see that!
 This may as well be The Great Unification that was needed to converge  
 std.container with dcollections in a harmonious whole.
I'm not sure what to think of this ;) Is this a "oh what could have been" statement or a "let's reopen negotiations" statement? Note, I would love for dcollections to be mainstream Phobos, but I have accepted the current reality and am fine with the way things are now too. -Steve
Feb 22 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/22/11 8:41 AM, Steven Schveighoffer wrote:
 On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/22/11 7:58 AM, Steven Schveighoffer wrote:
 A cursor in dcollections is actually a zero or one element range. It can
 only reference exactly one element. Since it has no references to other
 elements, it is immune to operations that use the surrounding elements.
At this exact point I had what would be either a good idea or a brainfart. I've been thinking for a good while to define a "singleton range", a range that has at most one element. I had the intuition that a singleton range is a useful concept, but I felt it was a bit tenuous to argue in its favor (mostly because one could easily simulate it with repeat(x, 1)), so I never put it in std.range. The definition would go like this: auto singletonRange(T)(T element) { static struct Result { private T _element; private bool _done; property bool empty() { return _done; } property auto front() { assert(!empty); return _element; } void popFront() { assert(!empty); _done = true; } auto save() { return this; } } return Result(element, false); }
This is almost the same as a dcollections cursor. The only difference is, popFront in a cursor not only sets the '_done' member, but also moves to the next element. This distinction is necessary with node-based containers that have an end marker node. So the cursor that is returned from 'end()' (or from find where the element was not found, etc.) is an already-empty cursor.
I thought about this overnight and reached the same conclusion. The thing is, what's needed is not one element, but one element of a specific range. Here's what I have right now in range.d: /** Returns a range with at most one element; for example, $(D takeOne([42, 43, 44])) returns a range consisting of the integer $(D 42). Calling $(D popFront()) off that range renders it empty. Sometimes an empty range with the same signature is needed. For such ranges use $(D takeNone!R()). For example: ---- auto s = takeOne([42, 43, 44]); static assert(isRandomAccessRange!(typeof(s))); assert(s.length == 1); assert(!s.empty); assert(s.front == 42); s.front() = 43; assert(s.front == 43); assert(s.back == 43); assert(s[0] == 43); s.popFront(); assert(s.length == 0); assert(s.empty); s = takeNone!(int[])(); assert(s.length == 0); assert(s.empty); ---- In effect $(D takeOne(r)) is equivalent to $(take(r, 1)) and $(D takeNone(r)) is equivalent to $(D take(r, 0)), but in certain interfaces it is important to know statically that the range may only have at most one element. The type returned by $(D takeOne) and $(D takeNone) is a random-access range. */ auto takeOne(R)(R source) if (isInputRange!R) { static struct Result { private R _source; bool _empty; property bool empty() const { return _empty; } property auto ref front() { assert(!empty); return _source.front; } void popFront() { assert(!empty); _empty = true; } void popBack() { assert(!empty); _empty = true; } auto save() { return Result(_source.save, empty); } property auto ref back() { assert(!empty); return _source.front; } property size_t length() const { return !empty; } auto ref opIndex(size_t n) { assert(n < length); return _source.front; } auto opSlice(size_t m, size_t n) { assert(m <= n && n < length); return n > m ? this : Result(_source, false); } } return Result(source, source.empty); } /// Ditto auto takeNone(R)() if (isInputRange!R) { return typeof(takeOne(R.init))(R.init, true); } unittest { auto s = takeOne([42, 43, 44]); static assert(isRandomAccessRange!(typeof(s))); assert(s.length == 1); assert(!s.empty); assert(s.front == 42); s.front() = 43; assert(s.front == 43); assert(s.back == 43); assert(s[0] == 43); s.popFront(); assert(s.length == 0); assert(s.empty); s = takeNone!(int[])(); assert(s.length == 0); assert(s.empty); }
 I hadn't thought of just setting the empty variable, but I think it
 wouldn't work properly. You could possibly say "a cursor that points to
 an element but is empty is actually pointing *after* the element." But
 then I'm not sure how to construct an end cursor. It's advantageous to
 point at the end of a container, where there is no true node to point
 at. Is there another way to think about this?
Yah, I think the right approach is to base the 0/1 range on an existing range, not on an existing value.
 But now I realized that singleton ranges are your cursors, so I'll
 definitely add them. And you also made me realize that a singleton
 range is very different from other ranges in the same way 1 is
 different from other numbers. Great.
Yes, that distinction is really important, I'm glad you see that!
 This may as well be The Great Unification that was needed to converge
 std.container with dcollections in a harmonious whole.
I'm not sure what to think of this ;) Is this a "oh what could have been" statement or a "let's reopen negotiations" statement? Note, I would love for dcollections to be mainstream Phobos, but I have accepted the current reality and am fine with the way things are now too.
Absolutely, and your collaboration on e.g. RedBlackTree and others is very much appreciated. The way I was thinking is, there would a lot of convergence if dcollections wiped the notion of "cursor" and replaced it with takeOne throughout. One obvious objection to the range/cursor design is there are two abstractions to deal with instead of one. I had the intuition that ranges should be enough, but was not quite able to substantiate it fully until just about now. With take, takeExactly, and takeOne, it seems that indeed there is only need for the range interface, and that particular range types can replace cursors. I realize that there are other major differences in design between dcollections and std.container, probably the largest one being the use of a hierarchy vs. free-floating types, so probably full unification is still not possible or quite remote. Nevertheless, keeping the communication channels open would make both libraries better and all of us a bit wiser. Andrei
Feb 23 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 23 Feb 2011 08:33:03 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/22/11 8:41 AM, Steven Schveighoffer wrote:
 On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 This may as well be The Great Unification that was needed to converge
 std.container with dcollections in a harmonious whole.
I'm not sure what to think of this ;) Is this a "oh what could have been" statement or a "let's reopen negotiations" statement? Note, I would love for dcollections to be mainstream Phobos, but I have accepted the current reality and am fine with the way things are now too.
Absolutely, and your collaboration on e.g. RedBlackTree and others is very much appreciated. The way I was thinking is, there would a lot of convergence if dcollections wiped the notion of "cursor" and replaced it with takeOne throughout. One obvious objection to the range/cursor design is there are two abstractions to deal with instead of one. I had the intuition that ranges should be enough, but was not quite able to substantiate it fully until just about now. With take, takeExactly, and takeOne, it seems that indeed there is only need for the range interface, and that particular range types can replace cursors.
I don't think this is possible. When passing a range to a container for removal, the container needs to access the underlying implementation (e.g. pointer to tree node) in order to immediately know what element is being removed. The takeOne range you propose does not allow this, you can't get at the underlying range. Even if you could, only takeOne!(myrangetype) would work, which leaves us right back at supporting a small number of specific ranges. In addition, a cursor points to one element, a range points to multiple elements. *conceptually* takeOne is the same, but it still stores the range internally, so it's actually more expensive than a range to pass around (additional _empty member). I was thinking more along the lines of ranges being able to generate cursors if it makes sense (i.e. base range is a range of the container). Dcollections already supports this with the two accessors begin() and end(). We might also need a last() which gets the last valid element in the range. This would be akin to back(). Here is what I was thinking that can help with unifying interface. I'll just show you as a code snippet: void remove(C)(C c) if (is(C == mycursortype)) { // since we know the structure of c, we can use it to remove the element from the container } void remove(R)(R r) if (is(R == myrangetype)) { // possibly can be optimized } void remove(R)(R r) if (!is(R == myrangetype) && isInputRange!R && is(typeof(r.begin) == mycursortype)) { while(!r.empty) { auto c = r.begin; r.popFront(); remove(c); } } If wrapper ranges can "forward" the begin and end functions through their API, then you can construct arbitrary ranges that will be accepted as parameters to remove. We could potentially add forwarding functions to all wrapper ranges, or we could pick ones that make the most sense (like take). In addition, dcollections (and any collection that can verify its endpoints and cursor membership, SList obviously cannot) allows slicing based on cursors in a limited fashion. Therefore, this allows constructing ranges from cursors if you have the original container. As an example of what this could allow (assuming retro and take forward the begin(), end() and last() methods): container.remove(take(retro(container[]), 5)); // remove the last 5 elements from the container.
 I realize that there are other major differences in design between  
 dcollections and std.container, probably the largest one being the use  
 of a hierarchy vs. free-floating types, so probably full unification is  
 still not possible or quite remote. Nevertheless, keeping the  
 communication channels open would make both libraries better and all of  
 us a bit wiser.
As I've said in the past, the interface hierarchy is not critical at the moment because D has very little shared library support. I'm willing to remove the interfaces as long as the types remain classes (which I believe you are more agreeable with lately). This allows the interfaces to be added on later if it makes sense. The cursor concept has to stay though. -Steve
Feb 23 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/23/11 8:51 AM, Steven Schveighoffer wrote:
 On Wed, 23 Feb 2011 08:33:03 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 2/22/11 8:41 AM, Steven Schveighoffer wrote:
 On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 This may as well be The Great Unification that was needed to converge
 std.container with dcollections in a harmonious whole.
I'm not sure what to think of this ;) Is this a "oh what could have been" statement or a "let's reopen negotiations" statement? Note, I would love for dcollections to be mainstream Phobos, but I have accepted the current reality and am fine with the way things are now too.
Absolutely, and your collaboration on e.g. RedBlackTree and others is very much appreciated. The way I was thinking is, there would a lot of convergence if dcollections wiped the notion of "cursor" and replaced it with takeOne throughout. One obvious objection to the range/cursor design is there are two abstractions to deal with instead of one. I had the intuition that ranges should be enough, but was not quite able to substantiate it fully until just about now. With take, takeExactly, and takeOne, it seems that indeed there is only need for the range interface, and that particular range types can replace cursors.
I don't think this is possible. When passing a range to a container for removal, the container needs to access the underlying implementation (e.g. pointer to tree node) in order to immediately know what element is being removed. The takeOne range you propose does not allow this, you can't get at the underlying range.
I agree that takeOne's source should be made public.
 Even if you could, only
 takeOne!(myrangetype) would work, which leaves us right back at
 supporting a small number of specific ranges.
That's arguably correct and in any case better than supporting a range plus a distinct cursor abstraction. You remove the cursor abstraction and replace it with a specific realization of the range abstraction.
 In addition, a cursor points to one element, a range points to multiple
 elements. *conceptually* takeOne is the same, but it still stores the
 range internally, so it's actually more expensive than a range to pass
 around (additional _empty member).
I agree. There are a number of ways around this if important, but I need first to be clear of the projected uses of takeOne.
 I was thinking more along the lines of ranges being able to generate
 cursors if it makes sense (i.e. base range is a range of the container).
 Dcollections already supports this with the two accessors begin() and
 end(). We might also need a last() which gets the last valid element in
 the range. This would be akin to back().

 Here is what I was thinking that can help with unifying interface. I'll
 just show you as a code snippet:

 void remove(C)(C c) if (is(C == mycursortype))
 {
 // since we know the structure of c, we can use it to remove the element
 from the container
 }

 void remove(R)(R r) if (is(R == myrangetype))
 {
 // possibly can be optimized
 }

 void remove(R)(R r) if (!is(R == myrangetype) && isInputRange!R &&
 is(typeof(r.begin) == mycursortype))
 {
 while(!r.empty)
 {
 auto c = r.begin;
 r.popFront();
 remove(c);
 }
 }

 If wrapper ranges can "forward" the begin and end functions through
 their API, then you can construct arbitrary ranges that will be accepted
 as parameters to remove. We could potentially add forwarding functions
 to all wrapper ranges, or we could pick ones that make the most sense
 (like take).
Soon as we get to begin() and end() as primitives it all starts being problematic. We may as well design with STL-style iterators then. One good thing about ranges is that they _don't_ need to rely on lower-level primitives.
 In addition, dcollections (and any collection that can verify its
 endpoints and cursor membership, SList obviously cannot) allows slicing
 based on cursors in a limited fashion. Therefore, this allows
 constructing ranges from cursors if you have the original container.

 As an example of what this could allow (assuming retro and take forward
 the begin(), end() and last() methods):

 container.remove(take(retro(container[]), 5)); // remove the last 5
 elements from the container.
I understand and I see the advantages. Still I believe that the disadvantages of dealing with cursors overcome this potential flexibility. I'd be more inclined to look for a design for which ranges suffice for iteration. Andrei
Feb 23 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 23 Feb 2011 12:16:26 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/23/11 8:51 AM, Steven Schveighoffer wrote:
 I don't think this is possible. When passing a range to a container for
 removal, the container needs to access the underlying implementation
 (e.g. pointer to tree node) in order to immediately know what element is
 being removed. The takeOne range you propose does not allow this, you
 can't get at the underlying range.
I agree that takeOne's source should be made public.
But what about takeOne(retro(myrange))? If support for that was desired, one would need to do it explicitly. As each new wrapper type is desired, one needs to add support for the specific configuration of wrappers.
 Even if you could, only
 takeOne!(myrangetype) would work, which leaves us right back at
 supporting a small number of specific ranges.
That's arguably correct and in any case better than supporting a range plus a distinct cursor abstraction. You remove the cursor abstraction and replace it with a specific realization of the range abstraction.
At the end of the day, a container needs a cursor (or something like it) in order to remove an element. The cursor is the gateway between the safe range abstraction, and the unsafe internal representation (with nasty pointers). In reality, supporting cursors and ranges vs. takeOne and ranges only differs in that you need to add a cursor type. The number of functions required remains the same (the cursor handling functions replace the takeOne handling functions).
 Soon as we get to begin() and end() as primitives it all starts being  
 problematic. We may as well design with STL-style iterators then. One  
 good thing about ranges is that they _don't_ need to rely on lower-level  
 primitives.
Ranges for containers necessarily need to rely on lower level primitives as I stated above. A cursor gives a safe abstraction of such a primitive. Example, An SList range: struct Range { private Node * _head; // <------ this is the primitive private this(Node * p) { _head = p; } /// Forward range primitives. bool empty() const { return !_head; } /// ditto property Range save() { return this; } /// ditto property T front() { return _head._payload; } /// ditto property void front(T value) { enforce(_head); _head._payload = value; } ... Note that the range *hides* the unsafe primitive. But so does a cursor. Essentially, a cursor is a way to refer to one of those primitives. Seeing as how the implementation needs to use one of those primitives, being able to pass around a safe version of that primitive is very advantageous. Requiring passing around a range of them is problematic for many functions.
 In addition, dcollections (and any collection that can verify its
 endpoints and cursor membership, SList obviously cannot) allows slicing
 based on cursors in a limited fashion. Therefore, this allows
 constructing ranges from cursors if you have the original container.

 As an example of what this could allow (assuming retro and take forward
 the begin(), end() and last() methods):

 container.remove(take(retro(container[]), 5)); // remove the last 5
 elements from the container.
I understand and I see the advantages. Still I believe that the disadvantages of dealing with cursors overcome this potential flexibility. I'd be more inclined to look for a design for which ranges suffice for iteration.
Then I think we shall keep things the way they are. Cursors are absolutely necessary in my model of collections, and to get rid of them would abandon the most fundamental reason I created dcollections. -Steve
Feb 23 2011
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Feb 22, 2011 at 15:23, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 auto singletonRange(T)(T element)
 {
 =C2=A0 =C2=A0static struct Result
 =C2=A0 =C2=A0{
 =C2=A0 =C2=A0 =C2=A0 =C2=A0private T _element;
 =C2=A0 =C2=A0 =C2=A0 =C2=A0private bool _done;
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 property bool empty() { return _done; }
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 property auto front() { assert(!empty); retur=
n _element; }
 =C2=A0 =C2=A0 =C2=A0 =C2=A0void popFront() { assert(!empty); _done =3D tr=
ue; }
 =C2=A0 =C2=A0 =C2=A0 =C2=A0auto save() { return this; }
 =C2=A0 =C2=A0}

 =C2=A0 =C2=A0return Result(element, false);
 }
That's also what many people would like a findFirst function to return. Either a 1-element range with the found value or an empty range if the value doesn't exist. auto v =3D findFirst(range, needle); if (!v.empty) { ... } Maybe you could allow for the creation of an empty output singletonRange where a lone value could then be put. auto singleton(T)() { ... } but the user would need to provide the 'T' by himself. and then: void put(T element) {assert(empty); _element =3D element;} That could be a way to modify a container. Btw, is there a way to have an empty container and use an output range to fill it? I didn't look at std.container for quite some time.
Feb 22 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/22/11 3:23 PM, Philippe Sigaud wrote:
 On Tue, Feb 22, 2011 at 15:23, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org>  wrote:

 auto singletonRange(T)(T element)
 {
     static struct Result
     {
         private T _element;
         private bool _done;
          property bool empty() { return _done; }
          property auto front() { assert(!empty); return _element; }
         void popFront() { assert(!empty); _done = true; }
         auto save() { return this; }
     }

     return Result(element, false);
 }
That's also what many people would like a findFirst function to
 return. Either a 1-element range with the found value or an empty
 range if the value doesn't exist.
auto v = findFirst(range, needle);
 if (!v.empty) { ... }
Good point.
 Maybe you could allow for the creation of an empty output
 singletonRange where a lone value could then be put.
 auto singleton(T)() { ... } but the user would need to provide the 'T'
 by himself.
Yah, I thought of that after posting. It would look something like this: auto singletonRange(T)() { typeof(singletonRange(T.init)) result = void; result._done = true; return result; } No mercy :o). But that's unsafe so probably we'd need to leave out "= void".
 and then:
void put(T element) {assert(empty); _element = element;} That could be a way to modify a container. Btw, is there a way to have
 an empty container and use an output range to fill it? I didn't look
 at std.container for quite some time.
No, but this may be an interesting idea to pursue. Andrei
Feb 22 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Feb 2011 16:55:29 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/22/11 3:23 PM, Philippe Sigaud wrote:
 Btw, is there a way to have
 an empty container and use an output range to fill it? I didn't look
 at std.container for quite some time.
No, but this may be an interesting idea to pursue.
s/insert/put Now all containers that support insertion are output ranges... Or am I missing something? -Steve
Feb 22 2011
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Feb 22, 2011 at 23:20, Steven Schveighoffer <schveiguy yahoo.com> wrote:
 s/insert/put

 Now all containers that support insertion are output ranges...

 Or am I missing something?
I mean that, in the same way that a container can expose its elements as an input range using [], a partially filled container could give access to its empty 'slots' (created by 'reserve()' ) via an output range.
Feb 22 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 23 Feb 2011 01:30:49 -0500, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:

 On Tue, Feb 22, 2011 at 23:20, Steven Schveighoffer  
 <schveiguy yahoo.com> wrote:
 s/insert/put

 Now all containers that support insertion are output ranges...

 Or am I missing something?
I mean that, in the same way that a container can expose its elements as an input range using [], a partially filled container could give access to its empty 'slots' (created by 'reserve()' ) via an output range.
Oh, that's easy. Any container range that allows setting front elements is fair game. For example SList's range can be an output range right now. (I believe isOutputRange!(SList.init[]) should be true) What's not available is adding new elements to a container via the output range concept. -Steve
Feb 23 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Feb 2011 08:58:04 -0500, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 So essentially, your code would look like this in dcollections:

 auto arr = new ArrayList!int(1,2,3,4,5);

 auto cursor = arr.find(3);

 int[] before = arr[0..cursor];
 int value = arr[cursor];
Actually, I haven't used dcollections (or much d code) in so long, I forgot the cursor's main function! int value = cursor.front; That looks better ;) -Steve
Feb 22 2011
prev sibling next sibling parent reply Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Jonathan M Davis wrote:

 Okay, removing elements from a container sucks right now. You can do stuff
 like removeAny (generally pretty useless IMHO) or removeFront just fine,
 but removing an arbitrary range from a container just plain sucks.
 
 remove takes a range type which is the range type for the container that
 it's on. That makes sense. It's obviously not going to be able to a take
 an arbitrary range and remove that from itself. How would it know which
 elements in that range corresponded to which elements in itself -
 especially when it could be a range which skips elements or something
 similar? So, _that_ part makes sense.
I don't understand why not. Given, as you said, that a lot of functions return a new type it would make sense. My answer as to how would be something like: while range not empty container.remove range.front range.popFront Is there a problem with that?
 But have you actually tried to get a range of the appropriate type to
 remove from a container? It seems like almost ever function in std.range
 and std.algorithm returns a new range type, making them completely useless
 for processing a range to be removed from a container.
 
 I was looking to remove a single element for a RedBlackTree. The best
 function that I could think to get the proper range was findSplit. The
 middle portion of the return value would be the portion that I was looking
 for. I'd take that and pass it to RedBlackTree's remove. Wrong. It uses
 takeExactly in its implementation and the first two portions of the result
 of findSplit aren't the right range type.
 
 So, what do I do? The _only_ thing that I can think of at the moment is to
 use find to locate the beginning of the range that I want, take the length
 of the range with walkLength and then use popBackN to pop of the elements
 I don't want. e.g.
The table in the docs mention stableRemoveAny(v) which says "Same as c.removeAny(v), but is guaranteed to not invalidate any iterators." Though c.removeAny(v) itself is not listed in the table nor implemented in RedBlackTree, isn't this the right function for the job? (I take it v stands for a value of the container, rather than a range). builtin aa's also implement this function.
Feb 22 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday 22 February 2011 01:04:48 Lutger Blijdestijn wrote:
 Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do
 stuff like removeAny (generally pretty useless IMHO) or removeFront just
 fine, but removing an arbitrary range from a container just plain sucks.
 
 remove takes a range type which is the range type for the container that
 it's on. That makes sense. It's obviously not going to be able to a take
 an arbitrary range and remove that from itself. How would it know which
 elements in that range corresponded to which elements in itself -
 especially when it could be a range which skips elements or something
 similar? So, _that_ part makes sense.
I don't understand why not. Given, as you said, that a lot of functions return a new type it would make sense. My answer as to how would be something like: while range not empty container.remove range.front range.popFront Is there a problem with that?
It's horribly inefficient for one. Also, I'm not sure that the range is valid any more after the remove, since it's front was removed. popFront may not work correctly.
 But have you actually tried to get a range of the appropriate type to
 remove from a container? It seems like almost ever function in std.range
 and std.algorithm returns a new range type, making them completely
 useless for processing a range to be removed from a container.
 
 I was looking to remove a single element for a RedBlackTree. The best
 function that I could think to get the proper range was findSplit. The
 middle portion of the return value would be the portion that I was
 looking for. I'd take that and pass it to RedBlackTree's remove. Wrong.
 It uses takeExactly in its implementation and the first two portions of
 the result of findSplit aren't the right range type.
 
 So, what do I do? The _only_ thing that I can think of at the moment is
 to use find to locate the beginning of the range that I want, take the
 length of the range with walkLength and then use popBackN to pop of the
 elements I don't want. e.g.
The table in the docs mention stableRemoveAny(v) which says "Same as c.removeAny(v), but is guaranteed to not invalidate any iterators." Though c.removeAny(v) itself is not listed in the table nor implemented in RedBlackTree, isn't this the right function for the job? (I take it v stands for a value of the container, rather than a range). builtin aa's also implement this function.
removeAny doesn't solve the problem. For starters, the table appears to be wrong in that stableRemoveAny takes a value and removeAny doesn't. So, either stableRemoveAny is supposed to not take a value or there's supposed to be another version of removeAny which takes a value, and it's missing. So, I don't know what exactly is intended with stableRemoveAny. Regardless of that, however, remove still needs to work. It's perfectly valid to want to remove a range of elements rather than just one. - Jonathan M Davis
Feb 22 2011
parent reply Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Jonathan M Davis wrote:

 On Tuesday 22 February 2011 01:04:48 Lutger Blijdestijn wrote:
 Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do
 stuff like removeAny (generally pretty useless IMHO) or removeFront
 just fine, but removing an arbitrary range from a container just plain
 sucks.
 
 remove takes a range type which is the range type for the container
 that it's on. That makes sense. It's obviously not going to be able to
 a take an arbitrary range and remove that from itself. How would it
 know which elements in that range corresponded to which elements in
 itself - especially when it could be a range which skips elements or
 something similar? So, _that_ part makes sense.
I don't understand why not. Given, as you said, that a lot of functions return a new type it would make sense. My answer as to how would be something like: while range not empty container.remove range.front range.popFront Is there a problem with that?
It's horribly inefficient for one. Also, I'm not sure that the range is valid any more after the remove, since it's front was removed. popFront may not work correctly.
It's a matter of range (in)validation right? I admit at this point I'm not sure how it is supposed to work. remove + popFront is a bad idea if the range is a view into the contained from where stuff is removed, but in c++ this works for map: some_map.erase(i++) where i is an iterator. So it depends on the type of container what is supported I think. But perhaps this falls under Walter's category of useless wankery, since it is easy to write yourself.
 But have you actually tried to get a range of the appropriate type to
 remove from a container? It seems like almost ever function in
 std.range and std.algorithm returns a new range type, making them
 completely useless for processing a range to be removed from a
 container.
 
 I was looking to remove a single element for a RedBlackTree. The best
 function that I could think to get the proper range was findSplit. The
 middle portion of the return value would be the portion that I was
 looking for. I'd take that and pass it to RedBlackTree's remove. Wrong.
 It uses takeExactly in its implementation and the first two portions of
 the result of findSplit aren't the right range type.
 
 So, what do I do? The _only_ thing that I can think of at the moment is
 to use find to locate the beginning of the range that I want, take the
 length of the range with walkLength and then use popBackN to pop of the
 elements I don't want. e.g.
The table in the docs mention stableRemoveAny(v) which says "Same as c.removeAny(v), but is guaranteed to not invalidate any iterators." Though c.removeAny(v) itself is not listed in the table nor implemented in RedBlackTree, isn't this the right function for the job? (I take it v stands for a value of the container, rather than a range). builtin aa's also implement this function.
removeAny doesn't solve the problem. For starters, the table appears to be wrong in that stableRemoveAny takes a value and removeAny doesn't. So, either stableRemoveAny is supposed to not take a value or there's supposed to be another version of removeAny which takes a value, and it's missing. So, I don't know what exactly is intended with stableRemoveAny. Regardless of that, however, remove still needs to work. It's perfectly valid to want to remove a range of elements rather than just one. - Jonathan M Davis
(stable)removeAny does not solve the problem of removing ranges, but there must be *something* that solves the problem of removing one element. You found one way to do it for RedBlackTree (i gave up), but if I am not mistaken it doesn't have the right complexity and efficient removal is a key property of this container.
Feb 22 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday 22 February 2011 03:52:34 Lutger Blijdestijn wrote:
 Jonathan M Davis wrote:
 On Tuesday 22 February 2011 01:04:48 Lutger Blijdestijn wrote:
 Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do
 stuff like removeAny (generally pretty useless IMHO) or removeFront
 just fine, but removing an arbitrary range from a container just plain
 sucks.
 
 remove takes a range type which is the range type for the container
 that it's on. That makes sense. It's obviously not going to be able to
 a take an arbitrary range and remove that from itself. How would it
 know which elements in that range corresponded to which elements in
 itself - especially when it could be a range which skips elements or
 something similar? So, _that_ part makes sense.
I don't understand why not. Given, as you said, that a lot of functions return a new type it would make sense. My answer as to how would be something like: while range not empty container.remove range.front range.popFront Is there a problem with that?
It's horribly inefficient for one. Also, I'm not sure that the range is valid any more after the remove, since it's front was removed. popFront may not work correctly.
It's a matter of range (in)validation right? I admit at this point I'm not sure how it is supposed to work. remove + popFront is a bad idea if the range is a view into the contained from where stuff is removed, but in c++ this works for map: some_map.erase(i++) where i is an iterator. So it depends on the type of container what is supported I think. But perhaps this falls under Walter's category of useless wankery, since it is easy to write yourself.
It depends on the implementation. It's possible that iterating an iterator or popping the front of a range where that iterator no longer points to a valid element actually works. It's also possible that, because it no longer points to a valid element, it _doesn't_ work. It wouldn't surprise me at all that some_map.erase(i++) isn't guaranteed to work in C++ at all but that you've just gotten lucky with the STL implementation that you've been using. I'd have to research it to be sure. But my guess would be that you've been lucky.
 But have you actually tried to get a range of the appropriate type to
 remove from a container? It seems like almost ever function in
 std.range and std.algorithm returns a new range type, making them
 completely useless for processing a range to be removed from a
 container.
 
 I was looking to remove a single element for a RedBlackTree. The best
 function that I could think to get the proper range was findSplit. The
 middle portion of the return value would be the portion that I was
 looking for. I'd take that and pass it to RedBlackTree's remove.
 Wrong. It uses takeExactly in its implementation and the first two
 portions of the result of findSplit aren't the right range type.
 
 So, what do I do? The _only_ thing that I can think of at the moment
 is to use find to locate the beginning of the range that I want, take
 the length of the range with walkLength and then use popBackN to pop
 of the elements I don't want. e.g.
The table in the docs mention stableRemoveAny(v) which says "Same as c.removeAny(v), but is guaranteed to not invalidate any iterators." Though c.removeAny(v) itself is not listed in the table nor implemented in RedBlackTree, isn't this the right function for the job? (I take it v stands for a value of the container, rather than a range). builtin aa's also implement this function.
removeAny doesn't solve the problem. For starters, the table appears to be wrong in that stableRemoveAny takes a value and removeAny doesn't. So, either stableRemoveAny is supposed to not take a value or there's supposed to be another version of removeAny which takes a value, and it's missing. So, I don't know what exactly is intended with stableRemoveAny. Regardless of that, however, remove still needs to work. It's perfectly valid to want to remove a range of elements rather than just one. - Jonathan M Davis
(stable)removeAny does not solve the problem of removing ranges, but there must be *something* that solves the problem of removing one element. You found one way to do it for RedBlackTree (i gave up), but if I am not mistaken it doesn't have the right complexity and efficient removal is a key property of this container.
If you could just do take or takeExactly on the range you got from find and pass it to remove, then it wouldn't matter whether you wanted to remove 1 element or many. The only difference is the number passed to take. The problem is that that doesn't work, because take returns the wrong range type. It has no way to get n elements from the front of the range and have them be in a range which is the same type as the orignal. So, I don't think that one element vs many is really the problem here. It's the inability to get the first n elements of a forward range and still retain the same range type. Regardless, you're right. the solution I found most definitely does _not_ have the right complexity. Because you have to use walkLength on the range that you get from find, it becomes O(n) instead of O(log n), and O(log n) is what it's _supposed_ to be for a red black tree. As I said, I don't believe that the current situation with remove is tenable, and the only solution that I see at the moment is to change forward range so that it has a function which returns the first n elements of that range with the same range type as that range. - Jonathan M Davis
Feb 22 2011
parent Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Jonathan M Davis wrote:

 On Tuesday 22 February 2011 03:52:34 Lutger Blijdestijn wrote:
 Jonathan M Davis wrote:
 On Tuesday 22 February 2011 01:04:48 Lutger Blijdestijn wrote:
 Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do
 stuff like removeAny (generally pretty useless IMHO) or removeFront
 just fine, but removing an arbitrary range from a container just
 plain sucks.
 
 remove takes a range type which is the range type for the container
 that it's on. That makes sense. It's obviously not going to be able
 to a take an arbitrary range and remove that from itself. How would
 it know which elements in that range corresponded to which elements
 in itself - especially when it could be a range which skips elements
 or something similar? So, _that_ part makes sense.
I don't understand why not. Given, as you said, that a lot of functions return a new type it would make sense. My answer as to how would be something like: while range not empty container.remove range.front range.popFront Is there a problem with that?
It's horribly inefficient for one. Also, I'm not sure that the range is valid any more after the remove, since it's front was removed. popFront may not work correctly.
It's a matter of range (in)validation right? I admit at this point I'm not sure how it is supposed to work. remove + popFront is a bad idea if the range is a view into the contained from where stuff is removed, but in c++ this works for map: some_map.erase(i++) where i is an iterator. So it depends on the type of container what is supported I think. But perhaps this falls under Walter's category of useless wankery, since it is easy to write yourself.
It depends on the implementation. It's possible that iterating an iterator or popping the front of a range where that iterator no longer points to a valid element actually works. It's also possible that, because it no longer points to a valid element, it _doesn't_ work. It wouldn't surprise me at all that some_map.erase(i++) isn't guaranteed to work in C++ at all but that you've just gotten lucky with the STL implementation that you've been using. I'd have to research it to be sure. But my guess would be that you've been lucky.
I'm fairly certain this is guaranteed, but specifically tied to std::map. The iterator returns the old value and is incremented before erasure, which doesn't invalidate iterators except the one that got removed.
 But have you actually tried to get a range of the appropriate type
 to remove from a container? It seems like almost ever function in
 std.range and std.algorithm returns a new range type, making them
 completely useless for processing a range to be removed from a
 container.
 
 I was looking to remove a single element for a RedBlackTree. The
 best function that I could think to get the proper range was
 findSplit. The middle portion of the return value would be the
 portion that I was looking for. I'd take that and pass it to
 RedBlackTree's remove. Wrong. It uses takeExactly in its
 implementation and the first two portions of the result of findSplit
 aren't the right range type.
 
 So, what do I do? The _only_ thing that I can think of at the moment
 is to use find to locate the beginning of the range that I want,
 take the length of the range with walkLength and then use popBackN
 to pop of the elements I don't want. e.g.
The table in the docs mention stableRemoveAny(v) which says "Same as c.removeAny(v), but is guaranteed to not invalidate any iterators." Though c.removeAny(v) itself is not listed in the table nor implemented in RedBlackTree, isn't this the right function for the job? (I take it v stands for a value of the container, rather than a range). builtin aa's also implement this function.
removeAny doesn't solve the problem. For starters, the table appears to be wrong in that stableRemoveAny takes a value and removeAny doesn't. So, either stableRemoveAny is supposed to not take a value or there's supposed to be another version of removeAny which takes a value, and it's missing. So, I don't know what exactly is intended with stableRemoveAny. Regardless of that, however, remove still needs to work. It's perfectly valid to want to remove a range of elements rather than just one. - Jonathan M Davis
(stable)removeAny does not solve the problem of removing ranges, but there must be *something* that solves the problem of removing one element. You found one way to do it for RedBlackTree (i gave up), but if I am not mistaken it doesn't have the right complexity and efficient removal is a key property of this container.
If you could just do take or takeExactly on the range you got from find and pass it to remove, then it wouldn't matter whether you wanted to remove 1 element or many. The only difference is the number passed to take. The problem is that that doesn't work, because take returns the wrong range type. It has no way to get n elements from the front of the range and have them be in a range which is the same type as the orignal. So, I don't think that one element vs many is really the problem here. It's the inability to get the first n elements of a forward range and still retain the same range type.
There are two problems I think. What if I want to remove an array of strings from a bst of strings? That should be supported, even if only by removing them one by one yourself. If all we got was remove(Range) then this scenario isn't supported at all. Another problem is the efficiency. With a bst, using find + take + remove has to locate the element twice (once for find, once for remove), whereas remove(value) would only need to do this once.
 Regardless, you're right. the solution I found most definitely does _not_
 have the right complexity. Because you have to use walkLength on the range
 that you get from find, it becomes O(n) instead of O(log n), and O(log n)
 is what it's _supposed_ to be for a red black tree. As I said, I don't
 believe that the current situation with remove is tenable, and the only
 solution that I see at the moment is to change forward range so that it
 has a function which returns the first n elements of that range with the
 same range type as that range.
 
 - Jonathan M Davis
Feb 22 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/22/11 3:04 AM, Lutger Blijdestijn wrote:
 The table in the docs mention stableRemoveAny(v) which says "Same as
 c.removeAny(v), but is guaranteed to not invalidate any iterators."

 Though c.removeAny(v) itself is not listed in the table nor implemented in
 RedBlackTree, isn't this the right function for the job? (I take it v stands
 for a value of the container, rather than a range). builtin aa's also
 implement this function.
I don't think removeAny() works for his case because he wants to remove a specific element from a container. removeAny() is useful when you want to express "pick one element from that container in the easiest way possible". Andrei
Feb 22 2011
parent Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Andrei Alexandrescu wrote:

 On 2/22/11 3:04 AM, Lutger Blijdestijn wrote:
 The table in the docs mention stableRemoveAny(v) which says "Same as
 c.removeAny(v), but is guaranteed to not invalidate any iterators."

 Though c.removeAny(v) itself is not listed in the table nor implemented
 in RedBlackTree, isn't this the right function for the job? (I take it v
 stands for a value of the container, rather than a range). builtin aa's
 also implement this function.
I don't think removeAny() works for his case because he wants to remove a specific element from a container. removeAny() is useful when you want to express "pick one element from that container in the easiest way possible". Andrei
I was looking for remove(ElementType value) but this function is not listed anywhere in std.container. The entry for stableRemoveAny(v) references removeAny(v) - note the parameter - so I thought that indicated the intent of a function removeAny(ElementType) but it doesn't exist in the table either. I assumed (mistakenly) that removeAny(v) would remove any value x where x == v from the container, where the choice of which would be left up to the container.
Feb 22 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/21/11 8:55 PM, Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do stuff like
 removeAny (generally pretty useless IMHO) or removeFront just fine, but
removing
 an arbitrary range from a container just plain sucks.

 remove takes a range type which is the range type for the container that it's
 on. That makes sense. It's obviously not going to be able to a take an
arbitrary
 range and remove that from itself. How would it know which elements in that
 range corresponded to which elements in itself - especially when it could be a
 range which skips elements or something similar? So, _that_ part makes sense.

 But have you actually tried to get a range of the appropriate type to remove
 from a container? It seems like almost ever function in std.range and
 std.algorithm returns a new range type, making them completely useless for
 processing a range to be removed from a container.

 I was looking to remove a single element for a RedBlackTree. The best function
 that I could think to get the proper range was findSplit. The middle portion of
 the return value would be the portion that I was looking for. I'd take that and
 pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
 implementation and the first two portions of the result of findSplit aren't the
 right range type.
It's good that positioned remove does not work with findSplit. It would be inefficient to use the wonderfully structured tree for linear search. The algorithm should be simple - find the key to delete in O(log n), then remove it.
 So, what do I do? The _only_ thing that I can think of at the moment is to use
 find to locate the beginning of the range that I want, take the length of the
 range with walkLength and then use popBackN to pop of the elements I don't
want.
[snip] What we need to do is add to RedBlackTree a function that accepts the result of take() - the same way SList does. It has only recently dawned on me that certain generic ranges are pivotal to algorithms and containers, and so far I identified take() and takeExactly() to be two such important ranges. One other thing that we can add to RedBlackTree is a simple removeKey() convenience method that does the find-and-remove thing. Any Phobos developer (including JMD of course :o)), please feel free to implement all of the above and submit it for pulling. And thanks Jonathan for using std.container - I am sure there are a few other wrinkles that will be revealed and then ironed out following consistent usage. Andrei
Feb 22 2011
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Feb 2011 08:01:24 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 2/21/11 8:55 PM, Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do  
 stuff like
 removeAny (generally pretty useless IMHO) or removeFront just fine, but  
 removing
 an arbitrary range from a container just plain sucks.

 remove takes a range type which is the range type for the container  
 that it's
 on. That makes sense. It's obviously not going to be able to a take an  
 arbitrary
 range and remove that from itself. How would it know which elements in  
 that
 range corresponded to which elements in itself - especially when it  
 could be a
 range which skips elements or something similar? So, _that_ part makes  
 sense.

 But have you actually tried to get a range of the appropriate type to  
 remove
 from a container? It seems like almost ever function in std.range and
 std.algorithm returns a new range type, making them completely useless  
 for
 processing a range to be removed from a container.

 I was looking to remove a single element for a RedBlackTree. The best  
 function
 that I could think to get the proper range was findSplit. The middle  
 portion of
 the return value would be the portion that I was looking for. I'd take  
 that and
 pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
 implementation and the first two portions of the result of findSplit  
 aren't the
 right range type.
It's good that positioned remove does not work with findSplit. It would be inefficient to use the wonderfully structured tree for linear search. The algorithm should be simple - find the key to delete in O(log n), then remove it.
This should be possible with equalRange. However, there can be needs to do a linear search on a RBT if you are not searching for keys. I think we definitely need take as a supported range in RBT (I didn't think so originally).
 So, what do I do? The _only_ thing that I can think of at the moment is  
 to use
 find to locate the beginning of the range that I want, take the length  
 of the
 range with walkLength and then use popBackN to pop of the elements I  
 don't want.
[snip] What we need to do is add to RedBlackTree a function that accepts the result of take() - the same way SList does. It has only recently dawned on me that certain generic ranges are pivotal to algorithms and containers, and so far I identified take() and takeExactly() to be two such important ranges. One other thing that we can add to RedBlackTree is a simple removeKey() convenience method that does the find-and-remove thing. Any Phobos developer (including JMD of course :o)), please feel free to implement all of the above and submit it for pulling. And thanks Jonathan for using std.container - I am sure there are a few other wrinkles that will be revealed and then ironed out following consistent usage.
I should be able to complete these improvements before the next release (excluding any quick-fix releases). Still need to learn git though... -Steve
Feb 22 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, February 22, 2011 05:01:24 Andrei Alexandrescu wrote:
 On 2/21/11 8:55 PM, Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do
 stuff like removeAny (generally pretty useless IMHO) or removeFront just
 fine, but removing an arbitrary range from a container just plain sucks.
 
 remove takes a range type which is the range type for the container that
 it's on. That makes sense. It's obviously not going to be able to a take
 an arbitrary range and remove that from itself. How would it know which
 elements in that range corresponded to which elements in itself -
 especially when it could be a range which skips elements or something
 similar? So, _that_ part makes sense.
 
 But have you actually tried to get a range of the appropriate type to
 remove from a container? It seems like almost ever function in std.range
 and std.algorithm returns a new range type, making them completely
 useless for processing a range to be removed from a container.
 
 I was looking to remove a single element for a RedBlackTree. The best
 function that I could think to get the proper range was findSplit. The
 middle portion of the return value would be the portion that I was
 looking for. I'd take that and pass it to RedBlackTree's remove. Wrong.
 It uses takeExactly in its implementation and the first two portions of
 the result of findSplit aren't the right range type.
It's good that positioned remove does not work with findSplit. It would be inefficient to use the wonderfully structured tree for linear search. The algorithm should be simple - find the key to delete in O(log n), then remove it.
Well, if RedBlackTree's remove gets changed to take the return values from take and takeExactly as you suggest below, then it _will_ work. Regardless, I don't think that findSplit is the best choice for this situation. It's just the best that I could think of given that take and takeExactly didn't work. I was then frustrated to discover that findSplit used takeExactly (though thinking about it now, given how forward ranges work, it's not like it could really do otherwise). removeKey is really what RedBlackTree needs for the most part, however. Removing a range from a RedBlackTree definitely makes sense in some cases, but usually you're looking to remove a particular element or set of elements which aren't necessarily in any specific order or adjacent in the tree (which implies that perhaps we need a removeKey(s) which takes a range of values - though not necessarily a range from RedBlackTree).
 So, what do I do? The _only_ thing that I can think of at the moment is
 to use find to locate the beginning of the range that I want, take the
 length of the range with walkLength and then use popBackN to pop of the
 elements I don't want.
[snip] What we need to do is add to RedBlackTree a function that accepts the result of take() - the same way SList does. It has only recently dawned on me that certain generic ranges are pivotal to algorithms and containers, and so far I identified take() and takeExactly() to be two such important ranges. One other thing that we can add to RedBlackTree is a simple removeKey() convenience method that does the find-and-remove thing. Any Phobos developer (including JMD of course :o)), please feel free to implement all of the above and submit it for pulling. And thanks Jonathan for using std.container - I am sure there are a few other wrinkles that will be revealed and then ironed out following consistent usage.
In this case, it probably makes sense to let Steve take care of it, since he's already working on it, though I may just add removeKey and submit a pull request which Steven can deal with as he sees appropriate, so that I can use it for what I'm doing. However, having found a fundamental flaw in how remove currently works with RedBlackTree, I thought it best to discuss how to solve the problem before making any changes to it anyway. Regardless, RedBlackTree is the container that I've been most missing in what I've been doing in D, so I'll definitely be using it in code now that I have it. By the way, are we looking at changing the containers to be classes by the next release (since, as I recall, you decided that we're definitely making that change)? That's one change that RedBlackTree could definitely benefit from (since you have to run one of its destructors for it to be set up correctly and it can't have a default constructor as a struct), and it's probably the sort of change that we should make sooner rather than later, since the longer that the types in std.container are structs, the more code it will break when they become classes. - Jonathan M Davis
Feb 22 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday 22 February 2011 05:01:24 Andrei Alexandrescu wrote:
 On 2/21/11 8:55 PM, Jonathan M Davis wrote:
 Okay, removing elements from a container sucks right now. You can do
 stuff like removeAny (generally pretty useless IMHO) or removeFront just
 fine, but removing an arbitrary range from a container just plain sucks.
 
 remove takes a range type which is the range type for the container that
 it's on. That makes sense. It's obviously not going to be able to a take
 an arbitrary range and remove that from itself. How would it know which
 elements in that range corresponded to which elements in itself -
 especially when it could be a range which skips elements or something
 similar? So, _that_ part makes sense.
 
 But have you actually tried to get a range of the appropriate type to
 remove from a container? It seems like almost ever function in std.range
 and std.algorithm returns a new range type, making them completely
 useless for processing a range to be removed from a container.
 
 I was looking to remove a single element for a RedBlackTree. The best
 function that I could think to get the proper range was findSplit. The
 middle portion of the return value would be the portion that I was
 looking for. I'd take that and pass it to RedBlackTree's remove. Wrong.
 It uses takeExactly in its implementation and the first two portions of
 the result of findSplit aren't the right range type.
It's good that positioned remove does not work with findSplit. It would be inefficient to use the wonderfully structured tree for linear search. The algorithm should be simple - find the key to delete in O(log n), then remove it.
 So, what do I do? The _only_ thing that I can think of at the moment is
 to use find to locate the beginning of the range that I want, take the
 length of the range with walkLength and then use popBackN to pop of the
 elements I don't want.
[snip] What we need to do is add to RedBlackTree a function that accepts the result of take() - the same way SList does. It has only recently dawned on me that certain generic ranges are pivotal to algorithms and containers, and so far I identified take() and takeExactly() to be two such important ranges. One other thing that we can add to RedBlackTree is a simple removeKey() convenience method that does the find-and-remove thing. Any Phobos developer (including JMD of course :o)), please feel free to implement all of the above and submit it for pulling. And thanks Jonathan for using std.container - I am sure there are a few other wrinkles that will be revealed and then ironed out following consistent usage.
I've made several improvements to RedBlackTree and created a pull request for them: https://github.com/D-Programming-Language/phobos/pull/10 - Jonathan M Davis
Feb 23 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 23 Feb 2011 07:01:12 -0500, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 I've made several improvements to RedBlackTree and created a pull  
 request for
 them: https://github.com/D-Programming-Language/phobos/pull/10
I'll be sure to look at this soon. I really need to ramp up my git skills... Anyone know where I can find a 30 hour day? ;) -Steve
Feb 23 2011
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, February 23, 2011 06:56:45 Steven Schveighoffer wrote:
 On Wed, 23 Feb 2011 07:01:12 -0500, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 I've made several improvements to RedBlackTree and created a pull
 request for
 them: https://github.com/D-Programming-Language/phobos/pull/10
I'll be sure to look at this soon. I really need to ramp up my git skills... Anyone know where I can find a 30 hour day? ;)
Yeah. It's hiding under couch, but sneaky. So, if you go looking, odds are you won't find it, and then you'll have even _fewer_ hours in the day. :) - Jonathan M Davis
Feb 23 2011
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 21 Feb 2011 21:55:20 -0500, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 Okay, removing elements from a container sucks right now. You can do  
 stuff like
 removeAny (generally pretty useless IMHO) or removeFront just fine, but  
 removing
 an arbitrary range from a container just plain sucks.

 remove takes a range type which is the range type for the container that  
 it's
 on. That makes sense. It's obviously not going to be able to a take an  
 arbitrary
 range and remove that from itself. How would it know which elements in  
 that
 range corresponded to which elements in itself - especially when it  
 could be a
 range which skips elements or something similar? So, _that_ part makes  
 sense.

 But have you actually tried to get a range of the appropriate type to  
 remove
 from a container? It seems like almost ever function in std.range and
 std.algorithm returns a new range type, making them completely useless  
 for
 processing a range to be removed from a container.

 I was looking to remove a single element for a RedBlackTree. The best  
 function
 that I could think to get the proper range was findSplit. The middle  
 portion of
 the return value would be the portion that I was looking for. I'd take  
 that and
 pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
 implementation and the first two portions of the result of findSplit  
 aren't the
 right range type.
RedBlackTree supports the equalRange function, which gives you a range of elements equal to the value you give. If your RedBlackTree does not support duplicate elements, then this should always be a 1 or zero element range, which you can then remove.
 That's disgusting. All that just to remove one element? And what if the  
 range
 isn't bidirectional (e.g. SList)? Well, then you have no popBack, and as  
 far as
 I can tell, you're screwed, since you can't use either take or  
 takeExactly,
 because both of them return new range types.
take is supported as a range type for SList. It is not for RedBlackTree because there are usually better ways to get ranges from the container. However, I can see reasons that take could be used. For example, in a RedBlackTree implementing a map, you may want to search for the first element that has a particular value (O(n) complexity find). In that case, you should be able to remove just one element. This should be added as a bugzilla report, and I'll add the ability to do take ranges to the red black tree. RBT is overdue for some improvements anyways (bearophile found quite a few shortfalls with it). But I see your point in that you should really be able to construct *any* type of range and have it work. I wonder if there is a way we could generalize "give me the implementation-specific representation of the first item *reference*" For example, in dcollections, we have the notion of cursors. The remove functions take either a cursor or a range. However, I could possibly extend the range removal function to allow any range type as long as the begin() member gives you the correct cursor type. -Steve
Feb 22 2011
next sibling parent reply Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Steven Schveighoffer wrote:

 On Mon, 21 Feb 2011 21:55:20 -0500, Jonathan M Davis <jmdavisProg gmx.com>
 wrote:
 
 Okay, removing elements from a container sucks right now. You can do
 stuff like
 removeAny (generally pretty useless IMHO) or removeFront just fine, but
 removing
 an arbitrary range from a container just plain sucks.

 remove takes a range type which is the range type for the container that
 it's
 on. That makes sense. It's obviously not going to be able to a take an
 arbitrary
 range and remove that from itself. How would it know which elements in
 that
 range corresponded to which elements in itself - especially when it
 could be a
 range which skips elements or something similar? So, _that_ part makes
 sense.

 But have you actually tried to get a range of the appropriate type to
 remove
 from a container? It seems like almost ever function in std.range and
 std.algorithm returns a new range type, making them completely useless
 for
 processing a range to be removed from a container.

 I was looking to remove a single element for a RedBlackTree. The best
 function
 that I could think to get the proper range was findSplit. The middle
 portion of
 the return value would be the portion that I was looking for. I'd take
 that and
 pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
 implementation and the first two portions of the result of findSplit
 aren't the
 right range type.
RedBlackTree supports the equalRange function, which gives you a range of elements equal to the value you give.
oo how I missed that. When you are working on RedBlackTree, would you please consider putting an example in the doc that uses it to this effect?
Feb 22 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Feb 2011 09:38:04 -0500, Lutger Blijdestijn  
<lutger.blijdestijn gmail.com> wrote:

 Steven Schveighoffer wrote:
 RedBlackTree supports the equalRange function, which gives you a range  
 of
 elements equal to the value you give.
oo how I missed that. When you are working on RedBlackTree, would you please consider putting an example in the doc that uses it to this effect?
I'm sorry you missed it, better docs is one of the planned improvements. Bearophile pointed out quite a few deficiencies which I need to work on. I'll be sure to make RedBlackTree a much more usable construct by the next release. -Steve
Feb 22 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/22/2011 03:13 PM, Steven Schveighoffer wrote:
 I wonder if there is a way we could generalize "give me the
 implementation-specific representation of the first item *reference*"
If this means a generalisation of what D's builtin 'in' provides, then I think this would be great. Then, passing back the 'reference' would provide _direct_ access (without [new] lookup) either to read, remove, change... Can't we unify this with your notion of cursor? What do you think? Denis -- _________________ vita es estrany spir.wikidot.com
Feb 22 2011