www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Removing elements from dynamic arrays?

reply Bill Baxter <dnewsgroup billbaxter.com> writes:
How do I remove an element from a dynamic array?

    int[] a = [1,2,3,4,5];

I tried every syntax I could think of:

    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];

The last one compiles, but fills a[0] with garbage.

I hope the answer isn't:

    a = a[0..3] ~ a[4..length];

Thanks!
--bb
Oct 29 2006
next sibling parent Lionello Lunesu <lio lunesu.remove.com> writes:
Bill Baxter wrote:

 How do I remove an element from a dynamic array?
 
    int[] a = [1,2,3,4,5];
 
 I tried every syntax I could think of:
 
    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];
 
 The last one compiles, but fills a[0] with garbage.
 
 I hope the answer isn't:
 
    a = a[0..3] ~ a[4..length];
 
 Thanks!
 --bb


 From a COW (copy on write) standpoint, that last one is the only safe 
one, i.e: a = a[0..x] ~ a[x+1..$]; with 'x' the index of the element you 
want to remove.

If you don't need COW and don't care for the order of the elements, you 
can do this: a[x] = a[$-1]; a.length = a.length - 1; //a.length-- won't work

L.
Oct 30 2006
prev sibling next sibling parent Karen Lanrap <karen digitaldaemon.com> writes:
Bill Baxter wrote:


 How do I remove an element from a dynamic array?


To me it is not clear what you mean by "remove".

Are you talking about associative arrays?
Oct 30 2006
prev sibling next sibling parent reply David Medlock <noone nowhere.com> writes:
Bill Baxter wrote:

 How do I remove an element from a dynamic array?
 
    int[] a = [1,2,3,4,5];
 
 I tried every syntax I could think of:
 
    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];
 
 The last one compiles, but fills a[0] with garbage.
 
 I hope the answer isn't:
 
    a = a[0..3] ~ a[4..length];
 
 Thanks!
 --bb



 From my personal tools library...

// remove an item from an array
template drop(T)
{
   T drop( inout T[] arr, int which )
   {
     debug if ( which>=arr.length)
         throw new Exception(str.format("Attempt to drop position %s 
from size %s",which,arr.length));
     T result = arr[which];
     int max = arr.length-1;
     for (; which < max; which++ ) arr[which]=arr[which+1];
     arr.length= max;
     return result;
   }
}


Even though it returns the array, it modifies it in place.

-DavidM
Oct 30 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
David Medlock wrote:

 Bill Baxter wrote:

 How do I remove an element from a dynamic array?

    int[] a = [1,2,3,4,5];

 I tried every syntax I could think of:

    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];

 The last one compiles, but fills a[0] with garbage.

 I hope the answer isn't:

    a = a[0..3] ~ a[4..length];

 Thanks!
 --bb


 
 
  From my personal tools library...
 
 // remove an item from an array
 template drop(T)
 {
   T drop( inout T[] arr, int which )
   {
     debug if ( which>=arr.length)
         throw new Exception(str.format("Attempt to drop position %s from 
 size %s",which,arr.length));
     T result = arr[which];
     int max = arr.length-1;
     for (; which < max; which++ ) arr[which]=arr[which+1];
     arr.length= max;
     return result;
   }
 }
 
 
 Even though it returns the array, it modifies it in place.
 
 -DavidM


Thanks David, this seems like the best answer in terms of efficiency, 
although I suppose the
     a = a[0..3] ~ a[4..length];
could theoretically be pretty similar depending how the compiler 
implements it.


There really should be syntax in the language or at least functions like 
the above in the standard library for this (and for removing slices). 
Otherwise std::vector starts to look handy compared to D arrays, and you 
don't want that! ;-)  Built-in arrays are supposed to be easier to use 
than library code, after all.

     // Erases the element at position pos.
     iterator std::vector::erase(iterator pos)
     //Erases the range [first, last)
     iterator std::vector::erase(iterator first, iterator last)

Other than that, it looks like arrays support a sane syntax for 
everything std::vector has, except maybe

     std::vector::reserve()/std::vector::capacity()

which has also been discussed recently.

--bb
Oct 30 2006
next sibling parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Bill Baxter wrote:


 best answer in terms of efficiency


For me removing an element does not affect other elements.
Oct 30 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Karen Lanrap wrote:

 Bill Baxter wrote:
 

 best answer in terms of efficiency


 
 For me removing an element does not affect other elements.


Then I think you want a linked list, not an array.

--bb
Oct 30 2006
parent Karen Lanrap <karen digitaldaemon.com> writes:
Bill Baxter wrote:


 Then I think you want a linked list, not an array.


The diversity of answers in this thread shows that there is no 
canonical remove operation for arrays. One can define some operation 
to be called a "remove" operation, but that is by pure will, when the 
invariants that have to be maintained are unknown.
Oct 31 2006
prev sibling parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bill Baxter wrote:

 David Medlock wrote:
 

 Bill Baxter wrote:


 How do I remove an element from a dynamic array?

    int[] a = [1,2,3,4,5];

 I tried every syntax I could think of:

    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];

 The last one compiles, but fills a[0] with garbage.

 I hope the answer isn't:

    a = a[0..3] ~ a[4..length];

 Thanks!
 --bb




  From my personal tools library...

 // remove an item from an array
 template drop(T)
 {
   T drop( inout T[] arr, int which )
   {
     debug if ( which>=arr.length)
         throw new Exception(str.format("Attempt to drop position %s 
 from size %s",which,arr.length));
     T result = arr[which];
     int max = arr.length-1;
     for (; which < max; which++ ) arr[which]=arr[which+1];
     arr.length= max;
     return result;
   }
 }




Something you might find interesting/indicative -- I wrote a little test
program to time 
your function versus that found in Cashew, and with the slicing expression
above.  Output:












Drop v2 was an attempt of mine at rewriting your .drop() that, obviously, falls
a little 
short of the original in performance.  I also find it odd that Cashew's
.removeIndex() is 
actually timing a little master than the slice expression, because that's
actually it is: 
a wrapper around that very same expression.  *confused*  Anyhow, clearly your
.drop() is 
running very fast!  I actually expected the opposite, and am
surprised/impressed.

Maybe you should release it into Cashew?  ;)  And maybe I should put more into 
benchmarking the entire Cashew array module.  There might be a few more placed
it could be 
sped up.


 Even though it returns the array, it modifies it in place.

 -DavidM


 
 
 Thanks David, this seems like the best answer in terms of efficiency, 
 although I suppose the
     a = a[0..3] ~ a[4..length];
 could theoretically be pretty similar depending how the compiler 
 implements it.
 
 
 There really should be syntax in the language or at least functions like 
 the above in the standard library for this (and for removing slices). 








etc.

That's why I maintain those.  Hopefully, eventually, it does spawn a standard
library 
module.  (I'm always looking for ways to further optimize them, but I do want
to keep them 
fairly simple.)

-- Chris Nicholson-Sauls
Oct 31 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Chris Nicholson-Sauls wrote:

 
 Anyhow, clearly 
 your .drop() is running very fast!  I actually expected the opposite, 
 and am surprised/impressed.
 
 Maybe you should release it into Cashew?  ;)  And maybe I should put 
 more into benchmarking the entire Cashew array module.  There might be a 
 few more placed it could be sped up.


I'd be interested in seeing a test using C's memmove as well.  Though 
I'm not surprised drop beats the slice version, since that will allocate 
a new array for the data.


Sean
Oct 31 2006
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Sean Kelly wrote:

 Chris Nicholson-Sauls wrote:
 

 Anyhow, clearly your .drop() is running very fast!  I actually 
 expected the opposite, and am surprised/impressed.

 Maybe you should release it into Cashew?  ;)  And maybe I should put 
 more into benchmarking the entire Cashew array module.  There might be 
 a few more placed it could be sped up.


 
 
 I'd be interested in seeing a test using C's memmove as well.  Though 
 I'm not surprised drop beats the slice version, since that will allocate 
 a new array for the data.
 
 
 Sean


Well, I just benchmarked the memmove() based approach, and it is indeed notably
faster 
still.  Here's a typical sample from the results:

<Benchmark traverse vs memmove> Baseline 3.130000
<Benchmark traverse vs memmove> Time 1.760000 & 1.778409 versus baseline

(Where the baseline was the current .drop() and the contender was a .drop()
using 
memmove().)  So, indeed, I am migrating Cashew to use memmove().  I may also
modify 
.dropIf() to use it as well.

-- Chris Nicholson-Sauls
Nov 03 2006
prev sibling next sibling parent reply David Medlock <noone nowhere.com> writes:
Chris Nicholson-Sauls wrote:

 Bill Baxter wrote:
 

 David Medlock wrote:


 Bill Baxter wrote:


 How do I remove an element from a dynamic array?

    int[] a = [1,2,3,4,5];

 I tried every syntax I could think of:

    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];

 The last one compiles, but fills a[0] with garbage.

 I hope the answer isn't:

    a = a[0..3] ~ a[4..length];

 Thanks!
 --bb





  From my personal tools library...

 // remove an item from an array
 template drop(T)
 {
   T drop( inout T[] arr, int which )
   {
     debug if ( which>=arr.length)
         throw new Exception(str.format("Attempt to drop position %s 
 from size %s",which,arr.length));
     T result = arr[which];
     int max = arr.length-1;
     for (; which < max; which++ ) arr[which]=arr[which+1];
     arr.length= max;
     return result;
   }
 }




 
 
 Something you might find interesting/indicative -- I wrote a little test 
 program to time your function versus that found in Cashew, and with the 
 slicing expression above.  Output:
 










 
 Drop v2 was an attempt of mine at rewriting your .drop() that, 
 obviously, falls a little short of the original in performance.  I also 
 find it odd that Cashew's .removeIndex() is actually timing a little 
 master than the slice expression, because that's actually it is: a 
 wrapper around that very same expression.  *confused*  Anyhow, clearly 
 your .drop() is running very fast!  I actually expected the opposite, 
 and am surprised/impressed.
 
 Maybe you should release it into Cashew?  ;)  And maybe I should put 
 more into benchmarking the entire Cashew array module.  There might be a 
 few more placed it could be sped up.
 

 Even though it returns the array, it modifies it in place.

 -DavidM




 Thanks David, this seems like the best answer in terms of efficiency, 
 although I suppose the
     a = a[0..3] ~ a[4..length];
 could theoretically be pretty similar depending how the compiler 
 implements it.


 There really should be syntax in the language or at least functions 
 like the above in the standard library for this (and for removing 
 slices). 


 
 






 etc.
 
 That's why I maintain those.  Hopefully, eventually, it does spawn a 
 standard library module.  (I'm always looking for ways to further 
 optimize them, but I do want to keep them fairly simple.)
 
 -- Chris Nicholson-Sauls


Its public domain.  Free to use in any way you wish.

-DavidM

For giggles I posted the conditional version(also public domain):

// remove items based on a predicate. returns number of items removed
template drop_if(T)
{
   int drop_if( T[] arr, bool delegate(T)pred )
   {
     int count = 0, dest=0;
     foreach( int index, T val ; arr )
     {
       if ( pred(val) ) { count++; continue; }
       if ( dest !=index ) arr[index] = dest;
       dest++;
     }
     return count;
   }
}
Oct 31 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
David Medlock wrote:


 For giggles I posted the conditional version(also public domain):
 
 // remove items based on a predicate. returns number of items removed
 template drop_if(T)
 {
   int drop_if( T[] arr, bool delegate(T)pred )
   {
     int count = 0, dest=0;
     foreach( int index, T val ; arr )
     {
       if ( pred(val) ) { count++; continue; }
       if ( dest !=index ) arr[index] = dest;
       dest++;
     }
     return count;
   }
 }
 


And here's the range-dropping version:

template drop_range(T)
{
   void drop_range( inout T[] arr, int start, int end )
   {
     debug if ( start>=arr.length && end > arr.length)
         throw new Exception(format("Attempt to drop range %s,%s from 
size %s",start,end,arr.length));
     if (start>=end) return;
     size_t len = end-start;
     size_t max = arr.length-len;
     for (; start < max; start++ ) arr[start]=arr[start+len];
     arr.length= max;
   }
}
Nov 01 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Bill Baxter wrote:

 David Medlock wrote:
 

 For giggles I posted the conditional version(also public domain):

 // remove items based on a predicate. returns number of items removed
 template drop_if(T)
 {
   int drop_if( T[] arr, bool delegate(T)pred )
   {
     int count = 0, dest=0;
     foreach( int index, T val ; arr )
     {
       if ( pred(val) ) { count++; continue; }
       if ( dest !=index ) arr[index] = dest;
       dest++;
     }
     return count;
   }
 }


 


And here's a better range-dropping version:

// Remove a range of elements from an array in place.
// It is not an error for the range to be empty or for start to be
// greater than end. If so, the array is not modified.
// Out of bounds checks performed only in debug mode.
// Returns: the array for convenience (but it is modified in-place).
// Note: This is an O(n) operation.
template drop_range(T)
{
   T[] drop_range( inout T[] arr, int start, int end )
   {
     debug if ( start>=arr.length || end > arr.length || start<0 || end<0)
         throw new Exception(format("Attempt to drop range %s,%s from 
size %s",start,end,arr.length));
     if (start>=end) return arr;
     size_t len = end-start;
     size_t max = arr.length-len;
     for (; start < max; start++ ) arr[start]=arr[start+len];
     arr.length= max;
     return arr;
   }
}

--bb
Nov 01 2006
parent David Medlock <noone nowhere.com> writes:
Bill Baxter wrote:

 Bill Baxter wrote:
 

 David Medlock wrote:


 For giggles I posted the conditional version(also public domain):

 // remove items based on a predicate. returns number of items removed
 template drop_if(T)
 {
   int drop_if( T[] arr, bool delegate(T)pred )
   {
     int count = 0, dest=0;
     foreach( int index, T val ; arr )
     {
       if ( pred(val) ) { count++; continue; }
       if ( dest !=index ) arr[index] = dest;
       dest++;
     }
     return count;
   }
 }




 
 And here's a better range-dropping version:
 
 // Remove a range of elements from an array in place.
 // It is not an error for the range to be empty or for start to be
 // greater than end. If so, the array is not modified.
 // Out of bounds checks performed only in debug mode.
 // Returns: the array for convenience (but it is modified in-place).
 // Note: This is an O(n) operation.
 template drop_range(T)
 {
   T[] drop_range( inout T[] arr, int start, int end )
   {
     debug if ( start>=arr.length || end > arr.length || start<0 || end<0)
         throw new Exception(format("Attempt to drop range %s,%s from 
 size %s",start,end,arr.length));
     if (start>=end) return arr;
     size_t len = end-start;
     size_t max = arr.length-len;
     for (; start < max; start++ ) arr[start]=arr[start+len];
     arr.length= max;
     return arr;
   }
 }
 
 --bb


Lets combine all these with what Oskar has and get them into Phobos!

Since arrays are built into the language, these should come with the 
standard library.

-DavidM
Nov 01 2006
prev sibling next sibling parent reply Fredrik Olsson <peylow gmail.com> writes:
Chris Nicholson-Sauls skrev:
<snip>







 etc.
 


I like these.


And I yet again see a situation where range and set types are useful. If 
a range, or a set where a basic type (just as an integer, or imaginary 
float) then removing a range, or a set of elements would be more 
intuitive. And the slice operation would not be an array-hack, but a 
more general expression reusable everywhere.

Imagine we have: int foo[] = [1,2,3,4,5,6];
// Each example is now assumed unrelated to all others!
foo.remove(1); // foo == [1, 3, 4, 5, 6]
foo.remove(1..3); // foo = [1, 5, 6];
foo.remove(<1, 4..5>); // foo = [1, 3, 4]

or a "slice" using a set:
auto bar = foo[<1, 4..5>]; // bar == [2, 5, 6]

Naturally this would require a range's upper bound to be inclusive, or 
else set's would behave unintuitive. That is todays:
foo[5..5] would be a slice with one element, not empty as is.

Today passing around a range can only be done by passing around two 
values, or a struct. The same could be said about passing around 
imaginary numbers. Why imaginary numbers are valuable enough to warrant 
build in types, while ranges are not is beyond me. I use ranges way more 
than imaginary numbers.

Same goes for sets. Sure bitshifted enumerations, and boolean logic does 
the same trick. But adding it as a build in type would allow for far 
more expressive and intuitive code (Just how would you do a foreach over 
some "ored" enumeration constants?)


// Fredrik Olsson
Nov 01 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Fredrik Olsson wrote:

 Chris Nicholson-Sauls skrev:
 <snip>
 







 etc.


 
 I like these.
 
 
 And I yet again see a situation where range and set types are useful. If 
 a range, or a set where a basic type (just as an integer, or imaginary 
 float) then removing a range, or a set of elements would be more 
 intuitive. And the slice operation would not be an array-hack, but a 
 more general expression reusable everywhere.


Agreed.  I'd like to see 4..6 return some sort of range struct/object 
too.  Something as simple as
struct range {
    int lo;
    int hi;
};
That plus a few methods would pretty much do it.  Give it an opApply and 
an opApplyReverse and you've got foreach(i, 0..10) working too. (or 
rather than opApply/Reverse, you might want to make another special case 
for it in the compiler, like for arrays, because the general foreach 
mechanism is too inefficient.)


 Imagine we have: int foo[] = [1,2,3,4,5,6];
 // Each example is now assumed unrelated to all others!
 foo.remove(1); // foo == [1, 3, 4, 5, 6]
 foo.remove(1..3); // foo = [1, 5, 6];
 foo.remove(<1, 4..5>); // foo = [1, 3, 4]
 
 or a "slice" using a set:
 auto bar = foo[<1, 4..5>]; // bar == [2, 5, 6]
 Naturally this would require a range's upper bound to be inclusive, or 
 else set's would behave unintuitive. That is todays:
 foo[5..5] would be a slice with one element, not empty as is.


Not sure I agree there, or with what seems to be your assumption that 
sets and ranges should be the same concept.  If sets were a built-in 
type I would expect them to be able to represent sets of anything, not 
just sets of integers.

So, limiting the discussion to just ranges, including the upper bound vs 
not including the upper bound to me is pretty much a wash.  There are 
cases where each one looks good or bad, and perhaps ruby's solution of 
two constructs is the best bet -- 4..5 being exclusive and 4...5 being 
inclusive.  Use whichever works best for your case.  Or not.  I can 
already hear the cries of "it looks too similar! there'll be bugs!". 
Whatever.  It seems to work for ruby.


 Today passing around a range can only be done by passing around two 
 values, or a struct. The same could be said about passing around 
 imaginary numbers. Why imaginary numbers are valuable enough to warrant 
 build in types, while ranges are not is beyond me. I use ranges way more 
 than imaginary numbers.


Good point.  That's probably true for most non-sci folk and even a good 
chunk of the sci-folk.  Actually if the range object was extented to 
include any type of bounds (e.g. floats, doubles), it could maybe be 
used for interval arithmetic.  Interval arithmetic is pretty useful for 
continuous collision detection algorithms that are hot these days, and 
many other useful geometric/numerical/mathy things.  Just take the range 
above and parameterize with one type:
struct range(T)
{
    T lo;
    T hi;
}
Maybe there'd need to be a lot more to it to be useful for interval 
arithmetic, though.  I haven't worked interval arithmetic much myself, 
just heard talks from folks who used it.


 Same goes for sets. Sure bitshifted enumerations, and boolean logic does 
 the same trick. But adding it as a build in type would allow for far 
 more expressive and intuitive code (Just how would you do a foreach over 
 some "ored" enumeration constants?)


By sets, once again, you apparently mean only sets of small integers. 
It seems like you could define a struct that hides bitshifting from you 
and can be foreach'ed without too much trouble.  You just need an 
appropiate opApply.  (But again it won't be as efficient as a handcoded 
for-loop unless it becomes a special case recognized by the compiler -- 
are we sensing a trend here yet?)

--

Finally on a related topic, I'd like to say that the current restriction 
on opIndex and opSlice methods to only take integers seems unnecessary 
and overly draconian.  Is there some technical reason for it?  If 
opIndex/opSlice could take any kind of object then it would be possible 
today to make things like a range object that can be used to slice or 
index a user defined-array.  This kind of thing is useful when you want 
to create a Matlab or Numpy-like array package (c.f. Norbert Nemec's N-d 
array proposal for D).  It's very useful for instance to be able to have 
a method like "find" that returns an index object that can be used to 
index another array.  In Numpy this sort of thing is refered to as 
"fancy indexing".  Numpy doesn't try to be too clever about compressing 
the representation of the index set returned.  It's just another array 
containing the index of every element that passed the 'find' test.  Not 
sure why it doesn't try to be smarter.  Probably because the logic to do 
that compression and decompression ends up being slower than just 
enumerating everything in many common cases.

Note that if 3..5 returned a range object, then there would be no real 
need for the opSlice methods.  They would be replaced by opIndex 
overloaed for the range type.  E.g opIndex(range r)



--bb
Nov 01 2006
parent reply Fredrik Olsson <peylow gmail.com> writes:
Bill Baxter skrev:
<snip>

 Note that if 3..5 returned a range object, then there would be no real 
 need for the opSlice methods.  They would be replaced by opIndex 
 overloaed for the range type.  E.g opIndex(range r)
 


I cut most of it, as you know what I am referring to anyway :).


Ranges and sets are related, in fact in my own sets implementation I 
have four kinds of sets:
- finite sets
- range sets
- computer sets
- functions sets
This implantation is however an overkill, and way too slow, as it also 
covers infinite sets. For a compiler feature finite sets is the only 
realistic goal. But having a infinite set solution as well in the 
standard lib is good too.


I think you should be able to have sets of any type, and ranges of any 
numeric type. For obvious reasons finite sets of integers can be 
optimized greatly if used having a special case. And in worst case, I 
can live with only them (As they make up for 99% of real world cases and 
a templete implementation can fix the rest).

I would suggest declaring a set as this:
int<> foo = <1,2,3>;
char<> bar = <'a'..'z', 'A'..'Z'>;

How a range type can be declared, I am not sure. Writing the literals is 
obvious with the .. operator. But for declaring?
int.. foo = 1..42;
Just does not look right :).

And yes, having sets and ranges solve many problems. More than a handful 
of the suggestions of the D wish list page, are solved easily and 
consistent using ranges or sets. Well conceptually solved, then comes 
the problem of actually implementing it is the compiler :/.

But I like the idea of a few universal components that fits together in 
infinite ways, better than exceptions, and special cases, that only 
solves a single problem.


// Fredrik Olsson


 
 
 --bb
Nov 01 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Fredrik Olsson wrote:

 Bill Baxter skrev:
 <snip>
 

 Note that if 3..5 returned a range object, then there would be no real 
 need for the opSlice methods.  They would be replaced by opIndex 
 overloaed for the range type.  E.g opIndex(range r)


 
 I cut most of it, as you know what I am referring to anyway :).
 
 
 Ranges and sets are related, in fact in my own sets implementation I 
 have four kinds of sets:
 - finite sets


Ok.  Is that just numbers or anything?


 - range sets


Ok.  That must be just numbers.  Does that include things like the set 
containing the semi-open real number intervals (1,3] and [5,7)?


 - computer sets


No idea what that is. It sounds like a set of computers, which would be 
hard to implement with just code. :-)


 - functions sets


A set of functions?  A collection of things like 'int function(int bar)'?


 This implantation is however an overkill, and way too slow, as it also 
 covers infinite sets. For a compiler feature finite sets is the only 
 realistic goal. But having a infinite set solution as well in the 
 standard lib is good too.


Haskell's lazy infinite lists are pretty nifty in that regard.



 I think you should be able to have sets of any type, and ranges of any 
 numeric type. For obvious reasons finite sets of integers can be 
 optimized greatly if used having a special case. And in worst case, I 
 can live with only them (As they make up for 99% of real world cases and 
 a templete implementation can fix the rest).


Ok, but I think sets of arbitrary objects are also about as common as 
sets of integers.


 I would suggest declaring a set as this:
 int<> foo = <1,2,3>;
 char<> bar = <'a'..'z', 'A'..'Z'>;


Y'know there's a reason the < and > are available.  It's because their 
use in templates caused annoying ambiguity in C++ when nesting.  Your 
sets notation will have the same problem.

    int<int<>> /*oops!*/ foo = <</*oops*/1,2>,<3,4>>/*oops!*/;

So instead you could follow the lead of templates and use parens with a 
sigil.  Like $!  Looks sort of like an 'S' for set. :-)

    $int foo = $(1,2,3);
    $char bar = $('a'..'z', 'A'..'Z');

Urm, nah.  People are going to start thinking they're reading Perl or 
BASIC code.  The great thing about sets is that 'set' is such a small word.
    auto foo = set([1,2,3]);
    auto bar = set(['a'..'z', 'A'..'Z']);

Why bother with introducing another syntax?


 How a range type can be declared, I am not sure. Writing the literals is 
 obvious with the .. operator. But for declaring?
 int.. foo = 1..42;
 Just does not look right :).


Yeh, that does look odd.  I don't really see a great need for a special 
range syntax.  Have a standard definition for a thing called a 'range', 
and make that be what 1..42 evaluates to.

   range!(int) foo = 1..42;

or

   auto foo = 1..42;

--bb
Nov 01 2006
parent Fredrik Olsson <peylow gmail.com> writes:
Bill Baxter skrev:

 Fredrik Olsson wrote:

 Bill Baxter skrev:
 <snip>


 Note that if 3..5 returned a range object, then there would be no 
 real need for the opSlice methods.  They would be replaced by opIndex 
 overloaed for the range type.  E.g opIndex(range r)


 I cut most of it, as you know what I am referring to anyway :).


 Ranges and sets are related, in fact in my own sets implementation I 
 have four kinds of sets:
 - finite sets


 
 Ok.  Is that just numbers or anything?
 


Anything.


 - range sets


 
 Ok.  That must be just numbers.  Does that include things like the set 
 containing the semi-open real number intervals (1,3] and [5,7)?
 


Yes. As well as -infinite, and +infinite.


 - computer sets


 
 No idea what that is. It sounds like a set of computers, which would be 
 hard to implement with just code. :-)
 


Misspelled, computed set that is. See it as "set operators". For example 
the union of sets, etc.



 - functions sets


 
 A set of functions?  A collection of things like 'int function(int bar)'?
 


No a set where membership is determined by a function. For example a set 
with primes, even integers, etc.



 This implantation is however an overkill, and way too slow, as it also 
 covers infinite sets. For a compiler feature finite sets is the only 
 realistic goal. But having a infinite set solution as well in the 
 standard lib is good too.


 
 Haskell's lazy infinite lists are pretty nifty in that regard.
 
 

 I think you should be able to have sets of any type, and ranges of any 
 numeric type. For obvious reasons finite sets of integers can be 
 optimized greatly if used having a special case. And in worst case, I 
 can live with only them (As they make up for 99% of real world cases 
 and a templete implementation can fix the rest).


 
 Ok, but I think sets of arbitrary objects are also about as common as 
 sets of integers.
 


Common yes, but set arithmetics are not common on them. So for most 
implementations a dynamic array is just fine. Some templates array 
manipulation, like what I think Oscar Linde posted some months ago would 
be fine (map function etc).



 I would suggest declaring a set as this:
 int<> foo = <1,2,3>;
 char<> bar = <'a'..'z', 'A'..'Z'>;


 
 Y'know there's a reason the < and > are available.  It's because their 
 use in templates caused annoying ambiguity in C++ when nesting.  Your 
 sets notation will have the same problem.
 
    int<int<>> /*oops!*/ foo = <</*oops*/1,2>,<3,4>>/*oops!*/;
 
 So instead you could follow the lead of templates and use parens with a 
 sigil.  Like $!  Looks sort of like an 'S' for set. :-)
 
    $int foo = $(1,2,3);
    $char bar = $('a'..'z', 'A'..'Z');
 
 Urm, nah.  People are going to start thinking they're reading Perl or 
 BASIC code.  The great thing about sets is that 'set' is such a small word.
    auto foo = set([1,2,3]);
    auto bar = set(['a'..'z', 'A'..'Z']);
 
 Why bother with introducing another syntax?
 

 How a range type can be declared, I am not sure. Writing the literals 
 is obvious with the .. operator. But for declaring?
 int.. foo = 1..42;
 Just does not look right :).


 
 Yeh, that does look odd.  I don't really see a great need for a special 
 range syntax.  Have a standard definition for a thing called a 'range', 
 and make that be what 1..42 evaluates to.
 
   range!(int) foo = 1..42;
 
 or
 
   auto foo = 1..42;
 


Well, I do not much care for the actual syntax, I just think <...> looks 
nice, and D-like :).
But $ works for me, but as a suffix when declaring, as you might want:
int[]$ foo; // set of int arrays. $int[] would be ambiguous.

I do however think a range-specific-syntax is crucial if ranges are to 
be first class citizens. Using range!(type) would demote it to a 
template hack, and auto would force programmers to initialize.


// Fredrik Olsson


 --bb
Nov 01 2006
prev sibling next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Chris Nicholson-Sauls wrote:







 etc.


I went to http://www.dsource.org/projects/cashew but found no obvious 
way to download cashew or instructions related to obtaining the software.

--bb
Nov 01 2006
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bill Baxter wrote:

 Chris Nicholson-Sauls wrote:
 







 etc.


 
 I went to http://www.dsource.org/projects/cashew but found no obvious 
 way to download cashew or instructions related to obtaining the software.
 
 --bb


I guess I could mention it explicitly, but the way to do it is to use
Subversion checkout. 
  I don't bother making "official" downloads of it, because there are constant
updates 
being made.  (This is also why each package/module gets its own version number,
rather 
than a library-wide version.)

-- Chris Nicholson-Sauls
Nov 01 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Chris Nicholson-Sauls wrote:

 Bill Baxter wrote:

 Chris Nicholson-Sauls wrote:








 etc.


 I went to http://www.dsource.org/projects/cashew but found no obvious 
 way to download cashew or instructions related to obtaining the software.

 --bb


 
 I guess I could mention it explicitly, but the way to do it is to use 
 Subversion checkout.  I don't bother making "official" downloads of it, 
 because there are constant updates being made.  (This is also why each 
 package/module gets its own version number, rather than a library-wide 
 version.)
 
 -- Chris Nicholson-Sauls


Ok, I know subversion, but I don't know how to do a subversion checkout 
from Dsource.  What's the subversion URL for your project?

--bb
Nov 01 2006
parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
Bill Baxter wrote:


 Chris Nicholson-Sauls wrote:

 Bill Baxter wrote:

 Chris Nicholson-Sauls wrote:








 etc.


 I went to http://www.dsource.org/projects/cashew but found no obvious
 way to download cashew or instructions related to obtaining the
 software.

 --bb


 
 I guess I could mention it explicitly, but the way to do it is to use
 Subversion checkout.  I don't bother making "official" downloads of it,
 because there are constant updates being made.  (This is also why each
 package/module gets its own version number, rather than a library-wide
 version.)
 
 -- Chris Nicholson-Sauls


 
 Ok, I know subversion, but I don't know how to do a subversion checkout
 from Dsource.  What's the subversion URL for your project?
 
 --bb


svn co http://svn.dsource.org/projects/cashew/trunk cashew

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource & #D: larsivi
Nov 01 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Lars Ivar Igesund wrote:

 Bill Baxter wrote:
 

 Chris Nicholson-Sauls wrote:

 Bill Baxter wrote:

 Chris Nicholson-Sauls wrote:








 etc.


 I went to http://www.dsource.org/projects/cashew but found no obvious
 way to download cashew or instructions related to obtaining the
 software.

 --bb


 I guess I could mention it explicitly, but the way to do it is to use
 Subversion checkout.  I don't bother making "official" downloads of it,
 because there are constant updates being made.  (This is also why each
 package/module gets its own version number, rather than a library-wide
 version.)

 -- Chris Nicholson-Sauls


 Ok, I know subversion, but I don't know how to do a subversion checkout
 from Dsource.  What's the subversion URL for your project?

 --bb


 
 svn co http://svn.dsource.org/projects/cashew/trunk cashew
 


Wikied!

Thanks.

--bb
Nov 01 2006
parent reply Mike Parker <aldacron71 yahoo.com> writes:
Bill Baxter wrote:

 Lars Ivar Igesund wrote:

 Bill Baxter wrote:


 Chris Nicholson-Sauls wrote:

 Bill Baxter wrote:

 Chris Nicholson-Sauls wrote:








 etc.


 I went to http://www.dsource.org/projects/cashew but found no obvious
 way to download cashew or instructions related to obtaining the
 software.

 --bb


 I guess I could mention it explicitly, but the way to do it is to use
 Subversion checkout.  I don't bother making "official" downloads of it,
 because there are constant updates being made.  (This is also why each
 package/module gets its own version number, rather than a library-wide
 version.)

 -- Chris Nicholson-Sauls


 Ok, I know subversion, but I don't know how to do a subversion checkout
 from Dsource.  What's the subversion URL for your project?

 --bb


 svn co http://svn.dsource.org/projects/cashew/trunk cashew


 
 Wikied!
 


DSource has always had a page describing this at 
http://www.dsource.org/site/svnclient.
Nov 01 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Mike Parker wrote:

 Bill Baxter wrote:

 Lars Ivar Igesund wrote:

 Bill Baxter wrote:


 svn co http://svn.dsource.org/projects/cashew/trunk cashew


 Wikied!


 
 DSource has always had a page describing this at 
 http://www.dsource.org/site/svnclient.


Quoth the above page:

"Once you have a client up and running, you may access code via the 
instructions on the page of the project you wish to access."

--bb
Nov 01 2006
prev sibling parent David Qualls <davidlqualls yahoo.com> writes:
I suspect that the benchmark timings may be highly dependent on
the type T of the array.  Integers should be very fast, since the
arr[which]=arr[which+1]
is effectively a memmove operation.
If the type T is char, I would expect things to slow down
considerably.

I might suggest that simply discovering the size of the memory
block to be moved, then using a memmove() on it would be robustly
fast (independent of type T) since it is (supposed to be)
optimised to use the native type-size best suited to the machine.

David Qualls
ps: I'm VERY new to D; just learning it...
Nov 01 2006
prev sibling next sibling parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bill Baxter wrote:

 How do I remove an element from a dynamic array?
 
    int[] a = [1,2,3,4,5];
 
 I tried every syntax I could think of:
 
    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];
 
 The last one compiles, but fills a[0] with garbage.
 
 I hope the answer isn't:
 
    a = a[0..3] ~ a[4..length];
 
 Thanks!
 --bb


Assuming you mean remove as in extract and throw away the item at a given
index, then yes 
that last one is the only way.  In Cashew this is abstracted to
array.removeIndex(size_t). 
  I really can't think of any other way it could be done, though...

Except for maybe:



Hrm, not really any better.  Or maybe, using Cashew (but avoiding .removeIndex):



Essentially, the same thing anyway.

-- Chris Nicholson-Sauls
Oct 30 2006
parent reply Sean Kelly <sean f4.ca> writes:
Chris Nicholson-Sauls wrote:

 Bill Baxter wrote:

 How do I remove an element from a dynamic array?

    int[] a = [1,2,3,4,5];

 I tried every syntax I could think of:

    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];

 The last one compiles, but fills a[0] with garbage.

 I hope the answer isn't:

    a = a[0..3] ~ a[4..length];

 Thanks!
 --bb


 
 Assuming you mean remove as in extract and throw away the item at a 
 given index, then yes that last one is the only way.  In Cashew this is 
 abstracted to array.removeIndex(size_t).  I really can't think of any 
 other way it could be done, though...
 
 Except for maybe:




Unfortunately, I think this is illegal.  See my thread in this group 
entitled "Removing an array element in order."


Sean
Oct 30 2006
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Sean Kelly wrote:

 Chris Nicholson-Sauls wrote:
 

 Bill Baxter wrote:


 How do I remove an element from a dynamic array?

    int[] a = [1,2,3,4,5];

 I tried every syntax I could think of:

    a[3] = void;
    a[3..4] = void;
    a[3..4] = a[3..3];
    a[3] = [];
    a[3..4] = [];
    delete a[3];
    delete a[3..4];

 The last one compiles, but fills a[0] with garbage.

 I hope the answer isn't:

    a = a[0..3] ~ a[4..length];

 Thanks!
 --bb



 Assuming you mean remove as in extract and throw away the item at a 
 given index, then yes that last one is the only way.  In Cashew this 
 is abstracted to array.removeIndex(size_t).  I really can't think of 
 any other way it could be done, though...

 Except for maybe:




 
 
 Unfortunately, I think this is illegal.  See my thread in this group 
 entitled "Removing an array element in order."
 
 
 Sean


Ah.  Most likely because of pointer corruption from assigning a slice of an
array into 
that same array.  Should still be doable with a little magic, but probably more
trouble 
than its worth.  Yet another reason I think Phobos needs an array utils module
like that 
in my Cashew or like Oskar's work... or any of the others that have popped up
now and 
then.  Even some of std.string could be abstracted into "std.array" for cases
where 
Unicode compatability is not neccessary (closed systems using strictly char[]
or dchar[], 
for example).

-- Chris Nicholson-Sauls
Oct 30 2006
prev sibling parent =?ISO-8859-1?Q?Anders_F_Bj=F6rklund?= <afb algonet.se> writes:
Bill Baxter wrote:


 How do I remove an element from a dynamic array?


[...]

 I hope the answer isn't:
 
    a = a[0..3] ~ a[4..length];


That's what I use...

--anders
Oct 30 2006