Removing Duplicates from Array of Int[]

Question

I have really been struggling with this for an hour or so now. I am trying to remove all the duplicates from an array of int[]. Every element of the array is a int[] containing the x & y positions of a tile. So, the it is [[3, 1], [3, 12], ...]. When generating my world, I add already seen tiles, so I am writing a function to "condense" the tile array.

I have tried using a hashSet & set, but for some reason, both DS do not remove the duplicates. Is there possibly an issue with overriding compare(object1, object2) for int[]'s?

// Takes array of x,y coordinates (form: int[]{x, y}) and condense it by removing the duplicates

private int[][] condenseTiles(int[][] tiles) {
    Set<int[]> setOfTiles = new LinkedHashSet<int[]>();

    for(int i = 0; i < tiles.length; i++){
        setOfTiles.add(tiles[i]);
    }

    System.out.println(setOfTiles.size());

    return tiles;
}

I know there are shortcut ways to add every element to a HashSet, but currently nothing is working and I am still seeing duplicates, so I'm just doing it the slow and expanded way. For reference, right now, setOfTiles and tiles have the same size no matter what I do. Please let me know if you have any suggestions.

Answer 1

One possible solution:

• Create a Tile class, one with x and y int fields
• Give the class decent public boolean equals(Object o) and public int hashCode() methods, one that regards two Tiles with the same x and y values as being equal and as returning the same hashCode
• Place the tiles in a Set<Tile> from the start -- this prevents duplicate entry.

e.g.,

public class Tile {
    private int x;
    private int y;

    public Tile(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Tile other = (Tile) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Tile [" + x + ", " + y + "]";
    }

}

And tested with:

import java.util.LinkedHashSet;
import java.util.Set;

public class TestTile {
    public static void main(String[] args) {
        Set<Tile> tileSet = new LinkedHashSet<>();

        int[][] testData = {{1, 2}, {3, 4}, {5, 6}, {1, 2}, {5, 6}};
        for (int[] pair : testData) {
            Tile tile = new Tile(pair[0], pair[1]);
            tileSet.add(tile);
            System.out.println("Tile added: " + tile);
            System.out.println("All Tiles: ");
            for (Tile t : tileSet) {
                System.out.println("  " + t);
            }
            System.out.println();
        }

    }
}

Which returns:

Tile added: Tile [1, 2]
All Tiles: 
  Tile [1, 2]

Tile added: Tile [3, 4]
All Tiles: 
  Tile [1, 2]
  Tile [3, 4]

Tile added: Tile [5, 6]
All Tiles: 
  Tile [1, 2]
  Tile [3, 4]
  Tile [5, 6]

Tile added: Tile [1, 2]
All Tiles: 
  Tile [1, 2]
  Tile [3, 4]
  Tile [5, 6]

Tile added: Tile [5, 6]
All Tiles: 
  Tile [1, 2]
  Tile [3, 4]
  Tile [5, 6]

---

Another possible solution, if you want to use Java 8 streams, note that it has a .filter() method, but this only works with the hashCode and the equals of the objects being streamed, and if you're streaming int arrays by themselves, this simply won't work. A work around is to use a wrapper class, similar to this Stack Overflow answer on "Remove duplicates from a list of objects based on property in Java 8".

A wrapper class that might work:

import java.util.Arrays;

public class WrapperArray {
    int[] array;

    public WrapperArray(int[] array) {
        this.array = array;
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(array);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        WrapperArray other = (WrapperArray) obj;
        if (!Arrays.equals(array, other.array))
            return false;
        return true;
    }

    public int[] unwrap() {
        return array;
    }
}

And this can be tested like so:

import java.util.Arrays;

public class TestTile {
    public static void main(String[] args) {

        int[][] testData = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 1, 2 }, { 5, 6 } };
        System.out.println("before filtering:");
        for (int[] is : testData) {
            System.out.println(Arrays.toString(is));
        }

        int[][] filteredArray = Arrays.stream(testData) // stream int[][] array
                .map(WrapperArray::new)     // map to our wrapper objects
                .distinct()                 // find distinct using wrapper equals/hashCode
                .map(WrapperArray::unwrap)  // convert back to int[]
                .toArray(int[][]::new);     // create new int[][] with results


        System.out.println("after filtering:");
        for (int[] is : filteredArray) {
            System.out.println(Arrays.toString(is));
        }
    }
}

Which returns:

before filtering:
[1, 2]
[3, 4]
[5, 6]
[1, 2]
[5, 6]
after filtering:
[1, 2]
[3, 4]
[5, 6]