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: # Array length: 10000 # Iterations removing middle element: 5000 # ---------- Slice syntax: a[0 .. mid] ~ [mid + 1 .. a.length] # <Benchmark array removals> Baseline 3.460000 # ---------- CashewUtils: a.removeIndex(mid) # <Benchmark array removals> Time 2.970000 & 1.164983 versus baseline # ---------- Drop: version 1 # <Benchmark array removals> Time 0.270000 & 12.814815 versus baseline # ---------- Drop: version 2 # <Benchmark array removals> Time 0.390000 & 8.871795 versus baseline 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).

# import cashew.utils.array; # # int[] foo = ... ; # foo.remove(3U); # foo.removeRange(2U, 7U); # foo.removeSub(foo[1 .. 5]); 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: # Array length: 10000 # Iterations removing middle element: 5000 # ---------- Slice syntax: a[0 .. mid] ~ [mid + 1 .. a.length] # <Benchmark array removals> Baseline 3.460000 # ---------- CashewUtils: a.removeIndex(mid) # <Benchmark array removals> Time 2.970000 & 1.164983 versus baseline # ---------- Drop: version 1 # <Benchmark array removals> Time 0.270000 & 12.814815 versus baseline # ---------- Drop: version 2 # <Benchmark array removals> Time 0.390000 & 8.871795 versus baseline 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).

# import cashew.utils.array; # # int[] foo = ... ; # foo.remove(3U); # foo.removeRange(2U, 7U); # foo.removeSub(foo[1 .. 5]); 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>
 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 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>
 
 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 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?

 - 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. :-)

the union of sets, etc.
 - functions sets

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

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.

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;

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:
 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 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:
 
 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 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:

 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 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:

 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 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:

 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 etc.

way to download cashew or instructions related to obtaining the software. --bb

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

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:

 # import cashew.utils.array;
 #
 # int[] foo = ... ;
 # foo.remove(3U);
 # foo.removeRange(2U, 7U);
 # foo.removeSub(foo[1 .. 5]);
 etc.

way to download cashew or instructions related to obtaining the software. --bb

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

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: # a[3 .. a.length - 1] = a[4 .. a.length]; # a.length = a.length - 1; Hrm, not really any better. Or maybe, using Cashew (but avoiding .removeIndex): # a[3 .. a.length].rotl; # a.pop; 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: # a[3 .. a.length - 1] = a[4 .. a.length]; # a.length = a.length - 1;

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: # a[3 .. a.length - 1] = a[4 .. a.length]; # a.length = a.length - 1;

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