1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#![feature(core)]
#![feature(alloc)]
#![allow(unused_features)]

//! `RcList` is read-only, append only list (log), that can share common tail (history) with other `RcList`.
//!
//! This data structure supports:
//!
//! * read-only appending which creates new RcList consisting of:
//!   (head, rest), where head is a new element and rest can be
//!   potentially shared with other `RcList`-s
//! * Strong and Weak links, allowing dynamic pruning,
//! * Iteration from the beginning (newest elements) to end (oldest elements).
//!

use std::rc::{Rc, Weak};
use std::iter::Iterator;
use std::ops::Deref;

#[derive(Clone, Debug)]
enum Link<T> {
    Weak(Weak<T>),
    Strong(Rc<T>),
    None
}

impl<T> Link<T> {
    fn downgrade(&self) -> Link<T> {
        match self {
            &Link::Weak(ref x) => Link::Weak(x.clone()),
            &Link::Strong(ref x) => Link::Weak(x.downgrade()),
            &Link::None => Link::None
        }
    }
}

#[derive(Clone, Debug)]
/// RcList Node
pub struct Node<T> {
    value: T,
    next: Link<Node<T>>,
}

impl<T> Deref for Node<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.value
    }
}

/// RcList Head
#[derive(Clone, Debug)]
pub struct RcList<T> {
    first: Link<Node<T>>,
}

impl<T> RcList<T> {

    /// Create new `RcList` with no entries
    pub fn new() -> RcList<T> {
        RcList { first: Link::None }
    }

}

impl<T : Clone> RcList<T> {
    /// Create new `RcList` from value and existing `RcList`
    pub fn new_append(value : T, rest : &RcList<T>) -> RcList<T> {
        let first = rest.first.clone();
        RcList {
            first: Link::Strong(Rc::new(
                           Node {
                               value: value,
                               next: first,
                           }
            ))
        }
    }

    /// Create new `RcList` from value and weakly referenced existing `RcList`
    ///
    /// Weak-reference is useful for limiting memory consumption. After no other `RcList` is
    /// holding a part of the `RcList` with non-weak reference, it will be freed.
    pub fn new_append_weak(value : T, rest : &RcList<T>) -> RcList<T> {
        let first = rest.first.clone();
        RcList {
            first: Link::Strong(Rc::new(
                           Node {
                               value: value,
                               next: first.downgrade(),
                           }
            ))
        }
    }

    /// Get iterator over `RcList`
    pub fn iter(&self) -> RcListIter<T> {
        RcListIter { iter: self.first.clone() }
    }
}

/// Iterator over RcList
pub struct RcListIter<T: 'static> {
    iter : Link<Node<T>>,
}

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

    type Item = Rc<Node<T>>;

    #[inline]
    fn next(&mut self) -> Option<Rc<Node<T>>> {
        let ret = match self.iter {
            Link::None => None,
            Link::Strong(ref rc) => Some(rc.clone()),
            Link::Weak(ref weak) => weak.upgrade(),
        };

        self.iter = match ret {
            Some(ref ret) => ret.next.clone(),
            None => Link::None
        };

        ret
    }
}

#[cfg(test)]
mod test;