ielr 0.1.1

/*
 * Copyright 2022 Arnaud Golfouse
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

//! Defines the [`Visit`] structure.

use std::{collections::HashSet, hash::BuildHasher};

/// Uniquely visit elements.
///
/// You may add elements to the visit (using [`Visit::insert`]), and retrieve the
/// next element to visit (using [`Visit::pop`]).
#[derive(Clone, Debug, Default)]
pub struct Visit<T, S = super::Hasher> {
    /// All the elements schelduled to be visited in the lifetime of the visit.
    visited: HashSet<T, S>,
    /// All the elements currently waiting to be visited.
    ///
    /// All of those are included in [`Self::visited`].
    to_visit: Vec<T>,
}

impl<T, S> Visit<T, S>
where
    S: BuildHasher + Default,
    T: Clone + Eq + std::hash::Hash,
{
    /// Create a new `Visit` with no items to visit, nor visited.
    pub fn new() -> Self {
        Self {
            visited: HashSet::<_, S>::default(),
            to_visit: Vec::new(),
        }
    }

    /// Returns `true` if the item was not already in the list of items to visit.
    ///
    /// # Example
    /// ```compile_fail
    /// # use ielr::structures::Visit;
    /// let mut visit = Visit::new();
    /// assert!(visit.insert(0i32));
    /// assert!(visit.insert(1i32));
    /// assert!(!visit.insert(0i32));
    /// assert!(!visit.insert(1i32));
    /// ```
    pub fn insert(&mut self, item: T) -> bool {
        let visit = self.visited.insert(item.clone());
        if visit {
            self.to_visit.push(item)
        }
        visit
    }

    /// Get the next item to visit.
    ///
    /// # Example
    /// ```compile_fail
    /// # use ielr::structures::Visit;
    /// let mut visit = Visit::new();
    /// visit.insert(5i32);
    /// assert_eq!(visit.pop(), Some(5i32));
    /// ```
    pub fn pop(&mut self) -> Option<T> {
        self.to_visit.pop()
    }
}

impl<T, S> IntoIterator for Visit<T, S>
where
    S: BuildHasher,
    T: Eq + std::hash::Hash,
{
    type Item = T;

    type IntoIter = <HashSet<T, S> as IntoIterator>::IntoIter;

    /// Get all visited items.
    ///
    /// Visited that were inserted but not visited are not included.
    fn into_iter(mut self) -> Self::IntoIter {
        for item in self.to_visit {
            self.visited.remove(&item);
        }
        self.visited.into_iter()
    }
}

/// Similar to [`Visit`], but allows visiting an item multiple times.
pub struct ReVisit<T, S = super::Hasher> {
    /// Items _currently_ in [`Self::to_visit`].
    visiting: HashSet<T, S>,
    to_visit: Vec<T>,
}

impl<T, S> ReVisit<T, S>
where
    S: BuildHasher + Default,
    T: Clone + Eq + std::hash::Hash,
{
    /// Create a new `ReVisit` with no items to visit, nor visited.
    pub fn new() -> Self {
        Self {
            visiting: HashSet::default(),
            to_visit: Vec::new(),
        }
    }

    /// Returns `true` if the item was not already in the list of items to visit.
    pub fn insert(&mut self, item: T) -> bool {
        let result = self.visiting.insert(item.clone());
        if result {
            self.to_visit.push(item);
        }
        result
    }

    /// Get the next item to visit.
    pub fn pop(&mut self) -> Option<T> {
        let item = self.to_visit.pop()?;
        self.visiting.remove(&item);
        Some(item)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{structures::Set, test_common::collect};

    #[test]
    fn visit() {
        let mut visit: Visit<i32> = Visit::new();

        assert!(visit.insert(0));
        assert!(visit.insert(1));
        assert!(visit.insert(2));
        assert!(!visit.insert(1));
        assert!(!visit.insert(2));

        assert_eq!(visit.pop(), Some(2));
        assert!(!visit.insert(2));
        assert_eq!(visit.pop(), Some(1));
        assert!(!visit.insert(2));

        assert!(visit.insert(3));
        assert_eq!(visit.pop(), Some(3));
        assert_eq!(visit.pop(), Some(0));

        assert!(visit.insert(4));

        assert_eq!(
            visit.into_iter().collect::<Set<i32>>(),
            collect(&[0, 1, 2, 3])
        );
    }

    #[test]
    fn re_visit() {
        let mut visit: ReVisit<i32> = ReVisit::new();

        assert!(visit.insert(0));
        assert!(visit.insert(1));
        assert!(visit.insert(2));
        assert!(!visit.insert(1));
        assert!(!visit.insert(2));

        assert_eq!(visit.pop(), Some(2));
        assert!(visit.insert(2));
        assert_eq!(visit.pop(), Some(2));
        assert!(!visit.insert(1));

        assert!(visit.insert(3));
        assert_eq!(visit.pop(), Some(3));
        assert_eq!(visit.pop(), Some(1));
        assert_eq!(visit.pop(), Some(0));
    }
}