Monatsarchiv für January 2011

 
 

JavaScript HashMap

In Java and C/C++ I use hash maps (hash tables) almost exclusively for creating associative arrays. The first time I stumbled upon this datatype I remember wondering to myself about why one would ever use something other than a String or Int as a key. I eventually found a few uses for using real Objects as keys in ActionScript where hash maps are called dictionaries (I realize in some languages Strings and Ints are considered Objects). One of the most useful things for the kind of work I do is using a hash map to associate a property or group of properties with an Object, without altering the interface of that Object. I’ll give a few examples. The jQuery data() method is used to associate properties with matched elements. Like this:

// match element with id "test"
var test = $("#test");
test.data("prop", "value");
 
// outputs value
console.log(test.data("prop"));

This is really nice. Some libraries don’t offer this kind of functionality though. So a hash map could come in handy:

 
var propLookup = new HashMap();
var paper = Raphael(0, 0, 400, 400);
 
var circle = paper.circle(100, 100, 10);
circle.attr("fill", "#f00");
 
propLookup(circle, "someProperty");
 
// outputs "someProperty"
console.log(propLookup(circle);

The above example uses the great Raphaeljs library. If there is a method for dealing with dynamic properties in Raphael I haven’t found it. You could of course just add the property “circle.someProp” which will work fine, but could potentially collide with an internal property.

Implementation

I designed a javascript hash map in a bit of a strange way. It works like this:

var hMap = new HashMap();
var a = {};
var b = {};
 
hMap(a, "one");
hMap(b, "two");
hMap(100, "three");
hMap("name", "Zevan");
 
hMap.each(function(key, value){
  console.log(key, value);
});
 
// removes the element with 100 for its key
hMap.delete(100);
 
// gets the number of elements in the hash map
console.log(hMap.size());

This outputs:

Object "one"
Object "two"
100 "three"
name Zevan
3

Basically doing new HashMap() returns a function that takes either 1 or two arguments. If it gets two arguments it populates the map using the first argument as a key and the next argument as a value. If it gets one argument, it assumes you are asking for a key and returns the corresponding value. It has three methods, delete(), size() and each() which are all pretty self explanatory. Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function HashMap() {
  var obj = [];
  function find(key){
    var i = obj.length;
    while (i--) {
      var curr = obj[i];
      if (curr[0] === key) {
        return i;
      }
    }
    return null;
  }
  var d = function dictionary(key, value) {
    var index = find(key);
    if (value) {
      if (index != null){
        obj.splice(index, 1);
      }
      obj.push([key, value]);
 
    } else {
      if (index != null){
        return obj[index][1];
      }
    }
  }
  d.size = function(){
    return obj.length;
  }
  d.delete = function(key) {
    obj.splice(find(key), 1);
  }
  d.each = function(func){
    for (var i = 0; i<obj.length; i++){
      var item = obj[i]
      func(item[0], item[1]); 
    }
  }
  return d;
}

This could probably be optimized a bit, but I wanted to leave it readable.

Just as a side note, here is the kind of thing I found myself doing in ActionScirpt from time to time:

1
2
3
4
5
6
7
8
var s:Sprite = new Sprite();
// dictionary is like a HashMap in AS
var lookup:Dictionary = new Dictionary();
lookup[s] = someValue;
s.addEventListener(MouseEvent.CLICK, onClick);
function onClick(evt:Event):void{
  trace(lookup[evt.currentTarget]);
}

Sand Dollar in OpenGL/C++

Awhile back I created a small experiment to showcase the speed of BitmapData.copyPixels in flash. Using BitmapData.copyPixels you can draw thousands of things to the screen a time. The original experiment draws 5,000 white rectangles:


Click to see original flash version:

I’ve been trying to think up a nice and simple OpenGL post for this site… porting this Sand Dollar thing from AS3 seemed to be a good idea. The OpenGL version is exactly like the flash one except it is fullscreen, has anti-aliased circles instead of rectangles and draws 15,000 elements instead of 5,000. You can download the application for your mac below. I actually started off doing OpenGL on the PC, so it would actually be pretty easy for me to make a windows version (especially since I used glut), maybe I’ll add one for download later on…

Download Mac Version of Sand Dollar Application

Here is the source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//
//  main.cpp
//  SandDollar
//
//  Created by Zevan Rosser on 1/22/11.
//
 
#include <iostream>
#include <GLUT/glut.h>
#include <OpenGL/OpenGL.h>
 
#define _USE_MATH_DEFINES
#include <cmath>
 
#define P_WIDTH  100
#define P_HEIGHT  150
#define NUM_POINTS  P_WIDTH * P_HEIGHT
 
// using namespace std; // for debugging with cout
 
typedef struct {
	float r, g, b, a;
} Color; 
 
 
typedef struct {
	float x;
	float y;
} Pnt;
 
int mouseX = 0;
int mouseY = 0;
int width, height;
 
Pnt points[NUM_POINTS];
Pnt easePoints[NUM_POINTS];
Color colors[NUM_POINTS];
 
void setupPoints(){
	int inc = 0;
 
	int hw = width / 2;
	int hh = height / 2;
	const float STEP = 2.399976;
	const float toRads = M_PI / 180.0;
 
	for (float i = 0; i < P_WIDTH; i++){
		for (float j = 0; j < P_HEIGHT; j++){
			float t = j * STEP;
			float r = (i + 5.0) * 4.0;
			float xp = hw + r * cos(t * toRads);
			float yp = hh + r * sin(t * toRads);
			Pnt p = {xp, yp};
			Pnt pe = {xp, yp};
			points[inc] = p;
			easePoints[inc] = pe;
			Color col = {1.0, 1.0, 1.0, 0.1};
 
			colors[inc] = col;
			inc++;
		}
	}
 
	glEnableClientState(GL_VERTEX_ARRAY);
	glEnableClientState(GL_COLOR_ARRAY); 
	glVertexPointer(2, GL_FLOAT, 0, easePoints);
	glColorPointer(4, GL_FLOAT, 0, colors);
}
 
inline float angle(float x0, float y0, float x1, float y1){
	float dx = x0 - x1;
	float dy = y0 - y1;
	return atan2(dy, dx);
}
 
inline float dist(float x0, float y0, float x1, float y1){
	float dx = x0 - x1;
	float dy = y0 - y1;
	return sqrt(dx * dx + dy * dy);
}
 
Pnt repel(float xp, float yp){
	float d = dist(xp, yp, mouseX, mouseY);
	if (d < 400.0){
		float ang = angle(xp, yp, mouseX, mouseY);
		xp = mouseX + 500 * cos(ang);
		yp = mouseY + 500 * sin(ang);
	}
	Pnt pnt = {xp, yp};
	return pnt;
}
 
void init(){
	glPointSize(20.0);
}
 
void render() {
	glClear(GL_COLOR_BUFFER_BIT);
 
	Pnt p;
	for (int i = 0; i<NUM_POINTS; i++){
		p = repel(points[i].x, points[i].y);
		easePoints[i].x += (p.x - easePoints[i].x) * 0.02;
		easePoints[i].y += (p.y - easePoints[i].y) * 0.02;
	}
 
	glDrawArrays(GL_POINTS, 0, NUM_POINTS);
 
	glutSwapBuffers();
}
 
bool firstResize = true;
void resize(int w, int h) {
	width = w;
	height = h;
	if (firstResize){
		setupPoints();
	}
	glViewport(0, 0, w, h);
	glMatrixMode(GL_PROJECTION);  
	glLoadIdentity();            
	glOrtho(0, w, 0, h, -1, 1);   
	glScalef(1, -1, 1);         
	glTranslatef(0, -h, 0);
}
 
void idle() {
	glutPostRedisplay();
}
 
void mouse(int x, int y){
	mouseX = x;
	mouseY = y;
}
 
int main(int argc, char** argv){
 
	glutInit(&argc, argv);
 
	glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE);
 
	glutInitWindowSize(640, 480);
	glutCreateWindow("Sand Dollar");
	glutFullScreen();
 
	glutPassiveMotionFunc(mouse);
	glutDisplayFunc(render);
	glutReshapeFunc(resize);
	glutIdleFunc(idle);
 
	glEnable (GL_BLEND);	
	glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
	glDisable(GL_DEPTH_TEST);
 
	glEnable (GL_POINT_SMOOTH);
	glHint (GL_POINT_SMOOTH_HINT, GL_NICEST);
 
	// VBL synching
	GLint sync = 1;
	CGLSetParameter(CGLGetCurrentContext(), kCGLCPSwapInterval, &sync);
 
	init();
	glutMainLoop();
 
	return EXIT_SUCCESS;
}

There are a few things I want to point out from the above code snippet:

typedef struct{
  float x, y;
} Pnt;
 
// then to make one and set the x and y values:
Pnt p = {100.0, 100.0};

To me this is much cleaner than:

struct Pnt{
  float x, y;
};
 
// kind of annoying
struct Pnt p = {10.0, 10.0};

Another trick is turning on anti-aliasing for points :

glEnable (GL_POINT_SMOOTH);
glHint (GL_POINT_SMOOTH_HINT, GL_NICEST);

This will turn GL_POINTS into circles (at least on the mac). You can then change the size of the circles using glPointSize().

The last thing I want to point out is that I’m using vertex arrays instead of lots of calls to glVertex*(). In OpenGL we might do things like this:

glBegin(GL_LINES);
glVertex2f(10.0, 10.0);
glVertex2f(100.0, 100.0);
glEnd();

… the problem is when you have hundreds or thousands of vertex values, that ends up being lots of function calls to glVertex*(). So we can use vertex arrays:

glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_COLOR_ARRAY); 
glVertexPointer(2, GL_FLOAT, 0, easePoints);
glColorPointer(4, GL_FLOAT, 0, colors);

and then to draw we do:

glDrawArrays(GL_POINTS, 0, NUM_POINTS);

The OpenGL docs for these few functions are actually really easy to understand, so I won’t bother explaining them in detail here… put simply we enable vertex array for vertex values and color values, associate arrays for both and then draw lots of points.

jQuerify & Console (Webkit-Inspector)

About a year ago I switched from using firefox as my main browser to chrome. I of course still test things across the board – I may even do a post about cross browser testing somtime. Anyway, I wanted to showcase a useful chrome plugin that I use a good deal called jQuerify. It just adds jQuery to the current page in chrome. This can come in handy when your taking over someone else’s project, or debugging your own. It’s important to note that the webkit-inspector console allows you to write javascript on the fly, so by adding jQuery to the page we can write jQuery code on the fly in-browser.

Here is a video of me messing around with jQuerify. WARNING: it’s a little strange, I just had a few snippets handy and sort of made things up as I went along. If you’re already familiar with jQuerify you can just skip to somewhere around 3:45…

This is the code snippet I used at the end:

1
2
3
4
5
$("body").css("background-color", "black"); 
$("a").css("color", "white !important"); 
$("#hplogo").attr("src", "http://jzerr.com/zoogle.gif"); 
$("div").css("background-image", 
"url(http://bestanimations.com/military/Explosions/Explode-05-june.gif)");

I also used the Chrome Color Picker plugin which just wraps the jQuery Color Picker plug-in. I actually made some updates to that jQuery plug-in… maybe I’ll post about that soon…


UPDATE

David pointed out in the commends that jQuirify uses jQuery 1.4.2. So I decided to tweak the extension for chrome, here is how to do it:

1) Install jQuirify
1) go to :

/Users/USER NAME/Library/Application Support/Google/
Chrome/Default/Extensions/
gbmifchmngifmadobkcpijhhldeeelkc/1.2.0_0/content.js

3) change line 56 of content.js to : script.src=”http://code.jquery.com/jquery-latest.min.js”;

Now jQuirify will alway use the latest version of jQuery. To make sure that its working you can do this in the console:

$().jquery

At the time of this post you should get back “1.4.4”