Element Duplication Detection in Array Lists

Element Duplication Detection in Array Lists

    Auth: Elliot Iddon
    Vers: 0.1
    Date: 21/1/2012


    1. The Self Detection Problem
    2. The Comparison Optimisation



    1. The Self Detection Problem
        You need to make sure that you don't check the object you're searching
        against for duplication. One way to do this is to add a check
        for same object e.g.

            //In this example I will assume that c is the card you are
            //searching against and d is your current possible duplicate.
            if (..your code to check if the card has the same value and suit...
            && !(c.equals(d)))

        However there are many more elegant solutions to this problem...

    2. The Comparison Optimisation
        Incidentally a more elegant solution to The Self Detection Problem is
        encompassed in an optimisation of which comparisons are performed.

        In a basic nested for loop you might take every element in an array:

         _ _ _ _ _ _ _

         and for each element compare it to every element in the same array:

             //In this diagram I'm assuming that none of the comparisons listed
             are matching cards and therefore the loop proceeds

             * _ _ _ _ _ _ N

             X + _ _ _ _ _ R

             X _ + _ _ _ _

             X _ _ + _ _ _

             X _ _ _ + _ _

             X _ _ _ _ + _

             X _ _ _ _ _ +

             + X _ _ _ _ _ R

             _ * _ _ _ _ _ N

             _ X + _ _ _ _

             _ X _ + _ _ _

             _ X _ _ + _ _

             // here I got bored of writing them out

             ...

             _ _ _ _ _ _ * N

        So the problemed lines are lines marked with a letter.

            N indicates you should never be performing this comparison
            obviously these cards will be the same but not duplicated!
            R indicates this is a repeated comparison (I've just marked
            one pair as I didn't draw the others).

        The solution to both of these is to compare only with elements AFTER the
        element you are checking against.

        The structure of such a solution might be:

        public boolean hasDuplicate(ArrayList<ElementType> l){
            for(int i = 0; i < l.size(); i++){
                ElementType e = l.get(i);
                for(int j = i+1; i < l.size(); j++){
                    ElementType f = l.get(j);
                    if(...some code to check if they are the same...)
                        return true;
                }
            }
            return false;
        }