"use strict";
var __defProp = Object.defineProperty;
var __getOwnPropDesc = Object.getOwnPropertyDescriptor;
var __getOwnPropNames = Object.getOwnPropertyNames;
var __hasOwnProp = Object.prototype.hasOwnProperty;
var __export = (target, all) => {
  for (var name in all)
    __defProp(target, name, { get: all[name], enumerable: true });
};
var __copyProps = (to, from, except, desc) => {
  if (from && typeof from === "object" || typeof from === "function") {
    for (let key of __getOwnPropNames(from))
      if (!__hasOwnProp.call(to, key) && key !== except)
        __defProp(to, key, { get: () => from[key], enumerable: !(desc = __getOwnPropDesc(from, key)) || desc.enumerable });
  }
  return to;
};
var __toCommonJS = (mod) => __copyProps(__defProp({}, "__esModule", { value: true }), mod);

// src/index.ts
var src_exports = {};
__export(src_exports, {
  BPTreeAsync: () => BPTreeAsync,
  BPTreeSync: () => BPTreeSync,
  InMemoryStoreStrategyAsync: () => InMemoryStoreStrategyAsync,
  InMemoryStoreStrategySync: () => InMemoryStoreStrategySync,
  NumericComparator: () => NumericComparator,
  SerializeStrategyAsync: () => SerializeStrategyAsync,
  SerializeStrategySync: () => SerializeStrategySync,
  StringComparator: () => StringComparator,
  ValueComparator: () => ValueComparator
});
module.exports = __toCommonJS(src_exports);

// src/base/ValueComparator.ts
var ValueComparator = class {
  isLower(value, than) {
    return this.asc(value, than) < 0;
  }
  isSame(value, than) {
    return this.asc(value, than) === 0;
  }
  isHigher(value, than) {
    return this.asc(value, than) > 0;
  }
};
var NumericComparator = class extends ValueComparator {
  asc(a, b) {
    return a - b;
  }
  match(value) {
    return value.toString();
  }
};
var StringComparator = class extends ValueComparator {
  asc(a, b) {
    return a.localeCompare(b);
  }
  match(value) {
    return value;
  }
};

// src/utils/InvertedWeakMap.ts
var InvertedWeakMap = class {
  _map;
  _registry;
  constructor() {
    this._map = /* @__PURE__ */ new Map();
    this._registry = new FinalizationRegistry((key) => this._map.delete(key));
  }
  clear() {
    return this._map.clear();
  }
  delete(key) {
    const ref = this._map.get(key);
    if (ref) {
      const raw = ref.deref();
      if (raw !== void 0) {
        this._registry.unregister(raw);
      }
    }
    return this._map.delete(key);
  }
  get(key) {
    return this._map.get(key)?.deref();
  }
  has(key) {
    return this._map.has(key) && this.get(key) !== void 0;
  }
  set(key, value) {
    this._map.set(key, new WeakRef(value));
    this._registry.register(value, key);
    return this;
  }
  get size() {
    return this._map.size;
  }
  keys() {
    return this._map.keys();
  }
};

// src/base/BPTree.ts
var BPTree = class {
  _cachedRegexp;
  strategy;
  comparator;
  nodes;
  order;
  root;
  _strategyDirty;
  _nodeCreateBuffer;
  _nodeUpdateBuffer;
  _nodeDeleteBuffer;
  verifierMap = {
    gt: (nv, v) => this.comparator.isHigher(nv, v),
    gte: (nv, v) => this.comparator.isHigher(nv, v) || this.comparator.isSame(nv, v),
    lt: (nv, v) => this.comparator.isLower(nv, v),
    lte: (nv, v) => this.comparator.isLower(nv, v) || this.comparator.isSame(nv, v),
    equal: (nv, v) => this.comparator.isSame(nv, v),
    notEqual: (nv, v) => this.comparator.isSame(nv, v) === false,
    like: (nv, v) => {
      const nodeValue = this.comparator.match(nv);
      const value = this.comparator.match(v);
      if (!this._cachedRegexp.has(value)) {
        const pattern = value.replace(/%/g, ".*").replace(/_/g, ".");
        const regexp2 = new RegExp(`^${pattern}$`, "i");
        this._cachedRegexp.set(value, regexp2);
      }
      const regexp = this._cachedRegexp.get(value);
      return regexp.test(nodeValue);
    }
  };
  verifierStartNode = {
    gt: (v) => this.insertableNode(v),
    gte: (v) => this.insertableNode(v),
    lt: (v) => this.insertableNode(v),
    lte: (v) => this.insertableNode(v),
    equal: (v) => this.insertableNode(v),
    notEqual: (v) => this.leftestNode(),
    like: (v) => this.leftestNode()
  };
  verifierDirection = {
    gt: 1,
    gte: 1,
    lt: -1,
    lte: -1,
    equal: 1,
    notEqual: 1,
    like: 1
  };
  verifierFullScan = {
    gt: false,
    gte: false,
    lt: false,
    lte: false,
    equal: false,
    notEqual: true,
    like: true
  };
  constructor(strategy, comparator) {
    this._strategyDirty = false;
    this._cachedRegexp = new InvertedWeakMap();
    this._nodeCreateBuffer = /* @__PURE__ */ new Map();
    this._nodeUpdateBuffer = /* @__PURE__ */ new Map();
    this._nodeDeleteBuffer = /* @__PURE__ */ new Map();
    this.nodes = new InvertedWeakMap();
    this.strategy = strategy;
    this.comparator = comparator;
  }
  _insertAtLeaf(node, key, value) {
    if (node.values.length) {
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        if (this.comparator.isSame(value, nValue)) {
          const keys = node.keys[i];
          keys.push(key);
          this.bufferForNodeUpdate(node);
          break;
        } else if (this.comparator.isLower(value, nValue)) {
          node.values.splice(i, 0, value);
          node.keys.splice(i, 0, [key]);
          this.bufferForNodeUpdate(node);
          break;
        } else if (i + 1 === node.values.length) {
          node.values.push(value);
          node.keys.push([key]);
          this.bufferForNodeUpdate(node);
          break;
        }
      }
    } else {
      node.values = [value];
      node.keys = [[key]];
      this.bufferForNodeUpdate(node);
    }
  }
  bufferForNodeCreate(node) {
    this._nodeCreateBuffer.set(node.id, node);
  }
  bufferForNodeUpdate(node) {
    this._nodeUpdateBuffer.set(node.id, node);
  }
  bufferForNodeDelete(node) {
    this._nodeDeleteBuffer.set(node.id, node);
  }
  /**
   * Returns the user-defined data stored in the head of the tree.
   * This value can be set using the `setHeadData` method. If no data has been previously inserted, the default value is returned, and the default value is `{}`.
   * @returns User-defined data stored in the head of the tree.
   */
  getHeadData() {
    return this.strategy.head.data;
  }
};

// src/BPTreeSync.ts
var BPTreeSync = class extends BPTree {
  constructor(strategy, comparator) {
    super(strategy, comparator);
  }
  getPairsRightToLeft(value, startNode, fullScan, comparator) {
    const pairs = [];
    let node = startNode;
    let done = false;
    let found = false;
    while (!done) {
      let i = node.values.length;
      while (i--) {
        const nValue = node.values[i];
        const keys = node.keys[i];
        if (comparator(nValue, value)) {
          found = true;
          let j = keys.length;
          while (j--) {
            pairs.push([keys[j], nValue]);
          }
        } else if (found && !fullScan) {
          done = true;
          break;
        }
      }
      if (!node.prev) {
        done = true;
        break;
      }
      node = this.getNode(node.prev);
    }
    return new Map(pairs.reverse());
  }
  getPairsLeftToRight(value, startNode, fullScan, comparator) {
    const pairs = [];
    let node = startNode;
    let done = false;
    let found = false;
    while (!done) {
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        const keys = node.keys[i];
        if (comparator(nValue, value)) {
          found = true;
          for (let j = 0, len2 = keys.length; j < len2; j++) {
            const key = keys[j];
            pairs.push([key, nValue]);
          }
        } else if (found && !fullScan) {
          done = true;
          break;
        }
      }
      if (!node.next) {
        done = true;
        break;
      }
      node = this.getNode(node.next);
    }
    return new Map(pairs);
  }
  getPairs(value, startNode, fullScan, comparator, direction) {
    switch (direction) {
      case -1:
        return this.getPairsRightToLeft(value, startNode, fullScan, comparator);
      case 1:
        return this.getPairsLeftToRight(value, startNode, fullScan, comparator);
      default:
        throw new Error(`Direction must be -1 or 1. but got a ${direction}`);
    }
  }
  _createNodeId(isLeaf) {
    const id = this.strategy.id(isLeaf);
    if (id === null) {
      throw new Error(`The node's id should never be null.`);
    }
    return id;
  }
  _createNode(isLeaf, keys, values, leaf = false, parent = null, next = null, prev = null) {
    const id = this._createNodeId(isLeaf);
    const node = {
      id,
      keys,
      values,
      leaf,
      parent,
      next,
      prev
    };
    this.nodes.set(id, node);
    return node;
  }
  _deleteEntry(node, key, value) {
    if (!node.leaf) {
      for (let i = 0, len = node.keys.length; i < len; i++) {
        const nKey = node.keys[i];
        if (nKey === key) {
          node.keys.splice(i, 1);
          this.bufferForNodeUpdate(node);
          break;
        }
      }
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        if (this.comparator.isSame(value, nValue)) {
          node.values.splice(i, 1);
          this.bufferForNodeUpdate(node);
          break;
        }
      }
    }
    if (this.root === node && node.keys.length === 1) {
      const keys = node.keys;
      this.bufferForNodeDelete(this.root);
      this.root = this.getNode(keys[0]);
      this.root.parent = null;
      this.strategy.head.root = this.root.id;
      this._strategyDirty = true;
      this.bufferForNodeUpdate(this.root);
      return;
    } else if (this.root === node) {
      return;
    } else if (node.keys.length < Math.ceil(this.order / 2) && !node.leaf || node.values.length < Math.ceil((this.order - 1) / 2) && node.leaf) {
      if (node.parent === null) {
        return;
      }
      let isPredecessor = false;
      let parentNode = this.getNode(node.parent);
      let prevNode = null;
      let nextNode = null;
      let prevValue = null;
      let postValue = null;
      for (let i = 0, len = parentNode.keys.length; i < len; i++) {
        const nKey = parentNode.keys[i];
        if (nKey === node.id) {
          if (i > 0) {
            prevNode = this.getNode(parentNode.keys[i - 1]);
            prevValue = parentNode.values[i - 1];
          }
          if (i < parentNode.keys.length - 1) {
            nextNode = this.getNode(parentNode.keys[i + 1]);
            postValue = parentNode.values[i];
          }
        }
      }
      let pointer;
      let guess;
      if (prevNode === null) {
        pointer = nextNode;
        guess = postValue;
      } else if (nextNode === null) {
        isPredecessor = true;
        pointer = prevNode;
        guess = prevValue;
      } else {
        if (node.values.length + nextNode.values.length < this.order) {
          pointer = nextNode;
          guess = postValue;
        } else {
          isPredecessor = true;
          pointer = prevNode;
          guess = prevValue;
        }
      }
      if (node.values.length + pointer.values.length < this.order) {
        if (!isPredecessor) {
          const pTemp = pointer;
          pointer = node;
          node = pTemp;
        }
        pointer.keys.push(...node.keys);
        if (!node.leaf) {
          pointer.values.push(guess);
        } else {
          pointer.next = node.next;
          pointer.prev = node.id;
          if (pointer.next) {
            const n = this.getNode(node.next);
            n.prev = pointer.id;
            this.bufferForNodeUpdate(n);
          }
          if (pointer.prev) {
            const n = this.getNode(node.id);
            n.next = pointer.id;
            this.bufferForNodeUpdate(n);
          }
          if (isPredecessor) {
            pointer.prev = null;
          }
        }
        pointer.values.push(...node.values);
        if (!pointer.leaf) {
          const keys = pointer.keys;
          for (const key2 of keys) {
            const node2 = this.getNode(key2);
            node2.parent = pointer.id;
            this.bufferForNodeUpdate(node2);
          }
        }
        this._deleteEntry(this.getNode(node.parent), node.id, guess);
        this.bufferForNodeUpdate(pointer);
        this.bufferForNodeDelete(node);
      } else {
        if (isPredecessor) {
          let pointerPm;
          let pointerKm;
          if (!node.leaf) {
            pointerPm = pointer.keys.splice(-1)[0];
            pointerKm = pointer.values.splice(-1)[0];
            node.keys = [pointerPm, ...node.keys];
            node.values = [guess, ...node.values];
            parentNode = this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointerKm;
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          } else {
            pointerPm = pointer.keys.splice(-1)[0];
            pointerKm = pointer.values.splice(-1)[0];
            node.keys = [pointerPm, ...node.keys];
            node.values = [pointerKm, ...node.values];
            parentNode = this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointerKm;
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          }
          this.bufferForNodeUpdate(node);
          this.bufferForNodeUpdate(pointer);
        } else {
          let pointerP0;
          let pointerK0;
          if (!node.leaf) {
            pointerP0 = pointer.keys.splice(0, 1)[0];
            pointerK0 = pointer.values.splice(0, 1)[0];
            node.keys = [...node.keys, pointerP0];
            node.values = [...node.values, guess];
            parentNode = this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointerK0;
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          } else {
            pointerP0 = pointer.keys.splice(0, 1)[0];
            pointerK0 = pointer.values.splice(0, 1)[0];
            node.keys = [...node.keys, pointerP0];
            node.values = [...node.values, pointerK0];
            parentNode = this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointer.values[0];
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          }
          this.bufferForNodeUpdate(node);
          this.bufferForNodeUpdate(pointer);
        }
        if (!pointer.leaf) {
          for (const key2 of pointer.keys) {
            const n = this.getNode(key2);
            n.parent = pointer.id;
            this.bufferForNodeUpdate(n);
          }
        }
        if (!node.leaf) {
          for (const key2 of node.keys) {
            const n = this.getNode(key2);
            n.parent = node.id;
            this.bufferForNodeUpdate(n);
          }
        }
        if (!parentNode.leaf) {
          for (const key2 of parentNode.keys) {
            const n = this.getNode(key2);
            n.parent = parentNode.id;
            this.bufferForNodeUpdate(n);
          }
        }
      }
    }
  }
  _insertInParent(node, value, pointer) {
    if (this.root === node) {
      const root = this._createNode(false, [node.id, pointer.id], [value]);
      this.root = root;
      this.strategy.head.root = root.id;
      this._strategyDirty = true;
      node.parent = root.id;
      pointer.parent = root.id;
      this.bufferForNodeCreate(root);
      this.bufferForNodeUpdate(node);
      this.bufferForNodeUpdate(pointer);
      return;
    }
    const parentNode = this.getNode(node.parent);
    for (let i = 0, len = parentNode.keys.length; i < len; i++) {
      const nKeys = parentNode.keys[i];
      if (nKeys === node.id) {
        parentNode.values.splice(i, 0, value);
        parentNode.keys.splice(i + 1, 0, pointer.id);
        this.bufferForNodeUpdate(parentNode);
        if (parentNode.keys.length > this.order) {
          const parentPointer = this._createNode(false, [], []);
          parentPointer.parent = parentNode.parent;
          const mid = Math.ceil(this.order / 2) - 1;
          parentPointer.values = parentNode.values.slice(mid + 1);
          parentPointer.keys = parentNode.keys.slice(mid + 1);
          const midValue = parentNode.values[mid];
          if (mid === 0) {
            parentNode.values = parentNode.values.slice(0, mid + 1);
          } else {
            parentNode.values = parentNode.values.slice(0, mid);
          }
          parentNode.keys = parentNode.keys.slice(0, mid + 1);
          for (const k of parentNode.keys) {
            const node2 = this.getNode(k);
            node2.parent = parentNode.id;
            this.bufferForNodeUpdate(node2);
          }
          for (const k of parentPointer.keys) {
            const node2 = this.getNode(k);
            node2.parent = parentPointer.id;
            this.bufferForNodeUpdate(node2);
          }
          this._insertInParent(parentNode, midValue, parentPointer);
          this.bufferForNodeCreate(parentPointer);
          this.bufferForNodeUpdate(parentNode);
        }
      }
    }
  }
  init() {
    const head = this.strategy.readHead();
    if (head === null) {
      this.order = this.strategy.order;
      this.root = this._createNode(true, [], [], true);
      this.strategy.head.root = this.root.id;
      this.bufferForNodeCreate(this.root);
      this.commitHeadBuffer();
      this.commitNodeCreateBuffer();
    } else {
      const { root, order } = head;
      this.strategy.head = head;
      this.order = order;
      this.root = this.getNode(root);
    }
    if (this.order < 3) {
      throw new Error(`The 'order' parameter must be greater than 2. but got a '${this.order}'.`);
    }
  }
  getNode(id) {
    if (!this.nodes.has(id)) {
      this.nodes.set(id, this.strategy.read(id));
    }
    return this.nodes.get(id);
  }
  insertableNode(value) {
    let node = this.root;
    while (!node.leaf) {
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        const k = node.keys;
        if (this.comparator.isSame(value, nValue)) {
          node = this.getNode(k[i + 1]);
          break;
        } else if (this.comparator.isLower(value, nValue)) {
          node = this.getNode(k[i]);
          break;
        } else if (i + 1 === node.values.length) {
          node = this.getNode(k[i + 1]);
          break;
        }
      }
    }
    return node;
  }
  leftestNode() {
    let node = this.root;
    while (!node.leaf) {
      const keys = node.keys;
      node = this.getNode(keys[0]);
    }
    return node;
  }
  commitHeadBuffer() {
    if (!this._strategyDirty) {
      return;
    }
    this._strategyDirty = false;
    this.strategy.writeHead(this.strategy.head);
  }
  commitNodeCreateBuffer() {
    for (const node of this._nodeCreateBuffer.values()) {
      this.strategy.write(node.id, node);
    }
    this._nodeCreateBuffer.clear();
  }
  commitNodeUpdateBuffer() {
    for (const node of this._nodeUpdateBuffer.values()) {
      this.strategy.write(node.id, node);
    }
    this._nodeUpdateBuffer.clear();
  }
  commitNodeDeleteBuffer() {
    for (const node of this._nodeDeleteBuffer.values()) {
      this.strategy.delete(node.id);
    }
    this._nodeDeleteBuffer.clear();
  }
  keys(condition, filterValues) {
    for (const k in condition) {
      const key = k;
      const value = condition[key];
      const startNode = this.verifierStartNode[key](value);
      const direction = this.verifierDirection[key];
      const fullScan = this.verifierFullScan[key];
      const comparator = this.verifierMap[key];
      const pairs = this.getPairs(value, startNode, fullScan, comparator, direction);
      if (!filterValues) {
        filterValues = new Set(pairs.keys());
      } else {
        const intersections = /* @__PURE__ */ new Set();
        for (const key2 of filterValues) {
          const has = pairs.has(key2);
          if (has) {
            intersections.add(key2);
          }
        }
        filterValues = intersections;
      }
    }
    return filterValues ?? /* @__PURE__ */ new Set([]);
  }
  where(condition) {
    let result = null;
    for (const k in condition) {
      const key = k;
      const value = condition[key];
      const startNode = this.verifierStartNode[key](value);
      const direction = this.verifierDirection[key];
      const fullScan = this.verifierFullScan[key];
      const comparator = this.verifierMap[key];
      const pairs = this.getPairs(value, startNode, fullScan, comparator, direction);
      if (result === null) {
        result = pairs;
      } else {
        const intersection = /* @__PURE__ */ new Map();
        for (const [k2, v] of pairs) {
          if (result.has(k2)) {
            intersection.set(k2, v);
          }
        }
        result = intersection;
      }
    }
    return result ?? /* @__PURE__ */ new Map();
  }
  insert(key, value) {
    const before = this.insertableNode(value);
    this._insertAtLeaf(before, key, value);
    if (before.values.length === this.order) {
      const after = this._createNode(
        true,
        [],
        [],
        true,
        before.parent,
        before.next,
        before.id
      );
      const mid = Math.ceil(this.order / 2) - 1;
      const beforeNext = before.next;
      after.values = before.values.slice(mid + 1);
      after.keys = before.keys.slice(mid + 1);
      before.values = before.values.slice(0, mid + 1);
      before.keys = before.keys.slice(0, mid + 1);
      before.next = after.id;
      if (beforeNext) {
        const node = this.getNode(beforeNext);
        node.prev = after.id;
        this.bufferForNodeUpdate(node);
      }
      this._insertInParent(before, after.values[0], after);
      this.bufferForNodeCreate(after);
      this.bufferForNodeUpdate(before);
    }
    this.commitHeadBuffer();
    this.commitNodeCreateBuffer();
    this.commitNodeUpdateBuffer();
  }
  delete(key, value) {
    const node = this.insertableNode(value);
    let i = node.values.length;
    while (i--) {
      const nValue = node.values[i];
      if (this.comparator.isSame(value, nValue)) {
        const keys = node.keys[i];
        if (keys.includes(key)) {
          if (keys.length > 1) {
            keys.splice(keys.indexOf(key), 1);
            this.bufferForNodeUpdate(node);
          } else if (node === this.root) {
            node.values.splice(i, 1);
            node.keys.splice(i, 1);
            this.bufferForNodeUpdate(node);
          } else {
            keys.splice(keys.indexOf(key), 1);
            node.keys.splice(i, 1);
            node.values.splice(node.values.indexOf(value), 1);
            this._deleteEntry(node, key, value);
            this.bufferForNodeUpdate(node);
          }
        }
      }
    }
    this.commitHeadBuffer();
    this.commitNodeCreateBuffer();
    this.commitNodeUpdateBuffer();
    this.commitNodeDeleteBuffer();
  }
  exists(key, value) {
    const node = this.insertableNode(value);
    for (let i = 0, len = node.values.length; i < len; i++) {
      const nValue = node.values[i];
      if (this.comparator.isSame(value, nValue)) {
        const keys = node.keys[i];
        return keys.includes(key);
      }
    }
    return false;
  }
  setHeadData(data) {
    this.strategy.head.data = data;
    this._strategyDirty = true;
    this.commitHeadBuffer();
  }
  forceUpdate() {
    const keys = [...this.nodes.keys()];
    this.nodes.clear();
    this.init();
    for (const key of keys) {
      this.getNode(key);
    }
    return keys.length;
  }
};

// src/BPTreeAsync.ts
var BPTreeAsync = class extends BPTree {
  constructor(strategy, comparator) {
    super(strategy, comparator);
  }
  async getPairsRightToLeft(value, startNode, fullScan, comparator) {
    const pairs = [];
    let node = startNode;
    let done = false;
    let found = false;
    while (!done) {
      let i = node.values.length;
      while (i--) {
        const nValue = node.values[i];
        const keys = node.keys[i];
        if (comparator(nValue, value)) {
          found = true;
          let j = keys.length;
          while (j--) {
            pairs.push([keys[j], nValue]);
          }
        } else if (found && !fullScan) {
          done = true;
          break;
        }
      }
      if (!node.prev) {
        done = true;
        break;
      }
      node = await this.getNode(node.prev);
    }
    return new Map(pairs.reverse());
  }
  async getPairsLeftToRight(value, startNode, fullScan, comparator) {
    const pairs = [];
    let node = startNode;
    let done = false;
    let found = false;
    while (!done) {
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        const keys = node.keys[i];
        if (comparator(nValue, value)) {
          found = true;
          for (let j = 0, len2 = keys.length; j < len2; j++) {
            const key = keys[j];
            pairs.push([key, nValue]);
          }
        } else if (found && !fullScan) {
          done = true;
          break;
        }
      }
      if (!node.next) {
        done = true;
        break;
      }
      node = await this.getNode(node.next);
    }
    return new Map(pairs);
  }
  async getPairs(value, startNode, fullScan, comparator, direction) {
    switch (direction) {
      case -1:
        return await this.getPairsRightToLeft(value, startNode, fullScan, comparator);
      case 1:
        return await this.getPairsLeftToRight(value, startNode, fullScan, comparator);
      default:
        throw new Error(`Direction must be -1 or 1. but got a ${direction}`);
    }
  }
  async _createNodeId(isLeaf) {
    const id = await this.strategy.id(isLeaf);
    if (id === null) {
      throw new Error(`The node's id should never be null.`);
    }
    return id;
  }
  async _createNode(isLeaf, keys, values, leaf = false, parent = null, next = null, prev = null) {
    const id = await this._createNodeId(isLeaf);
    const node = {
      id,
      keys,
      values,
      leaf,
      parent,
      next,
      prev
    };
    this.nodes.set(id, node);
    return node;
  }
  async _deleteEntry(node, key, value) {
    if (!node.leaf) {
      for (let i = 0, len = node.keys.length; i < len; i++) {
        const nKey = node.keys[i];
        if (nKey === key) {
          node.keys.splice(i, 1);
          this.bufferForNodeUpdate(node);
          break;
        }
      }
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        if (this.comparator.isSame(value, nValue)) {
          node.values.splice(i, 1);
          this.bufferForNodeUpdate(node);
          break;
        }
      }
    }
    if (this.root === node && node.keys.length === 1) {
      const keys = node.keys;
      this.bufferForNodeDelete(this.root);
      this.root = await this.getNode(keys[0]);
      this.root.parent = null;
      this.strategy.head.root = this.root.id;
      this._strategyDirty = true;
      this.bufferForNodeUpdate(this.root);
      return;
    } else if (this.root === node) {
      return;
    } else if (node.keys.length < Math.ceil(this.order / 2) && !node.leaf || node.values.length < Math.ceil((this.order - 1) / 2) && node.leaf) {
      if (node.parent === null) {
        return;
      }
      let isPredecessor = false;
      let parentNode = await this.getNode(node.parent);
      let prevNode = null;
      let nextNode = null;
      let prevValue = null;
      let postValue = null;
      for (let i = 0, len = parentNode.keys.length; i < len; i++) {
        const nKey = parentNode.keys[i];
        if (nKey === node.id) {
          if (i > 0) {
            prevNode = await this.getNode(parentNode.keys[i - 1]);
            prevValue = parentNode.values[i - 1];
          }
          if (i < parentNode.keys.length - 1) {
            nextNode = await this.getNode(parentNode.keys[i + 1]);
            postValue = parentNode.values[i];
          }
        }
      }
      let pointer;
      let guess;
      if (prevNode === null) {
        pointer = nextNode;
        guess = postValue;
      } else if (nextNode === null) {
        isPredecessor = true;
        pointer = prevNode;
        guess = prevValue;
      } else {
        if (node.values.length + nextNode.values.length < this.order) {
          pointer = nextNode;
          guess = postValue;
        } else {
          isPredecessor = true;
          pointer = prevNode;
          guess = prevValue;
        }
      }
      if (node.values.length + pointer.values.length < this.order) {
        if (!isPredecessor) {
          const pTemp = pointer;
          pointer = node;
          node = pTemp;
        }
        pointer.keys.push(...node.keys);
        if (!node.leaf) {
          pointer.values.push(guess);
        } else {
          pointer.next = node.next;
          pointer.prev = node.id;
          if (pointer.next) {
            const n = await this.getNode(node.next);
            n.prev = pointer.id;
            this.bufferForNodeUpdate(n);
          }
          if (pointer.prev) {
            const n = await this.getNode(node.id);
            n.next = pointer.id;
            this.bufferForNodeUpdate(n);
          }
          if (isPredecessor) {
            pointer.prev = null;
          }
        }
        pointer.values.push(...node.values);
        if (!pointer.leaf) {
          const keys = pointer.keys;
          for (const key2 of keys) {
            const node2 = await this.getNode(key2);
            node2.parent = pointer.id;
            this.bufferForNodeUpdate(node2);
          }
        }
        await this._deleteEntry(await this.getNode(node.parent), node.id, guess);
        this.bufferForNodeUpdate(pointer);
        this.bufferForNodeDelete(node);
      } else {
        if (isPredecessor) {
          let pointerPm;
          let pointerKm;
          if (!node.leaf) {
            pointerPm = pointer.keys.splice(-1)[0];
            pointerKm = pointer.values.splice(-1)[0];
            node.keys = [pointerPm, ...node.keys];
            node.values = [guess, ...node.values];
            parentNode = await this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointerKm;
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          } else {
            pointerPm = pointer.keys.splice(-1)[0];
            pointerKm = pointer.values.splice(-1)[0];
            node.keys = [pointerPm, ...node.keys];
            node.values = [pointerKm, ...node.values];
            parentNode = await this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointerKm;
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          }
          this.bufferForNodeUpdate(node);
          this.bufferForNodeUpdate(pointer);
        } else {
          let pointerP0;
          let pointerK0;
          if (!node.leaf) {
            pointerP0 = pointer.keys.splice(0, 1)[0];
            pointerK0 = pointer.values.splice(0, 1)[0];
            node.keys = [...node.keys, pointerP0];
            node.values = [...node.values, guess];
            parentNode = await this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointerK0;
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          } else {
            pointerP0 = pointer.keys.splice(0, 1)[0];
            pointerK0 = pointer.values.splice(0, 1)[0];
            node.keys = [...node.keys, pointerP0];
            node.values = [...node.values, pointerK0];
            parentNode = await this.getNode(node.parent);
            for (let i = 0, len = parentNode.values.length; i < len; i++) {
              const nValue = parentNode.values[i];
              if (this.comparator.isSame(guess, nValue)) {
                parentNode.values[i] = pointer.values[0];
                this.bufferForNodeUpdate(parentNode);
                break;
              }
            }
          }
          this.bufferForNodeUpdate(node);
          this.bufferForNodeUpdate(pointer);
        }
        if (!pointer.leaf) {
          for (const key2 of pointer.keys) {
            const n = await this.getNode(key2);
            n.parent = pointer.id;
            this.bufferForNodeUpdate(n);
          }
        }
        if (!node.leaf) {
          for (const key2 of node.keys) {
            const n = await this.getNode(key2);
            n.parent = node.id;
            this.bufferForNodeUpdate(n);
          }
        }
        if (!parentNode.leaf) {
          for (const key2 of parentNode.keys) {
            const n = await this.getNode(key2);
            n.parent = parentNode.id;
            this.bufferForNodeUpdate(n);
          }
        }
      }
    }
  }
  async _insertInParent(node, value, pointer) {
    if (this.root === node) {
      const root = await this._createNode(false, [node.id, pointer.id], [value]);
      this.root = root;
      this.strategy.head.root = root.id;
      this._strategyDirty = true;
      node.parent = root.id;
      pointer.parent = root.id;
      this.bufferForNodeCreate(root);
      this.bufferForNodeUpdate(node);
      this.bufferForNodeUpdate(pointer);
      return;
    }
    const parentNode = await this.getNode(node.parent);
    for (let i = 0, len = parentNode.keys.length; i < len; i++) {
      const nKeys = parentNode.keys[i];
      if (nKeys === node.id) {
        parentNode.values.splice(i, 0, value);
        parentNode.keys.splice(i + 1, 0, pointer.id);
        this.bufferForNodeUpdate(parentNode);
        if (parentNode.keys.length > this.order) {
          const parentPointer = await this._createNode(false, [], []);
          parentPointer.parent = parentNode.parent;
          const mid = Math.ceil(this.order / 2) - 1;
          parentPointer.values = parentNode.values.slice(mid + 1);
          parentPointer.keys = parentNode.keys.slice(mid + 1);
          const midValue = parentNode.values[mid];
          if (mid === 0) {
            parentNode.values = parentNode.values.slice(0, mid + 1);
          } else {
            parentNode.values = parentNode.values.slice(0, mid);
          }
          parentNode.keys = parentNode.keys.slice(0, mid + 1);
          for (const k of parentNode.keys) {
            const node2 = await this.getNode(k);
            node2.parent = parentNode.id;
            this.bufferForNodeUpdate(node2);
          }
          for (const k of parentPointer.keys) {
            const node2 = await this.getNode(k);
            node2.parent = parentPointer.id;
            this.bufferForNodeUpdate(node2);
          }
          await this._insertInParent(parentNode, midValue, parentPointer);
          this.bufferForNodeCreate(parentPointer);
          this.bufferForNodeUpdate(parentNode);
        }
      }
    }
  }
  async init() {
    const head = await this.strategy.readHead();
    if (head === null) {
      this.order = this.strategy.order;
      this.root = await this._createNode(true, [], [], true);
      this.strategy.head.root = this.root.id;
      this.bufferForNodeCreate(this.root);
      await this.commitHeadBuffer();
      await this.commitNodeCreateBuffer();
    } else {
      const { root, order } = head;
      this.strategy.head = head;
      this.order = order;
      this.root = await this.getNode(root);
    }
    if (this.order < 3) {
      throw new Error(`The 'order' parameter must be greater than 2. but got a '${this.order}'.`);
    }
  }
  async getNode(id) {
    if (!this.nodes.has(id)) {
      this.nodes.set(id, await this.strategy.read(id));
    }
    return this.nodes.get(id);
  }
  async insertableNode(value) {
    let node = this.root;
    while (!node.leaf) {
      for (let i = 0, len = node.values.length; i < len; i++) {
        const nValue = node.values[i];
        const k = node.keys;
        if (this.comparator.isSame(value, nValue)) {
          node = await this.getNode(k[i + 1]);
          break;
        } else if (this.comparator.isLower(value, nValue)) {
          node = await this.getNode(k[i]);
          break;
        } else if (i + 1 === node.values.length) {
          node = await this.getNode(k[i + 1]);
          break;
        }
      }
    }
    return node;
  }
  async leftestNode() {
    let node = this.root;
    while (!node.leaf) {
      const keys = node.keys;
      node = await this.getNode(keys[0]);
    }
    return node;
  }
  async commitHeadBuffer() {
    if (!this._strategyDirty) {
      return;
    }
    this._strategyDirty = false;
    await this.strategy.writeHead(this.strategy.head);
  }
  async commitNodeCreateBuffer() {
    for (const node of this._nodeCreateBuffer.values()) {
      await this.strategy.write(node.id, node);
    }
    this._nodeCreateBuffer.clear();
  }
  async commitNodeUpdateBuffer() {
    for (const node of this._nodeUpdateBuffer.values()) {
      await this.strategy.write(node.id, node);
    }
    this._nodeUpdateBuffer.clear();
  }
  async commitNodeDeleteBuffer() {
    for (const node of this._nodeDeleteBuffer.values()) {
      await this.strategy.delete(node.id);
    }
    this._nodeDeleteBuffer.clear();
  }
  async keys(condition, filterValues) {
    for (const k in condition) {
      const key = k;
      const value = condition[key];
      const startNode = await this.verifierStartNode[key](value);
      const direction = this.verifierDirection[key];
      const fullScan = this.verifierFullScan[key];
      const comparator = this.verifierMap[key];
      const pairs = await this.getPairs(value, startNode, fullScan, comparator, direction);
      if (!filterValues) {
        filterValues = new Set(pairs.keys());
      } else {
        const intersections = /* @__PURE__ */ new Set();
        for (const key2 of filterValues) {
          const has = pairs.has(key2);
          if (has) {
            intersections.add(key2);
          }
        }
        filterValues = intersections;
      }
    }
    return filterValues ?? /* @__PURE__ */ new Set([]);
  }
  async where(condition) {
    let result = null;
    for (const k in condition) {
      const key = k;
      const value = condition[key];
      const startNode = await this.verifierStartNode[key](value);
      const direction = this.verifierDirection[key];
      const fullScan = this.verifierFullScan[key];
      const comparator = this.verifierMap[key];
      const pairs = await this.getPairs(value, startNode, fullScan, comparator, direction);
      if (result === null) {
        result = pairs;
      } else {
        const intersection = /* @__PURE__ */ new Map();
        for (const [k2, v] of pairs) {
          if (result.has(k2)) {
            intersection.set(k2, v);
          }
        }
        result = intersection;
      }
    }
    return result ?? /* @__PURE__ */ new Map();
  }
  async insert(key, value) {
    const before = await this.insertableNode(value);
    this._insertAtLeaf(before, key, value);
    if (before.values.length === this.order) {
      const after = await this._createNode(
        true,
        [],
        [],
        true,
        before.parent,
        before.next,
        before.id
      );
      const mid = Math.ceil(this.order / 2) - 1;
      const beforeNext = before.next;
      after.values = before.values.slice(mid + 1);
      after.keys = before.keys.slice(mid + 1);
      before.values = before.values.slice(0, mid + 1);
      before.keys = before.keys.slice(0, mid + 1);
      before.next = after.id;
      if (beforeNext) {
        const node = await this.getNode(beforeNext);
        node.prev = after.id;
        this.bufferForNodeUpdate(node);
      }
      await this._insertInParent(before, after.values[0], after);
      this.bufferForNodeCreate(after);
      this.bufferForNodeUpdate(before);
    }
    await this.commitHeadBuffer();
    await this.commitNodeCreateBuffer();
    await this.commitNodeUpdateBuffer();
  }
  async delete(key, value) {
    const node = await this.insertableNode(value);
    let i = node.values.length;
    while (i--) {
      const nValue = node.values[i];
      if (this.comparator.isSame(value, nValue)) {
        const keys = node.keys[i];
        if (keys.includes(key)) {
          if (keys.length > 1) {
            keys.splice(keys.indexOf(key), 1);
            this.bufferForNodeUpdate(node);
          } else if (node === this.root) {
            node.values.splice(i, 1);
            node.keys.splice(i, 1);
            this.bufferForNodeUpdate(node);
          } else {
            keys.splice(keys.indexOf(key), 1);
            node.keys.splice(i, 1);
            node.values.splice(node.values.indexOf(value), 1);
            await this._deleteEntry(node, key, value);
            this.bufferForNodeUpdate(node);
          }
        }
      }
    }
    await this.commitHeadBuffer();
    await this.commitNodeCreateBuffer();
    await this.commitNodeUpdateBuffer();
    await this.commitNodeDeleteBuffer();
  }
  async exists(key, value) {
    const node = await this.insertableNode(value);
    for (let i = 0, len = node.values.length; i < len; i++) {
      const nValue = node.values[i];
      if (this.comparator.isSame(value, nValue)) {
        const keys = node.keys[i];
        return keys.includes(key);
      }
    }
    return false;
  }
  async setHeadData(data) {
    this.strategy.head.data = data;
    this._strategyDirty = true;
    await this.commitHeadBuffer();
  }
  async forceUpdate() {
    const keys = [...this.nodes.keys()];
    this.nodes.clear();
    await this.init();
    for (const key of keys) {
      await this.getNode(key);
    }
    return keys.length;
  }
};

// src/base/SerializeStrategy.ts
var SerializeStrategy = class {
  order;
  head;
  constructor(order) {
    this.order = order;
    this.head = {
      order,
      root: null,
      data: {}
    };
  }
};

// src/SerializeStrategySync.ts
var SerializeStrategySync = class extends SerializeStrategy {
  getHeadData(key, defaultValue) {
    if (!Object.hasOwn(this.head.data, key)) {
      this.setHeadData(key, defaultValue);
    }
    return this.head.data[key];
  }
  setHeadData(key, data) {
    this.head.data[key] = data;
    this.writeHead(this.head);
  }
  autoIncrement(key, defaultValue) {
    const current = this.getHeadData(key, defaultValue);
    const next = current + 1;
    this.setHeadData(key, next);
    return current;
  }
};
var InMemoryStoreStrategySync = class extends SerializeStrategySync {
  node;
  constructor(order) {
    super(order);
    this.node = {};
  }
  id(isLeaf) {
    return this.autoIncrement("index", 1).toString();
  }
  read(id) {
    if (!Object.hasOwn(this.node, id)) {
      throw new Error(`The tree attempted to reference node '${id}', but couldn't find the corresponding node.`);
    }
    return this.node[id];
  }
  write(id, node) {
    this.node[id] = node;
  }
  delete(id) {
    delete this.node[id];
  }
  readHead() {
    if (this.head.root === null) {
      return null;
    }
    return this.head;
  }
  writeHead(head) {
    this.head = head;
  }
};

// src/SerializeStrategyAsync.ts
var SerializeStrategyAsync = class extends SerializeStrategy {
  async getHeadData(key, defaultValue) {
    if (!Object.hasOwn(this.head.data, key)) {
      await this.setHeadData(key, defaultValue);
    }
    return this.head.data[key];
  }
  async setHeadData(key, data) {
    this.head.data[key] = data;
    await this.writeHead(this.head);
  }
  async autoIncrement(key, defaultValue) {
    const current = await this.getHeadData(key, defaultValue);
    const next = current + 1;
    await this.setHeadData(key, next);
    return current;
  }
};
var InMemoryStoreStrategyAsync = class extends SerializeStrategyAsync {
  node;
  constructor(order) {
    super(order);
    this.node = {};
  }
  async id(isLeaf) {
    return (await this.autoIncrement("index", 1)).toString();
  }
  async read(id) {
    if (!Object.hasOwn(this.node, id)) {
      throw new Error(`The tree attempted to reference node '${id}', but couldn't find the corresponding node.`);
    }
    return this.node[id];
  }
  async write(id, node) {
    this.node[id] = node;
  }
  async delete(id) {
    delete this.node[id];
  }
  async readHead() {
    if (this.head.root === null) {
      return null;
    }
    return this.head;
  }
  async writeHead(head) {
    this.head = head;
  }
};