dvcompute_utils 2.0.0

// Copyright (c) 2020-2022  David Sorokin <davsor@mail.ru>, based in Yoshkar-Ola, Russia
//
// 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/.

use std::rc::Rc;
use std::ops::Deref;

/// An immutable list.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum List<T> {

    /// The cons cell.
    Cons(T, Rc<List<T>>),

    /// An empty list.
    Nil
}

impl<T: Clone> Clone for List<T> {

    fn clone(&self) -> Self {
        match self {
            &List::Cons(ref head, ref tail) => {
                List::Cons(head.clone(), tail.clone())
            },
            &List::Nil => List::Nil
        }
    }
}

impl<T> List<T> {

    /// Test whether the list is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        match &self {
            &List::Cons(_, _) => false,
            &List::Nil => true
        }
    }

    /// Iterate the items of the list.
    #[inline]
    pub fn iter(&self) -> ListIterator<T> where T: Clone {
        ListIterator { list: self.clone() }
    }

    /// Dereference the argument as a list.
    #[inline]
    pub fn as_list(&self) -> Self where T: Clone {
        self.clone()
    }

    /// Return a singleton.
    #[inline]
    pub fn singleton(item: T) -> Self {
        List::Cons(item, Rc::new(List::Nil))
    }

    /// Remove the specified item from the list.
    pub fn remove(&self, item: T) -> Option<(T, Self)> where T: Clone + Eq {
        let mut first = List::Nil;
        let mut curr  = self;
        loop {
            match curr {
                &List::Nil => {
                    return None;
                },
                &List::Cons(ref head, ref tail) if item == *head => {
                    let update = first.append_rev(tail.clone());
                    return Some((head.clone(), update));
                },
                &List::Cons(ref head, ref tail) => {
                    first = List::Cons(head.clone(), Rc::new(first));
                    curr  = tail.deref();
                }
            }
        }
    }

    /// Remove an item satisfying the specified predicate.
    pub fn remove_by<F>(&self, predicate: F) -> Option<(T, Self)>
        where T: Clone,
              F: Fn(&T) -> bool
    {
        let mut first = List::Nil;
        let mut curr  = self;
        loop {
            match curr {
                &List::Nil => {
                    return None;
                },
                &List::Cons(ref head, ref tail) if predicate(head) => {
                    let update = first.append_rev(tail.clone());
                    return Some((head.clone(), update));
                },
                &List::Cons(ref head, ref tail) => {
                    first = List::Cons(head.clone(), Rc::new(first));
                    curr  = tail.deref();
                }
            }
        }
    }

    /// Test whether there is an item satisfying the specified predicate.
    pub fn exists<F>(&self, predicate: F) -> bool
        where T: Clone,
              F: Fn(&T) -> bool
    {
        let mut curr = self;
        loop {
            match curr {
                &List::Nil => {
                    return false;
                },
                &List::Cons(ref head, _) if predicate(head) => {
                    return true;
                },
                &List::Cons(_, ref tail) => {
                    curr = tail.deref();
                }
            }
        }
    }

    /// Find an item satisfying the specified predicate.
    pub fn find<F>(&self, predicate: F) -> Option<T>
        where T: Clone,
              F: Fn(&T) -> bool
    {
        let mut curr = self;
        loop {
            match curr {
                &List::Nil => {
                    return None;
                },
                &List::Cons(ref head, _) if predicate(head) => {
                    return Some(head.clone());
                },
                &List::Cons(_, ref tail) => {
                    curr = tail.deref();
                }
            }
        }
    }

    /// Revert the items of the list.
    #[inline]
    pub fn reversed(&self) -> Self where T: Clone {
        self.append_rev(Rc::new(List::Nil))
    }

    /// Append the current list to another.
    #[inline]
    pub fn append(&self, other: Rc<Self>) -> Self where T: Clone {
        self.reversed().append_rev(other)
    }

    /// Append the reversed items to the list tail.
    fn append_rev(&self, tail: Rc<Self>) -> Self where T: Clone {
        let mut result = tail;
        let mut curr   = self;
        loop {
            match curr {
                &List::Nil => {
                    return (*result).clone();
                },
                &List::Cons(ref head, ref tail) => {
                    curr = tail.deref();
                    let list = List::Cons(head.clone(), result);
                    match curr {
                        &List::Nil => {
                            return list;
                        },
                        &List::Cons(_, _) => {
                            result = Rc::new(list);
                        }
                    }
                }
            }
        }
    }
}

impl<T: Clone> IntoIterator for List<T> {

    type Item = T;
    type IntoIter = ListIterator<T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        ListIterator { list: self.clone() }
    }
}

/// Specifies the list iterator.
pub struct ListIterator<T> {

    /// The list to be iterated.
    list: List<T>
}

impl<T: Clone> Iterator for ListIterator<T> {

    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let (item, tail) = {
            match &self.list {
                &List::Cons(ref head, ref tail) => {
                    let item = head.clone();
                    let tail = tail.as_list();
                    (Some(item), tail)
                },
                &List::Nil => {
                    (None, List::Nil)
                }
            }
        };
        self.list = tail;
        item
    }
}