February 22, 2011
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
February 22, 2011
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
February 22, 2011
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?

February 22, 2011
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
February 22, 2011
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
February 22, 2011
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

February 22, 2011
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
February 22, 2011
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
February 22, 2011
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) { ... }


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 = 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.
February 22, 2011
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