test.js

'use strict'

const t = require('tape')
const cluster = require('./')
const approxEqual = require('almost-equal')

t('quad: offsets case', t => {
  let points = [.15,.8, .2,.15, .6,.6, .6,.45, .8,.1, .9,.6, .91,.61]
  let index = cluster(points, {bounds: [0,0,1,1]})

  t.deepEqual(index.slice(), [0, 1,3,2, 4,5, 6])

  t.end()
})

t('quad: output container', t => {
  let points = [.15,.8, .2,.15, .6,.6, .6,.45, .8,.1, .9,.6, .91,.61]
  let arr = []
  let index = cluster(points, {bounds: [0,0,1,1], output: arr})

  t.deepEqual(arr.slice(), [0, 1,3,2, 4,5, 6])
  t.equal(index, arr)

  t.end()
})


t('quad: max depth', t => {
  let points = []

  for (let i = 0; i < 1e4; i++) {
    points.push(0, 0)
  }

  let index = cluster(points)

  t.end()
})

t('quad: lod method', t => {
  let points = [0,0, 1,1, 2,2, 3,3, 4,4, 5,5, 6,6, 7,7]

  let index = cluster(points)

  t.deepEqual(index.range({lod: true, d: 1e-10}), [[0,1], [1,3], [3,6], [6,8]])
  t.deepEqual(index.range({lod: true, level: 400}), [[0,1], [1,3], [3,6], [6,8]])
  t.deepEqual(index.range({lod: true}), [[0,1], [1,3], [3,6], [6,8]])
  t.deepEqual(index.range([1,6], {lod: true}), [[0,1], [1,2], [3,4], [6,7]])

  t.end()
})

t('quad: selection', t => {
  let points = [0,0, 1,1, 2,2, 3,3, 4,4, 5,5, 6,6, 7,7]

  let index = cluster(points)

  t.deepEqual(index.range(), [0, 1, 2, 3, 4, 5, 6, 7])
  t.deepEqual(index.range(1,1,6,6), [1, 2, 3, 4, 5, 6])
  t.deepEqual(index.range(2,1,5,6), [2, 3, 4, 5])
  t.deepEqual(index.range(1,2,6,5), [2, 3, 4, 5])
  t.deepEqual(index.range(1,3,5,6), [3, 4, 5])

  t.deepEqual(index.range(5,6,1,3), [3, 4, 5])

  t.end()
})

t.skip('quad: snap-points-2d cases', t => {
  function verifySnap(srcPoints) {
    let numPoints = srcPoints.length>>>1

    let {levels, ids, weights, points, bounds} = cluster(srcPoints)
    let npoints = points

    let sx = bounds[0]
    let sy = bounds[1]
    let sw = bounds[2] - bounds[0]
    let sh = bounds[3] - bounds[1]

    for(let i=0; i < numPoints; ++i) {
      let id = ids[i]
      t.ok(approxEqual(sx + sw*npoints[2*i],   srcPoints[2*id], approxEqual.FLT_EPSILON),
        'id perm ok: ' + id + ' ' +  srcPoints[2*id] + ' = ' + (sx + sw*npoints[2*i]))
      t.ok(approxEqual(sy + sh*npoints[2*i+1], srcPoints[2*id+1], approxEqual.FLT_EPSILON), 'id perm ok: ' + id + ' ' +  srcPoints[2*id+1] + ' = ' + (sy + sh*npoints[2*i+1]))
    }

    t.equals(levels[levels.length-1].offset, 0, 'last item')
    t.equals(levels[0].offset+levels[0].count, numPoints, 'first item')

    for(let i=0; i < levels.length; ++i) {
      let s = levels[i]
      let r = s.pixelSize
      let offs  = s.offset
      let count = s.count

      if(i > 0) {
        t.equals(offs+count, levels[i-1].offset, 'offset for ' + i)
        t.ok(r < levels[i-1].pixelSize, 'test scales ok')
      }
    k_loop:
      for(let k=offs-1; k >= 0; --k) {
        let ax = npoints[2*k]
        let ay = npoints[2*k+1]

        let mind = Infinity

        for(let j=offs; j < offs+count; ++j) {
          let x = npoints[2*j]
          let y = npoints[2*j+1]

          mind = Math.min(mind, Math.max(Math.abs(ax-x), Math.abs(ay-y)))
        }

        t.ok(mind <= 2.0 * r, k + ':' + ax + ',' + ay + ' is not covered - closest pt = ' + mind)
      }
    }
  }

  verifySnap([
     1, 1,
     2, 2,
     3, 3,
     4, 4,
     5, 5
  ])

  verifySnap([
    0,0,
    0,0,
    0,0,
    0,0
  ])

  verifySnap([
    1, 2,
    2, 5,
    3, 6,
    4, -1
  ])

  let pts = new Array(100)
  for(let i=0; i < 100; ++i) {
    pts[i] = Math.random()
  }
  verifySnap(pts)

  t.end()
})

t.skip('quad: linear case', t => {
  let {levels, points, ids, weights} = cluster([1,1,2,2,3,3,4,4,5,5])

  t.deepEqual(ids, [2, 4, 1, 3, 0])
  t.deepEqual(points, [ 0.5, 0.5, 1, 1, 0.25, 0.25, 0.75, 0.75, 0, 0 ])
  t.deepEqual(weights, [1, 1, 2, 2, 5])
  t.deepEqual(levels, [
    { count: 1, offset: 4, pixelSize: 2 },
    { count: 2, offset: 2, pixelSize: 1 },
    { count: 2, offset: 0, pixelSize: 0.5 }
  ])

  t.end()
})

t.skip('quad: no arguments', t => {
  let levels = cluster([0,0, 1,1, 2,2])

  t.end()
})

t.skip('quad: larger bounds', t => {
  let pos = [0,0, 1,1, 2,2, 3,3, 4,4]

  let {levels} = cluster(pos.slice(), { bounds: [0,0,4,4] })
  t.deepEqual(levels, [
      {pixelSize: 2, offset: 4, count: 1},
      {pixelSize: 1, offset: 2, count: 2},
      {pixelSize: 0.5, offset: 0, count: 2}
  ])

  let index = cluster(pos.slice(), { bounds: [0,0,40,40] })
  levels = index.levels

  t.deepEqual(levels, [
    {pixelSize: 20, offset: 4, count: 1},
    {pixelSize: 10, offset: 3, count: 1},
    {pixelSize: 5, offset: 2, count: 1},
    {pixelSize: 2.5, offset: 1, count: 1},
    {pixelSize: 1.25, offset: 0, count: 1}
  ])

  t.end()
})

t.skip('quad: group id', t => {
  // TODO
  t.end()
})

t.skip('kd: creates an index', t => {
  var points = [
  54,1, 97,21, 65,35, 33,54, 95,39, 54,3, 53,54, 84,72, 33,34, 43,15, 52,83, 81,23, 1,61, 38,74,
  11,91, 24,56, 90,31, 25,57, 46,61, 29,69, 49,60, 4,98, 71,15, 60,25, 38,84, 52,38, 94,51, 13,25,
  77,73, 88,87, 6,27, 58,22, 53,28, 27,91, 96,98, 93,14, 22,93, 45,94, 18,28, 35,15, 19,81, 20,81,
      67,53, 43,3, 47,66, 48,34, 46,12, 32,38, 43,12, 39,94, 88,62, 66,14, 84,30, 72,81, 41,92, 26,4,
      6,76, 47,21, 57,70, 71,82, 50,68, 96,18, 40,31, 78,53, 71,90, 32,14, 55,6, 32,88, 62,32, 21,67,
      73,81, 44,64, 29,50, 70,5, 6,22, 68,3, 11,23, 20,42, 21,73, 63,86, 9,40, 99,2, 99,76, 56,77,
      83,6, 21,72, 78,30, 75,53, 41,11, 95,20, 30,38, 96,82, 65,48, 33,18, 87,28, 10,10, 40,34,
      10,20, 47,29, 46,78];

  var ids = [
      97,74,95,30,77,38,76,27,80,55,72,90,88,48,43,46,65,39,62,93,9,96,47,8,3,12,15,14,21,41,36,40,69,56,85,78,17,71,44,
      19,18,13,99,24,67,33,37,49,54,57,98,45,23,31,66,68,0,32,5,51,75,73,84,35,81,22,61,89,1,11,86,52,94,16,2,6,25,92,
      42,20,60,58,83,79,64,10,59,53,26,87,4,63,50,7,28,82,70,29,34,91];

  var coords = [
      10,20,6,22,10,10,6,27,20,42,18,28,11,23,13,25,9,40,26,4,29,50,30,38,41,11,43,12,43,3,46,12,32,14,35,15,40,31,33,18,
      43,15,40,34,32,38,33,34,33,54,1,61,24,56,11,91,4,98,20,81,22,93,19,81,21,67,6,76,21,72,21,73,25,57,44,64,47,66,29,
      69,46,61,38,74,46,78,38,84,32,88,27,91,45,94,39,94,41,92,47,21,47,29,48,34,60,25,58,22,55,6,62,32,54,1,53,28,54,3,
      66,14,68,3,70,5,83,6,93,14,99,2,71,15,96,18,95,20,97,21,81,23,78,30,84,30,87,28,90,31,65,35,53,54,52,38,65,48,67,
      53,49,60,50,68,57,70,56,77,63,86,71,90,52,83,71,82,72,81,94,51,75,53,95,39,78,53,88,62,84,72,77,73,99,76,73,81,88,
      87,96,98,96,82];
  var index = cluster(points, { nodeSize:10, type: 'kd', sort: false });

  t.same(index.ids, ids, 'ids are kd-sorted');
  // t.same(index.points, points, 'coords are kd-sorted');

  t.end();
})

t.skip('kd: range search', t => {
  var pts = points

  var index = cluster(pts, {nodeSize:10, type: 'kd'});

  var result = index.range(20, 30, 50, 70);

  t.same(result, [60,20,45,3,17,71,44,19,18,15,69,90,62,96,47,8,77,72], 'returns ids');

  for (var i = 0; i < result.length; i++) {
      var p = pts[result[i]];
      if (p[0] < 20 || p[0] > 50 || p[1] < 30 || p[1] > 70)
          t.fail('result point in range');
  }
  t.pass('result points in range');

  for (i = 0; i < ids.length; i++) {
      p = pts[ids[i]];
      if (result.indexOf(ids[i]) < 0 && p[0] >= 20 && p[0] <= 50 && p[1] >= 30 && p[1] <= 70)
          t.fail('outside point not in range');
  }
  t.pass('outside points not in range');

  t.end();
})

t.skip('kd: radius search', t => {
  var pts = points

  var index = cluster(pts, {nodeSize:10, type: 'kd'});

  var qp = [50, 50];
  var r = 20;
  var r2 = 20 * 20;

  var result = index.within(qp[0], qp[1], r);

  t.same(result, [60,6,25,92,42,20,45,3,71,44,18,96], 'returns ids');

  for (var i = 0; i < result.length; i++) {
      var p = pts[result[i]];
      if (sqDist(p, qp) > r2) t.fail('result point in range');
  }
  t.pass('result points in range');

  for (i = 0; i < ids.length; i++) {
      p = pts[ids[i]];
      if (result.indexOf(ids[i]) < 0 && sqDist(p, qp) <= r2)
          t.fail('outside point not in range');
  }
  t.pass('outside points not in range');

  t.end();
})

t('performance', t => {
	let N = 1e6
	let points = new Float64Array(N)
  let ids = new Uint32Array(N)

	for (let i = 0; i < N; i++) {
		points[i] = Math.random()
    ids[i] = i
	}

  console.time(1)
  cluster(points, {sort: false})
  console.timeEnd(1)

	t.end()
})