mux-radix-tree 0.1.0

use std::marker::PhantomData;
use std::mem;

use super::{RadixTree, RadixTreeNode};

use Entry::*;

/// This describes the location of the corresponding key in the tree. If the key does not actually
/// exist, then the key field will be non-empty and the node field points to the node in tree where
/// a new edge for this key would be inserted. If the key already exists in the tree, the key field
/// will be empty, and the node field points to the node corresponding to the key.
///
/// This allows to implement an API similar to `HashMap::entry`, so you can do in-place
/// modifications without duplicated tree traversals occurring.
pub enum Entry<'a, K: 'a, V: 'a>
where
    K: PartialEq,
{
    // There is a value for this key in the tree.
    Occupied(OccupiedEntry<'a, K, V>),
    // There is no value for this key in the tree, but the node exists.
    Vacant(VacantEntry<'a, K, V>),
    // There is no value for this key in the tree, and the node does not exist.
    NonExistent(NonExistentEntry<'a, K, V>),
}

// XXX we need to deal with the RadixTree struct so we can adjust the length as appropriate.
pub struct OccupiedEntry<'a, K, V>
where
    K: PartialEq,
{
    pub(super) tree: &'a mut RadixTree<K, V>,
    pub(super) value: &'a mut V,
    pub(super) _marker: PhantomData<K>,
}

pub struct VacantEntry<'a, K, V>
where
    K: PartialEq,
{
    pub(super) tree: &'a mut RadixTree<K, V>,
    pub(super) node: &'a mut RadixTreeNode<K, V>,
}

pub struct NonExistentEntry<'a, K, V>
where
    K: PartialEq,
{
    pub(super) tree: &'a mut RadixTree<K, V>,
    pub(super) suffix: Vec<K>,
    pub(super) parent: &'a mut RadixTreeNode<K, V>,
    pub(super) edge_index: Option<usize>,
}

impl<'a, K, V> Entry<'a, K, V>
where
    K: PartialEq + Copy,
{
    pub fn or_insert(self, default: V) -> &'a mut V {
        match self {
            Vacant(entry) => entry.insert(default),
            NonExistent(entry) => entry.insert(default),
            Occupied(entry) => entry.into_mut(),
        }
    }

    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
        match self {
            Vacant(entry) => entry.insert(default()),
            NonExistent(entry) => entry.insert(default()),
            Occupied(entry) => entry.into_mut(),
        }
    }

    pub fn and_modify<F>(self, f: F) -> Self
    where
        F: FnOnce(&mut V),
    {
        match self {
            Occupied(mut entry) => {
                f(entry.get_mut());
                Occupied(entry)
            }
            Vacant(entry) => Vacant(entry),
            NonExistent(entry) => NonExistent(entry),
        }
    }

    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
        match self {
            Occupied(mut entry) => {
                entry.insert(value);
                entry
            }
            Vacant(entry) => entry.insert_entry(value),
            NonExistent(entry) => entry.insert_entry(value),
        }
    }
}

impl<'a, K, V> OccupiedEntry<'a, K, V>
where
    K: PartialEq,
{
    fn into_mut(self) -> &'a mut V {
        self.value
    }

    fn get_mut(&mut self) -> &mut V {
        self.value
    }

    fn insert(&mut self, value: V) -> V {
        mem::replace(self.get_mut(), value)
    }
}

impl<'a, K, V> VacantEntry<'a, K, V>
where
    K: PartialEq + Copy,
{
    pub fn insert(self, value: V) -> &'a mut V {
        self.node.value.insert(value)
    }

    pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
        OccupiedEntry {
            value: self.insert(value),
            _marker: PhantomData,
        }
    }
}

impl<'a, K, V> NonExistentEntry<'a, K, V>
where
    K: PartialEq + Copy,
{
    pub fn insert(self, value: V) -> &'a mut V {
        // XXX need an insert function that returns the new edge
        self.parent.insert(self.suffix, value);
        unimplemented!();
    }
}