mapgraph 0.12.0

use crate::{
    map::{
        ExtKeyMap, Map, MapEntry, MapWithEntry, OccupiedError, OccupiedMapEntry, OrderedKeyMap,
        VacantMapEntry,
    },
    util::{self, KeyMap, KeyMapMut},
    KeySet,
};
use alloc::collections::{
    btree_map::{self, Iter, IterMut, Range, RangeMut},
    BTreeMap, BTreeSet,
};
use core::{fmt::Debug, ops::RangeBounds};

impl<K: Copy + Eq + Ord + Debug + 'static, T> Map<T> for BTreeMap<K, T> {
    type Key = K;
    type Iter<'a> = KeyMap<'a, Iter<'a, K, T>, K, T> where Self: 'a, T: 'a;
    type IterMut<'a> = KeyMapMut<'a, IterMut<'a, K, T>, K, T> where Self: 'a, T: 'a;

    fn len(&self) -> usize {
        BTreeMap::len(self)
    }

    fn is_empty(&self) -> bool {
        BTreeMap::is_empty(self)
    }

    fn contains_key(&self, index: Self::Key) -> bool {
        BTreeMap::contains_key(self, &index)
    }

    fn get(&self, index: Self::Key) -> Option<&T> {
        BTreeMap::get(self, &index)
    }

    fn get_mut(&mut self, index: Self::Key) -> Option<&mut T> {
        BTreeMap::get_mut(self, &index)
    }

    fn remove(&mut self, index: Self::Key) -> Option<T> {
        BTreeMap::remove(self, &index)
    }

    fn clear(&mut self) {
        BTreeMap::clear(self)
    }

    fn iter(&self) -> Self::Iter<'_> {
        BTreeMap::iter(self).map(util::map_deref_key)
    }

    fn iter_mut(&mut self) -> Self::IterMut<'_> {
        BTreeMap::iter_mut(self).map(util::map_deref_key)
    }
}

impl<K: Copy + Eq + Ord + Debug + 'static, T> ExtKeyMap<T> for BTreeMap<K, T> {
    fn try_insert(&mut self, key: Self::Key, value: T) -> Result<(), OccupiedError> {
        match BTreeMap::entry(self, key) {
            btree_map::Entry::Vacant(entry) => {
                entry.insert(value);
                Ok(())
            }
            btree_map::Entry::Occupied(_) => Err(OccupiedError),
        }
    }

    fn replace(&mut self, key: Self::Key, value: T) -> Option<T> {
        BTreeMap::insert(self, key, value)
    }
}

impl<K: Copy + Eq + Ord + Debug + 'static, T> OrderedKeyMap<T> for BTreeMap<K, T> {
    type Range<'a> = KeyMap<'a, Range<'a, K, T>, K, T> where Self: 'a;
    type RangeMut<'a> = KeyMapMut<'a, RangeMut<'a, K, T>, K, T> where Self: 'a;

    fn range<R: RangeBounds<Self::Key>>(&self, range: R) -> Self::Range<'_> {
        BTreeMap::range(self, range).map(util::map_deref_key)
    }

    fn range_mut<R: RangeBounds<Self::Key>>(&mut self, range: R) -> Self::RangeMut<'_> {
        BTreeMap::range_mut(self, range).map(util::map_deref_key)
    }

    fn first(&self) -> Option<(K, &T)> {
        BTreeMap::first_key_value(self).map(|(k, v)| (*k, v))
    }

    fn first_mut(&mut self) -> Option<(K, &mut T)> {
        BTreeMap::first_entry(self).map(|entry| {
            let key = *entry.key();
            let value = entry.into_mut();
            (key, value)
        })
    }

    fn last(&self) -> Option<(K, &T)> {
        BTreeMap::last_key_value(self).map(|(k, v)| (*k, v))
    }

    fn last_mut(&mut self) -> Option<(K, &mut T)> {
        BTreeMap::last_entry(self).map(|entry| {
            let key = *entry.key();
            let value = entry.into_mut();
            (key, value)
        })
    }
}

impl<'a, K: Copy + Eq + Ord + Debug + 'static, T> VacantMapEntry
    for btree_map::VacantEntry<'a, K, T>
{
    type Value = T;

    fn insert<'b>(self, value: Self::Value) -> &'b mut Self::Value
    where
        Self: 'b,
    {
        btree_map::VacantEntry::insert(self, value)
    }
}

impl<'a, K: Copy + Eq + Ord + Debug + 'static, T> OccupiedMapEntry
    for btree_map::OccupiedEntry<'a, K, T>
{
    type Value = T;

    fn get(&self) -> &Self::Value {
        btree_map::OccupiedEntry::get(self)
    }

    fn get_mut(&mut self) -> &mut Self::Value {
        btree_map::OccupiedEntry::get_mut(self)
    }

    fn into_mut<'b>(self) -> &'b mut Self::Value
    where
        Self: 'b,
    {
        btree_map::OccupiedEntry::into_mut(self)
    }

    fn replace(&mut self, value: Self::Value) -> Self::Value {
        btree_map::OccupiedEntry::insert(self, value)
    }

    fn remove(self) -> Self::Value {
        btree_map::OccupiedEntry::remove(self)
    }
}

impl<K: Copy + Eq + Ord + Debug + 'static, T> MapWithEntry<T> for BTreeMap<K, T> {
    type VacantEntry<'a> = btree_map::VacantEntry<'a, K, T> where T: 'a;
    type OccupiedEntry<'a> = btree_map::OccupiedEntry<'a, K, T> where T: 'a;

    fn entry(
        &mut self,
        key: Self::Key,
    ) -> MapEntry<Self::OccupiedEntry<'_>, Self::VacantEntry<'_>> {
        match BTreeMap::entry(self, key) {
            btree_map::Entry::Occupied(entry) => MapEntry::Occupied(entry),
            btree_map::Entry::Vacant(entry) => MapEntry::Vacant(entry),
        }
    }
}

impl<K: Copy + Eq + Ord + Debug + 'static> KeySet<K> for BTreeSet<K> {
    fn len(&self) -> usize {
        BTreeSet::len(self)
    }

    fn is_empty(&self) -> bool {
        BTreeSet::is_empty(self)
    }

    fn contains(&self, index: K) -> bool {
        BTreeSet::contains(self, &index)
    }

    fn insert(&mut self, index: K) -> bool {
        BTreeSet::insert(self, index)
    }

    fn remove(&mut self, index: K) -> bool {
        BTreeSet::remove(self, &index)
    }

    fn clear(&mut self) {
        BTreeSet::clear(self)
    }
}