DeepEqualsUpdated.java

package com.westwingnow.android.utils;

import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Test two objects for equivalence with a 'deep' comparison.  This will traverse
 * the Object graph and perform either a field-by-field comparison on each
 * object (if no .equals() method has been overridden from Object), or it
 * will call the customized .equals() method if it exists.  This method will
 * allow object graphs loaded at different times (with different object ids)
 * to be reliably compare
 *
 * Source of open-source lib the file is taken from: https://github.com/jdereg/java-util/
 * Exact file URL: https://github.com/jdereg/java-util/blob/5277d9d838e8d08aae1b0a6ae25e62c2dfd7f026/src/main/java/com/cedarsoftware/util/DeepEquals.java
 * License: Apache License 2.0 (Commercial use - allowed)
 **/
public class DeepEquals {
    private DeepEquals() {
    }

    static final String IGNORE_CUSTOM_EQUALS = "ignoreCustomEquals";
    private static final Map<Class, Boolean> _customEquals = new ConcurrentHashMap<>();
    private static final Map<Class, Boolean> _customHash = new ConcurrentHashMap<>();
    private static final double doubleEplison = 1e-15;
    private static final double floatEplison = 1e-6;
    private static final Set<Class> prims = new HashSet<>();

    static {
        prims.add(Byte.class);
        prims.add(Integer.class);
        prims.add(Long.class);
        prims.add(Double.class);
        prims.add(Character.class);
        prims.add(Float.class);
        prims.add(Boolean.class);
        prims.add(Short.class);
    }

    private final static class DualKey {
        private final Object _key1;
        private final Object _key2;

        private DualKey(Object k1, Object k2) {
            _key1 = k1;
            _key2 = k2;
        }

        public boolean equals(Object other) {
            if (!(other instanceof DualKey)) {
                return false;
            }

            DualKey that = (DualKey) other;
            return _key1 == that._key1 && _key2 == that._key2;
        }

        public int hashCode() {
            int h1 = _key1 != null ? _key1.hashCode() : 0;
            int h2 = _key2 != null ? _key2.hashCode() : 0;
            return h1 + h2;
        }
    }

    public static boolean deepEquals(Object a, Object b) {
        HashMap params = new HashMap();
        params.put(IGNORE_CUSTOM_EQUALS, new HashSet<>());

        return deepEquals(a, b, params);
    }

    static boolean deepEquals(Object a, Object b, Map options) {
        Set<DualKey> visited = new HashSet<>();
        Deque<DualKey> stack = new LinkedList<>();
        Set<String> ignoreCustomEquals = (Set<String>) options.get(IGNORE_CUSTOM_EQUALS);
        stack.addFirst(new DualKey(a, b));

        while (!stack.isEmpty()) {
            DualKey dualKey = stack.removeFirst();
            visited.add(dualKey);

            if (dualKey._key1 == dualKey._key2) {   // Same instance is always equal to itself.
                continue;
            }

            if (dualKey._key1 == null || dualKey._key2 == null) {   // If either one is null, not equal (both can't be null, due to above comparison).
                return false;
            }

            if (dualKey._key1 instanceof Double && compareFloatingPointNumbers(dualKey._key1, dualKey._key2, doubleEplison)) {
                continue;
            }

            if (dualKey._key1 instanceof Float && compareFloatingPointNumbers(dualKey._key1, dualKey._key2, floatEplison)) {
                continue;
            }

            Class key1Class = dualKey._key1.getClass();

            if (key1Class.isPrimitive() || prims.contains(key1Class) || dualKey._key1 instanceof String || dualKey._key1 instanceof Date || dualKey._key1 instanceof Class) {
                if (!dualKey._key1.equals(dualKey._key2)) {
                    return false;
                }
                continue;   // Nothing further to push on the stack
            }

            if (dualKey._key1 instanceof Collection) {   // If Collections, they both must be Collection
                if (!(dualKey._key2 instanceof Collection)) {
                    return false;
                }
            } else if (dualKey._key2 instanceof Collection) {   // They both must be Collection
                return false;
            }

            if (dualKey._key1 instanceof SortedSet) {
                if (!(dualKey._key2 instanceof SortedSet)) {
                    return false;
                }
            } else if (dualKey._key2 instanceof SortedSet) {
                return false;
            }

            if (dualKey._key1 instanceof SortedMap) {
                if (!(dualKey._key2 instanceof SortedMap)) {
                    return false;
                }
            } else if (dualKey._key2 instanceof SortedMap) {
                return false;
            }

            if (dualKey._key1 instanceof Map) {
                if (!(dualKey._key2 instanceof Map)) {
                    return false;
                }
            } else if (dualKey._key2 instanceof Map) {
                return false;
            }

            if (!isContainerType(dualKey._key1) && !isContainerType(dualKey._key2) && !key1Class.equals(dualKey._key2.getClass())) {   // Must be same class
                return false;
            }

            // Handle all [] types.  In order to be equal, the arrays must be the same
            // length, be of the same type, be in the same order, and all elements within
            // the array must be deeply equivalent.
            if (key1Class.isArray()) {
                if (!compareArrays(dualKey._key1, dualKey._key2, stack, visited)) {
                    return false;
                }
                continue;
            }

            // Special handle SortedSets because they are fast to compare because their
            // elements must be in the same order to be equivalent Sets.
            if (dualKey._key1 instanceof SortedSet) {
                if (!compareOrderedCollection((Collection) dualKey._key1, (Collection) dualKey._key2, stack, visited)) {
                    return false;
                }
                continue;
            }

            // Handled unordered Sets.  This is a slightly more expensive comparison because order cannot
            // be assumed, a temporary Map must be created, however the comparison still runs in O(N) time.
            if (dualKey._key1 instanceof Set) {
                if (!compareUnorderedCollection((Collection) dualKey._key1, (Collection) dualKey._key2, stack, visited)) {
                    return false;
                }
                continue;
            }

            // Check any Collection that is not a Set.  In these cases, element order
            // matters, therefore this comparison is faster than using unordered comparison.
            if (dualKey._key1 instanceof Collection) {
                if (!compareOrderedCollection((Collection) dualKey._key1, (Collection) dualKey._key2, stack, visited)) {
                    return false;
                }
                continue;
            }

            // Compare two SortedMaps.  This takes advantage of the fact that these
            // Maps can be compared in O(N) time due to their ordering.
            if (dualKey._key1 instanceof SortedMap) {
                if (!compareSortedMap((SortedMap) dualKey._key1, (SortedMap) dualKey._key2, stack, visited)) {
                    return false;
                }
                continue;
            }

            // Compare two Unordered Maps. This is a slightly more expensive comparison because
            // order cannot be assumed, therefore a temporary Map must be created, however the
            // comparison still runs in O(N) time.
            if (dualKey._key1 instanceof Map) {
                if (!compareUnorderedMap((Map) dualKey._key1, (Map) dualKey._key2, stack, visited)) {
                    return false;
                }
                continue;
            }

            // If there is a custom equals ... AND
            // the caller has not specified any classes to skip ... OR
            // the caller has specified come classes to ignore and this one is not in the list ... THEN
            // compare using the custom equals.
            if (hasCustomEquals(key1Class)) {
                if (ignoreCustomEquals == null || (ignoreCustomEquals.size() > 0 && !ignoreCustomEquals.contains(key1Class))) {
                    if (!dualKey._key1.equals(dualKey._key2)) {
                        return false;
                    }
                    continue;
                }
            }

            Collection<Field> fields = ReflectionUtils.getDeepDeclaredFields(key1Class);

            for (Field field : fields) {
                try {
                    DualKey dk = new DualKey(field.get(dualKey._key1), field.get(dualKey._key2));
                    if (!visited.contains(dk)) {
                        stack.addFirst(dk);
                    }
                } catch (Exception ignored) {
                }
            }
        }

        return true;
    }

    private static boolean isContainerType(Object o) {
        return o instanceof Collection || o instanceof Map;
    }

    private static boolean compareArrays(Object array1, Object array2, Deque stack, Set visited) {
        int len = Array.getLength(array1);
        if (len != Array.getLength(array2)) {
            return false;
        }

        for (int i = 0; i < len; i++) {
            DualKey dk = new DualKey(Array.get(array1, i), Array.get(array2, i));
            if (!visited.contains(dk)) {   // push contents for further comparison
                stack.addFirst(dk);
            }
        }
        return true;
    }

    private static boolean compareOrderedCollection(Collection col1, Collection col2, Deque stack, Set visited) {
        if (col1.size() != col2.size()) {
            return false;
        }

        Iterator i1 = col1.iterator();
        Iterator i2 = col2.iterator();

        while (i1.hasNext()) {
            DualKey dk = new DualKey(i1.next(), i2.next());
            if (!visited.contains(dk)) {   // push contents for further comparison
                stack.addFirst(dk);
            }
        }
        return true;
    }

    private static boolean compareUnorderedCollection(Collection col1, Collection col2, Deque stack, Set visited) {
        if (col1.size() != col2.size()) {
            return false;
        }

        Map<Integer, Collection> fastLookup = new HashMap<>();
        for (Object o : col2) {
            int hash = deepHashCode(o);
            Collection items = fastLookup.get(hash);
            if (items == null) {
                items = new ArrayList();
                fastLookup.put(hash, items);
            }
            items.add(o);
        }

        for (Object o : col1) {
            Collection other = fastLookup.get(deepHashCode(o));
            if (other == null || other.isEmpty()) {   // fail fast: item not even found in other Collection, no need to continue.
                return false;
            }

            if (other.size() == 1) {   // no hash collision, items must be equivalent or deepEquals is false
                DualKey dk = new DualKey(o, other.iterator().next());
                if (!visited.contains(dk)) {   // Place items on 'stack' for future equality comparison.
                    stack.addFirst(dk);
                }
            } else {   // hash collision: try all collided items against the current item (if 1 equals, we are good - remove it
                // from collision list, making further comparisons faster)
                if (!isContained(o, other)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean compareSortedMap(SortedMap map1, SortedMap map2, Deque stack, Set visited) {
        if (map1.size() != map2.size()) {
            return false;
        }

        Iterator i1 = map1.entrySet().iterator();
        Iterator i2 = map2.entrySet().iterator();

        while (i1.hasNext()) {
            Map.Entry entry1 = (Map.Entry) i1.next();
            Map.Entry entry2 = (Map.Entry) i2.next();

            // Must split the Key and Value so that Map.Entry's equals() method is not used.
            DualKey dk = new DualKey(entry1.getKey(), entry2.getKey());
            if (!visited.contains(dk)) {   // Push Keys for further comparison
                stack.addFirst(dk);
            }

            dk = new DualKey(entry1.getValue(), entry2.getValue());
            if (!visited.contains(dk)) {   // Push values for further comparison
                stack.addFirst(dk);
            }
        }
        return true;
    }

    private static boolean compareUnorderedMap(Map map1, Map map2, Deque stack, Set visited) {
        if (map1.size() != map2.size()) {
            return false;
        }

        Map<Integer, Collection<Map.Entry>> fastLookup = new HashMap<>();

        for (Map.Entry entry : (Set<Map.Entry>) map2.entrySet()) {
            int hash = deepHashCode(entry.getKey());
            Collection items = fastLookup.get(hash);
            if (items == null) {
                items = new ArrayList();
                fastLookup.put(hash, items);
            }
            items.add(entry);
        }

        for (Map.Entry entry : (Set<Map.Entry>) map1.entrySet()) {
            Collection<Map.Entry> other = fastLookup.get(deepHashCode(entry.getKey()));
            if (other == null || other.isEmpty()) {
                return false;
            }

            if (other.size() == 1) {
                Map.Entry entry2 = other.iterator().next();
                DualKey dk = new DualKey(entry.getKey(), entry2.getKey());
                if (!visited.contains(dk)) {   // Push keys for further comparison
                    stack.addFirst(dk);
                }

                dk = new DualKey(entry.getValue(), entry2.getValue());
                if (!visited.contains(dk)) {   // Push values for further comparison
                    stack.addFirst(dk);
                }
            } else {   // hash collision: try all collided items against the current item (if 1 equals, we are good - remove it
                // from collision list, making further comparisons faster)
                if (!isContained(entry, other)) {
                    return false;
                }
            }
        }

        return true;
    }

    private static boolean isContained(Object o, Collection other) {
        boolean found = false;
        Iterator i = other.iterator();
        while (i.hasNext()) {
            Object x = i.next();
            if (DeepEquals.deepEquals(o, x)) {
                found = true;
                i.remove(); // can only be used successfully once - remove from list
                break;
            }
        }
        return found;
    }

    private static boolean compareFloatingPointNumbers(Object a, Object b, double epsilon) {
        double a1 = a instanceof Double ? (Double) a : (Float) a;
        double b1 = b instanceof Double ? (Double) b : (Float) b;
        return nearlyEqual(a1, b1, epsilon);
    }

    private static boolean nearlyEqual(double a, double b, double epsilon) {
        final double absA = Math.abs(a);
        final double absB = Math.abs(b);
        final double diff = Math.abs(a - b);

        if (a == b) { // shortcut, handles infinities
            return true;
        } else if (a == 0 || b == 0 || diff < Double.MIN_NORMAL) {
            // a or b is zero or both are extremely close to it
            // relative error is less meaningful here
            return diff < (epsilon * Double.MIN_NORMAL);
        } else { // use relative error
            return diff / (absA + absB) < epsilon;
        }
    }

    static boolean hasCustomEquals(Class c) {
        Class origClass = c;
        if (_customEquals.containsKey(c)) {
            return _customEquals.get(c);
        }

        while (!Object.class.equals(c)) {
            try {
                c.getDeclaredMethod("equals", Object.class);
                _customEquals.put(origClass, true);
                return true;
            } catch (Exception ignored) {
            }
            c = c.getSuperclass();
        }
        _customEquals.put(origClass, false);
        return false;
    }

    static int deepHashCode(Object obj) {
        Set<Object> visited = new HashSet<>();
        LinkedList<Object> stack = new LinkedList<>();
        stack.addFirst(obj);
        int hash = 0;

        while (!stack.isEmpty()) {
            obj = stack.removeFirst();
            if (obj == null || visited.contains(obj)) {
                continue;
            }

            visited.add(obj);

            if (obj.getClass().isArray()) {
                int len = Array.getLength(obj);
                for (int i = 0; i < len; i++) {
                    stack.addFirst(Array.get(obj, i));
                }
                continue;
            }

            if (obj instanceof Collection) {
                stack.addAll(0, (Collection) obj);
                continue;
            }

            if (obj instanceof Map) {
                stack.addAll(0, ((Map) obj).keySet());
                stack.addAll(0, ((Map) obj).values());
                continue;
            }

            if (obj instanceof Double || obj instanceof Float) {
                // just take the integral value for hashcode
                // equality tests things more comprehensively
                stack.add(Math.round(((Number) obj).doubleValue()));
                continue;
            }

            if (hasCustomHashCode(obj.getClass())) {   // A real hashCode() method exists, call it.
                hash += obj.hashCode();
                continue;
            }

            Collection<Field> fields = ReflectionUtils.getDeepDeclaredFields(obj.getClass());
            for (Field field : fields) {
                try {
                    stack.addFirst(field.get(obj));
                } catch (Exception ignored) {
                }
            }
        }
        return hash;
    }


    static boolean hasCustomHashCode(Class c) {
        Class origClass = c;
        if (_customHash.containsKey(c)) {
            return _customHash.get(c);
        }

        while (!Object.class.equals(c)) {
            try {
                c.getDeclaredMethod("hashCode");
                _customHash.put(origClass, true);
                return true;
            } catch (Exception ignored) {
            }
            c = c.getSuperclass();
        }
        _customHash.put(origClass, false);
        return false;
    }
}