Skip to content

Instantly share code, notes, and snippets.

@Mithrandir0x
Last active October 10, 2015 11:27
Show Gist options
  • Save Mithrandir0x/3683228 to your computer and use it in GitHub Desktop.
Save Mithrandir0x/3683228 to your computer and use it in GitHub Desktop.
Function for traversing a matrix over its diagonals
function diagonalTraverse(m, fn)
{
// This only works for rectangular or square
// form matrices. So no rows of variable sizes!
if ( m && m.length > 0 && m[0].length > 0 )
{
var i = 0, j = 0,
ci = null, cj = null,
M = m[i].length, // # of columns
N = m.length - 1; // # of rows
while ( i < M || j < N )
{
// invariant:
// 0 <= i <= m.size.x
// 0 <= j <= m.size.y - 1
ci = i, cj = j;
while ( ci < M - 1 && cj > 0 )
{
// invariant:
// i <= ci < M - 1
// j >= cj >= 0
fn(m[cj][ci], cj, ci);
ci++;
cj--;
}
fn(m[cj][ci], cj, ci);
if ( j < N )
j++;
else
i++;
}
}
}
def high_triangular_traverse(m, f):
"""fugly but curious that only requires some minor var swaps..."""
i = j = 0
ci = cj = None
M = N = len(m)
N -= 1
while i < M or j < N:
cj = i
ci = j
while ci < (M - 1) and cj > 0:
f(m[cj][ci], cj, ci)
cj += 1
ci -= 1
f(m[cj][ci], cj, ci)
if j < N:
j += 1
else:
i += 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment