Fix bug 553895 - Add a hashed item array for quick indexing of calendar items. r=simon.at.orcl
authorPhilipp Kewisch <mozilla@kewis.ch>
Fri, 30 Apr 2010 14:55:21 +0200
changeset 5561 eaadbd3932e8f94c8a923397f4ac25a65ffa33bb
parent 5560 a1c46c82a4f1274753b148fb4d65e7920956f4d5
child 5562 8313958528c65a23a486311f275dc71b344138fd
push idunknown
push userunknown
push dateunknown
reviewerssimon.at.orcl
bugs553895
Fix bug 553895 - Add a hashed item array for quick indexing of calendar items. r=simon.at.orcl
calendar/base/modules/Makefile.in
calendar/base/modules/calHashedArray.jsm
calendar/test/unit/test_hashedarray.js
--- a/calendar/base/modules/Makefile.in
+++ b/calendar/base/modules/Makefile.in
@@ -42,17 +42,18 @@ srcdir    = @srcdir@
 VPATH     = @srcdir@
 
 include $(DEPTH)/config/autoconf.mk
 
 MODULE = calbase
 
 EXTRA_JS_MODULES = \
     calAlarmUtils.jsm \
-    calUtils.jsm \
+    calAuthUtils.jsm \
+    calHashedArray.jsm \
     calIteratorUtils.jsm \
     calItipUtils.jsm \
     calPrintUtils.jsm \
     calProviderUtils.jsm \
-    calAuthUtils.jsm \
+    calUtils.jsm \
     $(NULL)
 
 include $(topsrcdir)/config/rules.mk
new file mode 100644
--- /dev/null
+++ b/calendar/base/modules/calHashedArray.jsm
@@ -0,0 +1,289 @@
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla Calendar code.
+ *
+ * The Initial Developer of the Original Code is
+ *   Philipp Kewisch <mozilla@kewis.ch>
+ * Portions created by the Initial Developer are Copyright (C) 2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+Components.utils.import("resource://calendar/modules/calUtils.jsm");
+
+EXPORTED_SYMBOLS = ["cal"]; // even though it's defined in calUtils.jsm, import needs this
+
+/**
+ * An unsorted array of hashable items with some extra functions to quickly
+ * retrieve the item by its hash id.
+ *
+ * Performance Considerations:
+ *  - Accessing items is fast
+ *  - Adding items is fast (they are added to the end)
+ *  - Deleting items is O(n)
+ *  - Modifying items is fast.
+ */
+cal.HashedArray = function HashedArray() {
+    this.clear();
+}
+
+cal.HashedArray.prototype = {
+    mArray: null,
+    mHash: null,
+
+    mBatch: 0,
+    mFirstDirty: -1,
+
+    /**
+     * Returns a copy of the internal array. Note this is a shallow copy.
+     */
+    get arrayCopy() {
+        return this.mArray.concat([]);
+    },
+
+    /**
+     * The function to retrieve the hashId given the item. This function can be
+     * overridden by implementations, in case the added items are not instances
+     * of calIItemBase.
+     *
+     * @param item      The item to get the hashId for
+     * @return          The hashId of the item
+     */
+    hashAccessor: function(item) {
+        return item.hashId;
+    },
+
+    /**
+     * Returns the item, given its index in the array
+     *
+     * @param index         The index of the item to retrieve.
+     * @return              The retrieved item.
+     */
+    itemByIndex: function itemByIndex(index) {
+        return this.mArray[index];
+    },
+
+    /**
+     * Returns the item, given its hashId
+     *
+     * @param id            The hashId of the item to retrieve.
+     * @return              The retrieved item.
+     */
+    itemById: function itemById(id) {
+        if (this.mBatch > 0) {
+            throw "Accessing Array by ID not supported in batch mode ";
+        }
+        return (id in this.mHash ? this.mArray[this.mHash[id]] : null);
+    },
+
+    /**
+     * Returns the index of the given item. This function is cheap performance
+     * wise, since it uses the hash
+     *
+     * @param item          The item to search for.
+     * @return              The index of the item.
+     */
+    indexOf: function indexOf(item) {
+        if (this.mBatch > 0) {
+            throw "Accessing Array Indexes not supported in batch mode";
+        }
+        let hashId = this.hashAccessor(item);
+        return (hashId in this.mHash ? this.mHash[hashId] : -1);
+    },
+
+    /**
+     * Remove the item with the given hashId.
+     *
+     * @param id            The id of the item to be removed
+     */
+    removeById: function removeById(id) {
+        if (this.mBatch > 0) {
+            throw "Remvoing by ID in batch mode is not supported"; /* TODO */
+        }
+        let index = this.mHash[id];
+        delete this.mHash[id];
+        this.mArray.splice(index, 1);
+        this.reindex(index);
+    },
+
+    /**
+     * Remove the item at the given index.
+     *
+     * @param index         The index of the item to remove.
+     */
+    removeByIndex: function removeByIndex(index) {
+        delete this.mHash[this.hashAccessor(this.mArray[index])];
+        this.mArray.splice(index, 1);
+        this.reindex(index);
+    },
+
+    /**
+     * Clear the whole array, removing all items. This also resets batch mode.
+     */
+     clear: function clear() {
+        this.mHash = {};
+        this.mArray = [];
+        this.mFirstDirty = -1;
+        this.mBatch = 0;
+     },
+
+    /**
+     * Add the item to the array
+     *
+     * @param item          The item to add.
+     * @return              The index of the added item.
+     */
+    addItem: function addItem(item) {
+        let index = this.mArray.length;
+        this.mArray.push(item);
+        this.reindex(index);
+        return index;
+    },
+
+    /**
+     * Modifies the item in the array. If the item is already in the array, then
+     * it is replaced by the passed item. Otherwise, the item is added to the
+     * array.
+     *
+     * @param item          The item to modify.
+     * @return              The (new) index.
+     */
+    modifyItem: function modifyItem(item) {
+        let hashId = this.hashAccessor(item);
+        if (hashId in this.mHash) {
+            let index = this.mHash[this.hashAccessor(item)];
+            this.mArray[index] = item;
+            return index;
+        } else {
+            return this.addItem(item);
+        }
+    },
+
+    /**
+     * Reindexes the items in the array. This function is mostly used
+     * internally. All parameters are inclusive. The ranges are automatically
+     * swapped if from > to.
+     *
+     * @param from      (optional) The index to start indexing from. If left
+     *                    out, defaults to 0.
+     * @param to        (optional) The index to end indexing on. If left out,
+     *                    defaults to the array length.
+     */
+    reindex: function reindex(from, to) {
+        from = (from === undefined ? 0 : from);
+        to = (to === undefined ? this.mArray.length - 1 : to);
+
+        from = Math.min(this.mArray.length - 1, Math.max(0, from));
+        to = Math.min(this.mArray.length - 1, Math.max(0, to));
+
+        if (from > to) {
+            let tmp = from;
+            from = to;
+            to = tmp;
+        }
+
+        if (this.mBatch > 0) {
+            // No indexing in batch mode, but remember from where to index.
+            this.mFirstDirty = Math.min(Math.max(0, this.mFirstDirty), from);
+            return;
+        }
+
+        for (let idx = from; idx <= to; idx++) {
+            this.mHash[this.hashAccessor(this.mArray[idx])] = idx;
+        }
+    },
+
+    startBatch: function startBatch() {
+        this.mBatch++;
+    },
+
+    endBatch: function endBatch() {
+        this.mBatch = Math.max(0, this.mBatch - 1);
+
+        if (this.mBatch == 0 && this.mFirstDirty > -1) {
+            this.reindex(this.mFirstDirty);
+            this.mFirstDirty = -1;
+        }
+    },
+
+    /**
+     * Iterator to allow iterating the hashed array object.
+     */
+    __iterator__: function iterator(useKeys) {
+        return new Iterator(this.mArray, useKeys);
+    }
+};
+
+/**
+ * Sorted hashed array. The array always stays sorted.
+ *
+ * Performance Considerations:
+ *  - Accessing items is fast
+ *  - Adding and deleting items is O(n)
+ *  - Modifying items is fast.
+ */
+cal.SortedHashedArray = function SortedHashedArray(comparator) {
+    cal.HashedArray.apply(this, arguments);
+    if (!comparator) {
+        throw "Sorted Hashed Array needs a comparator"
+    }
+    this.mCompFunc = comparator;
+}
+
+cal.SortedHashedArray.prototype = {
+    __proto__: cal.HashedArray.prototype,
+
+    mCompFunc: null,
+
+    addItem: function addItem(item) {
+        let newIndex = cal.binaryInsert(this.mArray, item, this.mCompFunc, false);
+        this.reindex(newIndex);
+        return newIndex;
+    },
+
+    modifyItem: function modifyItem(item) {
+        let hashId = this.hashAccessor(item);
+        if (hashId in this.mHash) {
+            let cmp = this.mCompFunc(item, this.mArray[this.mHash[hashId]]);
+            if (cmp == 0) {
+                // The item will be at the same index, we just need to replace it
+                this.mArray[this.mHash[hashId]] = item;
+                return this.mHash[hashId];
+            } else {
+                let oldIndex = this.mHash[hashId];
+
+                let newIndex = cal.binaryInsert(this.mArray, item, this.mCompFunc, false);
+                this.mArray.splice(oldIndex, 1);
+                this.reindex(oldIndex, newIndex);
+                return newIndex;
+            }
+        } else {
+            return this.addItem(item);
+        }
+    }
+};
new file mode 100644
--- /dev/null
+++ b/calendar/test/unit/test_hashedarray.js
@@ -0,0 +1,236 @@
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla Calendar code.
+ *
+ * The Initial Developer of the Original Code is
+ *   Philipp Kewisch <mozilla@kewis.ch>
+ * Portions created by the Initial Developer are Copyright (C) 2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+Components.utils.import("resource://calendar/modules/calHashedArray.jsm");
+
+function run_test() {
+    test_array_base();
+    test_array_sorted();
+    test_hashAccessor();
+}
+
+/**
+ * Helper function to create an item that has a sensible hash id, with the given
+ * title identification.
+ *
+ * @param ident     The title to identify the item.
+ * @return          The created item.
+ */
+function hashedCreateItem(ident) {
+    let item = cal.createEvent();
+    item.calendar = { id : "test" }
+    item.id = cal.getUUID();
+    item.title = ident;
+    return item;
+}
+
+/**
+ * Comparator function to sort the items by their title
+ *
+ * @param a         Object to compare.
+ * @param b         Object to compare with.
+ * @return          0, -1, or 1 (usual comptor meanings)
+ */
+function titleComptor(a, b) {
+    if (a.title > b.title) {
+        return 1;
+    } else if (a.title < b.title) {
+        return -1;
+    } else {
+        return 0;
+    }
+}
+
+/**
+ * Checks if the hashed array accessor functions work for the status of the
+ * items array.
+ *
+ * @param har           The Hashed Array
+ * @param testItems     The array of test items
+ * @param itemAccessor  The accessor func to retrieve the items
+ * @throws Exception    If the arrays are not the same.
+ */
+function checkConsistancy(har, testItems, itemAccessor) {
+    itemAccessor = itemAccessor || function(o) { return o; }
+    for (let idx in testItems) {
+        let ti = itemAccessor(testItems[idx]);
+        do_check_eq(itemAccessor(har.itemByIndex(idx)).title,
+                    ti.title);
+        do_check_eq(itemAccessor(har.itemById(ti.hashId)).title,
+                    ti.title);
+        do_check_eq(har.indexOf(testItems[idx]), idx);
+    }
+}
+
+/**
+ * Useful for debugging, in case this test fails. Dumps the array showing the
+ * title identifications.
+ *
+ * @param ar        The array to dump
+ */
+function dumpArray(ar) {
+    dump("ARR: " + ar.map(function(e) e.title).toSource() + "\n");
+}
+
+/**
+ * Man, this function is really hard to keep general enough, I'm almost tempted
+ * to duplicate the code. It checks if the remove and modify operations work for
+ * the given hashed array.
+ *
+ * @param har               The Hashed Array
+ * @param testItems         The js array with the items
+ * @param postprocessFunc   (optional) The function to call after each
+ *                            operation, but before checking consistancy.
+ * @param itemAccessor      (optional) The function to access the item for an
+ *                            array element.
+ * @param itemCreator       (optional) Function to create a new item for the
+ *                            array.
+ */
+function testRemoveModify(har, testItems, postprocessFunc, itemAccessor, itemCreator) {
+    postprocessFunc = postprocessFunc || function(a, b) { return [a,b]; };
+    itemCreator = itemCreator || function(title) hashedCreateItem(title);
+    itemAccessor = itemAccessor || function(o) { return o; }
+
+    // Now, delete the second item and check again
+    har.removeById(itemAccessor(testItems[1]).hashId);
+    testItems.splice(1, 1);
+    [har, testItems] = postprocessFunc(har, testItems);
+
+    checkConsistancy(har, testItems, itemAccessor);
+
+    // Try the same by index
+    har.removeByIndex(2);
+    testItems.splice(2, 1);
+    [har, testItems] = postprocessFunc(har, testItems);
+    checkConsistancy(har, testItems, itemAccessor);
+
+    // Try modifying an item
+    let newInstance = itemCreator("z-changed");
+    itemAccessor(newInstance).id = itemAccessor(testItems[0]).id;
+    testItems[0] = newInstance;
+    har.modifyItem(newInstance);
+    [har, testItems] = postprocessFunc(har, testItems);
+    checkConsistancy(har, testItems, itemAccessor);
+}
+
+/**
+ * Tests the basic cal.HashedArray
+ */
+function test_array_base() {
+    let har, testItems;
+
+    // Test normal additions
+    har = new cal.HashedArray();
+    testItems = ["a","b","c","d"].map(hashedCreateItem);
+
+    testItems.forEach(har.addItem, har);
+    checkConsistancy(har, testItems);
+    testRemoveModify(har, testItems);
+
+    // Test adding in batch mode
+    har = new cal.HashedArray();
+    testItems = ["e", "f", "g", "h"].map(hashedCreateItem);
+    har.startBatch();
+    testItems.forEach(har.addItem, har);
+    har.endBatch();
+    checkConsistancy(har, testItems);
+    testRemoveModify(har, testItems);
+}
+
+/**
+ * Tests the sorted cal.SortedHashedArray
+ */
+function test_array_sorted() {
+    let har, testItems, testItemsSorted;
+
+    function sortedPostProcess(harParam, tiParam) {
+        tiParam = tiParam.sort(titleComptor);
+        return [harParam, tiParam];
+    }
+
+    // Test normal additions
+    har = new cal.SortedHashedArray(titleComptor);
+    testItems = ["d", "c", "a", "b"].map(hashedCreateItem);
+    testItemsSorted = testItems.sort(titleComptor);
+
+    testItems.forEach(har.addItem, har);
+    checkConsistancy(har, testItemsSorted);
+    testRemoveModify(har, testItemsSorted, sortedPostProcess);
+
+    // Test adding in batch mode
+    har = new cal.SortedHashedArray(titleComptor);
+    testItems = ["e", "f", "g", "h"].map(hashedCreateItem);
+    testItemsSorted = testItems.sort(titleComptor);
+    har.startBatch();
+    testItems.forEach(har.addItem, har);
+    har.endBatch();
+    checkConsistancy(har, testItemsSorted);
+    testRemoveModify(har, testItemsSorted, sortedPostProcess);
+}
+
+/**
+ * Tests cal.SortedHashedArray with a custom hashAccessor.
+ */
+function test_hashAccessor() {
+    let har, testItems, testItemsSorted;
+    let comptor = function(a,b) titleComptor(a.item, b.item);
+
+    har = new cal.SortedHashedArray(comptor);
+    har.hashAccessor = function(obj) {
+        return obj.item.hashId;
+    };
+
+    function itemAccessor(obj) {
+        if (!obj) do_throw("WTF?");
+        return obj.item;
+    }
+
+    function itemCreator(title) {
+        return { item: hashedCreateItem(title) };
+    }
+
+    function sortedPostProcess(harParam, tiParam) {
+        tiParam = tiParam.sort(comptor);
+        return [harParam, tiParam];
+    }
+
+    testItems = ["d", "c", "a", "b"].map(itemCreator);
+
+    testItemsSorted = testItems.sort(comptor);
+    testItems.forEach(har.addItem, har);
+    checkConsistancy(har, testItemsSorted, itemAccessor);
+    testRemoveModify(har, testItemsSorted, sortedPostProcess, itemAccessor, itemCreator);
+}