0

There are lots of questions on Stack Overflow about how to remove items from a collection while iterating over it (specifically in Java). This question has a decent set of options of how to do it. However, none of the conditions for removal described in those answers are functions of the entry's relationship to its neighboring entries. As an example...

Imagine I have a list of x,y points, and I want to reduce the list such that no series of 3 or more points are colinear. Put another way, I want to be able to reduce the list of points such that they describe the start/end points of a series of line segments such that no two segments are are subsections of a single larger segment. For instance, a given set might look like [ {0,0}, {3,0}, {5,2}, {7,4}, {10,4} ], and I would want to reduce it to the set [ {0,0}, {3,0}, {7,4}, {10,4} ], because the the {5,2} point is colinear with both {3,0} and {7,4}. The test of colinearity is dependent on the previous and subsequent point in the set, so it's impossible to know if a given point needs to be removed based on that point alone, which is a requirement for most of the options in the answer linked above, like the removeIf() method.

My question is simple: does there exist in Java a way of reducing a list in this way in one pass of the dataset? Obviously I could iterate over it once, test each point for colinearity with its neighbours, and store the indices of points to remove, and then in a second pass take only the wanted points and build up a new set.

MattS
  • 717
  • 2
  • 7
  • 22
  • Do you want to test it's neighbors from before removal or the current state of the list (as you're removing while iterating)? So with a simpler example if you'd like you'd to remove any ints from a list where the previous and next are -1 (prev) and +1(next) from current with this list: `[1,2,3,4,5,7,9]` would you expect the result to be `[1,5,7,9]` or `[1,3,5,7,9]` (once 2 is removed 3 no longer has a direct -1 as a before neighbor) – R4N Sep 20 '19 at 21:29
  • I guess that depends on the check itself, whether or not it's transitive. For instance, with the colinearity example, three, four, five, etc. colinear points would all collapse down to just two remaining entries because colinearity is a transitive property. In your case, there's not the same telescoping effect. As I'm asking this question more out of curiosity than to solve a particular problem, I'd be interested in seeing solutions for either case. – MattS Sep 20 '19 at 22:32
  • What’s the issue with one pass or multiple? For example, [`ArrayList.removeIf`](https://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/util/ArrayList.java#l1684) implements a two-pass technique internally. Does that count? – Stuart Marks Sep 20 '19 at 22:45
  • My main issue is that conceptually it's very easy to do it in one pass. As a person with pen and paper I could easily do it. There's nothing about the check itself that requires two passes; it's an API limitation. And I don't like when APIs require implementation that necessarily differs significantly from the simplest conceptual version of an algorithm. So no, I wouldn't count 'removeIf' as a two-pass solution because it doesn't require writing two passes. – MattS Sep 20 '19 at 23:00
  • OK so it sounds like the one-pass issue is about how this is expressed in the source code, not any underlying implementation requirement that requires only one pass, e.g., if the data were from a stream. – Stuart Marks Sep 21 '19 at 01:08
  • That is correct. It's not necessarily a performance concern (O(n) and O(2n) really aren't that different), moreso a matter of code readability and aesthetics, and the delta between how an algorithm is expressed in code (and how complicated that is) versus how it's expressed in pure mathematics (and how much simpler that is). – MattS Sep 21 '19 at 15:28

1 Answers1

1

As mentioned in the comments, you could use removeIf/streams.

A foreach/iterator would give a ConcurrentModificationException if you attempt to remove an item while iterating, but a standard for loop should work. Maintaining a separate counter for the number of items you've traversed (separate from the index). Here's a example which should work for the initial sample problem you outline:

        ArrayList<R4NPoint> arrList = new ArrayList<R4NPoint>() {{
            add(new R4NPoint(0, 0));
            add(new R4NPoint(3, 0));
            add(new R4NPoint(5, 2));
            add(new R4NPoint(7, 4));
            add(new R4NPoint(9, 6));
            add(new R4NPoint(5, 0));
            add(new R4NPoint(10, 4));
            add(new R4NPoint(15, 8));
        }};

        // start at the second item as our check is always dependent on our previous and next neighbors
        int index = 1;
        int totalSize = arrList.size();
        for (int numberOfItemsChecked = 1; numberOfItemsChecked < totalSize - 1; numberOfItemsChecked++) {
            int prevIndex = index - 1;
            int nextIndex = index + 1;
            // check previous and next for removal condition
            if (arrList.get(index).arePointsColinear(arrList.get(prevIndex), arrList.get(nextIndex))) {
                // if they are co-linear remove the item at our current index, and don't increment the index
                // the next item will now be at the current index
                arrList.remove(index);
            } else {
                index++;
            }
        }
        System.out.println("finalArrayAfterRemoval = " + arrList.toString());

which would result in an output of:

finalArrayAfterRemoval = [{0, 0}, {3, 0}, {9, 6}, {5, 0}, {15, 8}]

I've left off the implementation of R4NPoint as I'm assuming you already have something to that affect on your end.

R4N
  • 2,455
  • 1
  • 7
  • 9
  • Ah, the idea of managing the index of the collection separately from the iteration index of the for-loop didn't occur to me. I like it though, it's pretty clean. Thanks! – MattS Sep 24 '19 at 16:04