Finding matching objects in Java

Question

I'm currently trying to match 2 objects based on their values. Except, it's not a.a = a.a, but a.a = a.b and a.b = b.a. This means that overriding equals is an option but it's certainly not the right option.

While sorting these objects will make the matching time quicker, the population will be small so it is unnecessary. Also, compareTo isn't exactly right either for the same reason given for equals.

Do I simply make my own method in case? There will be 4 fields to match which is why I am not using an if statement up front.

public boolean isOpposite(Object other) {
    return (this.a == other.b) ? true : false;
}

There is also the possibility that the object will implement/extend a base object to take on more fields and implement its own way of matching.

I'm considering using a LinkedList because I know it to be quicker for use than ArrayList, however I've also been considering Maps. Edit: better explanation of objects

    public class Obj {     
public String a;     
public String b;     
public String c;     
public double d;    
}

The relationships are as follows:

    Obj obj1, obj2;
obj1.a == obj2.b //.equals for String of course
obj1.b == obj2.a
obj1.c == obj2.c
obj1.d == obj2.d * -1

Answer 1

I've done some testing and determined that the cleanest way I knew how to implement this was with using ArrayList<Obj>.

This was my implementation:

public static List<ObjGroup> getNewSampleGroup(int size) {
    List<ObjGroup> sampleGroup = new ArrayList<ObjGroup>();
    sampleGroup.add(new ObjGroup((generateNumbers(size, 1)))); //Positives
    sampleGroup.add(new ObjGroup((generateNumbers(size, -1)))); //Negatives
    return sampleGroup;
}

private static List<Obj> generateNumbers(int size, int x) {
    List<Obj> sampleGroup = new ArrayList<Obj>();
    for (int i = 0; i < size; i ++) {
        Random rand = new Random();
        String randC;
        String randA;
        String randB;
        double randD;

        if (x == 1) {
            randD = rand.nextInt((maxP - minP + 1) + minP);
            randA = "aval";// + String.valueOf(rand.nextInt((max - min + 1) + min));
            randB = "bval";// + String.valueOf(rand.nextInt((max - min + 1) + min));
            randC = "cval";// + String.valueOf(rand.nextInt((max - min + 1) + min));
        } else {
            randD = rand.nextInt((maxP - minP + 1) + minP) * -1;
            randA = "bval";// + String.valueOf(rand.nextInt((max - min + 1) + min));
            randB = "aval";// + String.valueOf(rand.nextInt((max - min + 1) + min));
            randC = "cval";// + String.valueOf(rand.nextInt((max - min + 1) + min));
        }
        sampleGroup.add(new Obj(randA, randB, randC, randD));
    }
    return sampleGroup;
}

public List<ObjGroup> findMatches(List<ObjGroup> unmatchedList) {
    List<Obj> pivotPos = unmatchedList.get(0).getObjs(); //First grouping are positives
    List<Obj> pivotNeg = unmatchedList.get(1).getObjs(); //Second grouping are negatives
    List<ObjGroup> matchedList = new ArrayList<ObjGroup>();
    long iterations = 0;

    Collections.sort(pivotPos);
    Collections.sort(pivotNeg, Collections.reverseOrder());

    for (Iterator<Obj> iteratorPos = pivotPos.iterator(); iteratorPos.hasNext();) {
        final Obj focus = iteratorPos.next();
        iteratorPos.remove(); //Remove this once pulled as you won't match it again.
        for (Iterator<Obj> iteratorNeg = pivotNeg.iterator(); iteratorNeg.hasNext();) {
            final Obj candidate = iteratorNeg.next();
            if (compare(focus, candidate)) {
                matchedList.add(new ObjGroup(new ArrayList<Obj>() {
                    {
                        add(focus);
                        add(candidate);
                    }
                }));
                iteratorNeg.remove(); //Remove this once matched as you won't match it again.
                break;
            }
            iterations ++;
        }
        iterations ++;
    }
    return matchedList;
}

I ran this against a sample size of 4,000,000 psuedo random Obj objects. This was my output:

Starting matching test.
18481512007 iterations.
3979042 matched objects.
10479 unmatched objects.
Processing time: 44 minutes.
There were 1989521 number of matches found.
Closing matching test.

Answer 2

Overriding the equals or compareTo is not the right way to go, as you've mentioned. Because there is an assumption that both methods should be transitive, i.e. A eq B and B eq C => A eq C but it doesn't hold for the "opposite" objects. It's good to know, because you can't define a equivalence class and partition it into subsets, but you need to find all the pairs (depending on your use case).

Not sure, what is your goal. If you have some containers with such objects and you need to find all pairs that suffice the condition, then I am afraid you'd need to do n^2 comparisons.

I'll probably create two hash sets, one with the originals and second with the opposites and ask if the second hash set contains the opposite of each member of original hash set.