Tuesday, October 05, 2010

Java : Get difference between two sets

Use this generic method to get the difference between to Sets. The sets should have ordered iterators. I used TreeSet in the calling code.



    // returns the difference between two sets <set1>, <set2> as a pair
    // where pair.one is the set of new entries and pair.two is the set of deleted entries
    // between <set1> and <set2>
    public static <T extends Comparable<T>> Pair<Set<T>,Set<T>> diff(Set<T> set1, Set<T> set2) {
        Set<T> deleted = new TreeSet<T>();
        Set<T> added = new TreeSet<T>();

        Iterator<T> it1 = set1.iterator();
        Iterator<T> it2 = set2.iterator();

        int diff = 0;
        T obj1 = null;
        T obj2 = null;
        while (it1.hasNext() && it2.hasNext()) {
            if (diff == 0) {
                obj1 = it1.next();
                obj2 = it2.next();
            } else if (diff < 0) {
                deleted.add(obj1);
                obj1 = it1.next();
            } else {
                added.add(obj2);
                obj2 = it2.next();
            }

            diff = obj1.compareTo(obj2);
        }

        if (diff < 0) {
            deleted.add(obj1);
            boolean addFlag = true;
            while (it1.hasNext()) {
                obj1 = it1.next();
                diff = obj1.compareTo(obj2);
                if (diff != 0) {
                   deleted.add(obj1);
                } else {
                   addFlag = false; 
                }
            }
            if (addFlag) {
                added.add(obj2);
            }
        } else if (diff > 0){
            added.add(obj2);
            boolean addFlag = true;
            while (it2.hasNext()) {
                obj2 = it2.next();
                diff = obj1.compareTo(obj2);
                if (diff != 0) {
                    added.add(obj2);
                } else {
                    addFlag = false;
                }
            }
            if (addFlag) {
                deleted.add(obj1);
            }
        }
        Iterator<T> remIt = it1.hasNext() ? it1 : it2;
        Set<T> remSet = it1.hasNext() ?  deleted : added;

        T obj;
        while (remIt.hasNext()) {
            obj = remIt.next();
            remSet.add(obj);
        }
        return new Pair<Set<T>, Set<T>>(added, deleted);


    }

No comments: