Modified HashMap

var HashMap = function HashMap( map ) {
this.data = [];
this.curKey = 0;
this._size = 0;

if (arguments.length == 1) {
// copy map to data
}

this.put = function put( key, value ) {
var rv;
if (typeof key == "object") {
if(!key._HashMap_key){
key._HashMap_key = "_HashMapKey_" + this.curKey++;
}
rv = this.data[key._HashMap_key];
this.data[key._HashMap_key] = value;
} else {
rv = this.data[typeof key + key];
this.data[typeof key + key] = value;
}
this._size = rv ? this._size : this._size + 1;
return rv;
}

this.get = function get( key ) {
if (typeof key == "object") {
return this.data[key._HashMap_key];
}
return this.data[typeof key + key];
}
}

Original HashMap

HashMap = function(){
  this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
  if(typeof key == "object"){
    if(!key.hasOwnProperty._id){
      key.hasOwnProperty = function(key){
        return Object.prototype.hasOwnProperty.call(this, key);
      }
      key.hasOwnProperty._id = this._shared.id++;
    }
    this._dict[key.hasOwnProperty._id] = value;
  }else{
    this._dict[key] = value;
  }
  return this; // for chaining
}
HashMap.prototype.get = function get(key){
  if(typeof key == "object"){
    return this._dict[key.hasOwnProperty._id];
  }
  return this._dict[key];
}

Map Implementation

// linking the key-value-pairs is optional
// if no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
    this.current = undefined;
    this.size = 0;

    if(linkItems === false)
        this.disableLinking();
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;

    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }

    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;
    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
    this.removeAll = Map.illegal;

    return this;
};

// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;

    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];

    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }

    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    while(this.size)
        this.remove(this.key());

    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    return this.current.key;
};

Map.prototype.value = function() {
    return this.current.value;
};

Road to Coding HashMap

For the 0.2 Release for the processing.js project, I decided I should code some more supportive classes to expand the processing.js library. I picked HashMap, because this class is missing and I still remember coding a C++ HashTable for an assignment in my previous course DSA555.

I start by reading the specifications in the processing.js references, the original processing implementation, and the Java API, to get a sense of what HashMap is supposed to do. The general idea of HashMap is very similar to HashTable, but I want to know the exact differences between them. So I did a search on Google and found this website. HashMap is actually just a new version of HashTable that accepts null keys; plus a name change. I guess I can start coding it.

Of course, I will not waste my time to come up with original codes if there's is a HashMap existed in the web. Therefore, I did a search on Google again to search for HashMap implementation on Javascript. I found this, and it's great, because the first thing I see is a Map implementation. That means I can probably take the code and do little work to use it. But it turns out that the Map class is more complicated than I thought, plus where is the missing Hash part?

I continue scrolling down and see HashMap implementation. As soon as I start tracing the codes, I realize there's no Hash anywhere in the code. Isn't it weird? Then one Javascript feature on array reappears to me: I don't even need to set a size for array in Javascript!! That means there's no need to hash the given key and insert into a limited size HashMap!! So why do I even need to write a HashMap for the processing.js library? The built-in Javascript array can do the exact same job already. That means all the above researches is wasted?

I decide that I shall code a HashMap anyways, since it is a class listed under processing.js reference. So I continue to trace the HashMap implementation. I don't really have a full understand on the usage for a few lines of codes. So I guess I can just modify some codes so that I understand the code better and see if it works the same way before I change those lines. Original version vs. Modified version.

It did, so the next will be inserting this chunk of code into processing.js. To do this, I decide to look at ArrayList, which has already been coded by someone else. Amazingly, I see uses of the keyword this, and I got freaked out since Dave have said something about it being different than what Java's keyword this. Then Dave sent me a link to show me how to use the troublesome keyword.

So, I coded this HashMap and pushed into the GitHub repository. I know it is not good codes, but I tried my best. It doesn't have codes to copy from another implementation of Map, either. But with the tests I throw to the code, it does what it is expected. I will refine the code so that it does more HashMap functions.

0.1 Release

For my 0.1 Release for a project on Processing.js, I have coded the following functions for Processing.js:

split(str, delim), trim(str), arrayCopy(arg1, arg2, arg3, arg4, arg5), match(str, regexp), append(array, element), splitToken(str, tokens) and online().

I have tested all of the functions and made sure they work. But there's 1 issue on arrayCopy(): it does shallow copy only. In the original Processing code, it does shallow copy, too. But it seems like deep copy is more useful. This should be addressed on my 0.2 Release.

My 0.2 Release

0.2 released.

In this release, I have implemented the HashMap function.

HashMap function contains the following member functions:

put(key,value)
get(key)
remove(key)
isEmpty()
size()
clear()
containsKey(key)
containsValue(value)

Initial Project Plan for OpenSource Development

The Project

The project I will be working on is Processing.js. It is a Mozilla project in which the main purpose is to allow people to create 2D or 3D graphics on web using embedded JavaScript and Canvas.

Not many graphics designer is fluent in using programming language to create graphics on web. This project will help them easily create the visuals on web with one platform. I don't have much knowledge of JavaScript. I expect to learn a lot more about JavaScript and using it to develop an easy tool for users to use.

Project tracking

I will post my updates of the project through this blog. There will be three major release dates within the coming three months: Week of Oct 19 (0.1 Release), Nov 16 (0.2 Release) and Dec 7 (0.3 Release). I'm also expecting to continue working towards 1.0 Release in the next 4 months.

Plan for 0.1, 0.2, and 0.3 releases

0.1
I will be implementing a few functions: trim(), split(), splitTokens(), append(), arraycopy(), match() and matchAll(). This will get me started with processing.js.

0.2
I will fix the bugs in 0.1 release and implement more functions. Possibly implement the rest of Easy functions listed in task list as well as other medium/difficult functions. I would like to contribute a large portion of codes in this release.

0.3
I will fix the bugs in 0.1 and 0.2 release and will be working on the 3D features listed in task list. This will get me familar with 3D programming on web.

Learning

The main language for this project is JavaScript. But I am unfamiliar with the language. My main research will be coming from the JavaScript API and other JavaScript information page. 3D programming will also be challenging. Although I have studied in Game Programming previously, it was mostly on DirectX. So there will be quite a bit of learning OpenGL in this aspect.

Helps Needed

I am a Windows guy, and very unfamiliar with Linux and Mac OS X. The only experiences with Linux are compiling small C/C++ codes remotely to the Matrix server Seneca provides through telnet and ftp. I would appreciate some help in these areas.
I am a detail oriented type of person. Whenever I am encountered with errors or wrong outputs, I can usually pin-point the causing problem easily. I would love to help others into fixing their problems, as I can learn their codes in return.

Risks

Except for the programming language and compiling platform learning, I also have a tight schedule this semester. I am used to just finish programming codes and submit them. Only when I have spare times, I will do some decorations and comment my codes. But since I'm working with an actual project out there in the web, I need to blog about it to gain exposure in the public. This requires me to actually divide some time to talk about what I have done. Just like writing journals, except that I have never written a journal entry before. This will be challenging, as well as very rewarding. I am very excited about having an experience with the open-source community.