Skip to content

Instantly share code, notes, and snippets.

@flopezluis

flopezluis/ordered_hm.js

Created June 3, 2011 07:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save flopezluis/1006007 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save flopezluis/1006007 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. flopezluis revised this gist Jun 3, 2011. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion ordered_hm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -23,7 +23,6 @@
    * Insert the new key using the sort method.
    */
    function insert(key) {
    sort = sort || default_sort;
    var len = order_keys.length;
    if (len == 0) {
    order_keys.push(key);
  2. flopezluis revised this gist Jun 3, 2011. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion ordered_hm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -71,11 +71,12 @@

    /*
    * Executes a specified function on each ordered element of the array;
    * Stop if the callback returns false
    */
    function foreach(callback) {
    var len = order_keys.length;
    for (var i = 0; i < len; i++) {
    callback(order_keys[i], data[order_keys[i]]);
    if (callback(order_keys[i], data[order_keys[i]]) === false) break;
    }
    }

  3. flopezluis revised this gist Jun 3, 2011. 1 changed file with 27 additions and 42 deletions.
    69 changes: 27 additions & 42 deletions ordered_hm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,13 +1,15 @@
    /*
    * Simple hash map using javascript objects and an ordered array.
    * Repeated elements are allowed
    * Repeated elements are not allowed.
    *
    * @param sort_method By default is ASC order, but you can specified whatever you want.
    *
    * The public methods are:
    * -set
    * -get
    * -del
    * -foreach
    * next step: Try to improve the insert method
    */
    var HashMap = function (sort_method){
    var data = {};
    @@ -28,7 +30,9 @@
    } else {
    for (i = 0; i < len; i++) {
    if (sort(key, order_keys[i])) {
    order_keys.splice(i,0, key);
    if (order_keys[i-1] != key) { /* the element is not repeated */
    order_keys.splice(i,0, key);
    }
    break;
    }
    }
    @@ -37,7 +41,25 @@
    }
    }
    }


    function binarySearch(a, value, low, high) {
    if (high < low)
    return -1 // not found
    mid = parseInt(low + (high - low) / 2)
    if (a[mid] > value)
    return binarySearch(a, value, low, mid-1)
    else if (a[mid] < value)
    return binarySearch(a, value, mid+1, high)
    else
    return mid // found
    }

    function del(key) {
    delete data[key];
    var index = binarySearch(order_keys, key, 0, order_keys.length);
    if (index > -1) order_keys.splice(index,1);
    }

    function set(key, value) {
    data[key] = value;
    insert(key);
    @@ -56,43 +78,6 @@
    callback(order_keys[i], data[order_keys[i]]);
    }
    }


    return {set:set, get:get, foreach:foreach};

    return {set:set, get:get, foreach:foreach, del:del};
    }

    console.log("ASC");
    var hash_number = new HashMap();
    hash_number.set(1, "uno");
    hash_number.set(7, "dos");
    hash_number.set(2, "tres");
    hash_number.set(4, "cuatro");
    hash_number.foreach(function(key, value) {
    console.log(key + " --> " + value);
    });

    console.log("DESC");
    var hash_number_desc = new HashMap(function(a,b) {
    return a > b;
    });
    hash_number_desc.set(1, "uno");
    hash_number_desc.set(7, "dos");
    hash_number_desc.set(2, "tres");
    hash_number_desc.set(4, "cuatro");
    hash_number_desc.set(2, "tres");
    hash_number_desc.foreach(function(key, value) {
    console.log(key + " --> " + value);
    });




    console.log("String ASC");
    var hash_string = new HashMap();
    hash_string.set("b", "2");
    hash_string.set("a", "1");
    hash_string.set("d", "4");
    hash_string.set("c", "3");
    hash_string.foreach(function(key, value) {
    console.log(key + " --> " + value);
    });
  4. flopezluis revised this gist Jun 3, 2011. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion ordered_hm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    /*
    * Simple hash map using javascript objects and an ordered array.
    * Repeat elements are allowed.
    * Repeated elements are allowed
    *
    * @param sort_method By default is ASC order, but you can specified whatever you want.
    *
  5. flopezluis created this gist Jun 3, 2011.
    98 changes: 98 additions & 0 deletions ordered_hm.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,98 @@
    /*
    * Simple hash map using javascript objects and an ordered array.
    * Repeat elements are allowed.
    *
    * @param sort_method By default is ASC order, but you can specified whatever you want.
    *
    * The public methods are:
    * -set
    * -get
    * -foreach
    */
    var HashMap = function (sort_method){
    var data = {};
    var order_keys = [];
    var default_sort = function(a,b) {
    return a < b;
    };
    var sort = sort_method || default_sort;

    /*
    * Insert the new key using the sort method.
    */
    function insert(key) {
    sort = sort || default_sort;
    var len = order_keys.length;
    if (len == 0) {
    order_keys.push(key);
    } else {
    for (i = 0; i < len; i++) {
    if (sort(key, order_keys[i])) {
    order_keys.splice(i,0, key);
    break;
    }
    }
    if ( i== len) {
    order_keys.splice(i,0, key);
    }
    }
    }

    function set(key, value) {
    data[key] = value;
    insert(key);
    }

    function get(key) {
    return data[key];
    }

    /*
    * Executes a specified function on each ordered element of the array;
    */
    function foreach(callback) {
    var len = order_keys.length;
    for (var i = 0; i < len; i++) {
    callback(order_keys[i], data[order_keys[i]]);
    }
    }


    return {set:set, get:get, foreach:foreach};
    }

    console.log("ASC");
    var hash_number = new HashMap();
    hash_number.set(1, "uno");
    hash_number.set(7, "dos");
    hash_number.set(2, "tres");
    hash_number.set(4, "cuatro");
    hash_number.foreach(function(key, value) {
    console.log(key + " --> " + value);
    });

    console.log("DESC");
    var hash_number_desc = new HashMap(function(a,b) {
    return a > b;
    });
    hash_number_desc.set(1, "uno");
    hash_number_desc.set(7, "dos");
    hash_number_desc.set(2, "tres");
    hash_number_desc.set(4, "cuatro");
    hash_number_desc.set(2, "tres");
    hash_number_desc.foreach(function(key, value) {
    console.log(key + " --> " + value);
    });




    console.log("String ASC");
    var hash_string = new HashMap();
    hash_string.set("b", "2");
    hash_string.set("a", "1");
    hash_string.set("d", "4");
    hash_string.set("c", "3");
    hash_string.foreach(function(key, value) {
    console.log(key + " --> " + value);
    });