www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - sorting hidden data.

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
I'm adding a new class to dcollections -- Deque of STL fame.

A deque implements dcollections' List interface, and one of the  
requirements of the List interface is to be able to sort elements.

One important property of most dcollections containers is that data is not  
exposed.  This means you cannot get an address to the internal storage of  
elements.  The one exception is ArrayList (which purposely exposes its  
representation via an array).  I initially wanted to make Deque also hide  
its internals, but I ran into a significant snag.

std.algorithm.sort seems to require lvalue access to elements of a range,  
presumably so it can call swap on two elements during sorting.  So while a  
range can technically allow changing of data, it cannot be passed to swap.

e.g.

struct myrange
{
     property T front() {...}
     property T front(T t) {...}
    void popFront() {...}
     property bool empty() {...}
    myrange opSlice(size_t low, size_t hi) {...}
     property size_t length() {...}
}


You cannot use std.algorithm.sort on this range.

So my current workaround is to allow ref return on front().

My questions are:

1. Does it make sense to allow ref access to Deque?
2. Is there a way to use std.algorithm.sort on myrange above?
3. Might people have interest in a "property delegate" that allows one to  
pass the ability to set/get a property? e.g.:

auto pdelegate = getPropertyDelegate!"front"(r);

-Steve
Sep 29 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


Good news - you should be able to use sort on sealed ranges if they 
define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also 
sealed yet you can sort Zips no problem.

This is a relatively new addition.

Andrei
Sep 29 2010
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.
 This is a relatively new addition.
 Andrei


Actually, this gives me the opportunity to bring up a point I've been meaning to
bring up.  moveFront() and friends don't even need to be explicitly defined. 
The
module level function moveFront() in std.range defines default behavior in the
following cases:

1.  If the range's elements don't have elaborate copy construction, moveFront
just
forwards to front.

2.  If the range's elements are lvalues, std.algorithm.move(range.front) can
give
the proper behavior.

Of course, these are just defaults and can be overridden by explicitly defining
moveFront() even where they apply.  If range.moveFront() is explicitly defined,
the module level function always forwards to it no matter what.

The situation has gradually evolved into this state due to discussions on
Bugzilla
and the Phobos list and the impracticality of forcing explicit moveFront() on
all
ranges.  Unless it's still subject to change, it should probably be documented
somewhere.
Sep 29 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/29/10 9:52 PDT, dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.
 This is a relatively new addition.
 Andrei


 Actually, this gives me the opportunity to bring up a point I've been meaning
to
 bring up.  moveFront() and friends don't even need to be explicitly defined. 
The
 module level function moveFront() in std.range defines default behavior in the
 following cases:

 1.  If the range's elements don't have elaborate copy construction, moveFront
just
 forwards to front.

 2.  If the range's elements are lvalues, std.algorithm.move(range.front) can
give
 the proper behavior.

 Of course, these are just defaults and can be overridden by explicitly defining
 moveFront() even where they apply.  If range.moveFront() is explicitly defined,
 the module level function always forwards to it no matter what.

 The situation has gradually evolved into this state due to discussions on
Bugzilla
 and the Phobos list and the impracticality of forcing explicit moveFront() on
all
 ranges.  Unless it's still subject to change, it should probably be documented
 somewhere.


Yah. I've been with a foot in the air regarding this until Walter 
figures out what to do about the rule a.f(b) -> f(a, b).

Andrei
Sep 29 2010
parent reply Jacob Carlborg <doob me.com> writes:
On 2010-09-29 19:42, Andrei Alexandrescu wrote:

 On 9/29/10 9:52 PDT, dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article

 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during
 sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.
 This is a relatively new addition.
 Andrei


 Actually, this gives me the opportunity to bring up a point I've been
 meaning to
 bring up. moveFront() and friends don't even need to be explicitly
 defined. The
 module level function moveFront() in std.range defines default
 behavior in the
 following cases:

 1. If the range's elements don't have elaborate copy construction,
 moveFront just
 forwards to front.

 2. If the range's elements are lvalues,
 std.algorithm.move(range.front) can give
 the proper behavior.

 Of course, these are just defaults and can be overridden by explicitly
 defining
 moveFront() even where they apply. If range.moveFront() is explicitly
 defined,
 the module level function always forwards to it no matter what.

 The situation has gradually evolved into this state due to discussions
 on Bugzilla
 and the Phobos list and the impracticality of forcing explicit
 moveFront() on all
 ranges. Unless it's still subject to change, it should probably be
 documented
 somewhere.


 Yah. I've been with a foot in the air regarding this until Walter
 figures out what to do about the rule a.f(b) -> f(a, b).

 Andrei


Would that be the uniform function call syntax that I've been waiting 
for since I first heard of it?

-- 
/Jacob Carlborg
Sep 29 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/29/10 13:10 PDT, Jacob Carlborg wrote:

 Would that be the uniform function call syntax that I've been waiting
 for since I first heard of it?


Yah. One unpleasant issue I found with it (as it's already implemented 
for arrays) is a chicken-and-egg thing: say I want to provide operation 
moveFront only if the type doesn't define it yet. Without UCF (Uniform 
Call Syntax) things are simple:

auto moveFront(R)(ref R r)
if (!is(typeof(r.moveFront())) && !hasElaborateCopy!(ElementType!R)) {
     return r.front;
}

With UCF things get messy because introducing moveFront at global level 
does make r.moveFront() legit, so the if clause returns true, which is 
weird because the function shouldn't have been introduced yet. So the 
compiler gets confused by this lying Cretan riddle - it recurses forever 
(when R is an array).

The solution would be probably to not consider the symbol introduced 
until the if-clause has cleared.


Andrei
Sep 29 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 29 Sep 2010 16:37:34 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 13:10 PDT, Jacob Carlborg wrote:

 Would that be the uniform function call syntax that I've been waiting
 for since I first heard of it?


 Yah. One unpleasant issue I found with it (as it's already implemented  
 for arrays) is a chicken-and-egg thing: say I want to provide operation  
 moveFront only if the type doesn't define it yet. Without UCF (Uniform  
 Call Syntax) things are simple:

 auto moveFront(R)(ref R r)
 if (!is(typeof(r.moveFront())) && !hasElaborateCopy!(ElementType!R)) {
      return r.front;
 }

 With UCF things get messy because introducing moveFront at global level  
 does make r.moveFront() legit, so the if clause returns true, which is  
 weird because the function shouldn't have been introduced yet. So the  
 compiler gets confused by this lying Cretan riddle - it recurses forever  
 (when R is an array).

 The solution would be probably to not consider the symbol introduced  
 until the if-clause has cleared.


__traits(hasMember, r, "moveFront") && rest_of_expression_you_had

-Steve
Oct 04 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/4/10 6:29 CDT, Steven Schveighoffer wrote:

 On Wed, 29 Sep 2010 16:37:34 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 13:10 PDT, Jacob Carlborg wrote:

 Would that be the uniform function call syntax that I've been waiting
 for since I first heard of it?


 Yah. One unpleasant issue I found with it (as it's already implemented
 for arrays) is a chicken-and-egg thing: say I want to provide
 operation moveFront only if the type doesn't define it yet. Without
 UCF (Uniform Call Syntax) things are simple:

 auto moveFront(R)(ref R r)
 if (!is(typeof(r.moveFront())) && !hasElaborateCopy!(ElementType!R)) {
 return r.front;
 }

 With UCF things get messy because introducing moveFront at global
 level does make r.moveFront() legit, so the if clause returns true,
 which is weird because the function shouldn't have been introduced
 yet. So the compiler gets confused by this lying Cretan riddle - it
 recurses forever (when R is an array).

 The solution would be probably to not consider the symbol introduced
 until the if-clause has cleared.


 __traits(hasMember, r, "moveFront") && rest_of_expression_you_had

 -Steve


Yah, I know - in fact I added a trait hasMember(T, "name") to std.traits 
that hides the __traits. For some reason that still has issues, probably 
due to lack of short-circuit evaluation of && during compilation (but 
I'm not positive).

Things are still unpleasant even assuming that works, so I think we need 
to look into that when considering committing to uniform call syntax.


Andrei
Oct 04 2010
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 29 Sep 2010 12:26:39 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they  
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also  
 sealed yet you can sort Zips no problem.

 This is a relatively new addition.


I'm not liking this...

How many more boiler-plate functions will we be forced to add in order to  
support standard ranges?  save() was bad enough, this is three more, when  
the functionality *already exists*.

Can't sort just use:

x = r1.front;
r1.front = r2.front;
r2.front = x;

???

-Steve
Sep 29 2010
next sibling parent Pelle <pelle.mansson gmail.com> writes:
On 09/29/2010 07:10 PM, Steven Schveighoffer wrote:

 On Wed, 29 Sep 2010 12:26:39 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.

 This is a relatively new addition.


 I'm not liking this...

 How many more boiler-plate functions will we be forced to add in order
 to support standard ranges? save() was bad enough, this is three more,
 when the functionality *already exists*.

 Can't sort just use:

 x = r1.front;
 r1.front = r2.front;
 r2.front = x;

 ???

 -Steve


I'm agreeing with this. Maybe because I don't really understand what 
move() and friends are good for.
Sep 29 2010
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/29/10 10:10 PDT, Steven Schveighoffer wrote:

 On Wed, 29 Sep 2010 12:26:39 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.

 This is a relatively new addition.


 I'm not liking this...

 How many more boiler-plate functions will we be forced to add in order
 to support standard ranges? save() was bad enough, this is three more,
 when the functionality *already exists*.

 Can't sort just use:

 x = r1.front;
 r1.front = r2.front;
 r2.front = x;

 ???

 -Steve


It could, if we decided to punt on types with expensive constructors.

Andrei
Sep 29 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 29 Sep 2010 13:25:23 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 10:10 PDT, Steven Schveighoffer wrote:

 On Wed, 29 Sep 2010 12:26:39 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting.  
 So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.

 This is a relatively new addition.


 I'm not liking this...

 How many more boiler-plate functions will we be forced to add in order
 to support standard ranges? save() was bad enough, this is three more,
 when the functionality *already exists*.

 Can't sort just use:

 x = r1.front;
 r1.front = r2.front;
 r2.front = x;

 ???

 -Steve


 It could, if we decided to punt on types with expensive constructors.


What I mean is, why is it automatically assumed that if front does not  
return a ref, the only way to swap is via moveX?  If T == int, why must we  
have a moveFront to deal with it?  IMO, all algorithms should default to  
copying unless alternatives exist.

 From what I understand, moveFront is going to be *more* expensive, since  
it has to zero out the original.  While this is fine for some types, it's  
not fine for simple types.

-Steve
Sep 29 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/29/10 10:43 PDT, Steven Schveighoffer wrote:

 What I mean is, why is it automatically assumed that if front does not
 return a ref, the only way to swap is via moveX? If T == int, why must
 we have a moveFront to deal with it? IMO, all algorithms should default
 to copying unless alternatives exist.


Good point. We should arrange things such that all types without 
elaborate copy constructors allow swapping by copying.

Could you please bugzillize this so it's not forgotten?


Thanks,

Andrei
Sep 29 2010
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 29 Sep 2010 15:46:19 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 9/29/10 10:43 PDT, Steven Schveighoffer wrote:

 What I mean is, why is it automatically assumed that if front does not
 return a ref, the only way to swap is via moveX? If T == int, why must
 we have a moveFront to deal with it? IMO, all algorithms should default
 to copying unless alternatives exist.


 Good point. We should arrange things such that all types without  
 elaborate copy constructors allow swapping by copying.


Well, this isn't exactly what I said, but it makes sense.  If there is an  
elaborate copy constructor, then you shouldn't be calling it frequently.   
But then at the same time, isn't front() expected to be a fast operation?   
It's kind of the basis of most algorithms anyways, no?

So if you build a range that returns T by value in front(), are you to not  
expect that people will call front() frequently?  How does foreach perform  
on such an "elaborate copy constructor" range?

I think there's a broken concept here somewhere...


 Could you please bugzillize this so it's not forgotten?


I will, I'll just wait a bit in case there are more responses.

-Steve
Sep 29 2010
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, September 29, 2010 12:55:40 Steven Schveighoffer wrote:

 On Wed, 29 Sep 2010 15:46:19 -0400, Andrei Alexandrescu
 
 <SeeWebsiteForEmail erdani.org> wrote:

 On 9/29/10 10:43 PDT, Steven Schveighoffer wrote:

 What I mean is, why is it automatically assumed that if front does not
 return a ref, the only way to swap is via moveX? If T == int, why must
 we have a moveFront to deal with it? IMO, all algorithms should default
 to copying unless alternatives exist.


 
 Good point. We should arrange things such that all types without
 elaborate copy constructors allow swapping by copying.


 
 Well, this isn't exactly what I said, but it makes sense.  If there is an
 elaborate copy constructor, then you shouldn't be calling it frequently.
 But then at the same time, isn't front() expected to be a fast operation?
 It's kind of the basis of most algorithms anyways, no?
 
 So if you build a range that returns T by value in front(), are you to not
 expect that people will call front() frequently?  How does foreach perform
 on such an "elaborate copy constructor" range?
 
 I think there's a broken concept here somewhere...


The real problem then is in any structs with elaborate copy constructors, isn't 
it? Essentially, it's foolish to put something which is expensive to copy in a 
situation where it's going to be copied much, if at all. So, essentially, any 
user who creates such a struct and then tries to use it with ranges is shooting 
themselves in the foot performance-wise. And Andrei thinks that this is a big 
enough issue to give them a way not to shoot themselves in the foot. I'm not 
sure that I agree, but I don't know that he's wrong either. Worrying about it
is 
certainly complicating ranges though.

- Jonathan M Davis
Sep 29 2010
prev sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 On 9/29/10 10:43 PDT, Steven Schveighoffer wrote:

 What I mean is, why is it automatically assumed that if front does not
 return a ref, the only way to swap is via moveX? If T == int, why must
 we have a moveFront to deal with it? IMO, all algorithms should default
 to copying unless alternatives exist.


 Good point. We should arrange things such that all types without
 elaborate copy constructors allow swapping by copying.
 Could you please bugzillize this so it's not forgotten?
 Thanks,
 Andrei


This should already work (I noticed that it didn't a long time ago and checked
in
the fix, but I don't remember how thoroughly I tested the fix).  Here's the
relevant snippet from std.algorithm:

 	void swapAt(R)(R r, size_t i1, size_t i2)
 	{
 	    static if (is(typeof(&r[i1])))
 	    {
 	        swap(r[i1], r[i2]);
 	    }
 	    else
 	    {
 	        if (i1 == i2) return;
 	        auto t1 = moveAt(r, i1);
 	        auto t2 = moveAt(r, i2);
 	        r[i2] = t1;
 	        r[i1] = t2;
 	    }
 	}

moveAt() simply copies if the range doesn't provide an explicit moveAt() and the
element type doesn't have an elaborate copy constructor.
Sep 29 2010
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Steven Schveighoffer (schveiguy yahoo.com)'s article

 On Wed, 29 Sep 2010 12:26:39 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 9/29/10 6:22 PDT, Steven Schveighoffer wrote:

 std.algorithm.sort seems to require lvalue access to elements of a
 range, presumably so it can call swap on two elements during sorting. So
 while a range can technically allow changing of data, it cannot be
 passed to swap.

 e.g.

 struct myrange
 {
  property T front() {...}
  property T front(T t) {...}
 void popFront() {...}
  property bool empty() {...}
 myrange opSlice(size_t low, size_t hi) {...}
  property size_t length() {...}
 }


 Good news - you should be able to use sort on sealed ranges if they
 define moveFront, moveBack, and moveAt. Look e.g. at Zip, it's also
 sealed yet you can sort Zips no problem.

 This is a relatively new addition.


 I'm not liking this...
 How many more boiler-plate functions will we be forced to add in order to
 support standard ranges?  save() was bad enough, this is three more, when
 the functionality *already exists*.
 Can't sort just use:
 x = r1.front;
 r1.front = r2.front;
 r2.front = x;
 ???
 -Steve


I somewhat agree, but apparently noone noticed my other post.  moveFront() and
friends **have default behavior** via the module level function
std.range.moveFront() in most cases, and when they don't it is for a good
reason.
 If Phobos directly calls the object's moveFront() instead of using the module
level one with this default behavior, then IMHO it's **a bug**.  Please read my
post from ~an hour ago on this default behavior.
Sep 29 2010
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 29 Sep 2010 13:40:49 -0400, dsimcha <dsimcha yahoo.com> wrote:


 I somewhat agree, but apparently noone noticed my other post.   
 moveFront() and
 friends **have default behavior** via the module level function
 std.range.moveFront() in most cases, and when they don't it is for a  
 good reason.
  If Phobos directly calls the object's moveFront() instead of using the  
 module
 level one with this default behavior, then IMHO it's **a bug**.  Please  
 read my
 post from ~an hour ago on this default behavior.


I did see your other post.  From reading the docs for moveFront and  
friends, it appears that you are supposed to leave the original in a  
default "empty shell" state.  But that makes no sense in terms of simple  
types, like an int, or some POD struct.  Am I wrong on this?

But I agree with the gist of your post -- I should not have to define  
moveFront and friends if it makes no sense to.

One problem I see here is, unless your range is specific to the element  
type, you have to deal with moveFront and friends.  Because someone could  
use an element type that wants a moveFront-style swap.  And this will  
almost certainly be boilerplate code.  where's that std.mixins module? :)

The easiest thing, and probably the most appropriate, is to just return  
ref from my Deque range.  That avoids having to define moveFront, and sort  
still works with it.  As far as danger of exposing internals, I'm not  
manually managing the memory anyways (it just uses array appending).

But on a higher-level note, I feel ranges are becoming more complex than  
I'd like.  The first time I heard of a range, it was a simple wrapper for  
two iterators.  Soon, you might need a whole book to determine how to  
properly implement ranges so they fit into the correct algorithms.  It  
would appear to be enough to just statically assert a range is a certain  
type, but I think you might actually have to assert that it's not other  
types.  Duck typing is great for using libraries, but it's a pain for  
writing them.

-Steve
Sep 29 2010
prev sibling parent reply BLS <windevguy hotmail.de> writes:
On 29/09/2010 15:22, Steven Schveighoffer wrote:

 I'm adding a new class to dcollections -- Deque of STL fame.


Hi Steve,
thank you for adding the dequeue data structure! :)

since you have trouble regarding my email address
.. nanali at wanadoo fr

would be nice if we can discuss (and hopefully implement) container 
triggers and left leaning rb trees as well as  skiplists as rb tree 
replacement/plugin data-structure.

Bjoern
Sep 29 2010
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 29 Sep 2010 14:07:36 -0400, BLS <windevguy hotmail.de> wrote:


 On 29/09/2010 15:22, Steven Schveighoffer wrote:

 I'm adding a new class to dcollections -- Deque of STL fame.


 Hi Steve,
 thank you for adding the dequeue data structure! :)


hehe, I haven't had any real interesting D projects to do for a while :)   
It seemed like a good challenge


 since you have trouble regarding my email address
 .. nanali at wanadoo fr


Sent you a mail, hopefully it goes through.


 would be nice if we can discuss (and hopefully implement) container  
 triggers and left leaning rb trees as well as  skiplists as rb tree  
 replacement/plugin data-structure.


Definitely.

-Steve
Sep 29 2010