/
11-8.cpp
203 lines (169 loc) · 5.16 KB
/
11-8.cpp
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include <iostream>
#include <memory>
#include <algorithm>
#include <vector>
using std::allocator;
using std::cout;
using std::endl;
using std::max;
using std::uninitialized_copy;
using std::ptrdiff_t;
using std::copy;
using std::vector;
template <class T>
class Node;
template <class T>
class LList {
public:
typedef Node<T> value_type;
typedef Node<T>& reference;
typedef const Node<T>& const_reference;
typedef int size_type;
class iterator {
public:
typedef iterator self_type;
typedef Node<T>& reference;
typedef Node<T>* pointer;
typedef std::forward_iterator_tag iterator_category;
typedef int difference_type;
typedef int size_type;
typedef Node<T> value_type;
iterator() { }
iterator(pointer ptr) : ptr_(ptr) { }
self_type operator++() { self_type it = *this; ptr_ = ptr_->next; return it; }
self_type operator+(int junk) { self_type it = *this;
for (int i = 1; i != junk; i++) {
ptr_ = ptr_->next;
}
return it; }
self_type operator-(int junk) { self_type it = *this;
for (int i = junk; i != 0; i--) {
ptr_ = ptr_->previous;
}
return it; }
self_type operator++(int junk) { ptr_ = ptr_->next ; return *this; }
self_type operator--() { self_type it = *this; ptr_ = ptr_->previous; return it; }
self_type operator--(int junk) { ptr_ = ptr_->previous; return *this; }
reference operator*() { return *ptr_; }
pointer operator->() { return ptr_; }
bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
bool operator!=(const self_type& rhs) { return ptr_ != rhs.ptr_; }
pointer getPtr() { return ptr_; }
private:
pointer ptr_;
};
LList() { create(); } // default constructor
LList(LList& ll) { create(ll.begin(), ll.end()); } // copy constructor
//Vec& operator=(const Vec&);
//~Vec() {uncreate(); }
void push_back(const T& t) {
iterator lastIter;
iterator nextIter;
// handle assigning start if first element
if (finish == 0) {
Node<T>* st = alloc.allocate(1);
iterator start_(st);
start = start_;
start->object = t;
start->previous = 0;
start->next = 0;
lastIter = start;
}
else {
finish->object = t;
lastIter = finish;
}
// create empty final element
Node<T>* fn = alloc.allocate(1);
iterator finish_(fn);
finish = finish_;
finish->previous = lastIter.getPtr();
lastIter->next = finish.getPtr();
finish->next = 0;
}
iterator begin() { return start; }
iterator end() { return finish; }
private:
iterator start;
iterator finish;
size_type size_;
allocator<Node<T> > alloc;
void create();
void create(iterator, iterator);
void uncreate();
};
template <class T>
class Node {
public:
Node() : previous(0), next(0) { };
typedef Node<T>* ptr;
typedef T value_type;
value_type object;
ptr previous;
ptr next;
// should define operator=
};
template <class T>
void LList<T>::create()
{
start = finish = 0;
}
template <class T>
void LList<T>::create(iterator i, iterator j)
{
iterator lastIter;
iterator nextIter;
for (LList<T>::iterator it = i; it != j; it++) {
// assign iterator values for start, previous, and next
if (it == i) {
Node<T>* st = alloc.allocate(1);
iterator start_(st);
start = start_;
nextIter = uninitialized_copy(it, it+1, start);
// since copy copies the previous and next members from the original list
// we need to negate them here
start->previous = 0;
start->next = 0;
lastIter = start;
}
else {
nextIter = uninitialized_copy(it, it+1, finish);
lastIter = finish;
}
// create empty final element
Node<T>* fn = alloc.allocate(1);
iterator finish_(fn);
finish = finish_;
finish->previous = lastIter.getPtr();
lastIter->next = finish.getPtr();
finish->next = 0;
}
}
template <class T>
void LList<T>::uncreate()
{
if (start) {
iterator it = finish;
while (it != start)
alloc.destroy(--it);
alloc.deallocate(start, finish - start);
}
start = finish = 0;
}
int main()
{
LList<int> ages;
ages.push_back(31);
ages.push_back(60);
ages.push_back(0);
ages.push_back(36);
ages.push_back(14);
ages.push_back(0);
LList<int> copyAges(ages);
int x = ages.begin()->object;
int y = ages.begin()->object;
cout << x << " " << y << endl;
//for (LList<int>::iterator it = ages.begin(); it != ages.end(); it++)
// cout << it->object << endl;
return 0;
}