/*
 *                 Sun Public License Notice
 * 
 * The contents of this file are subject to the Sun Public License
 * Version 1.0 (the "License"). You may not use this file except in
 * compliance with the License. A copy of the License is available at
 * http://www.sun.com/
 * 
 * The Original Code is NetBeans. The Initial Developer of the Original
 * Code is Sun Microsystems, Inc. Portions Copyright 1997-2000 Sun
 * Microsystems, Inc. All Rights Reserved.
 */

package org.netbeans.modules.java.bridge;

import java.beans.PropertyChangeEvent;
import java.util.*;

import org.openide.src.MultiPropertyChangeEvent;

/**
 * This class serves as a base for indexed properties in the model. The class performs
 * basic services as creating diff required to construct a specific PropertyChangeEvent,
 * or to actually handle the property change.
 * The class does not define how a property's value is stored. Its methods are protected;
 * subclasses will bind the algorithms to the actual storage. This base class can be used
 * to implement flyweight logic for "simple" properties too.
 *
 * @author  sdedic
 * @version 
 */
public abstract class IndexedPropertyBase extends Object {
    public static final int SMALL_THRESHOLD = 500;

    private String  propertyName;
    /**
    private MatchStrategy defaultStrategy;
    
     * Strategy that searches for matches between two attribute sets.
    public interface MatchStrategy {
        /** Detects matching items and returns a mapping from new items to the old
         * ones. If a new item does not have a match among the old items, the function
         * report -1 at its position in the resulting array. If there are no differencies
         * between the two item sets, the function may return null.
         * @param it1 old (current) item set
         * @param it2 new (updated) item set
         * @return array indexed by item positions in the new set, containing indexes
         * into the old set.
        public int[] matchItems(Object[] it1, Object[] it2);
    }
    */

    /** Helper information object that carries informations about changes made to the
     * indexed property. This object is much like a diff and reports exact change types
     * made to the property.
     */
    public static class Change {
        // collection of removed items
        public Collection  removed;
        // indexes of the items being removed
        public int[]       removeIndices;
        // permutation of items reordered (if items are removed, the permutation is
        // computed with respect to the new positions)
        public int[]       reordered;
        // collection of new items
        public Collection  inserted;
        // indexes where the new items were inserted
        public int[]       insertIndices;
        // items that replaced others
        public Collection  replacements;
        // indices for replacements
        public int[]       replaceIndices;
        // offsets to add to old positions to get new ones. No value is defined for
        // positions that go away during the change (i.e. matching something from removeIndices)
        // and there's no place to record new ones (those from insertIndices)
        public int[]       offsets;
        // determines how much phases that particular change contains.
        public int         phaseCount;
        
        public int[]       mapping;
        
        public int         sizeDiff;
        
        public String toString() {
            StringBuffer sb = new StringBuffer();
            if (removed != null) {
                sb.append("removed(" + removed.size() + ")"); // NOI18N
            }
            if (reordered != null) {
                sb.append(" reordered "); // NOI18N
            }
            if (inserted != null) {
                sb.append("inserted(" + inserted.size() + ")"); // NOI18N
            }
            if (replacements != null) {
                sb.append("replaced(" + replacements.size() + ")"); // NOI18N
            }
            sb.append("sizedif=" + sizeDiff); // NOI18N
            return sb.toString();
        }
        
        public Object clone() {
            try {
                return super.clone();
            } catch (Exception ex) {
            }
            return null;
        }
    }

    /** Constructs the object. The only parameter is the property name that is used
     * in PropertyChangeEvent construction.
     */
    public IndexedPropertyBase(String propName) {
        this.propertyName = propName;
    }
    
    /** Detects changes in the multivalued property and creates an information
     * object that holds the changes.
     */
    public Change computeChanges(Object[] olds, Object[] newValue) {
        return computeChanges2(olds, newValue, pairItems(olds, newValue));
    }

    /** Detects changes in the multivalued property and creates an information
     * object that holds the changes.
     */
    public static Change computeChanges2(Object[] olds, Object[] newValue, int[] mapping) {
        int[] perm = new int[olds.length];
        int matched = 0;
        int inserted = 0;
        boolean removed = false;
        int reordered = 0;
        int[] insertIndices = null;
        int removeCount;
        int[] offsets = null;
        //int[] reverseOffsets = null;

        //Util.log("-change computation starts"); // NOI18N
        // clean the permutation:
        int oldIndex = 0;
        
        for (int i = 0; i < mapping.length; i++) {
            if (offsets != null && i - inserted < olds.length) {
                offsets[i - inserted] = inserted;
            }
            //Util.log("mapping[" + i + "] = " + mapping[i]); // NOI18N
            if (mapping[i] == -1) {
                // Ith element was newly added.
                if (insertIndices == null) {
                    offsets = new int[olds.length];
                    insertIndices = new int[mapping.length];
                    //reverseOffsets = new int[mapping.length];
                    // insertIndices == null implies that offsets == null
                    // note - item on this - old - position is offsetted too. The
                }
                //Util.log("insertion at " + i); // NOI18N
                insertIndices[inserted] = i;
                inserted++;
            } else {
                perm[mapping[i]] = i + 1;
                /*
                if (inserted > 0)
                    reverseOffsets[i] = -bias;
                 */
                matched++;
            }
        }
        if (inserted > 0 && mapping.length < olds.length) {
            Arrays.fill(offsets, mapping.length, olds.length - 1, inserted);
        }

        removeCount = perm.length - matched;
        removed = removeCount > 0;
        
        Change ch = new Change();
        int eventCount = 0;
        PropertyChangeEvent removeEvent = null, addEvent = null, reorderEvent = null;
        
        if (removed) {
            Collection rem = new ArrayList(perm.length - matched);
            int bias = 0;
            int reorderIndex = 0;
            int removedSoFar = 0;
            int[] indices = new int[removeCount];
            int indicePos = 0;
            int diff = 0;

            // offsets WILL be needed -- if there were no INSERTs, positions were
            // changed if there are some removes. 
            if (offsets == null) {
                offsets = new int[olds.length];
                //reverseOffsets = new int[mapping.length];
            }
            // must fire removed items first.
            for (int i = 0; i < perm.length; i++) {
                if (perm[i] == 0) {
                    //Util.log("removing at index " + i); // NOI18N
                    bias--;
                    indices[indicePos++] = i;
                    rem.add(olds[i]);
                    removedSoFar++;
                    // the client gets position of -1 in the new state ==> item does not exist.
                    offsets[i] = -i - 1;
                } else {
                    offsets[i] += bias;
                    //reverseOffsets[i + bias] -= bias;
                }
            }
            ch.removed = rem;
            ch.removeIndices = indices;
            eventCount++;
        }
        // reorder detection :-(
        if (true) {
            int nextInsert;
            int insertPos = 1;
            
            if (insertIndices == null)
                nextInsert = -1;
            else 
                nextInsert = insertIndices[0];
            int pos = 0;
            
            reordered = 0;
            int j = 0;

            //Util.log("reorder detection: "); // NOI18N
            for (int i = 0; i < perm.length; i++) {
                if (perm[i] == 0) {
                    perm[i] = -1;
                    //Util.log("element " + i + " removed, newPos = " + j); // NOI18N
                    continue;
                }
                int newPlace = perm[i] - 1;
                int expectedPlace = i;
                
                if (offsets != null)
                    expectedPlace += offsets[i];
                /*
                int newPlace = perm[i] - 1;
                 */
                //Util.log("perm[" + i + "] = " + perm[i] + ", offsets[] = " + (offsets == null ? -1 : offsets[i])); // NOI18N
                if (newPlace != expectedPlace) {
                    reordered++;
                    //Util.log("element " + i + " moved to " + reverseOffsets[perm[i] - 1]); // NOI18N
                    perm[i] = newPlace;
                } else {
                    //Util.log("no change for " + i); // NOI18N
                    perm[i] = -1;
                }
                /*
                if (j == nextInsert) {
                    if (insertPos < inserted)
                        nextInsert = insertIndices[insertPos++];
                    else 
                        nextInsert = -1;
                    Util.log("element " + i + " offseted, newPos = " + j); // NOI18N
                    Util.log("next insert is at " + nextInsert); // NOI18N
                }
                if (perm[i] - 1 == j) {
                    Util.log("no change at pos " + i); // NOI18N
                    perm[i] = -1;
                } else {
                    Util.log("element " + i + " moved to " + (perm[i] - 1)); // NOI18N
                    reordered++;
                    perm[i]--;
                }
                j++;
                 */
            }
            if (reordered > 0) {
                ch.reordered = perm;
                eventCount++;
            }
        }
        if (inserted > 0) {
            //Util.log("inserted: " + inserted); // NOI18N
            Collection col = new ArrayList(inserted);
            int[] indices = new int[inserted];
            System.arraycopy(insertIndices, 0, indices, 0, inserted);
            for (int i = 0; i < indices.length; i++) {
                col.add(newValue[insertIndices[i]]);
            }
            ch.inserted = col;
            ch.insertIndices = indices;
            eventCount++;
        }
        ch.offsets = offsets;
        ch.phaseCount = eventCount;
        ch.sizeDiff = inserted - removeCount;
        return ch;
    }

    /** Creates a PropertyChangeEvent based on the Change object.
     */
    public MultiPropertyChangeEvent createPropertyEvent(Change ch, 
        Object source, Object oldV, Object newV) {
        if (ch.phaseCount == 0)
            return null;
        
        MultiPropertyChangeEvent evt = null;
        boolean compound = ch.phaseCount > 1;
        Collection sub = null;

        newV = ((Object[])newV).clone();
        if (compound) {
            sub = new ArrayList(ch.phaseCount);
        } 
        if (ch.inserted != null) {
            evt = createInsertionEvent(source, oldV, newV, ch.inserted,
                ch.insertIndices);
            if (compound)
                sub.add(evt);
        }
        if (ch.removed != null) {
            evt = createRemovalEvent(source, oldV, newV, ch.removed,
                ch.removeIndices);
            if (compound)
                sub.add(evt);
        }
        if (ch.reordered != null) {
            evt = createReorderEvent(source, oldV, newV, ch.reordered);
            if (compound)
                sub.add(evt);
        }
        if (compound) {
            return createCompoundEvent(source, sub, ch.offsets, oldV, newV);
        } else {
            return evt;
        }
    }
    
    public MultiPropertyChangeEvent createChangeEvent(Object source,
        Object[] olds, Object[] newValue) {
        Change ch = computeChanges(olds, newValue);
        return createPropertyEvent(ch, source, olds, newValue);
    }
    
    protected MultiPropertyChangeEvent createInsertionEvent(Object source,
        Object previous, Object now, Collection inserted,
        int[] indices) {
        MultiPropertyChangeEvent insertEvent = new MultiPropertyChangeEvent(
            source,
            getPropertyName(), previous, now);
        insertEvent.makeInsertion(inserted, indices);
        return insertEvent;
    }
    
    protected MultiPropertyChangeEvent createRemovalEvent(Object source,
        Object prev, Object now, Collection removed, int[] indices) {
        MultiPropertyChangeEvent evt = new MultiPropertyChangeEvent(
            source,
            getPropertyName(), prev, now);
        evt.makeRemoval(removed, indices);
        return evt;
    }
    
    protected MultiPropertyChangeEvent createModifyEvent(Object source,
    Object prev, Object now, Collection origs, Collection replacements, int[] indices) {
        MultiPropertyChangeEvent evt = new MultiPropertyChangeEvent(
            source,
            getPropertyName(), prev, now);
        evt.makeReplacement(origs, replacements, indices);
        return evt;
    }
    
    /**
     * Called to create a compound event.
     */
    protected MultiPropertyChangeEvent createCompoundEvent(Object source,
        Collection subEvents, int[] offsets, Object old, Object newValue) {
        MultiPropertyChangeEvent evt = new MultiPropertyChangeEvent(source,
            getPropertyName(), old, newValue);
        evt.makeCompound(subEvents, offsets);
        return evt;
    }
    
    /**
     * Helper function that creates reorder event from the given bean implementation and
     * a permutation of current elements
     * @param beanImpl bean implementation.
     * @param old old value of the whole multivalued property
     * @param now new value of the multivalued property
     * @param perm permutation that describes the change.
     */
    protected MultiPropertyChangeEvent createReorderEvent(Object source,
        Object old, Object now, int[] perm) {
        MultiPropertyChangeEvent evt = new MultiPropertyChangeEvent(source,
            getPropertyName(), old, now);
        evt.makeReorder(perm);
        return evt;
    }

    /** Default, stupid implementation of item matcher. The matcher uses algorithm
     * with complexity of O(n^2) comparing object referencies.
     * @param o first (old) array of objects.
     * @param n second (new) array of objects.
     */
    public int[] pairItems(Object[] o, Object[] n) {
        int[] map = new int[n.length];
        boolean[] used = new boolean[o.length];
        
        for (int i = 0; i < n.length; i++) {
            map[i] = -1;
            for (int j = 0; j < o.length; j++) {
                if (used[j])
                    continue;
                if (o[j] == n[i] || compareValues(o[j], n[i])) {
                    used[j] = true;
                    map[i] = j;
                }
            }
        }
        return map;
    }


    protected int[] createIdentityMap(Object[] els, Object[] olds) {
        int avgOps = els.length * olds.length;
        
        if (avgOps < SMALL_THRESHOLD) {
            
            // fallback to "stupid" method that uses brute force (and is n^2)
            return pairItems(olds, els);
        }
        
        Map indexM = new HashMap((int)(olds.length * 1.3));
        int[] mapping = new int[els.length];
        
        for (int idx = 0; idx < olds.length; idx++) {
            indexM.put(olds[idx], new Integer(idx));
        }
        
        for (int i = 0; i < els.length; i++) {
            Integer pos = (Integer)indexM.get(els[i]);
            mapping[i] = pos == null ? -1 : pos.intValue();
        }
        return mapping;
    }

    /** Returns false, causing the pairItems method to use only object identity for
     * the comparison.
     * @param o1 one object
     * @param o2 another object
     */
    protected boolean compareValues(Object o1, Object o2) {
        return false;
    }
    
    /** Retrieves the source reference from the given bean.
     */
    protected Object getSource(ElementImpl key) {
        return key.getElement();
    }
    
    // 
    ///////////////////////////////////////////////////////////////////////////
    protected String getPropertyName() {
        return propertyName;
    }
}