/*******************************************************************************
 * Copyright (c) 2006, 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *     Matthew Hall - bug 226216
 *******************************************************************************/

module org.eclipse.core.databinding.observable.Diffs;

import java.lang.all;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import org.eclipse.core.databinding.observable.list.ListDiff;
import org.eclipse.core.databinding.observable.list.ListDiffEntry;
import org.eclipse.core.databinding.observable.map.MapDiff;
import org.eclipse.core.databinding.observable.set.SetDiff;
import org.eclipse.core.databinding.observable.value.ValueDiff;
import org.eclipse.core.internal.databinding.Util;

/**
 * @since 1.0
 * 
 */
public class Diffs {

    /**
     * @param oldList
     * @param newList
     * @return the differences between oldList and newList
     */
    public static ListDiff computeListDiff(List oldList, List newList) {
        List diffEntries = new ArrayList();
        createListDiffs(new ArrayList(oldList), newList, diffEntries);
        ListDiff listDiff = createListDiff(cast(ListDiffEntry[]) diffEntries
                .toArray(new ListDiffEntry[diffEntries.size()]));
        return listDiff;
    }
    
    /**
     * adapted from EMF's ListDifferenceAnalyzer
     */
    private static void createListDiffs(List oldList, List newList,
            List listDiffs) {
        int index = 0;
        for (Iterator it = newList.iterator(); it.hasNext();) {
            Object newValue = it.next();
            if (oldList.size() <= index) {
                // append newValue to newList 
                listDiffs.add(createListDiffEntry(index, true, newValue));
            } else {
                bool done;
                do {
                    done = true;
                    Object oldValue = oldList.get(index);
                    if (oldValue is null ? newValue !is null : !oldValue.equals(newValue)) {
                        int oldIndexOfNewValue = listIndexOf(oldList, newValue, index);
                        if (oldIndexOfNewValue !is -1) {
                            int newIndexOfOldValue = listIndexOf(newList, oldValue, index);
                            if (newIndexOfOldValue is -1) {
                                // removing oldValue from list[index]
                                listDiffs.add(createListDiffEntry(index, false, oldValue));
                                oldList.remove(index);
                                done = false;
                            } else if (newIndexOfOldValue > oldIndexOfNewValue) {
                                // moving oldValue from list[index] to [newIndexOfOldValue] 
                                if (oldList.size() <= newIndexOfOldValue) {
                                    // The element cannot be moved to the correct index
                                    // now, however later iterations will insert elements
                                    // in front of it, eventually moving it into the
                                    // correct spot.
                                    newIndexOfOldValue = oldList.size() - 1;
                                }
                                listDiffs.add(createListDiffEntry(index, false, oldValue));
                                oldList.remove(index);
                                listDiffs.add(createListDiffEntry(newIndexOfOldValue, true, oldValue));
                                oldList.add(newIndexOfOldValue, oldValue);
                                done = false;
                            } else {
                                // move newValue from list[oldIndexOfNewValue] to [index]
                                listDiffs.add(createListDiffEntry(oldIndexOfNewValue, false, newValue));
                                oldList.remove(oldIndexOfNewValue);
                                listDiffs.add(createListDiffEntry(index, true, newValue));
                                oldList.add(index, newValue);
                            }
                        } else {
                            // add newValue at list[index]
                            oldList.add(index, newValue);
                            listDiffs.add(createListDiffEntry(index, true, newValue));
                        }
                    }
                } while (!done);
            }
            ++index;
        }
        for (int i = oldList.size(); i > index;) {
            // remove excess trailing elements not present in newList
            listDiffs.add(createListDiffEntry(--i, false, oldList.get(i)));
        }
    }

    /**
     * @param list
     * @param object
     * @param index
     * @return the index, or -1 if not found
     */
    private static int listIndexOf(List list, Object object, int index) {
        int size = list.size();
        for (int i=index; i<size;i++) {
            Object candidate = list.get(i);
            if (candidateisnull ? objectisnull : candidate.equals(object)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * Checks whether the two objects are <code>null</code> -- allowing for
     * <code>null</code>.
     * 
     * @param left
     *            The left object to compare; may be <code>null</code>.
     * @param right
     *            The right object to compare; may be <code>null</code>.
     * @return <code>true</code> if the two objects are equivalent;
     *         <code>false</code> otherwise.
     */
    public static final override equals_t opEquals(final Object left, final Object right) {
        return left is null ? right is null : ((right !is null) && left
                .equals(right));
    }

    /**
     * @param oldSet
     * @param newSet
     * @return a set diff
     */
    public static SetDiff computeSetDiff(Set oldSet, Set newSet) {
        Set additions = new HashSet(newSet);
        additions.removeAll(oldSet);
        Set removals = new HashSet(oldSet);
        removals.removeAll(newSet);
        return createSetDiff(additions, removals);
    }

    /**
     * Computes the difference between two maps.
     * 
     * @param oldMap
     * @param newMap
     * @return a map diff representing the changes needed to turn oldMap into
     *         newMap
     */
    public static MapDiff computeMapDiff(Map oldMap, Map newMap) {
        // starts out with all keys from the new map, we will remove keys from
        // the old map as we go
        final Set addedKeys = new HashSet(newMap.keySet());
        final Set removedKeys = new HashSet();
        final Set changedKeys = new HashSet();
        final Map oldValues = new HashMap();
        final Map newValues = new HashMap();
        for (Iterator it = oldMap.entrySet().iterator(); it.hasNext();) {
            Map.Entry oldEntry = cast(Entry) it.next();
            Object oldKey = oldEntry.getKey();
            if (addedKeys.remove(oldKey)) {
                // potentially changed key since it is in oldMap and newMap
                Object oldValue = oldEntry.getValue();
                Object newValue = newMap.get(oldKey);
                if (!Util.equals(oldValue, newValue)) {
                    changedKeys.add(oldKey);
                    oldValues.put(oldKey, oldValue);
                    newValues.put(oldKey, newValue);
                }
            } else {
                removedKeys.add(oldKey);
                oldValues.put(oldKey, oldEntry.getValue());
            }
        }
        for (Iterator it = addedKeys.iterator(); it.hasNext();) {
            Object newKey = it.next();
            newValues.put(newKey, newMap.get(newKey));
        }
        return new class() MapDiff {
            public Set getAddedKeys() {
                return addedKeys;
            }

            public Set getChangedKeys() {
                return changedKeys;
            }

            public Set getRemovedKeys() {
                return removedKeys;
            }

            public Object getNewValue(Object key) {
                return newValues.get(key);
            }

            public Object getOldValue(Object key) {
                return oldValues.get(key);
            }
        };
    }
    
    /**
     * @param oldValue
     * @param newValue
     * @return a value diff
     */
    public static ValueDiff createValueDiff(final Object oldValue,
            final Object newValue) {
        return new class() ValueDiff {

            public Object getOldValue() {
                return oldValue;
            }

            public Object getNewValue() {
                return newValue;
            }
        };
    }

    /**
     * @param additions
     * @param removals
     * @return a set diff
     */
    public static SetDiff createSetDiff(Set additions, Set removals) {
        final Set unmodifiableAdditions = Collections
                .unmodifiableSet(additions);
        final Set unmodifiableRemovals = Collections.unmodifiableSet(removals);
        return new class() SetDiff {

            public Set getAdditions() {
                return unmodifiableAdditions;
            }

            public Set getRemovals() {
                return unmodifiableRemovals;
            }
        };
    }

    /**
     * @param difference
     * @return a list diff with one differing entry
     */
    public static ListDiff createListDiff(ListDiffEntry difference) {
        return createListDiff(new ListDiffEntry[] { difference });
    }

    /**
     * @param difference1
     * @param difference2
     * @return a list diff with two differing entries
     */
    public static ListDiff createListDiff(ListDiffEntry difference1,
            ListDiffEntry difference2) {
        return createListDiff(new ListDiffEntry[] { difference1, difference2 });
    }

    /**
     * @param differences
     * @return a list diff with the given entries
     */
    public static ListDiff createListDiff(final ListDiffEntry[] differences) {
        return new class() ListDiff {
            public ListDiffEntry[] getDifferences() {
                return differences;
            }
        };
    }

    /**
     * @param position
     * @param isAddition
     * @param element
     * @return a list diff entry
     */
    public static ListDiffEntry createListDiffEntry(final int position,
            final bool isAddition, final Object element) {
        return new class() ListDiffEntry {

            public int getPosition() {
                return position;
            }

            public bool isAddition() {
                return isAddition;
            }

            public Object getElement() {
                return element;
            }
        };
    }

    /**
     * @param addedKey
     * @param newValue
     * @return a map diff
     */
    public static MapDiff createMapDiffSingleAdd(final Object addedKey,
            final Object newValue) {
        return new class() MapDiff {

            public Set getAddedKeys() {
                return Collections.singleton(addedKey);
            }

            public Set getChangedKeys() {
                return Collections.EMPTY_SET;
            }

            public Object getNewValue(Object key) {
                return newValue;
            }

            public Object getOldValue(Object key) {
                return null;
            }

            public Set getRemovedKeys() {
                return Collections.EMPTY_SET;
            }
        };
    }

    /**
     * @param existingKey
     * @param oldValue
     * @param newValue
     * @return a map diff
     */
    public static MapDiff createMapDiffSingleChange(final Object existingKey,
            final Object oldValue, final Object newValue) {
        return new class() MapDiff {

            public Set getAddedKeys() {
                return Collections.EMPTY_SET;
            }

            public Set getChangedKeys() {
                return Collections.singleton(existingKey);
            }

            public Object getNewValue(Object key) {
                return newValue;
            }

            public Object getOldValue(Object key) {
                return oldValue;
            }

            public Set getRemovedKeys() {
                return Collections.EMPTY_SET;
            }
        };
    }

    /**
     * @param removedKey
     * @param oldValue
     * @return a map diff
     */
    public static MapDiff createMapDiffSingleRemove(final Object removedKey,
            final Object oldValue) {
        return new class() MapDiff {

            public Set getAddedKeys() {
                return Collections.EMPTY_SET;
            }

            public Set getChangedKeys() {
                return Collections.EMPTY_SET;
            }

            public Object getNewValue(Object key) {
                return null;
            }

            public Object getOldValue(Object key) {
                return oldValue;
            }

            public Set getRemovedKeys() {
                return Collections.singleton(removedKey);
            }
        };
    }

    /**
     * @param copyOfOldMap
     * @return a map diff
     */
    public static MapDiff createMapDiffRemoveAll(final Map copyOfOldMap) {
        return new class() MapDiff {

            public Set getAddedKeys() {
                return Collections.EMPTY_SET;
            }

            public Set getChangedKeys() {
                return Collections.EMPTY_SET;
            }

            public Object getNewValue(Object key) {
                return null;
            }

            public Object getOldValue(Object key) {
                return copyOfOldMap.get(key);
            }

            public Set getRemovedKeys() {
                return copyOfOldMap.keySet();
            }
        };
    }

    /**
     * @param addedKeys
     * @param removedKeys
     * @param changedKeys
     * @param oldValues
     * @param newValues
     * @return a map diff
     */
    public static MapDiff createMapDiff(final Set addedKeys,
            final Set removedKeys, final Set changedKeys, final Map oldValues,
            final Map newValues) {
        return new class() MapDiff {

            public Set getAddedKeys() {
                return addedKeys;
            }

            public Set getChangedKeys() {
                return changedKeys;
            }

            public Object getNewValue(Object key) {
                return newValues.get(key);
            }

            public Object getOldValue(Object key) {
                return oldValues.get(key);
            }

            public Set getRemovedKeys() {
                return removedKeys;
            }
        };
    }
}