use std::cmp::Ordering;
use std::collections::HashMap;
use crate::error::{VectorError, VectorResult};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Metric {
Cosine,
Dot,
Euclidean,
}
impl Metric {
fn score(&self, a: &[f32], na: f32, entry: &Entry) -> f32 {
let b = &entry.vector;
match self {
Metric::Cosine => {
let nb = entry.norm;
if na == 0.0 || nb == 0.0 {
0.0
} else {
dot(a, b) / (na * nb)
}
}
Metric::Dot => dot(a, b),
Metric::Euclidean => -l2(a, b),
}
}
fn norm_of(&self, v: &[f32]) -> f32 {
match self {
Metric::Cosine => norm(v),
Metric::Dot | Metric::Euclidean => 0.0,
}
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Match {
pub id: String,
pub score: f32,
}
struct Entry {
id: String,
vector: Vec<f32>,
norm: f32,
}
pub struct VectorIndex {
dim: usize,
metric: Metric,
entries: Vec<Entry>,
positions: HashMap<String, usize>,
}
impl VectorIndex {
pub fn new(dim: usize, metric: Metric) -> Self {
Self {
dim,
metric,
entries: Vec::new(),
positions: HashMap::new(),
}
}
pub fn dim(&self) -> usize {
self.dim
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
if vector.len() != self.dim {
return Err(VectorError::DimMismatch {
expected: self.dim,
got: vector.len(),
});
}
let id = id.into();
let norm = self.metric.norm_of(&vector);
if let Some(&at) = self.positions.get(&id) {
let existing = &mut self.entries[at];
existing.vector = vector;
existing.norm = norm;
} else {
self.positions.insert(id.clone(), self.entries.len());
self.entries.push(Entry { id, vector, norm });
}
Ok(())
}
pub fn remove(&mut self, id: &str) -> bool {
let Some(at) = self.positions.remove(id) else {
return false;
};
self.entries.remove(at);
for entry in &self.entries[at..] {
if let Some(p) = self.positions.get_mut(&entry.id) {
*p -= 1;
}
}
true
}
pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
if query.len() != self.dim {
return Err(VectorError::DimMismatch {
expected: self.dim,
got: query.len(),
});
}
let query_norm = self.metric.norm_of(query);
let mut scored: Vec<(f32, usize)> = self
.entries
.iter()
.enumerate()
.map(|(at, e)| (self.metric.score(query, query_norm, e), at))
.collect();
let rank = |a: &(f32, usize), b: &(f32, usize)| {
b.0.partial_cmp(&a.0)
.unwrap_or(Ordering::Equal)
.then_with(|| self.entries[a.1].id.cmp(&self.entries[b.1].id))
};
if k < scored.len() && !scored.iter().any(|(s, _)| s.is_nan()) {
if k > 0 {
scored.select_nth_unstable_by(k - 1, rank);
}
scored.truncate(k);
}
scored.sort_by(rank);
scored.truncate(k);
Ok(scored
.into_iter()
.map(|(score, at)| Match {
id: self.entries[at].id.clone(),
score,
})
.collect())
}
}
fn dot(a: &[f32], b: &[f32]) -> f32 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
fn norm(a: &[f32]) -> f32 {
dot(a, a).sqrt()
}
fn l2(a: &[f32], b: &[f32]) -> f32 {
a.iter()
.zip(b)
.map(|(x, y)| {
let d = x - y;
d * d
})
.sum::<f32>()
.sqrt()
}