hayson-engine 0.17.0

use std::cmp::Ordering;

use serde_json::Value;

#[derive(Debug, Clone, PartialEq)]
pub enum SortValue {
    Num(f64),
    Str(String),
    Bool(bool),
}

impl SortValue {
    pub fn from_json(value: &Value) -> Option<Self> {
        match value {
            Value::Number(n) => n.as_f64().map(SortValue::Num),
            Value::String(s) => Some(SortValue::Str(s.clone())),
            Value::Bool(b) => Some(SortValue::Bool(*b)),
            _ => None,
        }
    }
}

// NOTE: mismatched variants have no defined order (mirrors comparing unlike JS operands loosely).
fn compare_values(a: &SortValue, b: &SortValue) -> Ordering {
    match (a, b) {
        (SortValue::Num(x), SortValue::Num(y)) => x.partial_cmp(y).unwrap_or(Ordering::Equal),
        (SortValue::Str(x), SortValue::Str(y)) => x.cmp(y),
        (SortValue::Bool(x), SortValue::Bool(y)) => x.cmp(y),
        _ => Ordering::Equal,
    }
}

pub type SortVector = Vec<SortValue>;

#[derive(Debug, Clone, Default)]
pub struct RangeBounds {
    pub gt: Option<SortVector>,
    pub gte: Option<SortVector>,
    pub lt: Option<SortVector>,
    pub lte: Option<SortVector>,
}

fn compare_shared(a: &[SortValue], b: &[SortValue]) -> Ordering {
    let shared = a.len().min(b.len());
    for at in 0..shared {
        let ordering = compare_values(&a[at], &b[at]);
        if ordering != Ordering::Equal {
            return ordering;
        }
    }
    Ordering::Equal
}

pub fn compare_vectors(a: &[SortValue], b: &[SortValue]) -> Ordering {
    let shared = compare_shared(a, b);
    // NOTE: a shorter vector sorts before every vector it prefixes, matching a prefix bound's needs.
    if shared != Ordering::Equal {
        shared
    } else {
        a.len().cmp(&b.len())
    }
}

fn compare_to_bound_width(entry: &[SortValue], bound: &[SortValue]) -> Ordering {
    let shared = compare_shared(entry, bound);
    if shared != Ordering::Equal {
        return shared;
    }
    // NOTE: fields past the bound's width cannot move the entry out of it -- only shorter entries rank.
    if entry.len() < bound.len() {
        Ordering::Less
    } else {
        Ordering::Equal
    }
}

struct SortedEntry {
    value: SortVector,
    key: String,
}

fn compare_entries(a: &SortedEntry, b: &SortedEntry) -> Ordering {
    let by_value = compare_vectors(&a.value, &b.value);
    if by_value != Ordering::Equal {
        return by_value;
    }
    a.key.cmp(&b.key)
}

#[derive(Default)]
pub struct ArraySortedIndex {
    entries: Vec<SortedEntry>,
}

impl ArraySortedIndex {
    pub fn new() -> Self {
        ArraySortedIndex { entries: Vec::new() }
    }

    #[allow(dead_code)]
    pub fn size(&self) -> usize {
        self.entries.len()
    }

    fn locate(&self, entry: &SortedEntry) -> usize {
        let mut low = 0;
        let mut high = self.entries.len();
        while low < high {
            let middle = (low + high) / 2;
            if compare_entries(&self.entries[middle], entry) == Ordering::Less {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        low
    }

    pub fn insert(&mut self, key: &str, value: SortVector) {
        let entry = SortedEntry {
            value,
            key: key.to_string(),
        };
        let at = self.locate(&entry);
        self.entries.insert(at, entry);
    }

    pub fn remove(&mut self, key: &str, value: &[SortValue]) {
        let wanted = SortedEntry {
            value: value.to_vec(),
            key: key.to_string(),
        };
        let at = self.locate(&wanted);
        if let Some(found) = self.entries.get(at) {
            if found.key == key && compare_vectors(&found.value, value) == Ordering::Equal {
                self.entries.remove(at);
            }
        }
    }

    pub fn range(&self, bounds: &RangeBounds) -> Vec<String> {
        let lower = bounds.gte.as_ref().or(bounds.gt.as_ref());
        let start = match lower {
            None => 0,
            Some(value) => self.locate(&SortedEntry {
                value: value.clone(),
                key: String::new(),
            }),
        };
        let mut keys = Vec::new();
        for entry in &self.entries[start..] {
            if let Some(gt) = &bounds.gt {
                if compare_to_bound_width(&entry.value, gt) != Ordering::Greater {
                    continue;
                }
            }
            if let Some(lt) = &bounds.lt {
                if compare_to_bound_width(&entry.value, lt) != Ordering::Less {
                    break;
                }
            }
            if let Some(lte) = &bounds.lte {
                if compare_to_bound_width(&entry.value, lte) == Ordering::Greater {
                    break;
                }
            }
            keys.push(entry.key.clone());
        }
        keys
    }

    #[allow(dead_code)]
    pub fn ordered(&self, direction: Direction) -> Vec<String> {
        let mut keys: Vec<String> = self.entries.iter().map(|e| e.key.clone()).collect();
        if direction == Direction::Desc {
            keys.reverse();
        }
        keys
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[allow(dead_code)]
pub enum Direction {
    Asc,
    Desc,
}

#[cfg(test)]
mod tests {
    use super::*;

    fn num(n: f64) -> SortVector {
        vec![SortValue::Num(n)]
    }

    fn bound(values: &[f64]) -> SortVector {
        values.iter().map(|n| SortValue::Num(*n)).collect()
    }

    #[test]
    fn keeps_entries_ordered_and_answers_ranges() {
        let mut index = ArraySortedIndex::new();
        index.insert("c", num(30.0));
        index.insert("a", num(10.0));
        index.insert("b", num(20.0));

        assert_eq!(index.ordered(Direction::Asc), vec!["a", "b", "c"]);
        assert_eq!(index.ordered(Direction::Desc), vec!["c", "b", "a"]);
        assert_eq!(
            index.range(&RangeBounds {
                gte: Some(bound(&[20.0])),
                ..Default::default()
            }),
            vec!["b", "c"]
        );
        assert_eq!(
            index.range(&RangeBounds {
                gt: Some(bound(&[20.0])),
                ..Default::default()
            }),
            vec!["c"]
        );
        assert_eq!(
            index.range(&RangeBounds {
                gte: Some(bound(&[10.0])),
                lte: Some(bound(&[20.0])),
                ..Default::default()
            }),
            vec!["a", "b"]
        );
        assert_eq!(
            index.range(&RangeBounds {
                lt: Some(bound(&[20.0])),
                ..Default::default()
            }),
            vec!["a"]
        );

        index.remove("b", &num(20.0));
        assert_eq!(index.size(), 2);
        assert_eq!(
            index.range(&RangeBounds {
                gte: Some(bound(&[0.0])),
                ..Default::default()
            }),
            vec!["a", "c"]
        );
    }

    fn text(s: &str) -> SortValue {
        SortValue::Str(s.to_string())
    }

    #[test]
    fn orders_a_shorter_entry_before_every_longer_one_that_shares_its_prefix() {
        let mut index = ArraySortedIndex::new();
        index.insert("below", vec![text("u0"), SortValue::Num(9.0)]);
        index.insert("short", vec![text("u1")]);
        index.insert("long", vec![text("u1"), SortValue::Num(5.0)]);

        assert_eq!(index.ordered(Direction::Asc), vec!["below", "short", "long"]);
        assert_eq!(
            index.range(&RangeBounds {
                lt: Some(vec![text("u1"), SortValue::Num(5.0)]),
                ..Default::default()
            }),
            vec!["below", "short"]
        );
        assert_eq!(
            index.range(&RangeBounds {
                lte: Some(vec![text("u1"), SortValue::Num(5.0)]),
                ..Default::default()
            }),
            vec!["below", "short", "long"]
        );
        assert_eq!(
            index.range(&RangeBounds {
                gte: Some(vec![text("u1")]),
                ..Default::default()
            }),
            vec!["short", "long"]
        );
    }
}