rclist/
lib.rs

1#![feature(core)]
2#![feature(alloc)]
3#![allow(unused_features)]
4
5//! `RcList` is read-only, append only list (log), that can share common tail (history) with other `RcList`.
6//!
7//! This data structure supports:
8//!
9//! * read-only appending which creates new RcList consisting of:
10//!   (head, rest), where head is a new element and rest can be
11//!   potentially shared with other `RcList`-s
12//! * Strong and Weak links, allowing dynamic pruning,
13//! * Iteration from the beginning (newest elements) to end (oldest elements).
14//!
15
16use std::rc::{Rc, Weak};
17use std::iter::Iterator;
18use std::ops::Deref;
19
20#[derive(Clone, Debug)]
21enum Link<T> {
22    Weak(Weak<T>),
23    Strong(Rc<T>),
24    None
25}
26
27impl<T> Link<T> {
28    fn downgrade(&self) -> Link<T> {
29        match self {
30            &Link::Weak(ref x) => Link::Weak(x.clone()),
31            &Link::Strong(ref x) => Link::Weak(x.downgrade()),
32            &Link::None => Link::None
33        }
34    }
35}
36
37#[derive(Clone, Debug)]
38/// RcList Node
39pub struct Node<T> {
40    value: T,
41    next: Link<Node<T>>,
42}
43
44impl<T> Deref for Node<T> {
45    type Target = T;
46    fn deref(&self) -> &T {
47        &self.value
48    }
49}
50
51/// RcList Head
52#[derive(Clone, Debug)]
53pub struct RcList<T> {
54    first: Link<Node<T>>,
55}
56
57impl<T> RcList<T> {
58
59    /// Create new `RcList` with no entries
60    pub fn new() -> RcList<T> {
61        RcList { first: Link::None }
62    }
63
64}
65
66impl<T : Clone> RcList<T> {
67    /// Create new `RcList` from value and existing `RcList`
68    pub fn new_append(value : T, rest : &RcList<T>) -> RcList<T> {
69        let first = rest.first.clone();
70        RcList {
71            first: Link::Strong(Rc::new(
72                           Node {
73                               value: value,
74                               next: first,
75                           }
76            ))
77        }
78    }
79
80    /// Create new `RcList` from value and weakly referenced existing `RcList`
81    ///
82    /// Weak-reference is useful for limiting memory consumption. After no other `RcList` is
83    /// holding a part of the `RcList` with non-weak reference, it will be freed.
84    pub fn new_append_weak(value : T, rest : &RcList<T>) -> RcList<T> {
85        let first = rest.first.clone();
86        RcList {
87            first: Link::Strong(Rc::new(
88                           Node {
89                               value: value,
90                               next: first.downgrade(),
91                           }
92            ))
93        }
94    }
95
96    /// Get iterator over `RcList`
97    pub fn iter(&self) -> RcListIter<T> {
98        RcListIter { iter: self.first.clone() }
99    }
100}
101
102/// Iterator over RcList
103pub struct RcListIter<T: 'static> {
104    iter : Link<Node<T>>,
105}
106
107impl<T : Clone> Iterator for RcListIter< T> {
108
109    type Item = Rc<Node<T>>;
110
111    #[inline]
112    fn next(&mut self) -> Option<Rc<Node<T>>> {
113        let ret = match self.iter {
114            Link::None => None,
115            Link::Strong(ref rc) => Some(rc.clone()),
116            Link::Weak(ref weak) => weak.upgrade(),
117        };
118
119        self.iter = match ret {
120            Some(ref ret) => ret.next.clone(),
121            None => Link::None
122        };
123
124        ret
125    }
126}
127
128#[cfg(test)]
129mod test;
130
rclist/lib.rs

rclist/
lib.rs
