Move sorting logic from table to list.

chrome/browser/resources/shared/js/cr/ui/array_data_model.js

 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 /**
  * @fileoverview This is a data model representin
  */
 
 cr.define('cr.ui', function() {
   const EventTarget = cr.EventTarget;
   const Event = cr.Event;
 
   /**
-   * A data model that wraps a simple array.
+   * A data model that wraps a simple array and supports sorting by storing
+   * initial indexes of elements for each position in sorted array.
    * @param {!Array} array The underlying array.
    * @constructor
    * @extends {EventTarget}
    */
   function ArrayDataModel(array) {
     this.array_ = array;
+    this.indexes_ = [];
+    for (var i = 0; i < array.length; i++) {
+      this.indexes_.push(i);
+    }
   }
 
   ArrayDataModel.prototype = {
     __proto__: EventTarget.prototype,
 
     /**
      * The length of the data model.
      * @type {number}
      */
     get length() {
       return this.array_.length;
     },
 
     /**
      * Returns the item at the given index.
+     * This implementation returns the item at the given index in the source
+     * array before sort.
+     * @param {number} index The index of the element to get.
+     * @return {*} The element at the given index.
+     */
+    getItemByUnsortedIndex_: function(unsortedIndex) {

[arv (Not doing code reviews), 2011/05/19 16:17:56]

Why is this needed?

[vsevik, 2011/05/19 20:07:02]

Inlined.

+      return this.array_[unsortedIndex];
+    },
+
+    /**
+     * Returns the item at the given index.
+     * This implementation returns the item at the given index in the sorted
+     * array.
      * @param {number} index The index of the element to get.
      * @return {*} The element at the given index.
      */
     item: function(index) {
-      return this.array_[index];
+      if (index >= 0 && index < this.length)
+        return this.getItemByUnsortedIndex_(this.indexes_[index]);
+      return undefined;
     },
 
     /**
+     * Returns compare function set for given field.
+     * @param {string} field The field to get compare function for.
+     * @return {Function(*, *): number} Compare function set for given field.

[arv (Not doing code reviews), 2011/05/19 16:17:56]

{function(*, *) : number}

[vsevik, 2011/05/19 20:07:02]

Done.

+     */
+    compareFunction: function(field) {
+      return this.compareFunctions_[field];
+    },
+
+    /**
+     * Sets compare function for given field.
+     * @param {string} field The field to set compare function.
+     * @param {Function(*, *): number} Compare function to set for given field.
+     */
+    setCompareFunction: function(field, compareFunction) {
+      this.compareFunctions_[field] = compareFunction;
+    },
+
+    /**
+     * Returns current sort status.
+     * @return {!Object} Current sort status.
+     */
+    get sortStatus() {
+      if (this.sortStatus_) {
+        return this.createSortStatus(
+            this.sortStatus_.field, this.sortStatus_.direction);
+      } else {
+        return this.createSortStatus(null, null);
+      }
+    },
+
+
+
+    /**
      * Returns the first matching item.
      * @param {*} item The item to find.
      * @param {number=} opt_fromIndex If provided, then the searching start at
      *     the {@code opt_fromIndex}.
      * @return {number} The index of the first found element or -1 if not found.
      */
     indexOf: function(item, opt_fromIndex) {
       return this.array_.indexOf(item, opt_fromIndex);
     },
 
     /**
      * Returns an array of elements in a selected range.
      * @param {number=} opt_from The starting index of the selected range.
      * @param {number=} opt_to The ending index of selected range.
      * @return {Array} An array of elements in the selected range.
      */
     slice: function(opt_from, opt_to) {
       return this.array_.slice.apply(this.array_, arguments);
     },
 
     /**
      * This removes and adds items to the model.
-     *
      * This dispatches a splice event.
-     *
+     * This implementation runs sort after splice and creates permutation for
+     * the whole change.
      * @param {number} index The index of the item to update.
      * @param {number} deleteCount The number of items to remove.
      * @param {...*} The items to add.
      * @return {!Array} An array with the removed items.
      */
     splice: function(index, deleteCount, var_args) {
+      var addCount = arguments.length - 2;

[arv (Not doing code reviews), 2011/05/19 16:17:56]

Can we skip this work in case there isn't any sorting happening?

[vsevik, 2011/05/19 20:07:02]

As discussed, I've done benchmarking that showed regression. I've made some
changes to ensure only one redraw is done on splice, now it looks like we get
some performance improvement.

+      var newIndexes = [];
+      var deletePermutation = [];
+      var deleted = 0;
+      for (var i = 0; i < this.indexes_.length; i++) {
+        var oldIndex = this.indexes_[i];
+        if (oldIndex < index) {
+          newIndexes.push(oldIndex);
+          deletePermutation.push(i - deleted);
+        } else if (oldIndex >= index + deleteCount) {
+          newIndexes.push(oldIndex - deleteCount + addCount);
+          deletePermutation.push(i - deleted);
+        } else {
+          deletePermutation.push(-1);
+          deleted++;
+        }
+      }
+      for (var i = 0; i < addCount; i++) {
+        newIndexes.push(index + i);
+      }
+      this.indexes_ = newIndexes;
+
       var arr = this.array_;
 
       // TODO(arv): Maybe unify splice and change events?
-      var e = new Event('splice');
-      e.index = index;
-      e.removed = arr.slice(index, index + deleteCount);
-      e.added = Array.prototype.slice.call(arguments, 2);
+      var spliceEvent = new Event('splice');
+      spliceEvent.index = index;
+      spliceEvent.removed = arr.slice(index, index + deleteCount);
+      spliceEvent.added = Array.prototype.slice.call(arguments, 2);
 
       var rv = arr.splice.apply(arr, arguments);
 
-      this.dispatchEvent(e);
+      this.dispatchPermutedEvent_(deletePermutation);
 
+      // if sortStatus.field is null, this restores original order.
+      this.doSort_(this.sortStatus.field, this.sortStatus.direction);
+
+      this.dispatchEvent(spliceEvent);
       return rv;
     },
 
     /**
      * Appends items to the end of the model.
      *
      * This dispatches a splice event.
      *
      * @param {...*} The items to append.
      * @return {number} The new length of the model.
      */
     push: function(var_args) {
       var args = Array.prototype.slice.call(arguments);
       args.unshift(this.length, 0);
       this.splice.apply(this, args);
       return this.length;
     },
 
     /**
      * Use this to update a given item in the array. This does not remove and
      * reinsert a new item.
-     *
      * This dispatches a change event.
-     *
+     * This runs sort after updating.
      * @param {number} index The index of the item to update.
      */
     updateIndex: function(index) {
       if (index < 0 || index >= this.length)
         throw Error('Invalid index, ' + index);
 
       // TODO(arv): Maybe unify splice and change events?
       var e = new Event('change');
       e.index = index;
       this.dispatchEvent(e);
+
+      if (this.sortStatus.field)
+        this.doSort_(this.sortStatus.field, this.sortStatus.direction);
+    },
+
+    /**
+     * Creates sort status with given field and direction.
+     * @param {string} field Sort field.
+     * @param {string} direction Sort direction.
+     * @return {!Object} Created sort status.
+     */
+    createSortStatus: function(field, direction) {
+      return {
+        field: field,
+        direction: direction
+      };
+    },
+
+    /**
+     * Called before a sort happens so that you may fetch additional data
+     * required for the sort.
+     *
+     * @param {string} field Sort field.
+     * @param {function()} callback The function to invoke when preparation
+     *     is complete.
+     */
+    prepareSort: function(field, callback) {
+      callback();
+    },
+
+    /**
+     * Sorts data model according to given field and direction and dispathes
+     * sorted event.
+     * @param {string} field Sort field.
+     * @param {string} direction Sort direction.
+     */
+    sort: function(field, direction) {
+      var self = this;
+
+      this.prepareSort(field, function() {
+        var sortPermutation = self.doSort_(field, direction);
+        self.dispatchSortEvent_();
+      });
+    },
+
+    /**
+     * Sorts data model according to given field and direction.
+     * @param {string} field Sort field.
+     * @param {string} direction Sort direction.
+     */
+    doSort_: function(field, direction) {
+      var compareFunction = this.sortFunction_(field, direction);
+      var positions = [];
+      for (var i = 0; i < this.length; i++) {
+        positions[this.indexes_[i]] = i;
+      }
+      this.indexes_.sort(compareFunction);
+      this.sortStatus_ = this.createSortStatus(field, direction);
+      var sortPermutation = [];
+      for (var i = 0; i < this.length; i++) {
+        sortPermutation[positions[this.indexes_[i]]] = i;
+      }
+      this.dispatchPermutedEvent_(sortPermutation);
+    },
+
+    dispatchSortEvent_: function() {
+      var e = new Event('sorted');
+      this.dispatchEvent(e);
+    },
+
+    dispatchPermutedEvent_: function(permutation) {
+      var e = new Event('permuted');
+      e.permutation = permutation;
+      this.dispatchEvent(e);
+    },
+
+    /**
+     * Creates compare function for the field.
+     * Returns the function set as sortFunction for given field
+     * or default compare function
+     * @param {string} field Sort field.
+     * @param {Function(*, *): number} Compare function.
+     */
+    createCompareFunction_: function(field) {
+      var compareFunction =
+          this.compareFunctions_ ? this.compareFunctions_[field] : null;
+      var defaultValuesCompareFunction = this.defaultValuesCompareFunction;
+      if (compareFunction) {
+        return compareFunction;
+      } else {
+        return function(a, b) {
+          return defaultValuesCompareFunction.call(null, a[field], b[field]);
+        }
+      }
+      return compareFunction;
+    },
+
+    /**
+     * Creates compare function for given field and direction.
+     * @param {string} field Sort field.
+     * @param {string} direction Sort direction.
+     * @param {Function(*, *): number} Compare function.
+     */
+    sortFunction_: function(field, direction) {
+      var compareFunction = null;
+      if (field !== null)
+        compareFunction = this.createCompareFunction_(field);
+      var dirMultiplier = direction == 'desc' ? -1 : 1;
+
+      return function(index1, index2) {
+        var item1 = this.getItemByUnsortedIndex_(index1);
+        var item2 = this.getItemByUnsortedIndex_(index2);
+
+        var compareResult = 0;
+        if (typeof(compareFunction) === 'function')
+          compareResult = compareFunction.call(null, item1, item2);
+        if (compareResult != 0)
+          return dirMultiplier * compareResult;
+        return dirMultiplier * this.defaultValuesCompareFunction(index1,
+                                                                 index2);
+      }.bind(this);
+    },
+
+    /**
+     * Default compare function.
+     */
+    defaultValuesCompareFunction: function(a, b) {
+      // We could insert i18n comparisons here.
+      if (a < b)
+        return -1;
+      if (a > b)
+        return 1;
+      return 0;
     }
   };
 
   return {
     ArrayDataModel: ArrayDataModel
   };
 });