/** @import { Metric } from "../metrics/index.js" */
/** @import { ParametersHNSW } from "./index.js" */
/**
 * @typedef {Object} Layer
 * @property {number} l_c - Layer number
 * @property {number[]} point_indices - Global indices of points in this layer
 * @property {Map<number, number[]>} edges - Global index -> array of connected global indices
 */
/**
 * @template {number[] | Float64Array} T
 * @typedef {Object} Candidate
 * @property {T} element - The actual data point
 * @property {number} index - Global index in the dataset
 * @property {number} distance - Distance from query
 */
/**
 * Hierarchical Navigable Small World (HNSW) graph for approximate nearest neighbor search.
 *
 * HNSW builds a multi-layer graph structure where each layer is a navigable small world graph.
 * The top layers serve as "highways" for fast traversal, while lower layers provide accuracy.
 * Each element is assigned to a random level, allowing logarithmic search complexity.
 *
 * Key parameters:
 * - `m`: Controls the number of connections per element (affects accuracy/memory)
 * - `ef_construction`: Controls the quality of the graph during construction (higher = better but slower)
 * - `ef`: Controls the quality of search (higher = better recall but slower)
 *
 * Based on:
 * - "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs"
 *   by Malkov & Yashunin (2016)
 * - "Approximate Nearest Neighbor Search on High Dimensional Data"
 *   by Li et al. (2019)
 *
 * @class
 * @category KNN
 * @template {number[] | Float64Array} T
 * @extends KNN<T, ParametersHNSW>
 *
 * @example
 * import * as druid from "@saehrimnir/druidjs";
 *
 * const points = [[1, 2], [3, 4], [5, 6], [7, 8]];
 * const hnsw = new druid.HNSW(points, {
 *     metric: druid.euclidean,
 *     m: 16,
 *     ef_construction: 200
 * });
 *
 * const query = [2, 3];
 * const neighbors = hnsw.search(query, 2);
 * // [{ element: [1, 2], index: 0, distance: 1.41 }, ...]
 */
export class HNSW<T extends number[] | Float64Array> extends KNN<T, ParametersHNSW> {
  /**
   * Creates a new HNSW index.
   *
   * @param {T[]} points - Initial points to add to the index
   * @param {ParametersHNSW} [parameters={}] - Configuration parameters
   */
  constructor(points: T[], parameters?: ParametersHNSW);
  /** @type {Metric} */
  _metric: Metric;
  /** @type {Function} */
  _select: Function;
  /**
   * @private
   * @type {Map<number, Layer>}
   */
  private _graph;
  /** @type {number} */
  _next_index: number;
  /** @type {number} */
  _m: number;
  /** @type {number} */
  _ef_construction: number;
  /** @type {number} */
  _ef: number;
  /** @type {number} */
  _m0: number;
  /** @type {number} */
  _mL: number;
  /** @type {Randomizer} */
  _randomizer: Randomizer;
  /** @type {number} - Current maximum layer in the graph */
  _L: number;
  /** @type {number[] | null} - Entry point indices for search */
  _ep: number[] | null;
  /**
   * Add a single element to the index.
   *
   * @param {T} element - Element to add
   * @returns {HNSW<T>} This instance for chaining
   */
  addOne(element: T): HNSW<T>;
  /**
   * Add multiple elements to the index.
   *
   * @param {T[]} new_elements - Elements to add
   * @returns {HNSW<T>} This instance for chaining
   */
  add(new_elements: T[]): HNSW<T>;
  /**
   * Select neighbors using the heuristic approach.
   *
   * The heuristic extends candidates with their neighbors and selects
   * points that are closer to the query than to already selected points.
   * This maintains graph connectivity better than simple selection.
   *
   * @private
   * @param {T} q - Query element
   * @param {Candidate<T>[]} candidates - Candidate elements with distances
   * @param {number} M - Maximum number of neighbors to return
   * @param {number} l_c - Layer number
   * @param {boolean} [extend_candidates=true] - Whether to extend candidates with their neighbors
   * @param {boolean} [keep_pruned_connections=true] - Whether to add pruned connections back if needed
   * @returns {number[]} Selected neighbor indices
   */
  private _select_heuristic;
  /**
   * Select neighbors using simple distance-based selection.
   *
   * Simply returns the M closest candidates to the query.
   *
   * @private
   * @param {T} q - Query element
   * @param {Candidate<T>[]} C - Candidate elements with distances
   * @param {number} M - Maximum number of neighbors to return
   * @returns {number[]} M nearest candidate indices
   */
  private _select_simple;
  /**
   * Search a single layer for nearest neighbors.
   *
   * Implements the greedy search algorithm: start from entry points,
   * always expand the closest unvisited candidate, maintain a list
   * of the ef closest found neighbors.
   *
   * @private
   * @param {T} q - Query element
   * @param {number[] | null} ep_indices - Entry point indices
   * @param {number} ef - Number of nearest neighbors to find
   * @param {number} l_c - Layer number to search
   * @returns {Candidate<T>[]} ef nearest neighbors found with their distances
   */
  private _search_layer;
  /**
   * Fallback linear search when graph search fails
   * @private
   * @param {T} q - Query element
   * @param {number} K - Number of nearest neighbors to return
   * @returns {Candidate<T>[]}
   */
  private _linear_search;
  /**
   * Iterator for searching the HNSW graph layer by layer.
   *
   * Yields intermediate results at each layer for debugging or visualization.
   *
   * @param {T} q - Query element
   * @param {number} K - Number of nearest neighbors to return
   * @param {number?} [ef] - Size of dynamic candidate list
   * @yields {{layer: number, candidates: Candidate[]}}
   */
  search_iter(
    q: T,
    K: number,
    ef?: number | null,
  ): Generator<
    {
      layer: number;
      candidates: {
        element: T;
        index: number;
        distance: number;
      }[];
    },
    void,
    unknown
  >;
  /**
   * Get the number of elements in the index.
   *
   * @returns {number} Number of elements
   */
  get size(): number;
  /**
   * Get the number of layers in the graph.
   *
   * @returns {number} Number of layers
   */
  get num_layers(): number;
  /**
   * Get an element by its index.
   *
   * @param {number} index - Element index
   * @returns {T} The element at the given index
   */
  get_element(index: number): T;
  /**
   * Search for nearest neighbors using an element index as the query.
   *
   * @param {number} i - Index of the query element
   * @param {number} [K=5] - Number of nearest neighbors to return
   * @returns {Candidate<T>[]} K nearest neighbors
   */
  search_by_index(i: number, K?: number): Candidate<T>[];
}
export type Layer = {
  /**
   * - Layer number
   */
  l_c: number;
  /**
   * - Global indices of points in this layer
   */
  point_indices: number[];
  /**
   * - Global index -> array of connected global indices
   */
  edges: Map<number, number[]>;
};
export type Candidate<T extends number[] | Float64Array> = {
  /**
   * - The actual data point
   */
  element: T;
  /**
   * - Global index in the dataset
   */
  index: number;
  /**
   * - Distance from query
   */
  distance: number;
};
import type { ParametersHNSW } from "./index.js";
import { KNN } from "./KNN.js";
import type { Metric } from "../metrics/index.js";
import { Randomizer } from "../util/index.js";
//# sourceMappingURL=HNSW.d.ts.map