//Copyright 2026 Henry Smith
//SPDX-License-Identifier: MIT OR Apache-2.0

// Top level documentation lives in the README
#![doc = include_str!("../README.md")]

use std::collections::HashMap;
use std::collections::VecDeque;
use std::fmt::Debug;

/// The error thrown in the case that an insert operation fails
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum InsertError {
    /// Thrown when an item that is not the end of a path isn't a table.
    /// This means the code is unable to find the item 'within' it
    PathItemNotATable,

    /// Thrown when an empty path is given to the insert function
    EmptyPath,
}

/// The error thrown in the case that a get operation fails.
///
/// Note that this will also also be thrown if the item is not found, which is why the function [`Self::is_actual_error()`]
/// is quite useful for sanitising this enum
#[derive(Debug, Clone, PartialEq, Hash)]
pub enum GetError {
    /// Thrown when an empty path is given to the get function,
    /// if you want a copy of the table, use [`std::clone`]
    EmptyPath,

    /// Thrown if you try to get an item which is in a directory that does not exist,
    NonExistentPathItem,

    /// Thrown in the case that a path value couldn't be converted into a map,
    /// This could be for many reasons such as a path item not being a table or an error in the
    /// [`NestableValue`] implementation of the value
    CouldNotConvertToMap,

    /// Thrown if there is no item at the end of the path, will throw [`Self::NonExistentPathItem`] if an item
    /// in the path does not exist.
    ItemNotFound,
}
impl GetError {
    /// Returns a boolean to check if it is an actual error or if the item simply isn't present
    /// It will return false if [`GetError::ItemNotFound`] or [`GetError::NonExistentPathItem`] are the members of the
    /// enum.
    ///
    /// This may be useful if you are not sure if the item exists in the map, but still want to
    /// panic if an actual error occurs.
    ///
    /// This will be automatically be updated in the case that `GetError` is changed to add more
    /// not found variants
    ///
    /// For example:
    /// ```
    /// use nestmap::GetError;
    ///
    /// let output = GetError::EmptyPath;
    ///
    /// assert!(output.is_actual_error());
    ///
    /// let output = GetError::ItemNotFound;
    ///
    /// assert!(!output.is_actual_error());
    /// ```
    pub fn is_actual_error(&self) -> bool {
        !matches!(*self, Self::ItemNotFound | Self::NonExistentPathItem)
    }
}

/// An extension trait which allows you to map the output of [`NestMap::get_path`] and [`NestMap::get_path_mut`] into options
pub trait GetResultExt<T> {
    /// Converts the output of [`NestMap::get_path`] and [`NestMap::get_path_mut`] into a [`Result`] containing an [`Option`]
    ///
    /// # Examples
    /// ```rust
    /// use nestmap::{GetError, GetResultExt};
    /// use nestmap::samples::SampleValue;
    ///
    /// let not_found: Result<SampleValue, GetError> = Err(GetError::ItemNotFound);
    ///
    /// assert_eq!(not_found.into_option().unwrap(), None);
    ///
    /// let real_error: Result<SampleValue, GetError> = Err(GetError::EmptyPath);
    ///
    /// assert_eq!(real_error.into_option(), Err(GetError::EmptyPath));
    ///
    /// let good_output: Result<SampleValue, GetError> = Ok(SampleValue::Int(16));
    ///
    /// assert_eq!(good_output.into_option().unwrap(), Some(SampleValue::Int(16)));
    /// ```
    fn into_option(self) -> Result<Option<T>, GetError>;
}

impl<T> GetResultExt<T> for Result<T, GetError> {
    fn into_option(self) -> Result<Option<T>, GetError> {
        match self {
            Ok(item) => Ok(Some(item)),
            Err(e) => {
                if e.is_actual_error() {
                    Err(e)
                } else {
                    Ok(None)
                }
            }
        }
    }
}

/// Defines a value that can be used in a [`NestMap`]
/// The main properties are that the item has a 'map' variant / field,
/// allowing it to be turned into a map for path explorations and that a
/// blank map can be made from the item for path building
pub trait NestableValue<K, V>
where
    // Ah yes, to implement the trait you must have implemented the trait
    // Of course I know it doesn't work like that but it is still funny
    V: NestableValue<K, V> + Debug + Clone,
    K: Eq + std::hash::Hash + Clone + Debug + 'static,
{
    /// The error returned if the value can't be made into a map reference
    type IntoMapError: Debug;

    /// The error returned if the value can't be made into a mutable map reference
    type IntoMapMutError: Debug;

    /// Generates a value which contains an empty map. The map must be a [`NestMap`] containing 0 keys
    fn empty_map() -> Self;

    /// Converts a mutable reference to the value into a mutable reference to a `NestMap`
    fn as_map_mut(&mut self) -> Result<&mut NestMap<K, V>, Self::IntoMapMutError>;

    /// Converts a reference to the value into a reference to a `NestedHashMap`
    fn as_map(&self) -> Result<&NestMap<K, V>, Self::IntoMapError>;
}

/// A HashMap which supports filepath like nesting.
///
/// See the crate root for details about using this structure or see documentation of internal methods for usage
///
/// ### How it works
/// It is essentially a wrapper around a hashmap which provides methods for interaction. It also uses rust's trait model
/// to ensure as few panics as possible. Most of the benefits of this library come from the internal methods, which use
/// recursive searching to insert and find items throughout the tree with filepath style paths without much effort for the
/// user.
///
/// ### Length
/// Unlike a regular HashMap, a custom length system has to be used so that users can know how many keys are in the map.
/// The system is incremented every time a new key is added. If the key is a map, the length of that map will be added.
/// This can sometimes be wrong though, if the length of the map was wrong or if the map was converted into a plain hashmap.
/// Therefore there is a `recalculate_len()` function which enable a recount, use this if you need a guarantee the length is
/// correct for the map
#[derive(PartialEq, Clone, Default)]
pub struct NestMap<K, V>
where
    V: NestableValue<K, V> + Debug + Clone,
    K: Eq + std::hash::Hash + Clone + Debug + 'static,
{
    inner: HashMap<K, V>,
    len: usize,
}
impl<K, V> NestMap<K, V>
where
    V: NestableValue<K, V> + Debug + Clone,
    K: Eq + std::hash::Hash + Clone + Debug + 'static,
{
    // ============
    // INNER ACCESS
    // ============

    /// Gets the internal hashmap as an immutable reference, useful for more complex operations
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue, Key};
    /// # use std::collections::HashMap;
    ///
    /// let map = SampleMap::new();
    /// assert_eq!(map.get_inner(), &HashMap::<Key, SampleValue>::new());
    /// ```
    pub fn get_inner(&self) -> &HashMap<K, V> {
        &self.inner
    }

    /// Get the internal hashmap as a mutable reference, useful for more complex operations
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue, Key};
    /// # use std::collections::HashMap;
    ///
    /// let mut map = SampleMap::new();
    /// assert_eq!(map.get_inner_mut(), &mut HashMap::<Key, SampleValue>::new());
    /// ```
    pub fn get_inner_mut(&mut self) -> &mut HashMap<K, V> {
        &mut self.inner
    }

    /// Converts the [`NestMap`] into a plain [`HashMap`], consuming itself in the process
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue, Key};
    /// # use std::collections::HashMap;
    ///
    /// let map = SampleMap::new();
    /// assert_eq!(map.into_inner(), HashMap::<Key, SampleValue>::new());
    /// ```
    pub fn into_inner(self) -> HashMap<K, V> {
        self.inner
    }

    /// Builds a [`NestMap`] from a plain [`HashMap`], consuming the hashmap in the process
    ///
    /// > Note that this captures only the basic length of the plain [`HashMap`], meaning a nested hashmap may not
    /// > have the right length. You can use [`Self::recalc_len()`] to make sure the length is correct after building the map
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, Key, SampleValue};
    /// # use std::collections::HashMap;
    ///
    /// let inner = HashMap::<Key, SampleValue>::new();
    ///
    /// assert_eq!(SampleMap::from_inner(inner), SampleMap::new());
    /// ```
    pub fn from_inner(inner: HashMap<K, V>) -> Self {
        let len = inner.len();
        Self { inner, len }
    }

    // ==============
    // INITIALISATION
    // ==============

    /// Initialises a new [`NestMap`] with an empty internal hashmap
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::SampleMap;
    ///
    /// let map = SampleMap::new();
    ///
    /// assert!(map.is_empty());
    /// ```
    pub fn new() -> Self {
        Self {
            inner: HashMap::new(),
            len: 0,
        }
    }

    // =============
    // BASIC HELPERS
    // =============

    /// Gets a reference to a value from the map using the provided key. This wraps the inner's `get` function.
    /// Will return `None` if the value is not present
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// let map_with_key = SampleMap::from([("key".into(), SampleValue::Int(32))]);
    /// let empty_map = SampleMap::new();
    ///
    /// assert_eq!(map_with_key.get(&String::from("key")), Some(&SampleValue::Int(32)));
    /// assert_eq!(empty_map.get(&String::from("key")), None);
    /// ```
    pub fn get(&self, k: &K) -> Option<&V> {
        self.inner.get(k)
    }

    /// Gets a mutable reference to a value from the map using the provided key. This wraps the inner's `get_mut` function.
    /// Will return `None` if the value is not present
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// let mut map_with_key = SampleMap::from([("key".into(), SampleValue::Int(32))]);
    /// let mut empty_map = SampleMap::new();
    ///
    /// assert_eq!(map_with_key.get_mut(&String::from("key")), Some(&mut SampleValue::Int(32)));
    /// assert_eq!(empty_map.get_mut(&String::from("key")), None);
    /// ```
    pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
        self.inner.get_mut(k)
    }

    /// Inserts a value into the map, registered with the provided key. This wraps the inner's `insert` function.
    /// Returns `None` if the value was not previously present and `Some(V)` if it was.
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// let mut map = SampleMap::new();
    /// map.insert("key".into(), SampleValue::Int(32));
    ///
    /// assert_eq!(map, SampleMap::from([("key".into(), SampleValue::Int(32))]));
    /// ```
    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
        match v.as_map() {
            Ok(map) => self.len += map.len,
            Err(_) => self.len += 1,
        };

        self.inner.insert(k, v)
    }

    /// Returns the amount of keys in the map. This **does not** wraps the inner's `len` function.
    ///
    /// This returns the value of the length counter, meaning it should track the total amount of items, not just in
    /// the top level map. If you wish to just get the length of the top map, use `map.get_inner().len()`
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    /// let map = SampleMap::from([("key".into(), SampleValue::Int(32))]);
    ///
    /// assert_eq!(map.len(), 1);
    ///
    /// let empty = SampleMap::new();
    /// assert_eq!(empty.len(), 0);
    /// ```
    pub fn len(&self) -> usize {
        self.len
    }

    /// Returns [`true`] if the map contains no **nodes**
    /// This will ignore nodes that are maps. Use `self.get_inner().is_empty()` to check if there are no nodes or maps
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    /// let map = SampleMap::from([("key".into(), SampleValue::Int(32))]);
    ///
    /// assert!(!map.is_empty());
    ///
    /// let empty = SampleMap::new();
    /// assert!(empty.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    // ============================
    // PATH INSERTION AND RETRIEVAL
    // ============================

    /// Inserts an item into the map. Works very similarly to [`Self::insert`] in that it returns either
    /// `None` if the item wasn't previously present or `Some(V)` if the item was present.
    ///
    /// This method CAN error, and will return an [`InsertError`] if it does.
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleValue, SampleMap};
    /// use std::collections::VecDeque;
    ///
    /// let mut map = SampleMap::new();
    /// println!("{:?}", map.len());
    /// map.insert_path(["uwu".into(), "nya".into()], SampleValue::Int(32));
    /// println!("{:?}", map.len());
    ///
    /// let mut expected = SampleMap::from([
    ///     ("uwu".into(), SampleValue::Map(SampleMap::from([
    ///         ("nya".into(), SampleValue::Int(32))
    ///     ])))
    /// ]);
    ///
    /// assert_eq!(map, expected);
    /// ```
    ///
    /// # Errors
    /// ```rust
    /// use nestmap::samples::{SampleValue, SampleMap};
    ///
    /// let mut map = SampleMap::new();
    /// assert_eq!(
    ///     map.insert_path([], SampleValue::Int(32)),
    ///     Err(nestmap::InsertError::EmptyPath)
    /// );
    ///
    /// map.insert("key".into(), SampleValue::Int(16));
    ///
    /// assert_eq!(
    ///     map.insert_path(["key".into(), "uwu".into()], SampleValue::Int(64)),
    ///     Err(nestmap::InsertError::PathItemNotATable)
    /// );
    /// ```
    pub fn insert_path(
        &mut self,
        path: impl Into<VecDeque<K>>,
        v: V,
    ) -> Result<Option<V>, InsertError> {
        self.insert_path_inner(path.into(), v)
    }

    fn insert_path_inner(&mut self, mut path: VecDeque<K>, v: V) -> Result<Option<V>, InsertError> {
        if path.is_empty() {
            Err(InsertError::EmptyPath)
        } else if path.len() == 1 {
            // SAFETY:
            // The path has been checked in the above if statement to make sure it is long enough
            Ok(self.insert(path.pop_front().unwrap(), v))
        } else {
            // SAFETY:
            // The path has been checked in the first if statement to make sure it is long enough
            let path_top = path.pop_front().unwrap();
            if let Some(outer_val) = self.get_mut(&path_top) {
                if let Ok(outer_table) = outer_val.as_map_mut() {
                    Ok(outer_table.insert_path_inner(path, v)?)
                } else {
                    // If this fails it means we can't make a table from the outer value
                    // This is most often because it is not a table
                    Err(InsertError::PathItemNotATable)
                }
            }
            // There is no table in the path so we must make one
            else {
                let mut new_val = V::empty_map();
                let new_val_ref = &mut new_val;

                // SAFETY:
                // This should never fail given we just made a new table
                // However this isn't the responsibility of the library so `expect` is used instead of `unwrap_unchecked`
                // This means UB can't happen if the user of the library makes a mistake
                let new_val_table = new_val_ref
                    .as_map_mut()
                    .expect("Couldn't build table from value, is Tablable written correctly?");
                new_val_table.insert_path_inner(path, v)?;
                Ok(self.insert(path_top, new_val))
            }
        }
    }

    /// Gets a reference to an item from the table using a path.
    /// Unlike the hashmap equivalent it will NOT return `None` if the item isn't present, it will instead return
    /// a [`GetError::ItemNotFound`] if the path is valid except for the end or a [`GetError::NonExistentPathItem`] if an
    /// item in the path does not exist
    ///
    /// See [`GetResultExt::into_option`] for details on managing the output
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// // A map containing one term "uwu" which contains another term "nya"
    /// let map = SampleMap::from([
    ///     ("uwu".into(), SampleValue::Map(SampleMap::from([
    ///         ("nya".into(), SampleValue::Int(32))
    ///     ])))
    /// ]);
    ///
    /// assert_eq!(map.get_path(["uwu".into(), "nya".into()]), Ok(&SampleValue::Int(32)));
    /// ```
    ///
    /// # Errors
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// let mut map = SampleMap::new();
    ///
    /// assert_eq!(
    ///     map.get_path([]),
    ///     Err(nestmap::GetError::EmptyPath)
    /// );
    ///
    /// map.insert("key".into(), SampleValue::Int(16));
    ///
    /// assert_eq!(
    ///     map.get_path(["notkey".into(), "uwu".into()]),
    ///     Err(nestmap::GetError::NonExistentPathItem)
    /// );
    ///
    /// assert_eq!(
    ///     map.get_path(["key".into(), "uwu".into()]),
    ///     Err(nestmap::GetError::CouldNotConvertToMap)
    /// );
    ///
    /// assert_eq!(
    ///     map.get_path(["notkey".into()]),
    ///     Err(nestmap::GetError::ItemNotFound)
    /// );
    /// ```
    pub fn get_path(&self, path: impl Into<VecDeque<K>>) -> Result<&V, GetError> {
        self.get_path_inner(path.into())
    }

    fn get_path_inner(&self, mut path: VecDeque<K>) -> Result<&V, GetError> {
        if path.is_empty() {
            Err(GetError::EmptyPath)
        } else if path.len() == 1 {
            // SAFETY:
            // The front of the path can be popped safely as we have checked the path length in the if statement
            match self.get(&path.pop_front().unwrap()) {
                Some(item) => Ok(item),
                None => Err(GetError::ItemNotFound),
            }
        } else {
            // SAFETY:
            // Same as above, the length of the path has already been checked
            if let Some(inner) = self.get(&path.pop_front().unwrap()) {
                if let Ok(new_val) = inner.as_map() {
                    Ok(new_val.get_path_inner(path)?)
                } else {
                    Err(GetError::CouldNotConvertToMap)
                }
            } else {
                Err(GetError::NonExistentPathItem)
            }
        }
    }

    /// Gets a mutable reference to an item from the table using a path.
    /// Unlike the hashmap equivalent it will NOT return `None` if the item isn't present, it will instead return
    /// a [`GetError::ItemNotFound`] if the path is valid except for the end or a [`GetError::NonExistentPathItem`] if an
    /// item in the path does not exist
    ///
    /// See [`GetResultExt::into_option`] for details on managing the output
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// // A map containing one term "uwu" which contains another term "nya"
    /// let mut map = SampleMap::from([
    ///     ("uwu".into(), SampleValue::Map(SampleMap::from([
    ///         ("nya".into(), SampleValue::Int(32))
    ///     ])))
    /// ]);
    ///
    /// assert_eq!(map.get_path_mut(["uwu".into(), "nya".into()]), Ok(&mut SampleValue::Int(32)));
    /// ```
    ///
    /// # Errors
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// let mut map = SampleMap::new();
    ///
    /// assert_eq!(
    ///     map.get_path_mut([]),
    ///     Err(nestmap::GetError::EmptyPath)
    /// );
    ///
    /// map.insert("key".into(), SampleValue::Int(16));
    ///
    /// assert_eq!(
    ///     map.get_path_mut(["notkey".into(), "uwu".into()]),
    ///     Err(nestmap::GetError::NonExistentPathItem)
    /// );
    ///
    /// assert_eq!(
    ///     map.get_path_mut(["key".into(), "uwu".into()]),
    ///     Err(nestmap::GetError::CouldNotConvertToMap)
    /// );
    ///
    /// assert_eq!(
    ///     map.get_path_mut(["notkey".into()]),
    ///     Err(nestmap::GetError::ItemNotFound)
    /// );
    /// ```
    pub fn get_path_mut(&mut self, path: impl Into<VecDeque<K>>) -> Result<&mut V, GetError> {
        self.get_path_mut_inner(path.into())
    }
    fn get_path_mut_inner(&mut self, mut path: VecDeque<K>) -> Result<&mut V, GetError> {
        if path.is_empty() {
            Err(GetError::EmptyPath)
        } else if path.len() == 1 {
            // SAFETY:
            // The front of the path can be popped safely as we have checked the path length in the if statement
            match self.get_mut(&path.pop_front().unwrap()) {
                Some(item) => Ok(item),
                None => Err(GetError::ItemNotFound),
            }
        } else {
            // SAFETY:
            // Same as above, the length of the path has already been checked
            if let Some(inner) = self.get_mut(&path.pop_front().unwrap()) {
                if let Ok(new_val) = inner.as_map_mut() {
                    Ok(new_val.get_path_mut_inner(path)?)
                } else {
                    Err(GetError::CouldNotConvertToMap)
                }
            } else {
                Err(GetError::NonExistentPathItem)
            }
        }
    }

    /// Updates the length by calling [`Self::calc_len`]
    pub fn recalc_len(&mut self) {
        self.len = self.calc_len();
    }

    /// Rebuilds the length value, manually checking each value within the structure. This garuntees a correct length but
    /// can be slow so should only be used when necessary
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    ///
    /// let mut map = SampleMap::from([("k1".into(), SampleValue::Int(1)), ("k2".into(), SampleValue::Int(2))]);
    /// assert_eq!(map.calc_len(), 2);
    ///
    /// map.insert_path(["uwu".into(), "nya".into(), ":3".into()], SampleValue::Int(3));
    /// assert_eq!(map.calc_len(), 3);
    ///
    /// let hash = map.into_inner();
    /// let from = SampleMap::from_inner(hash);
    ///
    /// assert_eq!(from.calc_len(), 3);
    /// ```
    pub fn calc_len(&self) -> usize {
        let mut len = 0;

        for (_, v) in self.get_inner().iter() {
            match v.as_map() {
                Ok(map) => len += map.calc_len(),
                Err(_) => len += 1,
            }
        }

        len
    }

    /// Flattens out the 2D map into a 1D map. This removes all values from the hashmap leaving the memory available.
    ///
    /// This variant truncates all paths into only the end key name, **discarding the rest**.
    /// If you want instead to have full paths in the output, considering using [`Self::flatten_preserve()`].
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    /// use std::collections::{HashMap, VecDeque};
    ///
    /// let mut map = SampleMap::new();
    ///
    /// map.insert("intkey".into(), SampleValue::Int(32));
    /// map.insert_path(VecDeque::from(["uwu".into(), "nya".into()]), SampleValue::Int(16));
    ///
    /// let mut target_output = HashMap::<String, SampleValue>::new();
    ///
    /// target_output.insert("intkey".into(), SampleValue::Int(32));
    /// target_output.insert("nya".into(), SampleValue::Int(16));
    ///
    /// let output = map.flatten_discard();
    ///
    /// assert_eq!(target_output, output);
    /// ```
    pub fn flatten_discard(&mut self) -> HashMap<K, V> {
        let mut outmap = HashMap::<K, V>::new();
        let inner = self.get_inner_mut();

        for (k, mut v) in inner.drain() {
            // Check if V is a table
            if let Ok(tab) = v.as_map_mut() {
                let flattened = tab.flatten_discard();
                for (k, v) in flattened {
                    outmap.insert(k, v);
                }
            } else {
                outmap.insert(k, v);
            }
        }

        outmap
    }

    /// Flattens out the 2D map into a 1D map. This removes all values from the hashmap leaving the memory available.
    ///
    /// This variant maintains the full tree paths.
    /// If you want instead to have only item paths in the output, considering using [`Self::flatten_discard()`].
    ///
    /// # Example
    /// ```rust
    /// use nestmap::samples::{SampleMap, SampleValue};
    /// use std::collections::{HashMap, VecDeque};
    ///
    /// let mut map = SampleMap::new();
    ///
    /// map.insert("intkey".into(), SampleValue::Int(32));
    /// map.insert_path(VecDeque::from(["uwu".into(), "nya".into()]), SampleValue::Int(16));
    ///
    /// let mut target_output = HashMap::<VecDeque<String>, SampleValue>::new();
    ///
    /// target_output.insert(VecDeque::from(["intkey".into()]), SampleValue::Int(32));
    /// target_output.insert(VecDeque::from(["uwu".into(), "nya".into()]), SampleValue::Int(16));
    ///
    /// let output = map.flatten_preserve();
    ///
    /// assert_eq!(target_output, output);
    /// ```
    pub fn flatten_preserve(&mut self) -> HashMap<VecDeque<K>, V> {
        self.flatten_preserve_inner(VecDeque::<K>::new())
    }

    // Because flatten_preserve needs a path for context, it wraps this inner function which needs a path
    fn flatten_preserve_inner(&mut self, path: VecDeque<K>) -> HashMap<VecDeque<K>, V> {
        let mut outmap = HashMap::<VecDeque<K>, V>::new();
        let inner = self.get_inner_mut();

        for (k, mut v) in inner.drain() {
            let mut item_path = path.clone();
            item_path.push_back(k);

            if let Ok(tab) = v.as_map_mut() {
                let flattened = tab.flatten_preserve_inner(item_path);
                for (k, v) in flattened {
                    outmap.insert(k, v);
                }
            } else {
                outmap.insert(item_path, v);
            }
        }

        outmap
    }
}
impl<K, V> std::fmt::Debug for NestMap<K, V>
where
    V: NestableValue<K, V> + Debug + Clone,
    K: Eq + std::hash::Hash + Clone + Debug + 'static,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}, len: {}", self.inner, self.len)
    }
}

impl<K, V, T> From<T> for NestMap<K, V>
where
    T: Into<HashMap<K, V>>,
    V: NestableValue<K, V> + Debug + Clone,
    K: Eq + std::hash::Hash + Clone + Debug + 'static,
{
    fn from(v: T) -> Self {
        NestMap::from_inner(v.into())
    }
}

/// This function checks if a [`NestableValue`] upholds its invariants.
/// It will panic if any of the invariants are not upheld.
/// The intention is for it to be used in unit tests to catch incorrect [`NestableValue`] implementations as early as possible
///
/// The type parameters `K` and `V` can be automatically inferred as seen in the example.
///
/// ### Example Usage
/// ```rust
/// // Assume we have already defined a NestableValue called `SampleValue`
/// use nestmap::{check_value, samples::SampleValue};
///
/// // This will panic if `SampleValue` doesn't meet the invariants of a NestableValue
/// check_value::<_, _, SampleValue>();
/// ```
///
/// ### Panics
/// ```should_panic
/// use nestmap::{check_value, samples::BadValue};
///
/// // This *will* panic because `BadValue` is purposefully written to be bad
/// check_value::<_, _, BadValue>();
/// ```
// I may expand this later to make it more useful
pub fn check_value<K, V, T>()
where
    V: NestableValue<K, V> + Debug + Clone,
    K: Eq + std::hash::Hash + Clone + Debug + 'static,
    T: NestableValue<K, V>,
{
    // Try to build a new value
    let mut m = T::empty_map();

    // Convert the empty value into a NestMap
    let map = m.as_map().unwrap();

    // Check that the empty value contains no keys
    assert!(map.is_empty());

    // Same but for mutables
    let _ = m.as_map_mut().unwrap();
}

/// A collection of sample values and definitions, mostly used for doc tests.
///
/// I wouldn't recommend using them in your code, and they **aren't** part of the public API,
/// but if you want to get a feel for the library, or see a good (and bad) implementation of
/// the library, these are here for that
#[allow(missing_docs, reason = "this is mostly an internal module")]
pub mod samples {
    use crate::NestMap;

    /// The standard `key` type for all the values, you don't have to set this to a type but
    /// I find it easier to manage this way
    pub type Key = String;

    /// A correctly implemented, albeit sparse, `Value` enum. Note how it contains simple variants (int and float).
    /// But also a `Map` variant. This is important as it is what allows this to be nested
    #[allow(missing_docs, reason = "Internals explained above")]
    #[derive(Debug, Clone, PartialEq)]
    pub enum SampleValue {
        Int(i32),
        Float(f32),
        Map(NestMap<Key, SampleValue>),
    }

    /// Type alias to make it more concise to just make a `Map` instead of messing with generics
    pub type SampleMap = NestMap<Key, SampleValue>;

    impl crate::NestableValue<Key, SampleValue> for SampleValue {
        type IntoMapMutError = &'static str;

        type IntoMapError = &'static str;

        fn empty_map() -> Self {
            Self::Map(NestMap::new())
        }

        fn as_map_mut(
            &mut self,
        ) -> Result<&mut NestMap<String, SampleValue>, Self::IntoMapMutError> {
            match self {
                Self::Map(m) => Ok(m),
                _ => Err("wrong value!"),
            }
        }

        fn as_map(&self) -> Result<&NestMap<String, SampleValue>, Self::IntoMapError> {
            match self {
                Self::Map(m) => Ok(m),
                _ => Err("wrong value!"),
            }
        }
    }

    pub type BadMap = NestMap<Key, BadValue>;

    // Hehehe badmapple
    #[allow(dead_code, reason = "funny")]
    type BadMapple = BadMap;

    // Define a purposefully bad implementation
    #[derive(Debug, Clone, PartialEq)]
    pub enum BadValue {
        Int(i32),
        Map(NestMap<Key, BadValue>),
    }

    impl crate::NestableValue<Key, BadValue> for BadValue {
        type IntoMapError = &'static str;
        type IntoMapMutError = &'static str;

        // This should give an empty map but this one has things in it
        fn empty_map() -> Self {
            let mut map = NestMap::<Key, BadValue>::new();
            map.insert("uwu".into(), BadValue::Int(32));
            Self::Map(map)
        }

        // This always fails
        fn as_map(&self) -> Result<&NestMap<Key, BadValue>, Self::IntoMapError> {
            match self {
                Self::Map(_) => Err("Right Type?"),
                _ => Err("Wrong Type!"),
            }
        }

        // This one is fine
        fn as_map_mut(&mut self) -> Result<&mut NestMap<Key, BadValue>, Self::IntoMapMutError> {
            match self {
                Self::Map(m) => Ok(m),
                _ => Err("Wrong Type!"),
            }
        }
    }
}

#[allow(unused_imports, reason = "These are used in doc tests")]
use samples::*;
