unique_id_lookup 0.2.11

use std::collections::HashMap;

/// An associative array specifically designed for integer keys.
///
/// # Examples
///
/// ```
/// use unique_id_lookup::UniqueIdLookup;
/// let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
/// lookup.insert(5, 'a');
/// assert_eq!(lookup.get(5).unwrap(), 'a');
/// ```
pub struct UniqueIdLookup<T> {
    buf: Vec<Option<T>>,
    offset: usize,
}

/// Will be retired soon.
pub struct UniqueIdLookupIterator<'a, T> {
    lookup: &'a UniqueIdLookup<T>,
    index: usize,
}

/// An iterator over the ID-value pairs visiting all occupied entries.
pub struct UniqueIdLookupIteratorOccupied<'a, T> {
    lookup: &'a UniqueIdLookup<T>,
    index: usize,
}

/// An iterator over the values (only occupied entries have a value).
pub struct UniqueIdLookupIteratorValues<'a, T> {
    lookup: &'a UniqueIdLookup<T>,
    index: usize,
}

/// An iterator over the IDs visiting all vacant entries.
pub struct UniqueIdLookupIteratorVacantIDs<'a, T> {
    lookup: &'a UniqueIdLookup<T>,
    index: usize,
}

impl<T> UniqueIdLookup<T> {
    const RESULT_NONE: Option<T> = None;

    /// Creates an empty `UniqueIdLookup`.
    ///
    /// The map is initially created with a capacity of 0, so it will not allocate until it
    /// is first inserted into.
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let mut lookup: UniqueIdLookup<i16> = UniqueIdLookup::new();
    /// ```
    pub const fn new() -> Self {
        UniqueIdLookup {
            buf: Vec::new(),
            offset: 0,
        }
    }

    /// Creates an empty `UniqueIdLookup` with at least the specified capacity.
    #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `with_capacity_and_offset()` instead.")]
    pub fn with_capacity(capacity: usize) -> Self {
        UniqueIdLookup::with_capacity_and_offset(capacity, 0)
    }

    /// Creates an empty `UniqueIdLookup` with at least the specified capacity and `offset` (the minimum ID).
    /// 
    /// If `capacity` and `offset` are set correctly this leads to more space efficiency and
    /// a constant time complexity of `insert()`.
    pub fn with_capacity_and_offset(capacity: usize, offset: usize) -> Self {
        UniqueIdLookup {
            buf: Vec::with_capacity(capacity),
            offset,
        }
    }

    /// Creates an empty `UniqueIdLookup` capacity to hold all values between min_id and max_id.
    /// 
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let min_id = 10;
    /// let max_id = 30;
    /// let lookup: UniqueIdLookup<i16> = UniqueIdLookup::with_min_max_id(min_id, max_id);
    /// assert_eq!(lookup.get_offset(), min_id);
    /// assert_eq!(lookup.capacity(), 1 + max_id - min_id);
    /// ```
    pub fn with_min_max_id<I: Into<usize> + Copy>(min_id: I, max_id: I) -> Self {
        let capacity = 1 + max_id.into() - min_id.into();
        UniqueIdLookup::with_capacity_and_offset(capacity, min_id.into())
    }

    #[deprecated(since = "0.2.10", note = "Will be removed in v0.3. Use `from()` instead.")]
    pub fn from_hash_map<I: Into<usize> + Ord + Copy>(map: HashMap<I, T>) -> Self {
        Self::from(map)
    }

    /// Inserts a ID-value pair into the map.
    /// 
    /// The method always inserts (replaces it the key is present already).
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
    /// lookup.insert(1, 'a');
    /// assert_eq!(lookup.get(1).unwrap(), 'a');
    /// lookup.insert(1, 'b');
    /// assert_eq!(lookup.get(1).unwrap(), 'b');
    /// ```
    ///
    /// # Complexity
    ///
    /// Can have constant time complexity if the map is pre-allocated using with_capacity_and_offset().
    pub fn insert(&mut self, id: usize, value: T) -> &mut T {
        if !self.buf.is_empty() {
            if id < self.offset {
                let nbr_prepend_elements = self.offset - id;
                for _i in 0..(nbr_prepend_elements - 1) {
                    self.buf.insert(0, None);
                }
                self.buf.insert(0, Some(value));
                self.offset = id;
                return self.buf[0].as_mut().unwrap();
            } else {
                let index = id - self.offset;
                if index < self.buf.len() {
                    self.buf[index] = Some(value);
                } else {
                    self.buf.resize_with(index + 1, || None);
                    self.buf[index] = Some(value);
                }
                return self.buf[index].as_mut().unwrap();
            }
        } else {
            // empty
            if self.capacity() == 0 || id < self.offset {
                self.offset = id;
                self.buf.push(Some(value));
                return self.buf[0].as_mut().unwrap();
            } else {
                let index = id - self.offset;
                self.buf.resize_with(index + 1, || None);
                self.buf[index] = Some(value);
                return self.buf[index].as_mut().unwrap();
            }
        }
    }


    /// Only inserts a ID-value pair into the map if not present, and does nothing otherwise.
    /// 
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let mut lookup: UniqueIdLookup<char> = UniqueIdLookup::new();
    /// lookup.insert_if_absent(1, 'a');
    /// assert_eq!(lookup.get(1).unwrap(), 'a');
    /// lookup.insert_if_absent(1, 'b');
    /// assert_eq!(lookup.get(1).unwrap(), 'a');
    /// ```
    ///
    /// # Complexity
    ///
    /// Can have constant time complexity if the map is pre-allocated using with_capacity_and_offset().
    pub fn insert_if_absent(&mut self, id: usize, value: T) -> &mut T {
        if self.contains_id(id) {
            return self.get_mut(id).unwrap();
        }
        return self.insert(id, value);
    }

    /// Returns `true` if the map contains a value for the specified ID.
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let mut lookup: UniqueIdLookup<i16> = UniqueIdLookup::new();
    /// lookup.insert(5, 17);
    /// assert_eq!(lookup.contains_id(0), false);
    /// assert_eq!(lookup.contains_id(5), true);
    /// ```
    #[inline]
    pub fn contains_id(&self, id: usize) -> bool {
        if id < self.offset {
            return false;
        }
        let index = id - self.offset;
        if index >= self.buf.len() {
            return false;
        }
        let value = &self.buf[index];
        value.is_some()
    }

    /// Returns a reference to an element or `None` if the ID was not found.
    ///
    /// # Panics
    ///
    /// Panics if `id` is out of bounds of the underlying vector.
    ///     
    /// # Examples
    ///
    /// ```
    /// use std::collections::HashMap;
    /// use unique_id_lookup::UniqueIdLookup;
    /// let hash_map: HashMap<u16, char> = HashMap::from([(5, 'c')]);
    /// let lookup = UniqueIdLookup::from_hash_map(hash_map);
    /// let c = lookup.get(5).unwrap();
    /// ```
    #[inline]
    pub fn get(&self, id: usize) -> &Option<T> {
        let index = id - self.offset;
        &self.buf[index]
    }

    /// Same as .get() but returns None outside of the bounds of the underlying vector.
    #[inline]
    pub fn get_or_none(&self, id: usize) -> &Option<T> {
        if id < self.offset {
            return &UniqueIdLookup::RESULT_NONE;
        }
        let index = id - self.offset;
        if index >= self.buf.len() {
            return &UniqueIdLookup::RESULT_NONE;
        }
        &self.buf[index]
    }

    /// Returns a mutable reference to an element or `None` if the ID was not found.    
    #[inline]
    pub fn get_mut(&mut self, id: usize) -> Option<&mut T> {
        let index = id - self.offset;
        self.buf.get_mut(index)?.as_mut()
    }

    /// Removes and returns the element with ID `id`. Essentially this is just marking the element as vacant.
    ///
    /// # Panics
    ///
    /// Panics if `id` is out of bounds of the underlying vector.
    ///
    /// # Complexity
    ///
    /// Constant time complexity
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::HashMap;
    /// use unique_id_lookup::UniqueIdLookup;
    /// let hash_map: HashMap<u16, char> = HashMap::from([(5, 'c'), (6, 'd')]);
    /// let mut lookup = UniqueIdLookup::from_hash_map(hash_map);
    /// assert_eq!(lookup.len_occupied(), 2);
    /// assert_eq!(lookup.remove(5).unwrap(), 'c');
    /// assert_eq!(lookup.len_occupied(), 1);
    /// assert!(lookup.get(5).is_none());
    /// ```
    #[inline]
    pub fn remove(&mut self, id: usize) -> Option<T> {
        let index = id - self.offset;
        let mut removed_value: Option<T> = None;
        std::mem::swap(&mut self.buf[index], &mut removed_value);
        removed_value
    }

    /// An iterator visiting all elements that have a value.
    #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `iter_occupied()` instead.")]
    pub fn iter(&self) -> UniqueIdLookupIterator<T> {
        UniqueIdLookupIterator {
            lookup: self,
            index: 0,
        }
    }

    /// Returns an iterator over the ID-value pairs visiting all occupied entries.
    /// 
    /// The iterator element type is the tuple (usize, &'a T)`.
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let arr: [(usize, char); 3] = [(5, 'c'), (6, 'd'), (8, 'f')];
    /// let lookup = UniqueIdLookup::from(arr);
    /// for (id, payload) in lookup.iter_occupied() {
    ///     let tup = (id, *payload);
    ///     assert!(arr.contains(&tup));            
    /// }
    /// ```
    pub fn iter_occupied(&self) -> UniqueIdLookupIteratorOccupied<T> {
        UniqueIdLookupIteratorOccupied {
            lookup: self,
            index: 0,
        }
    }

    /// Returns an iterator over the values (only occupied entries have a value).
    /// 
    /// The iterator element type is &'a T.
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let arr: [(usize, char); 3] = [(5, 'c'), (6, 'd'), (8, 'f')];
    /// let lookup = UniqueIdLookup::from(arr);
    /// for payload in lookup.values() {
    ///     assert!(['c', 'd', 'f'].contains(&payload));
    /// }
    /// ```    
    pub fn values(&self) -> UniqueIdLookupIteratorValues<T> {
        UniqueIdLookupIteratorValues {
            lookup: self,
            index: 0,
        }
    }

    /// An iterator visiting all vacant IDs.
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let arr: [(usize, char); 4] = [(5, 'c'), (6, 'd'), (8, 'f'), (10, 'h')];
    /// let lookup = UniqueIdLookup::from(arr);
    /// for id in lookup.iter_vacant_ids() {
    ///     assert_eq!([7, 9].contains(&id), true);
    /// }
    /// ```
    pub fn iter_vacant_ids(&self) -> UniqueIdLookupIteratorVacantIDs<T> {
        UniqueIdLookupIteratorVacantIDs {
            lookup: self,
            index: 0,
        }
    }

    /// Returns the offset to the underlying (dynamic) array. Mainly important for testing.
    #[inline]
    pub const fn get_offset(&self) -> usize {
        self.offset
    }

    #[inline]
    pub fn capacity(&self) -> usize {
        self.buf.capacity()
    }

    /// Returns the number of elements in the underlying (dynamic) array.
    #[inline]
    pub fn range_len(&self) -> usize {
        self.buf.len()
    }

    /// Returns the number of elements in the underlying (dynamic) array that actually have a value.
    #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `len_occupied()` instead  (just a name change).")]
    pub fn len(&self) -> usize {
        self.len_occupied()
    }

    /// Returns the number of occupied entries.
    ///
    /// # Complexity
    ///
    /// Takes linear (in `self.buf.len()`) time.
    pub fn len_occupied(&self) -> usize {
        self.buf.iter().filter(|payload| payload.is_some()).count()
    }

    /// Returns the fraction of accupied elements to all elements in the underlying vector.
    /// 
    /// UniqueIdLookup is a good choice if the density is close to 1.
    /// 
    /// ```
    /// use std::collections::HashMap;
    /// use unique_id_lookup::UniqueIdLookup;
    /// let hash_map: HashMap<u16, char> = HashMap::from([(1, 'a'), (4, 'd')]);
    /// let mut lookup = UniqueIdLookup::from_hash_map(hash_map);
    /// assert_eq!(lookup.occupation_density(), 0.5);
    /// ```
    pub fn occupation_density(&self) -> f64 {
        if self.buf.is_empty() {
            return f64::NAN;
        }
        self.len_occupied() as f64 / self.buf.len() as f64
    }    

    /// Returns false if at least one occupied entry exists.
    pub fn is_occupied_empty(&self) -> bool {
        for e in self.buf.iter() {
            if e.is_some() {
                return false;
            }
        }
        true
    }

    #[deprecated(since = "0.2.4", note = "Will be removed in v0.3. Use `is_occupied_empty()` instead (just a name change).")]
    pub fn is_empty(&self) -> bool {
        self.is_occupied_empty()
    }

    /// Returns a flatten vector with all occupied entires consuming the collection itself.
    /// 
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let arr: [(usize, char); 4] = [(5, 'c'), (6, 'd'), (8, 'f'), (10, 'h')];
    /// let lookup = UniqueIdLookup::from(arr);
    /// assert_eq!(lookup.into_occupied_vec(), vec!['c', 'd', 'f', 'h']);
    /// ```
    pub fn into_occupied_vec(self) -> Vec<T> {
        let nbr_occupied = self.len_occupied();
        let mut result = Vec::with_capacity(nbr_occupied);
        for item in self.buf.into_iter().flatten() {
            result.push(item);
        }
        result
    }    

    /// Shrinks the capacity of the underlying vector as much as possible. 
    /// 
    /// This includes removing vacant ememnts on both sides. Hence the offset might be changed.
    /// 
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    /// let mut lookup = UniqueIdLookup::with_capacity_and_offset(10, 5);
    /// assert_eq!(lookup.get_offset(), 5);
    /// lookup.insert(8, 8);
    /// lookup.insert(12, 12);
    /// assert_eq!(lookup.get_offset(), 5);
    /// 
    /// lookup.shrink_to_fit_and_trim_vacant();
    /// assert_eq!(lookup.len_occupied(), 2);
    /// assert_eq!(lookup.capacity(), 5);
    /// assert_eq!(lookup.get_offset(), 8);
    /// assert_eq!(lookup.get(8).unwrap(), 8);
    /// assert_eq!(lookup.get(12).unwrap(), 12);
    /// ```
    pub fn shrink_to_fit_and_trim_vacant(&mut self) {
        if let Some(index_r) = self.buf.iter().rposition(Option::is_some) {
            self.buf.truncate(index_r + 1);
            let mut new_offset = self.offset;
            while !self.buf.is_empty() && self.buf[0].is_none() {
                self.buf.remove(0);
                new_offset += 1;
            }
            self.offset = new_offset;
        } else {
            self.buf.clear();
            self.offset = 0;
        }
        self.buf.shrink_to_fit()        
    }

}


/// Implement From trait for HashMap conversion
/// Creates a `UniqueIdLookup<T>` from a `HashMap<I, T>`.
/// 
/// The ID-Type `I` has to implement the trait `Into<usize>`.
///
/// # Examples
///
/// ```
/// use std::collections::HashMap;
/// use unique_id_lookup::UniqueIdLookup;
/// let hash_map: HashMap<u16, char> = HashMap::from([(65, 'A'), (66, 'B')]);
/// let lookup_from = UniqueIdLookup::from(hash_map);
/// assert_eq!(lookup_from.get(66).unwrap(), 'B');
/// 
/// let hash_map: HashMap<u16, char> = HashMap::from([(67, 'C'), (68, 'D')]);
/// let lookup_into: UniqueIdLookup<char> = hash_map.into();
/// assert_eq!(lookup_into.get(68).unwrap(), 'D');
/// ```
impl<T, I> From<HashMap<I, T>> for UniqueIdLookup<T>
where 
    I: Into<usize> + Ord + Copy,
{
    fn from(hash_map: HashMap<I, T>) -> Self {
        if hash_map.is_empty() {
            return Self::new();
        }

        let (min_id, max_id) = hash_map.keys()
            .map(|&k| k.into())
            .fold((usize::MAX, 0), |(min, max), id| {
                (min.min(id), max.max(id))
            });

        let mut lookup = Self::with_min_max_id(min_id, max_id);
        for (id, value) in hash_map {
            lookup.insert(id.into(), value);
        }
        lookup
    }
}

impl<T> Default for UniqueIdLookup<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// Will be retired soon.
impl<'a, T> Iterator for UniqueIdLookupIterator<'a, T> {
    type Item = (usize, &'a Option<T>);

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.lookup.buf.len() {
            let payload = &self.lookup.buf[self.index];
            if payload.is_none() {
                self.index += 1;
                continue;
            }
            let id = self.index + self.lookup.offset;
            let result = Some((id, payload));
            self.index += 1;
            return result;
        }
        None
    }
}




impl<'a, T> Iterator for UniqueIdLookupIteratorValues<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.lookup.buf.len() {
            let payload = &self.lookup.buf[self.index];
            if payload.is_none() {
                self.index += 1;
                continue;
            }
            let result = Some(payload.as_ref().unwrap());
            self.index += 1;
            return result;
        }
        None
    }
}

impl<'a, T> Iterator for UniqueIdLookupIteratorOccupied<'a, T> {
    type Item = (usize, &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.lookup.buf.len() {
            let payload = &self.lookup.buf[self.index];
            if payload.is_none() {
                self.index += 1;
                continue;
            }
            let id = self.index + self.lookup.offset;
            let result = Some((id, payload.as_ref().unwrap()));
            self.index += 1;
            return result;
        }
        None
    }
}

impl<'a, T> Iterator for UniqueIdLookupIteratorVacantIDs<'a, T> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.lookup.buf.len() {
            let payload = &self.lookup.buf[self.index];
            if payload.is_some() {
                self.index += 1;
                continue;
            }
            let id = self.index + self.lookup.offset;
            let result = Some(id);
            self.index += 1;
            return result;
        }
        None
    }
}

impl<I, T, const N: usize> From<[(I, T); N]> for UniqueIdLookup<T>
where
    I: Into<usize> + Ord + Copy,
{
    /// Converts a array `[(I, T); N]` into a `UniqueIdLookup<T>`.
    ///
    /// # Examples
    ///
    /// ```
    /// use unique_id_lookup::UniqueIdLookup;
    ///
    /// let arr: [(usize, char); 3] = [(5, 'c'), (7, 'e'), (8, 'f')];
    /// let lookup = UniqueIdLookup::from(arr);
    /// assert_eq!(lookup.len_occupied(), 3);
    /// assert_eq!(lookup.get(5).unwrap(), 'c');
    /// ```    
    fn from(arr: [(I, T); N]) -> Self {
        if arr.is_empty() {
            return UniqueIdLookup::new();
        }
        let mut min_id = usize::MAX;
        let mut max_id = 0usize;
        for &(id, _) in &arr {
            let id_usize = id.into();
            min_id = min_id.min(id_usize);
            max_id = max_id.max(id_usize);
        }
        let mut lookup = UniqueIdLookup::with_min_max_id(min_id, max_id);
        for (id, v) in arr.into_iter() {
            lookup.insert(id.into(), v);
        }
        lookup
    }
}