Codexon

Morton codes (or Z-order curves) are a way to hash coordinates in 1 dimension. This is useful for problems such as “which stores are 10 miles away from me?” without searching through all the stores in existence.

Why Not Use A 2d Array?

You might ask, why not just store the information in a 2d array in C or Java? The problem is caching.

      y=0              y=1         y=2            y=3           ....    y=99
[1,2,3,4...99] [1,2,3,4...99] [1,2,3,4...99]  [1,2,3,4...99]    ....

How a 99×99 2d array could be stored in memory.

Lets say you try to find some stuff closest to x=5, y=1. The cpu then loads the nearby arrays y=0, y=1 and y=2 for speedy access, because that is how modern cpus work. The problem is when you search for a “close” coordinate such as x=5 y=20, its too far away from x=5 y=1.

To you , it looks like its only 19 units away, but in the computer its 19 x 99 units away because each y-array between y=1 and y=20 has 99 slots.

Generating Morton Codes

Generating a Morton number is easy. All you do is convert the x and y coordinate numbers into binary. Then “interleave” the bits to get the Morton number. It does not matter which goes first, but you must be consistent.

Example

-0-0-1 : 1 in binary
1-0-1- : 5 in binary
xyxyxy

100011 : 35 Your interleaved Morton number

My interleave function for python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def interleave(x, y):
    result = 0
    position = 0
    bit = 1
 
    while bit <= x or bit <= y:
 
        if bit & x:
            result |= 1 << (2*position+1)
        if bit & y:
            result |= 1 << (2*position)
 
        position += 1
        bit = 1 << position
 
    return result

Using Morton Codes

6 |20  22  28  30  52  54  60
5 |17  19  25  27  49  51  57
4 |16  18  24  26  48  50  56
3 |5   7   13  15  37  39  45
2 |4   6   12  14  36  38  44
1 |1   3   9   11  33  35  41
0 |0   2   8   10  32  34  40
   --------------------------
   0   1   2   3   4   5   6

A table of Morton codes on a 2d graph. The x coordinate is interleaved in front of the Y coordinate.

Now lets say you would like to find all the objects 1 unit away from x=1 y=1. Find the upper bound number by finding the Morton number at x=2 y=2 (12). Then do the same for the lower bound at x=0 y=0 (0). So now you will need to search for any objects from 0 to 12.

This limits the search space. But it is not perfect, so you will have to verify each one manually.

As you can see, the numbers 5, 7, 10, 11 are out of bounds, but are between 0 to 12.

Our 2d Cartesian graph, with the Morton order (Z-curve) in red from lowest to highest. As you can see here, as the Morton number grows, the space covered expands in a zig zag fashion, from the bottom left to right.

You can use Morton codes in higher dimensions as well. For example in 3d, you might interlace coordinates as xyzxyzxyz. Hilbert codes supposedly have better locality, but is harder to compute.

Javascript enjoys its presence on the internet due to its age and wide support.

Here are some snippets that you may find useful.

javascript:document.body.contentEditable='true'; document.designMode='on'; void 0

Paste this over the url of a webpage, and you will be able to edit the text like notepad. The source code will be updated when you save it as a file. Tested in IE7 and Firefox 3.

javascript:document.getElementsByTagName("embed")[0].SetVariable("moviename.somevariablename", 12345)

This snippet will allow you to change the variable inside a flash movie. To find out what the movie or variable names are, you will need the source code, or use a flash decompiler.

Note that if the flash file isn’t in the “embed” tag, then you will need to find the appropriate tag name.

The [0], indicates that it is the first embed tag on the page. If you are trying to locate the 5th embed tag, then you would replace [0] with [4].

Have you ever wanted to rewrite your program while it was running? According to wikipedia, this feature is called live coding.

This is a big deal for applications such as internet servers and the telecom industry. Restarting the program every time you make a change is unnecessary downtime when you would like to have +99.9% uptime.

Some languages were made with this feature in mind, such as Erlang and ColdC. However for Python, it is not as easy.

Most people just look at the reload() function for Python and are satisfied with that. Unfortunately, the deeper you dig into it, the more deficiencies you will see.

Example

You make a module file.

# mod.py
class foo: value=5

In your prompt you type:
>>> import mod
>>> a = mod.foo()
>>> a.value
5

Then you edit the module file again.

# mod.py
class foo: value=1

>>> reload(mod)
<module ‘mod’ from ‘mod.pyc’>
>>> a.value
5

Its still 5! Why is it not 1?

It is because the variable “a” is still linked to the old module. The new module merely replaced the name “mod”. All calls to mod now point to the new code.

But the old code still exists, and will live as long as any variable uses it, such as the object at ‘a’.

>>> b = mod.foo()
>>> b.value
1

The class of b and a are different, even though they come from the same file.
>>> a.__class__ is b.__class__
False

So how do we go about solving this problem without using another language? We have two options.

1. Make a special class that records all it’s instances. Then when you reload, you tell all the instances to change their __bases__ variable to the new version.

2. Copy all the member variables from the new object to the old object. This seems to be the best choice.

Here is a replacement for the reload function. However, note that there is a strange piece of code that looks like the following:

class object(object):pass
__builtin__.object = object

This piece of code replaces the default “object” class in order to bypass an unfixed 6 year old problem in the python interpreter. http://bugs.python.org/issue672115

import sys, types
import __builtin__
 
# override the regular object type
# http://bugs.python.org/issue672115
class object(object):pass
__builtin__.object = object
 
# save the old reload
oldreload = reload
 
# Here is a list of datatypes we want to update.
# We want to update class definitions and functions
types_to_update = (type, types.FunctionType)
 
# the replacement function
def reload(mod):
 
    # record all the variables we want at the lowest level only.
    oldstuff = []
    for key, obj in mod.__dict__.iteritems():
        if type(obj) in types_to_update:
            oldstuff.append( (key,obj) )
 
    # perform the regular reload
    oldreload(mod)
 
    # if the old classes are in the new one, then update them, and copy them over.
    for key, obj in oldstuff:
        if key in mod.__dict__:
            update2(obj, mod.__dict__[key])
            mod.__dict__[key] = obj
 
# the object updating function.
# all of the data from "b" gets ripped and placed into "a"
def update2(a,b):
 
    for varname in dir(a):
        try: delattr(a, varname)
        except: pass
 
    for varname in dir(b):
        newvalue = getattr(b, varname)
        try: setattr(a, varname, newvalue)
        except: pass

Caveats:

1. The entire program should be paused while the update takes place. Bugs could result if part of your program accesses old and new code in one go.

2. Some objects can never be updated in place because their member variables are uncopyable or unchangable. Forunately, regular classes and functions seem to work.

3. Only things defined at the lowest level of the module will be able to be updated reliably. This means you can’t update things defined inside methods and functions.

You can’t update ‘b’ in a module like this. You can only update a.

class a:
    def make(self):
        return class b: pass