www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Do we have a simple find/remove algorithm?

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
"Find it and kill it" seems rather tedious to do. We have 
https://dlang.org/library/std/algorithm/mutation/remove.html, which 
operates with either indices or predicates. Then we have find and 
findSplitXxx, but neither seems to make it easy to find some element and 
remove it by shifting the range backwards. What am I missing?
Sep 25 2020
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Sep 25, 2020 at 10:29:57PM -0400, Andrei Alexandrescu via Digitalmars-d
wrote:

 "Find it and kill it" seems rather tedious to do. We have
 https://dlang.org/library/std/algorithm/mutation/remove.html, which
 operates with either indices or predicates. Then we have find and
 findSplitXxx, but neither seems to make it easy to find some element
 and remove it by shifting the range backwards. What am I missing?


It's a bit wordy, true, but I wouldn't say it's _tedious_ per se:

	import std;
	void main() {
		auto data = [ 1,2,3,4,5 ];
		data = data.remove!(x => x == 3);
		writeln(data);
	}


T

-- 
Written on the window of a clothing store: No shirt, no shoes, no service.
Sep 25 2020
parent reply mipri <mipri minimaltype.com> writes:
On Saturday, 26 September 2020 at 02:48:54 UTC, H. S. Teoh wrote:

 On Fri, Sep 25, 2020 at 10:29:57PM -0400, Andrei Alexandrescu 
 via Digitalmars-d wrote:

 "Find it and kill it" seems rather tedious to do. We have 
 https://dlang.org/library/std/algorithm/mutation/remove.html, 
 which operates with either indices or predicates. Then we have 
 find and findSplitXxx, but neither seems to make it easy to 
 find some element and remove it by shifting the range 
 backwards. What am I missing?


 It's a bit wordy, true, but I wouldn't say it's _tedious_ per 
 se:

 	import std;
 	void main() {
 		auto data = [ 1,2,3,4,5 ];
 		data = data.remove!(x => x == 3);
 		writeln(data);
 	}


 T


This removes two elements however:

[1,2,3,4,5,3].remove!(x => x==3)
Sep 25 2020
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/25/20 11:45 PM, mipri wrote:

 On Saturday, 26 September 2020 at 02:48:54 UTC, H. S. Teoh wrote:

 On Fri, Sep 25, 2020 at 10:29:57PM -0400, Andrei Alexandrescu via 
 Digitalmars-d wrote:

 "Find it and kill it" seems rather tedious to do. We have 
 https://dlang.org/library/std/algorithm/mutation/remove.html, which 
 operates with either indices or predicates. Then we have find and 
 findSplitXxx, but neither seems to make it easy to find some element 
 and remove it by shifting the range backwards. What am I missing?


 It's a bit wordy, true, but I wouldn't say it's _tedious_ per se:

     import std;
     void main() {
         auto data = [ 1,2,3,4,5 ];
         data = data.remove!(x => x == 3);
         writeln(data);
     }


 T


 
 This removes two elements however:
 
 [1,2,3,4,5,3].remove!(x => x==3)


Yah, removing all is not too difficult. Removing one is oddly missing. I 
think we should add a findRemove algorithm. Question is, should it go in 
iteration.d or mutation.d? :o)

Also, loosely related: findSplitXxx does not work for finding individual 
elements, only (sub)ranges.
Sep 26 2020
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Saturday, 26 September 2020 at 12:22:52 UTC, Andrei 
Alexandrescu wrote:

 Removing one is oddly missing. I think we should add a 
 findRemove algorithm. Question is, should it go in iteration.d 
 or mutation.d? :o)


Something I often end up wanting in this is replace first 
occurrence, and return the remainder.

So I have "abc" and you do replace a with ab,  want:

result == "abbc"
remainder = "bc"

So then I can replace one and keep going without getting stuck in 
a loop. I often do this myself with indexOf and slicing.


I guess it might be best to do it with findSplit but it would be 
cool if a findAndReplaceFirst could return the remainder somehow 
too.
Sep 26 2020
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/26/20 8:46 AM, Adam D. Ruppe wrote:

 On Saturday, 26 September 2020 at 12:22:52 UTC, Andrei Alexandrescu wrote:

 Removing one is oddly missing. I think we should add a findRemove 
 algorithm. Question is, should it go in iteration.d or mutation.d? :o)


 
 Something I often end up wanting in this is replace first occurrence, 
 and return the remainder.
 
 So I have "abc" and you do replace a with ab,  want:
 
 result == "abbc"
 remainder = "bc"
 
 So then I can replace one and keep going without getting stuck in a 
 loop. I often do this myself with indexOf and slicing.
 
 
 I guess it might be best to do it with findSplit but it would be cool if 
 a findAndReplaceFirst could return the remainder somehow too.


I think it's easy IF findSplit worked with individual elements. On your 
code:

auto r = range.findSplit(x);
r[1] = x;
range = r[2];
Sep 26 2020
prev sibling parent reply Sebastiaan Koppe <mail skoppe.eu> writes:
On Saturday, 26 September 2020 at 12:22:52 UTC, Andrei 
Alexandrescu wrote:

 On 9/25/20 11:45 PM, mipri wrote:

 This removes two elements however:
 
 [1,2,3,4,5,3].remove!(x => x==3)


 Yah, removing all is not too difficult. Removing one is oddly 
 missing. I think we should add a findRemove algorithm. Question 
 is, should it go in iteration.d or mutation.d? :o)


I usually do r.remove(r.countUntil(3)), but its not intuitive.
Sep 26 2020
next sibling parent Paolo Invernizzi <paolo.invernizzi gmail.com> writes:
On Saturday, 26 September 2020 at 14:00:34 UTC, Sebastiaan Koppe 
wrote:

 On Saturday, 26 September 2020 at 12:22:52 UTC, Andrei 
 Alexandrescu wrote:

 On 9/25/20 11:45 PM, mipri wrote:

 This removes two elements however:
 
 [1,2,3,4,5,3].remove!(x => x==3)


 Yah, removing all is not too difficult. Removing one is oddly 
 missing. I think we should add a findRemove algorithm. 
 Question is, should it go in iteration.d or mutation.d? :o)


 I usually do r.remove(r.countUntil(3)), but its not intuitive.


Same here ...
Sep 26 2020
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/26/20 10:00 AM, Sebastiaan Koppe wrote:

 On Saturday, 26 September 2020 at 12:22:52 UTC, Andrei Alexandrescu wrote:

 On 9/25/20 11:45 PM, mipri wrote:

 This removes two elements however:

 [1,2,3,4,5,3].remove!(x => x==3)


 Yah, removing all is not too difficult. Removing one is oddly missing. 
 I think we should add a findRemove algorithm. Question is, should it 
 go in iteration.d or mutation.d? :o)


 
 I usually do r.remove(r.countUntil(3)), but its not intuitive.


Good to know, thanks.
Sep 26 2020
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Sep 26, 2020 at 02:00:34PM +0000, Sebastiaan Koppe via Digitalmars-d
wrote:

 On Saturday, 26 September 2020 at 12:22:52 UTC, Andrei Alexandrescu wrote:

 On 9/25/20 11:45 PM, mipri wrote:

 This removes two elements however:
 
 [1,2,3,4,5,3].remove!(x => x==3)


 
 Yah, removing all is not too difficult. Removing one is oddly
 missing. I think we should add a findRemove algorithm. Question is,
 should it go in iteration.d or mutation.d? :o)


 
 I usually do r.remove(r.countUntil(3)), but its not intuitive.


And also countUntil can return -1, which is invalid input for .remove.
So writing it this way is not safe against corner cases.


T

-- 
Doubt is a self-fulfilling prophecy.
Sep 26 2020
prev sibling parent reply Guillaume Piolat <first.last gmail.com> writes:
On Saturday, 26 September 2020 at 02:29:57 UTC, Andrei 
Alexandrescu wrote:

 "Find it and kill it" seems rather tedious to do.


Yes, this is indeed the only non-trivial operation in this area:
https://p0nce.github.io/d-idioms/#Adding-or-removing-an-element-from-arrays
Sep 26 2020
parent aberba <karabutaworld gmail.com> writes:
On Saturday, 26 September 2020 at 17:41:13 UTC, Guillaume Piolat 
wrote:

 On Saturday, 26 September 2020 at 02:29:57 UTC, Andrei 
 Alexandrescu wrote:

 "Find it and kill it" seems rather tedious to do.


 Yes, this is indeed the only non-trivial operation in this area:
 https://p0nce.github.io/d-idioms/#Adding-or-removing-an-element-from-arrays


removeOne(), removeOneElement()
Sep 26 2020