    package flare.vis.data
    {
        import flare.animate.Transitioner;
        import flare.util.Arrays;
        import flare.util.Filter;
        import flare.util.IEvaluable;
        import flare.util.Property;
        import flare.util.Sort;
        import flare.util.Stats;
        import flare.util.math.DenseMatrix;
        import flare.util.math.IMatrix;
        import flare.vis.events.DataEvent;

        import flash.events.Event;
        import flash.events.EventDispatcher;
        import flash.events.IEventDispatcher;
        import flash.utils.Dictionary;
        import flash.utils.Proxy;
        import flash.utils.flash_proxy;

        [Event("add",    type="flare.vis.events.DataEvent")]
        [Event("remove", type="flare.vis.events.DataEvent")]

        /**
         * Data structure for a collection of <code>DataSprite</code> instances.
         * Items contained in this list can be accessed using array notation
         * (<code>[]</code>), iterated over using the <code>for each</code>
         * construct, or can be processed by passing a visitor function to the
         * <code>visit</code> method.
         *
         * <p>Data lists provide methods for sorting elements both in a one-time
         * and persistent fashion, for setting the properties of contained
         * items in a batch-processing style (see the <code>setProperty</code>
         * and <code>setProperties</code> methods), and for computing and
         * caching summary statistics of data variables (see the
         * <code>stats</code> method.</p>
         *
         * <p>Data lists also support listeners for add and remove events. These
         * events are fired <em>before</em> the add or remove is executed. These
         * data events can be canceled by calling <code>preventDefault()</code>
         * on the <code>DataEvent</code> object, thereby preventing the add or
         * remove from being performed. Using this mechanism, clients can add
         * custom constraints on the contents of a data list by adding new
         * listeners that monitor add and remove events and cancel them when
         * desired.</p>
         */
        public class DataList extends Proxy implements IEventDispatcher
        {
            private var _dispatch:EventDispatcher = new EventDispatcher();

            /** Hashed set of items in the data list. */
            private var _map:Dictionary = new Dictionary();
            /** Array of items in the data set. */
            private var _list:Array = [];
            /** Default property values to be applied to new items. */
            private var _defs:Object = null;
            /** Cache of Stats objects for item properties. */
            private var _stats:Object = {};
            /** The underlying array storing the list. */
            internal function get list():Array { return _list; }

            /** The name of this data list. */
            public function get name():String { return _name; }
            private var _name:String;

            /** Internal count of visitors traversing the current list. */
            private var _visiting:int = 0;
            private var _sort:Sort;

            /** The number of items contained in this list. */
            public function get length():int { return _list.length; }

            /** A standing sort criteria for items in the list. */
            public function get sort():Sort { return _sort; }
            public function set sort(s:*):void {
                _sort = s==null ? s : (s is Sort ? Sort(s) : new Sort(s));
                if (_sort != null) _sort.sort(_list);
            }

            // --------------------------------------------------------------------

            /**
             * Creates a new DataList instance.
             * @param editable indicates if this list should be publicly editable.
             */
            public function DataList(name:String) {
                _name = name;
            }

            // -- Basic Operations: Contains, Add, Remove, Clear ------------------

            /**
             * Indicates if the given object is contained in this list.
             * @param d the object to check for containment
             * @return true if the list contains the object, false otherwise.
             */
            public function contains(d:DataSprite):Boolean
            {
                return (_map[d] != undefined);
            }

            /**
             * Add a DataSprite to the list.
             * @param d the DataSprite to add
             * @return the added DataSprite, or null if the add failed
             */
            public function add(d:DataSprite):DataSprite
            {
                if (!fireEvent(DataEvent.ADD, d))
                    return null;

                _map[d] = _list.length;
                _stats = {};
                if (_sort != null) {
                    var idx:int = Arrays.binarySearch(_list, d, null,
                                                      _sort.comparator);
                    _list.splice(-(idx+1), 0, d);
                } else {
                    _list.push(d);
                }
                return d;
            }

            /**
             * Remove a data sprite from the list.
             * @param ds the DataSprite to remove
             * @return true if the object was found and removed, false otherwise
             */
            public function remove(d:DataSprite):Boolean
            {
                if (_map[d] == undefined) return false;
                if (!fireEvent(DataEvent.REMOVE, d))
                    return false;
                if (_visiting > 0) {
                    // if called from a visitor, use a copy-on-write strategy
                    _list = Arrays.copy(_list);
                    _visiting = 0; // reset the visitor count
                }
                Arrays.remove(_list, d);
                delete _map[d];
                _stats = {};
                return true;
            }

            /**
             * Remove a DataSprite from the list.
             * @param idx the index of the DataSprite to remove
             * @return the removed DataSprite
             */
            public function removeAt(idx:int):DataSprite
            {
                var d:DataSprite = _list[idx];
                if (d == null || !fireEvent(DataEvent.REMOVE, d))
                    return null;

                Arrays.removeAt(_list, idx);
                if (d != null) {
                    delete _map[d];
                    _stats = {};
                }
                return d;
            }

            /**
             * Remove all DataSprites from this list.
             */
            public function clear():Boolean
            {
                if (_list.length == 0) return true;
                if (!fireEvent(DataEvent.REMOVE, _list))
                    return false;
                _map = new Dictionary();
                _list = [];
                _stats = {};
                return true;
            }

            // -- Data Representations --------------------------------------------

            /**
             * Returns an array of data objects for each item in this data list.
             * Data objects are retrieved from the "data" property for each item.
             * @return an array of data objects for items in this data list
             */
            public function toDataArray():Array
            {
                var a:Array = new Array(_list.length);
                for (var i:int=0; i<a.length; ++i) {
                    a[i] = _list[i].data;
                }
                return a;
            }

            /**
             * Creates a new adjacency matrix representing the connections between
             * items in this DataList. This method should only be applied when the
             * items contained in this list are <code>NodeSprite</code> instances.
             * The method takes an optional function to compute edge weights.
             * @param w the edge weight function. This function should take an
             *  <code>EdgeSprite</code> as input and return a <code>Number</code>.
             * @param mat a matrix instance in which to store the adjacency matrix
             *  values. If this value is null, a new <code>DenseMatrix</code> will
             *  be constructed.
             * @return the adjacency matrix
             */
            public function adjacencyMatrix(w:Function=null,
                mat:IMatrix=null):IMatrix
            {
                var N:int = length, k:int = 0;

                // build dictionary of nodes
                var idx:Dictionary = new Dictionary();
                for (k=0; k<N; ++k) {
                    if (!(_list[k] is NodeSprite))
                        throw new Error("Only NodeSprites can be used to " +
                                "create an adjacency matrix.");
                    idx[_list[k]] = k;
                }

                // initialize matrix
                if (mat) {
                    mat.init(N, N)
                } else {
                    mat = new DenseMatrix(N, N);
                }

                // build adjacency matrix
                for each (var n:NodeSprite in _list) {
                    var i:int = idx[n];
                    n.visitEdges(function(e:EdgeSprite):void {
                        if (idx[e.target] == undefined) return;
                        var j:int = idx[e.target];
                        var v:Number = w==null ? 1 : w(e);
                        mat.set(i,j,v); mat.set(j,i,v);
                    }, NodeSprite.OUT_LINKS);
                }
                return mat;
            }

            /**
             * Creates a new distance matrix based on a distance function.
             * @param d the distance function. This should take two
             *  <code>DataSprite</code> instances and return a <code>Number</code>
             * @param mat a matrix instance in which to store the adjacency matrix
             *  values. If this value is null, a new <code>DenseMatrix</code> will
             *  be constructed.
             * @return the distance matrix
             */
            public function distanceMatrix(d:Function, mat:IMatrix=null):IMatrix
            {
                var N:int = length, i:uint, j:uint;

                if (mat) {
                    mat.init(N, N);
                } else {
                    mat = new DenseMatrix(N, N);
                }
                for (i=0; i<N; ++i) {
                    for (j=i+1; j<N; ++j) {
                        var v:Number = d(_list[i], _list[j]);
                        mat.set(i,j,v); mat.set(j,i,v);
                    }
                }
                return mat;
            }

            // -- Sort ------------------------------------------------------------

            /**
             * Sort DataSprites according to their properties. This method performs
             * a one-time sorting. To establish a consistent sort order robust over
             * the addition of new items, use the <code>sort</code> property.
             * @param args the sort arguments.
             *     If a String is provided, the data will be sorted in ascending order
             *   according to the data field named by the string.
             *  If an Array is provided, the data will be sorted according to the
             *   fields in the array. In addition, field names can optionally
             *   be followed by a boolean value. If true, the data is sorted in
             *   ascending order (the default). If false, the data is sorted in
             *   descending order.
             */
            public function sortBy(...args):void
            {
                if (args.length == 0) return;
                if (args[0] is Array) args = args[0];

                var f:Function = Sort.$(args);
                _list.sort(f);
            }

            // -- Visitation ------------------------------------------------------

            /**
             * Iterates over the contents of the list, invoking a visitor function
             * on each element of the list. If the visitor function returns a
             * Boolean true value, the iteration will stop with an early exit.
             * @param visitor the visitor function to be invoked on each item
             * @param filter an optional boolean-valued function indicating which
             *  items should be visited
             * @param reverse optional flag indicating if the list should be
             *  visited in reverse order
             * @return true if the visitation was interrupted with an early exit
             */
            public function visit(visitor:Function, filter:*=n