Edit detail for MortonCode revision 1 of 4

changed:
-
References to Morton codes:

- http://www.codexon.com/posts/morton-codes

- http://en.wikipedia.org/wiki/Z-order_%28curve%29

- http://www.cs.umd.edu/~hjs/pubs/bulkload.pdf

\begin{axiom}
-- i'th group of n bits of h
bits(h,n,i) == And(mask n,shift(h,-n*i))

-- mix groups of n bits of h with groups of m bits of k
morton(h,n,k,m) ==
 r:SingleInteger:=0
 if n+m > 0 then
   i:=0
   -- stop before fixnum overflow
   while (i+1)*(n+m) <= 29 repeat
     mix:=Or(shift(bits(h,n,i),m),bits(k,m,i))
     r:=Or(r,shift(mix,i*(n+m)))
     i:=i+1
 r

listHash(l) ==
 r:SingleInteger:=0
 i:=0
 while not empty?(l) repeat
   -- equalize hash weight by number of elements
   r:=morton(r,i,hash first l,1)
   l:=rest l
   i:=i+1
 r
\end{axiom}

\begin{axiom}
[hash i for i in 1..5]
[morton(0,0,hash i,1) for i in 1..5]
listHash([1])
matrix [[listHash([i,j]) for j in 1..5] for i in 1..5]
matrix [[listHash([1,i,j]) for j in 1..5] for i in 1..5]
matrix [[listHash([2,i,j]) for j in 1..5] for i in 1..5]
\end{axiom}

References to Morton codes:

• http://www.codexon.com/posts/morton-codes
• http://en.wikipedia.org/wiki/Z-order_%28curve%29
• http://www.cs.umd.edu/~hjs/pubs/bulkload.pdf

axiom

-- i'th group of n bits of h
bits(h,n,i) == And(mask n,shift(h,-n*i))

Type: Void

axiom

-- mix groups of n bits of h with groups of m bits of k
morton(h,n,k,m) ==
 r:SingleInteger:=0
 if n+m > 0 then
   i:=0
   -- stop before fixnum overflow
   while (i+1)*(n+m) <= 29 repeat
     mix:=Or(shift(bits(h,n,i),m),bits(k,m,i))
     r:=Or(r,shift(mix,i*(n+m)))
     i:=i+1
 r

Type: Void

axiom

listHash(l) ==
 r:SingleInteger:=0
 i:=0
 while not empty?(l) repeat
   -- equalize hash weight by number of elements
   r:=morton(r,i,hash first l,1)
   l:=rest l
   i:=i+1
 r

Type: Void

axiom

[hash i for i in 1..5]

(1)

Type: List(Integer)

axiom

[morton(0,0,hash i,1) for i in 1..5]

axiom

Compiling function bits with type (NonNegativeInteger,
      NonNegativeInteger,NonNegativeInteger) -> SingleInteger

axiom

Compiling function bits with type (Integer,PositiveInteger,
      NonNegativeInteger) -> SingleInteger

axiom

Compiling function morton with type (NonNegativeInteger,
      NonNegativeInteger,Integer,PositiveInteger) -> SingleInteger

(2)

Type: List(SingleInteger)

axiom

listHash([1])

axiom

Compiling function bits with type (SingleInteger,NonNegativeInteger,
      NonNegativeInteger) -> SingleInteger

axiom

Compiling function morton with type (SingleInteger,
      NonNegativeInteger,Integer,PositiveInteger) -> SingleInteger

axiom

Compiling function listHash with type List(PositiveInteger) -> 
      SingleInteger

(3)

Type: SingleInteger

axiom

matrix [[listHash([i,j]) for j in 1..5] for i in 1..5]

(4)

Type: Matrix(SingleInteger)

axiom

matrix [[listHash([1,i,j]) for j in 1..5] for i in 1..5]

(5)

Type: Matrix(SingleInteger)

axiom

matrix [[listHash([2,i,j]) for j in 1..5] for i in 1..5]

(6)

Type: Matrix(SingleInteger)