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)]
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)]
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
}
}
#[derive(Clone, Debug)]
pub struct RcList<T> {
first: Link<Node<T>>,
}
impl<T> RcList<T> {
pub fn new() -> RcList<T> {
RcList { first: Link::None }
}
}
impl<T : Clone> RcList<T> {
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,
}
))
}
}
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(),
}
))
}
}
pub fn iter(&self) -> RcListIter<T> {
RcListIter { iter: self.first.clone() }
}
}
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;