//! A tiny insertion-ordered map.
//!
//! The weave algorithm depends on iteration order matching the order keys were
//! first inserted. A plain hash map would not hold that order, so this small
//! vector-backed map keeps it.

use std::collections::HashMap;

/// A map that iterates keys in first-insertion order.
pub struct OrderedMap<K, V> {
    entries: Vec<(K, V)>,
    index: HashMap<K, usize>,
}

impl<K: Clone + Eq + std::hash::Hash, V> OrderedMap<K, V> {
    /// Create an empty map.
    pub fn new() -> Self {
        OrderedMap {
            entries: Vec::new(),
            index: HashMap::new(),
        }
    }

    /// Insert or replace `key` with `value`. Insertion order is set on first
    /// insert and kept on replace.
    pub fn insert(&mut self, key: K, value: V) {
        if let Some(&i) = self.index.get(&key) {
            self.entries[i].1 = value;
        } else {
            let i = self.entries.len();
            self.index.insert(key.clone(), i);
            self.entries.push((key, value));
        }
    }

    /// Get a mutable reference to the value for `key`, inserting `default`
    /// first if the key is absent.
    pub fn get_mut_or_insert(&mut self, key: K, default: V) -> &mut V {
        if let Some(&i) = self.index.get(&key) {
            &mut self.entries[i].1
        } else {
            let i = self.entries.len();
            self.index.insert(key.clone(), i);
            self.entries.push((key, default));
            &mut self.entries[i].1
        }
    }

    /// Iterate keys in insertion order.
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        self.entries.iter().map(|(k, _)| k)
    }

    /// Iterate key and value references in insertion order.
    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        self.entries.iter().map(|(k, v)| (k, v))
    }
}

impl<K, V> IntoIterator for OrderedMap<K, V> {
    type Item = (K, V);
    type IntoIter = std::vec::IntoIter<(K, V)>;

    fn into_iter(self) -> Self::IntoIter {
        self.entries.into_iter()
    }
}
