View mode: basic / threaded / horizontal-split · Log in · Help
February 22, 2011
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
Re: We need to rethink remove in std.container
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
1 2 3 4
Top | Discussion index | About this forum | D home