/*

 * Copyright 1997-2008 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

package javax.swing.tree;

import java.beans.PropertyChangeListener;

import java.io.*;

import java.util.ArrayList;

import java.util.BitSet;

import java.util.Enumeration;

import java.util.EventListener;

import java.util.Hashtable;

import java.util.List;

import java.util.Vector;

import javax.swing.event.*;

import javax.swing.DefaultListSelectionModel;

/**

 * Default implementation of TreeSelectionModel.  Listeners are notified

 * whenever

 * the paths in the selection change, not the rows. In order

 * to be able to track row changes you may wish to become a listener

 * for expansion events on the tree and test for changes from there.

 * <p>resetRowSelection is called from any of the methods that update

 * the selected paths. If you subclass any of these methods to

 * filter what is allowed to be selected, be sure and message

 * <code>resetRowSelection</code> if you do not message super.

 *

 * <strong>Warning:</strong>

 * Serialized objects of this class will not be compatible with

 * future Swing releases. The current serialization support is

 * appropriate for short term storage or RMI between applications running

 * the same version of Swing.  As of 1.4, support for long term storage

 * of all JavaBeans<sup><font size="-2">TM</font></sup>

 * has been added to the <code>java.beans</code> package.

 * Please see {@link java.beans.XMLEncoder}.

 *

 * @see javax.swing.JTree

 *

 * @author Scott Violet

 */

public class DefaultTreeSelectionModel implements Cloneable, Serializable, TreeSelectionModel

{

    /** Property name for selectionMode. */

    public static final String          SELECTION_MODE_PROPERTY = "selectionMode";

    /** Used to messaged registered listeners. */

    protected SwingPropertyChangeSupport     changeSupport;

    /** Paths that are currently selected.  Will be null if nothing is

      * currently selected. */

    protected TreePath[]                selection;

    /** Event listener list. */

    protected EventListenerList   listenerList = new EventListenerList();

    /** Provides a row for a given path. */

    transient protected RowMapper               rowMapper;

    /** Handles maintaining the list selection model. The RowMapper is used

     * to map from a TreePath to a row, and the value is then placed here. */

    protected DefaultListSelectionModel     listSelectionModel;

    /** Mode for the selection, will be either SINGLE_TREE_SELECTION,

     * CONTIGUOUS_TREE_SELECTION or DISCONTIGUOUS_TREE_SELECTION.

     */

    protected int                           selectionMode;

    /** Last path that was added. */

    protected TreePath                      leadPath;

    /** Index of the lead path in selection. */

    protected int                           leadIndex;

    /** Lead row. */

    protected int                           leadRow;

    /** Used to make sure the paths are unique, will contain all the paths

     * in <code>selection</code>.

     */

    private Hashtable<TreePath, Boolean>    uniquePaths;

    private Hashtable<TreePath, Boolean>    lastPaths;

    private TreePath[]                      tempPaths;

    /**

     * Creates a new instance of DefaultTreeSelectionModel that is

     * empty, with a selection mode of DISCONTIGUOUS_TREE_SELECTION.

     */

    public DefaultTreeSelectionModel() {

        listSelectionModel = new DefaultListSelectionModel();

        selectionMode = DISCONTIGUOUS_TREE_SELECTION;

        leadIndex = leadRow = -1;

        uniquePaths = new Hashtable<TreePath, Boolean>();

        lastPaths = new Hashtable<TreePath, Boolean>();

        tempPaths = new TreePath[1];

    }

    /**

     * Sets the RowMapper instance. This instance is used to determine

     * the row for a particular TreePath.

     */

    public void setRowMapper(RowMapper newMapper) {

        rowMapper = newMapper;

        resetRowSelection();

    }

    /**

     * Returns the RowMapper instance that is able to map a TreePath to a

     * row.

     */

    public RowMapper getRowMapper() {

        return rowMapper;

    }

    /**

     * Sets the selection model, which must be one of SINGLE_TREE_SELECTION,

     * CONTIGUOUS_TREE_SELECTION or DISCONTIGUOUS_TREE_SELECTION. If mode

     * is not one of the defined value,

     * <code>DISCONTIGUOUS_TREE_SELECTION</code> is assumed.

     * <p>This may change the selection if the current selection is not valid

     * for the new mode. For example, if three TreePaths are

     * selected when the mode is changed to <code>SINGLE_TREE_SELECTION</code>,

     * only one TreePath will remain selected. It is up to the particular

     * implementation to decide what TreePath remains selected.

     * <p>

     * Setting the mode to something other than the defined types will

     * result in the mode becoming <code>DISCONTIGUOUS_TREE_SELECTION</code>.

     */

    public void setSelectionMode(int mode) {

        int            oldMode = selectionMode;

        selectionMode = mode;

        if(selectionMode != TreeSelectionModel.SINGLE_TREE_SELECTION &&

           selectionMode != TreeSelectionModel.CONTIGUOUS_TREE_SELECTION &&

           selectionMode != TreeSelectionModel.DISCONTIGUOUS_TREE_SELECTION)

            selectionMode = TreeSelectionModel.DISCONTIGUOUS_TREE_SELECTION;

        if(oldMode != selectionMode && changeSupport != null)

            changeSupport.firePropertyChange(SELECTION_MODE_PROPERTY,

                                             Integer.valueOf(oldMode),

                                             Integer.valueOf(selectionMode));

    }

    /**

     * Returns the selection mode, one of <code>SINGLE_TREE_SELECTION</code>,

     * <code>DISCONTIGUOUS_TREE_SELECTION</code> or

     * <code>CONTIGUOUS_TREE_SELECTION</code>.

     */

    public int getSelectionMode() {

        return selectionMode;

    }

    /**

      * Sets the selection to path. If this represents a change, then

      * the TreeSelectionListeners are notified. If <code>path</code> is

      * null, this has the same effect as invoking <code>clearSelection</code>.

      *

      * @param path new path to select

      */

    public void setSelectionPath(TreePath path) {

        if(path == null)

            setSelectionPaths(null);

        else {

            TreePath[]          newPaths = new TreePath[1];

            newPaths[0] = path;

            setSelectionPaths(newPaths);

        }

    }

    /**

     * Sets the selection. Whether the supplied paths are taken as the

     * new selection depends upon the selection mode. If the supplied

     * array is {@code null}, or empty, the selection is cleared. If

     * the selection mode is {@code SINGLE_TREE_SELECTION}, only the

     * first path in {@code pPaths} is used. If the selection

     * mode is {@code CONTIGUOUS_TREE_SELECTION} and the supplied paths

     * are not contiguous, then only the first path in {@code pPaths} is

     * used. If the selection mode is

     * {@code DISCONTIGUOUS_TREE_SELECTION}, then all paths are used.

     * <p>

     * All {@code null} paths in {@code pPaths} are ignored.

     * <p>

     * If this represents a change, all registered {@code

     * TreeSelectionListener}s are notified.

     * <p>

     * The lead path is set to the last unique path.

     * <p>

     * The paths returned from {@code getSelectionPaths} are in the same

     * order as those supplied to this method.

     *

     * @param pPaths the new selection

     */

    public void setSelectionPaths(TreePath[] pPaths) {

        int            newCount, newCounter, oldCount, oldCounter;

        TreePath[]     paths = pPaths;

        if(paths == null)

            newCount = 0;

        else

            newCount = paths.length;

        if(selection == null)

            oldCount = 0;

        else

            oldCount = selection.length;

        if((newCount + oldCount) != 0) {

            if(selectionMode == TreeSelectionModel.SINGLE_TREE_SELECTION) {

                /* If single selection and more than one path, only allow

                   first. */

                if(newCount > 1) {

                    paths = new TreePath[1];

                    paths[0] = pPaths[0];

                    newCount = 1;

                }

            }

            else if(selectionMode ==

                    TreeSelectionModel.CONTIGUOUS_TREE_SELECTION) {

                /* If contiguous selection and paths aren't contiguous,

                   only select the first path item. */

                if(newCount > 0 && !arePathsContiguous(paths)) {

                    paths = new TreePath[1];

                    paths[0] = pPaths[0];

                    newCount = 1;

                }

            }

            TreePath         beginLeadPath = leadPath;

            Vector<PathPlaceHolder> cPaths = new Vector<PathPlaceHolder>(newCount + oldCount);

            List<TreePath> newSelectionAsList =

                    new ArrayList<TreePath>(newCount);

            lastPaths.clear();

            leadPath = null;

            /* Find the paths that are new. */

            for(newCounter = 0; newCounter < newCount; newCounter++) {

                TreePath path = paths[newCounter];

                if (path != null && lastPaths.get(path) == null) {

                    lastPaths.put(path, Boolean.TRUE);

                    if (uniquePaths.get(path) == null) {

                        cPaths.addElement(new PathPlaceHolder(path, true));

                    }

                    leadPath = path;

                    newSelectionAsList.add(path);

                }

            }

            TreePath[] newSelection = newSelectionAsList.toArray(

                    new TreePath[newSelectionAsList.size()]);

            /* Get the paths that were selected but no longer selected. */

            for(oldCounter = 0; oldCounter < oldCount; oldCounter++)

                if(selection[oldCounter] != null &&

                    lastPaths.get(selection[oldCounter]) == null)

                    cPaths.addElement(new PathPlaceHolder

                                      (selection[oldCounter], false));

            selection = newSelection;

            Hashtable<TreePath, Boolean>  tempHT = uniquePaths;

            uniquePaths = lastPaths;

            lastPaths = tempHT;

            lastPaths.clear();

            // No reason to do this now, but will still call it.

            insureUniqueness();

            updateLeadIndex();

            resetRowSelection();

            /* Notify of the change. */

            if(cPaths.size() > 0)

                notifyPathChange(cPaths, beginLeadPath);

        }

    }

    /**

      * Adds path to the current selection. If path is not currently

      * in the selection the TreeSelectionListeners are notified. This has

      * no effect if <code>path</code> is null.

      *

      * @param path the new path to add to the current selection

      */

    public void addSelectionPath(TreePath path) {

        if(path != null) {

            TreePath[]            toAdd = new TreePath[1];

            toAdd[0] = path;

            addSelectionPaths(toAdd);

        }

    }

    /**

      * Adds paths to the current selection. If any of the paths in

      * paths are not currently in the selection the TreeSelectionListeners

      * are notified. This has

      * no effect if <code>paths</code> is null.

      * <p>The lead path is set to the last element in <code>paths</code>.

      * <p>If the selection mode is <code>CONTIGUOUS_TREE_SELECTION</code>,

      * and adding the new paths would make the selection discontiguous.

      * Then two things can result: if the TreePaths in <code>paths</code>

      * are contiguous, then the selection becomes these TreePaths,

      * otherwise the TreePaths aren't contiguous and the selection becomes

      * the first TreePath in <code>paths</code>.

      *

      * @param paths the new path to add to the current selection

      */

    public void addSelectionPaths(TreePath[] paths) {

        int       newPathLength = ((paths == null) ? 0 : paths.length);

        if(newPathLength > 0) {

            if(selectionMode == TreeSelectionModel.SINGLE_TREE_SELECTION) {

                setSelectionPaths(paths);

            }

            else if(selectionMode == TreeSelectionModel.

                    CONTIGUOUS_TREE_SELECTION && !canPathsBeAdded(paths)) {

                if(arePathsContiguous(paths)) {

                    setSelectionPaths(paths);

                }

                else {

                    TreePath[]          newPaths = new TreePath[1];

                    newPaths[0] = paths[0];

                    setSelectionPaths(newPaths);

                }

            }

            else {

                int               counter, validCount;

                int               oldCount;

                TreePath          beginLeadPath = leadPath;

                Vector<PathPlaceHolder>  cPaths = null;

                if(selection == null)

                    oldCount = 0;

                else

                    oldCount = selection.length;

                /* Determine the paths that aren't currently in the

                   selection. */

                lastPaths.clear();

                for(counter = 0, validCount = 0; counter < newPathLength;

                    counter++) {

                    if(paths[counter] != null) {

                        if (uniquePaths.get(paths[counter]) == null) {

                            validCount++;

                            if(cPaths == null)

                                cPaths = new Vector<PathPlaceHolder>();

                            cPaths.addElement(new PathPlaceHolder

                                              (paths[counter], true));

                            uniquePaths.put(paths[counter], Boolean.TRUE);

                            lastPaths.put(paths[counter], Boolean.TRUE);

                        }

                        leadPath = paths[counter];

                    }

                }

                if(leadPath == null) {

                    leadPath = beginLeadPath;

                }

                if(validCount > 0) {

                    TreePath         newSelection[] = new TreePath[oldCount +

                                                                  validCount];

                    /* And build the new selection. */

                    if(oldCount > 0)

                        System.arraycopy(selection, 0, newSelection, 0,

                                         oldCount);

                    if(validCount != paths.length) {

                        /* Some of the paths in paths are already in

                           the selection. */

                        Enumeration<TreePath> newPaths = lastPaths.keys();

                        counter = oldCount;

                        while (newPaths.hasMoreElements()) {

                            newSelection[counter++] = newPaths.nextElement();

                        }

                    }

                    else {

                        System.arraycopy(paths, 0, newSelection, oldCount,

                                         validCount);

                    }

                    selection = newSelection;

                    insureUniqueness();

                    updateLeadIndex();

                    resetRowSelection();

                    notifyPathChange(cPaths, beginLeadPath);

                }

                else

                    leadPath = beginLeadPath;

                lastPaths.clear();

            }

        }

    }

    /**

      * Removes path from the selection. If path is in the selection

      * The TreeSelectionListeners are notified. This has no effect if

      * <code>path</code> is null.

      *

      * @param path the path to remove from the selection

      */

    public void removeSelectionPath(TreePath path) {

        if(path != null) {

            TreePath[]             rPath = new TreePath[1];

            rPath[0] = path;

            removeSelectionPaths(rPath);

        }

    }

    /**

      * Removes paths from the selection.  If any of the paths in paths

      * are in the selection the TreeSelectionListeners are notified.

      * This has no effect if <code>paths</code> is null.

      *

      * @param paths the paths to remove from the selection

      */

    public void removeSelectionPaths(TreePath[] paths) {

        if (paths != null && selection != null && paths.length > 0) {

            if(!canPathsBeRemoved(paths)) {

                /* Could probably do something more interesting here! */

                clearSelection();

            }

            else {

                Vector<PathPlaceHolder> pathsToRemove = null;

                /* Find the paths that can be removed. */

                for (int removeCounter = paths.length - 1; removeCounter >= 0;

                     removeCounter--) {

                    if(paths[removeCounter] != null) {

                        if (uniquePaths.get(paths[removeCounter]) != null) {

                            if(pathsToRemove == null)

                                pathsToRemove = new Vector<PathPlaceHolder>(paths.length);

                            uniquePaths.remove(paths[removeCounter]);

                            pathsToRemove.addElement(new PathPlaceHolder

                                         (paths[removeCounter], false));

                        }

                    }

                }

                if(pathsToRemove != null) {

                    int         removeCount = pathsToRemove.size();

                    TreePath    beginLeadPath = leadPath;

                    if(removeCount == selection.length) {

                        selection = null;

                    }

                    else {

                        Enumeration<TreePath> pEnum = uniquePaths.keys();

                        int                  validCount = 0;

                        selection = new TreePath[selection.length -

                                                removeCount];

                        while (pEnum.hasMoreElements()) {

                            selection[validCount++] = pEnum.nextElement();

                        }

                    }

                    if (leadPath != null &&

                        uniquePaths.get(leadPath) == null) {

                        if (selection != null) {

                            leadPath = selection[selection.length - 1];

                        }

                        else {

                            leadPath = null;

                        }

                    }

                    else if (selection != null) {

                        leadPath = selection[selection.length - 1];

                    }

                    else {

                        leadPath = null;

                    }

                    updateLeadIndex();

                    resetRowSelection();

                    notifyPathChange(pathsToRemove, beginLeadPath);

                }

            }

        }

    }

    /**

      * Returns the first path in the selection. This is useful if there

      * if only one item currently selected.

      */

    public TreePath getSelectionPath() {

        if (selection != null && selection.length > 0) {

            return selection[0];

        }

        return null;

    }

    /**

      * Returns the selection.

      *

      * @return the selection

      */

    public TreePath[] getSelectionPaths() {

        if(selection != null) {

            int                 pathSize = selection.length;