inexorabletash · April 16, 2024 20:38
diff --git a/@ Indexed DB - N-Dimensional Select.md b/@ Indexed DB - N-Dimensional Select.md
diff --git a/demo.html b/demo.html
 <!DOCTYPE html>
 <title>Indexed DB: N-Dimensional Select Example</title>
 <script src="select.js"></script>
 <script>
 // Copyright 2019 Google LLC.
 // SPDX-License-Identifier: Apache-2.0
  
 indexedDB.deleteDatabase('example');
 var open = indexedDB.open('example');
 open.onupgradeneeded = function() {
  var db = open.result;
  var store = db.createObjectStore('things', {autoIncrement: true});
  var index = store.createIndex('coords', ['x', 'y', 'z'], {unique: false});
  for (var x = 1; x <= 10; ++x) {
    for (var y = 1; y <= 10; ++y) {
      for (var z = 1; z <= 10; ++z) {
        store.put({name:''+x+','+y+','+z, x:x, y:y, z:z});
      }
    }
  }
 };

 function log(m) {
  document.documentElement
    .appendChild(document.createElement('div'))
    .appendChild(document.createTextNode(m));
 }
 open.onsuccess = function() {
  var db = open.result;
  var tx = db.transaction('things');
  var index = tx.objectStore('things').index('coords');

  select(index, [[4,6], [3,5], [7,10]],
    function(value) {
      log(JSON.stringify(value));
    },
    function() {
      log('done!');
    });
 };
 </script>
diff --git a/select.js b/select.js
 // Copyright 2019 Google LLC.
 // SPDX-License-Identifier: Apache-2.0

 // First, we need to define a "successor" function. This works for numbers and
 // strings, but not other key types - add as necessary.
 function successor(key) {
  switch (typeof key) {
  case 'number':
    if (key === -Infinity) return -Number.MAX_VALUE;
    if (key === Infinity) return new Date(-8640000000000000);
    if (key === 0) return Number.MIN_VALUE;
    var epsilon = Math.abs(key);
    while (key + epsilon / 2 !== key)
      epsilon = epsilon / 2;
    return key + epsilon;
  case 'string':
    return key + '\x00';
  default:
    throw TypeError('Unsupported key type: ' + key);
  }
 }

 // And here's the N-dimensions selection function.
 // * index is the IDBIndex with an array key path of length N
 // * query is [[dim1_min, dim1_max], [dim2_min, dim3_max]]
 // * valueCallback() will be called synchronously with each value
 // * completeCallback() will be called when completed
 function select(index, query, valueCallback, completeCallback) {
  var min = query.map(function(dim) { return dim[0]; });
  var max = query.map(function(dim) { return dim[1]; });
  index.openCursor(IDBKeyRange.bound(min, max)).onsuccess = function(e) {
    var cursor = e.target.result;
    if (!cursor) {
      completeCallback();
      return;
    }

    for (var i = 1; i < cursor.key.length; ++i) {
      var key_tail = cursor.key.slice(i);

      var min_tail = min.slice(i);
      if (indexedDB.cmp(key_tail, min_tail) < 0) {
        cursor.continue(cursor.key.slice(0, i).concat(min_tail));
        return;
      }

      var max_tail = max.slice(i);
      if (indexedDB.cmp(key_tail, max_tail) > 0) {
        cursor.continue(cursor.key.slice(0, i)
                        .concat([successor(cursor.key[i])])
                        .concat(min.slice(i + 1)));
        return;
      }
    }
    valueCallback(cursor.value);
    cursor.continue();
  };
 }
	<!DOCTYPE html>
	<title>Indexed DB: N-Dimensional Select Example</title>
	<script src="select.js"></script>
	<script>
	// Copyright 2019 Google LLC.
	// SPDX-License-Identifier: Apache-2.0

	indexedDB.deleteDatabase('example');
	var open = indexedDB.open('example');
	open.onupgradeneeded = function() {
	var db = open.result;
	var store = db.createObjectStore('things', {autoIncrement: true});
	var index = store.createIndex('coords', ['x', 'y', 'z'], {unique: false});
	for (var x = 1; x <= 10; ++x) {
	for (var y = 1; y <= 10; ++y) {
	for (var z = 1; z <= 10; ++z) {
	store.put({name:''+x+','+y+','+z, x:x, y:y, z:z});
	}
	}
	}
	};

	function log(m) {
	document.documentElement
	.appendChild(document.createElement('div'))
	.appendChild(document.createTextNode(m));
	}
	open.onsuccess = function() {
	var db = open.result;
	var tx = db.transaction('things');
	var index = tx.objectStore('things').index('coords');

	select(index, [[4,6], [3,5], [7,10]],
	function(value) {
	log(JSON.stringify(value));
	},
	function() {
	log('done!');
	});
	};
	</script>
	// Copyright 2019 Google LLC.
	// SPDX-License-Identifier: Apache-2.0

	// First, we need to define a "successor" function. This works for numbers and
	// strings, but not other key types - add as necessary.
	function successor(key) {
	switch (typeof key) {
	case 'number':
	if (key === -Infinity) return -Number.MAX_VALUE;
	if (key === Infinity) return new Date(-8640000000000000);
	if (key === 0) return Number.MIN_VALUE;
	var epsilon = Math.abs(key);
	while (key + epsilon / 2 !== key)
	epsilon = epsilon / 2;
	return key + epsilon;
	case 'string':
	return key + '\x00';
	default:
	throw TypeError('Unsupported key type: ' + key);
	}
	}

	// And here's the N-dimensions selection function.
	// * index is the IDBIndex with an array key path of length N
	// * query is [[dim1_min, dim1_max], [dim2_min, dim3_max]]
	// * valueCallback() will be called synchronously with each value
	// * completeCallback() will be called when completed
	function select(index, query, valueCallback, completeCallback) {
	var min = query.map(function(dim) { return dim[0]; });
	var max = query.map(function(dim) { return dim[1]; });
	index.openCursor(IDBKeyRange.bound(min, max)).onsuccess = function(e) {
	var cursor = e.target.result;
	if (!cursor) {
	completeCallback();
	return;
	}

	for (var i = 1; i < cursor.key.length; ++i) {
	var key_tail = cursor.key.slice(i);

	var min_tail = min.slice(i);
	if (indexedDB.cmp(key_tail, min_tail) < 0) {
	cursor.continue(cursor.key.slice(0, i).concat(min_tail));
	return;
	}

	var max_tail = max.slice(i);
	if (indexedDB.cmp(key_tail, max_tail) > 0) {
	cursor.continue(cursor.key.slice(0, i)
	.concat([successor(cursor.key[i])])
	.concat(min.slice(i + 1)));
	return;
	}
	}
	valueCallback(cursor.value);
	cursor.continue();
	};
	}