javac++c

How to get all sets of three consecutive elements in an array or ArrayList with a for statement, circling the end to the beginning?


I'm trying to do a convex hull approach and the little problem is that I need to get all sets of three consecutive vertices, like this:

private void isConvexHull(Ponto[] points) {
    Arrays.sort(points);
    for (int i = 0; i <points.length; i++) {
        isClockWise(points[i],points[i+1],points[i+2]);
    }
    //... 
}

I always do something that I don't consider clean code. Could please help me find one or more ways to this? I want it to be circular, i.e., if my fisrt point of the a set is the last element in the array, the 2nd element will be the 3rd in the list and the 3rd in that set will be the the 2nd element in the list, and so on. They must be consecutive, that's all.


Solution

  • The remainder "trick"

    You can use the % "trick" (% is the remainder operator JLS 15.17.3) for circular indexing. Here I will illustrate the general idea using a String instead.

        String s = "ABCDE";
        final int L = s.length();
        for (int i = 0; i < L; i++) {
            System.out.format("%c%c%c ",
                s.charAt(i),
                s.charAt((i + 1) % L),
                s.charAt((i + 2) % L)
            );
        } // prints "ABC BCD CDE DEA EAB "
    

    An Iterator approach

    If you're doing this triplet processing often, though, it will be a better overall design to have an Iterator<PointTriplet> or something similar.

    Here's a prototype to illustrate the idea:

    import java.util.*;
    
    public class CircSubArray {
        static <T> Iterator<T[]> circularIterator(final T[] arr, final int K) {
            return new Iterator<T[]>() {
                int index = 0;
                final int L = arr.length;
                T[] sub = Arrays.copyOf(arr, K); // let it do the dirty work!
    
                @Override public boolean hasNext() {
                    return index < L;
                }
                @Override public T[] next() {
                    for (int i = 0; i < K; i++) {
                        sub[i] = arr[(index + i) % L];
                    }
                    index++;
                    return sub; // we always overwrite; no need to .clone()
                }
                @Override public void remove() {
                    throw new UnsupportedOperationException();
                }
            };
        }   
        public static void main(String[] args) {
            String[] arr = { "s1", "s2", "s3", "s4", "s5", "s6" };
    
            Iterator<String[]> iter = circularIterator(arr, 4);
            while (iter.hasNext()) {
                System.out.println(Arrays.toString(iter.next()));
            }
        }
    }
    

    This prints:

    [s1, s2, s3, s4]
    [s2, s3, s4, s5]
    [s3, s4, s5, s6]
    [s4, s5, s6, s1]
    [s5, s6, s1, s2]
    [s6, s1, s2, s3]
    

    A List-based solution

    As Effective Java 2nd Edition says, Item 25: Prefer lists to arrays. Here's a solution that redundantly stores the first K-1 elements at the end of the List, and then simply uses subList to get K elements at a time.

        String[] arr = { "s1", "s2", "s3", "s4", "s5", "s6" };
    
        final int L = arr.length;
        final int K = 3;
        List<String> list = new ArrayList<String>(Arrays.asList(arr));
        list.addAll(list.subList(0, K-1));
    
        for (int i = 0; i < L; i++) {
            System.out.println(list.subList(i, i + K));
        }
    

    This prints:

    [s1, s2, s3]
    [s2, s3, s4]
    [s3, s4, s5]
    [s4, s5, s6]
    [s5, s6, s1]
    [s6, s1, s2]
    

    Since subList is a view, this does not have to do the O(K) shifting that the array-based solution does. This also shows the expressiveness of List over arrays.