1
use std::cell::RefCell;
2
use std::rc::Rc;
3
type NodeRef<T> = Rc<RefCell<Node<T>>>;
4
#[derive(Clone)]
5
struct Node<T: Clone> {
6
    data: Option<T>,
7
    next: Option<NodeRef<T>>,
8
    previous: Option<NodeRef<T>>,
9
}
10
struct LinkedList<T: Clone> {
11
    head: Option<NodeRef<T>>,
12
    tail: Option<NodeRef<T>>,
13
    pub size: usize,
14
}
15
impl<T: Clone> LinkedList<T> {
16
    fn get_ptr_at(&self, index: usize) -> NodeRef<T> {
17
        if index < (self.size / 2) as usize {
18
            let head = self.head.clone().unwrap().clone();
19
            let mut ptr = head;
20
            for i in 0..index+1 {
21
                let next = ptr.borrow().next.clone().unwrap();
22
                ptr = next;
23
            }
24
            ptr
25
        } else {
26
            let tail = self.tail.clone().unwrap().clone();
27
            let mut ptr = tail;
28
            for i in 0..self.size - index {
29
                let prev = ptr.borrow().previous.clone().unwrap();
30
                ptr = prev;
31
            }
32
            ptr
33
        }
34
    }
35
    pub fn is_empty(&self) -> bool {
36
        self.head
37
            .clone()
38
            .unwrap()
39
            .borrow()
40
            .next
41
            .clone()
42
            .unwrap()
43
            .borrow()
44
            .next
45
            .is_none()
46
            && self
47
                .tail
48
                .clone()
49
                .unwrap()
50
                .borrow()
51
                .previous
52
                .clone()
53
                .unwrap()
54
                .borrow()
55
                .previous
56
                .is_none()
57
    }
58
    fn insert_first(&mut self, value: T) {
59
        let new_node = Rc::new(RefCell::new(Node {
60
            data: Some(value),
61
            next: None,
62
            previous: None,
63
        }));
64
        let new_head = self.head.clone().unwrap();
65
        let new_tail = self.tail.clone().unwrap();
66
        new_head.borrow_mut().next = Some(Rc::clone(&new_node));
67
        new_node.borrow_mut().previous = Some(Rc::clone(&new_head));
68
        new_tail.borrow_mut().previous = Some(Rc::clone(&new_node));
69
        new_node.borrow_mut().next = Some(Rc::clone(&new_tail));
70
        self.tail = Some(new_tail);
71
        self.head = Some(new_head);
72
    }
73
    pub fn new() -> Self {
74
        let head = Rc::new(RefCell::new(Node {
75
            data: None,
76
            next: None,
77
            previous: None,
78
        }));
79

80
        let tail = Rc::new(RefCell::new(Node {
81
            data: None,
82
            next: None,
83
            previous: Some(Rc::clone(&head)),
84
        }));
85

86
        head.borrow_mut().next = Some(Rc::clone(&tail));
87

88
        Self {
89
            head: Some(head),
90
            tail: Some(tail),
91
            size: 0,
92
        }
93
    }
94

95
    pub fn push_back(&mut self, value: T) {
96
        if !self.is_empty() {
97
            let new_node = Rc::new(RefCell::new(Node {
98
                data: Some(value),
99
                next: None,
100
                previous: None,
101
            }));
102
            let tail = &self.tail.clone().unwrap();
103
            let mut new_tail = tail.clone();
104
            let prev = new_tail.borrow().previous.clone().unwrap();
105
            prev.borrow_mut().next = Some(Rc::clone(&new_node));
106
            new_node.borrow_mut().previous = Some(prev);
107
            new_node.borrow_mut().next = Some(new_tail.clone());
108
            new_tail.borrow_mut().previous = Some(Rc::clone(&new_node));
109
            self.tail = Some(new_tail);
110
        } else {
111
            self.insert_first(value);
112
        }
113
        self.size += 1;
114
    }
115
    pub fn push_front(&mut self, value: T) {
116
        if !self.is_empty() {
117
            let new_node = Rc::new(RefCell::new(Node {
118
                data: Some(value),
119
                next: None,
120
                previous: None,
121
            }));
122
            let head = &self.head.clone().unwrap();
123
            let mut new_head = head.clone();
124
            let next = new_head.borrow().next.clone().unwrap();
125
            next.borrow_mut().next = Some(Rc::clone(&new_node));
126
            new_head.borrow_mut().next = Some(Rc::clone(&new_node));
127
            new_node.borrow_mut().next = Some(next);
128
            new_node.borrow_mut().previous = Some(new_head.clone());
129
            self.head = Some(new_head);
130
        } else {
131
            self.insert_first(value);
132
        }
133
        self.size += 1;
134
    }
135
    pub fn get(&self, index: usize) -> Result<Option<T>, String> {
136
        return if index >= self.size as usize || index < 0 {
137
            Err("".to_string())
138
        } else {
139
            let ptr = self.get_ptr_at(index);
140
            let value = ptr.borrow().clone().data;
141
            Ok(value)
142
        };
143
    }
144
    pub fn insert_at(&mut self,value:T,index:usize)->Result<(),String>{
145
        if self.size==0{
146
            self.push_back(value);
147
            return Ok(())
148
        }
149
        if self.size == index{
150
            self.push_back(value);
151
            return Ok(())
152
        }
153
        if self.size == 0{
154
            self.push_front(value);
155
            return Ok(())
156
        }
157
        let ptr=self.get_ptr_at(index);
158
        let new_previous=ptr.borrow().previous.clone().unwrap();
159
        let new_node=Rc::new(RefCell::new(Node{
160
            data: Some(value),
161
            next: Some(ptr.clone()),
162
            previous: Some(new_previous.clone()),
163
        }));
164
        ptr.borrow_mut().previous=Some(Rc::clone(&new_node));
165
        new_previous.borrow_mut().next=Some(Rc::clone(&new_node));
166
        self.size+=1;
167
        Ok(())
168
    }
169
    pub fn remove_at(&mut self, index: usize) -> Result<Option<T>, String> {
170
        return if index >= self.size as usize || index < 0 {
171
            Err("".to_string())
172
        } else {
173
            let ptr = self.get_ptr_at(index);
174
            let new_previous = ptr.borrow().clone().previous.unwrap();
175
            let new_next = ptr.borrow().clone().next.unwrap();
176
            new_previous.borrow_mut().next = Some(new_next.clone());
177
            new_next.borrow_mut().previous = Some(new_previous.clone());
178
            ptr.borrow().previous.clone().unwrap().borrow_mut().next = Some(new_next.clone());
179
            ptr.borrow().next.clone().unwrap().borrow_mut().previous = Some(new_previous.clone());
180
            let value = ptr.borrow().clone().data;
181
            self.size -= 1;
182
            Ok(value)
183
        };
184
    }
185
}
186
fn main() {
187
    let mut list_i32: LinkedList<i32> = LinkedList::new();
188
    for i in 0..100 {
189
        list_i32.push_back(i);
190
    }
191
    list_i32.insert_at(-1, 1).expect("TODO: panic message");
192
    list_i32.insert_at(-1, 0).expect("TODO: panic message");
193
    list_i32.insert_at(-1, list_i32.size-1).expect("TODO: panic message");
194
    list_i32.insert_at(-1, list_i32.size).expect("TODO: panic message");
195
    list_i32.insert_at(-1, 50).expect("TODO: panic message");
196
    for i in 0..list_i32.size{
197
        if let Ok(Some(v))= list_i32.get(i){
198
            println!("{}",v);
199
        }
200
    }
201
    return;
202
}