Remove duplicate to ArrayList from custom objects

First you need to order your collection in both c x

and y

c x

(think of it as x and y, forming a hypothetical number with x on the left side of the decimal point and y on the right side: when you sort a number in ascending order, if the integral parts are equal, you are sorting by decimal). Now, with a predicate equal

, it will be difficult to sort the values ​​(you can only tell if they are equal, not if they are in front of another). Instead, you need to implement the interface comparable

with the following method:

public int compare(Object obj) {
  if (obj == null || !(obj instanceof MyObject)) {
    // raise an Exception
  }
  MyObject other = (MyObject)obj;
  if (x < other.x) return -1;
 if (this.x > other.x) return 1;
  if (this.y < other.y) return -1;
  if (this.y > other.y) return 1;
  return 0;
}

      

        
        
        
      

    

If your array is sorted according to this comparison, you just need to keep the last entry with the same x

in your array to get what you want. This means that you delete records if its successor has no other x

.

This method is interesting because you don't want to store the original data, but you keep the result: it updates the existing array in place, for O (n) complexity in time (not counting the sorting, which should happen anyway if I understood your question correctly ).

Alternatively, all filtering can be achieved by applying a crease to your collection, where the folding here just keeps the highest y

for the same thing x

(as you exactly stated in your question). Since your collection is already sorted by x

, this means that it is naturally split into values x

, so you can build a new collection by accumulating the correct one x

for each section in a different array. For each element of the array, you compare it with the last inserted entry in the new array, if they x

match, you replace it with the object with the highest y

. If the parameter x

is different, you add it to a new array.

The advantage of this approach is that you don't need to change the sorting algorithm, but on the other hand, you need a new array. Therefore, this algorithm should work in O (n) space and time.

Finally, this algorithm can be adapted to update the original array in place. This is a little more complicated, but will allow you to avoid additional allocation (which is important for embedded systems).

Pseudocode:

int idx = 0;
while (idx + 1 < Objarray.size()){
  MyObj oi = Objarray.get(idx), on = Objarray.get(idx+1);
  if (oi.x == on.x) {
    if (on.y < oi.y) 
      Objarray.remove(idx++);
    else
      Objarray.remove(idx+1);
  } else
    idx++;
}

      

        
        
        
      

    

Note that when working in constant space, it may be slightly less efficient than the allocation algorithm, as the method ArrayList

works internally (although it should be better than using other common container types).

The most optimal solution would be to use Set

. However, Java has two implementations Set

: HashSet

and TreeSet

. HashSet

requires you to declare methods equals

and hashCode

, but TreeSet

requires your class to implement Comparable

with a method compareTo

or supply Comparator

. Neither solution will work in your case, because you want to keep the higher y

when x

equal. If you sort / calculate equality based on x

, y

you will have a duplicate x

, and if you sort / calculate equality based on x

, you only get the first one x

, which is not something you want.

Therefore, we need to do the following:

• Sort x ascending, descending
• Convert to Set
  
  , which preserves the original ordering but bases equality only onx
  
  
• Convert back to list (if needed)

Comparator method XAscYdesc (excluding zeros):

public int compare(MyObject left, MyObject right) {
  int c = left.x - right.x;
  if(c != 0) {
    return c;
  }
  return right.y - left.y;
}

      

        
        
        
      

    

XAsc comparator method (excluding zeros):

public int compare(MyObject left, MyObject right) {
  return left.x - right.x;
}

      

        
        
        
      

    

(Using the Guava library it is very useful for one line files):

Collections.sort(list, new XAscYdesc());
Lists.newArrayList(ImmutableSortedSet.copyOf(new XAsc(), list));