1 /*
2 * =====================================================================================
3 *
4 * Filename: linklist.h
5 *
6 * Description: Link List Exercise with MYSQL Hooks
7 *
8 * Version: 1.0
9 * Created: 03/21/2011 12:42:28 PM
10 * Revision: none
11 * Compiler: gcc
12 *
13 * Author: Ruben Safir,
14 * Company: NYLXS Workshops
15 *
16 * =====================================================================================
17 */
18 #ifndef LINKLIST_H
19 #define LINKLIST_H
20 #endif /* LINKLIST_H */
21
22 #include<iostream>
23 #include<cstdlib>
24 namespace chainlist {
25
26
27 /*
28 * =====================================================================================
29 * Class: Node
30 * Description: This is a node in the "List" Link List
31 * =====================================================================================
32 */
33
34 template < class unk >
35 class Node
36 {
37 public:
38
39 // ==================== LIFECYCLE =======================================
40 /* constructor */
41 Node<unk>( unk value, Node<unk> *item_to_link_to = 0);
42 Node ( const Node &other ); /* copy constructor - Need to write this! */
43 ~Node<unk> (); /* destructor */
44
45
46 /* ==================== ACCESSORS ======================================= */
47 inline unk* value ()const{
48 return value_;
49 }
50 inline Node<unk> * next()const {
51 return next_;
52 }
53
54 inline void value(unk *);
55 inline void value(unk);
56 inline void next(Node<unk> *);
57
58 /* ==================== MUTATORS ======================================= */
59
60 /* ==================== OPERATORS ======================================= */
61
62 Node& operator=( const Node &other ); // assignment operator
63 unk& operator*(){ //gain access to real value
64 return *(value());
65 }
66 unk& operator*(unk);
67
68 protected:
69 /* ==================== DATA MEMBERS ======================================= */
70
71
72
73 private:
74 /* ==================== DATA MEMBERS ======================================= */
75
76 unk * value_ ;
77 Node * next_;
78 }; /* ----- end of template class Node ----- */
79
80 template<class unk>
81 Node<unk>::Node(unk val, Node<unk> *item_to_link_to){
82 value(val);
83 if(!item_to_link_to){
84 next_ = 0;
85 }
86
87 else{
88 next(item_to_link_to->next());
89 item_to_link_to->next(this);
90 }
91 }
92
93 template<class unk>
94 Node<unk>::~Node(){
95 if(value_)
96 delete value_;
97 // std::cout << "Delete Node" << __LINE__ << std::endl;
98
99 }
100
101 template <typename unk>
102 void Node<unk>::next(Node * next_node){
103 next_ = next_node;
104 }
105
106 template<class unk>
107 void Node<unk>::value(unk val){
108 value_ = new unk(val);
109 }
110
111 template<class unk>
112 void Node<unk>::value(unk * val){
113 value_ = val;
114 }
115
116 /* ===================================================================================== */
117
118 template < class T >
119 class List
120 {
121 public:
122
123 /* ==================== LIFECYCLE ======================================= */
124 List<T>(): front_(0),end_(0), cursor_(0), size_(0){} /* constructor */
125 void remove_all();
126 ~List<T>();
127
128 /* ==================== ACCESSORS ======================================= */
129 unsigned int size()const { return size_; }
130 inline Node<T>* const &front()const{ return front_;}
131 inline Node<T>* &endd(){return end_;}
132
133 inline Node<T> *& cursor(){return cursor_; }
134
135 inline void cursor(Node<T> * a){ cursor_ = a; }
136
137 inline void endd(Node<T> *a){ end_ = a; }
138 inline void front(Node<T> *a){ front_ = a; }
139 inline void display();
140
141
142
143 /* ==================== MUTATORS ======================================= */
144
145 inline void sizeup(){ ++size_; }
146 inline void sizedown(){ --size_; }
147 void insert_front( T value); //add a node to the front
148 void insert(T value, Node<T> * &place_after_this); //add a new node after the Node given and return the new node
149 void insert(T value); //add a new node at the end of the list
150 void insert_end(T value); // Add a new node to the end
151
152 void find_value(T value); //find a value from it's first occurance in the list
153 Node<T>*& find_next_value(const T& value, Node<T>*& last_node_searched); //find a value in the list after the
154 //current node which is not searched
155 void remove_node_by_value(T value);
156 void remove_node_by_node(Node<T> cur);
157 void remove_front();
158 void remove_end();
159
160
161
162 /* ==================== OPERATORS ======================================= */
163
164 T& operator[](unsigned int const);
165
166
167
168
169
170 protected:
171 /* ==================== DATA MEMBERS ======================================= */
172
173 private:
174 /* ==================== DATA MEMBERS ======================================= */
175 Node<T> * front_;
176 Node<T> * end_;
177 Node<T> * cursor_;
178 unsigned int size_;
179
180 }; /* ---------- end of template class Lists ---------- */
181
182 template <class T>
183 void List<T>::insert_front ( T value )
184 {
185 Node<T> *tmp = new Node<T>(value);
186 Node<T> * tmp2 = front();
187 if(tmp2 == 0){
188 // tmp2 = tmp;
189 endd(tmp);//endd not null anymore
190 cursor(tmp);
191 tmp->next(0);
192 front(tmp);//front not null anymore
193 }
194 else{
195 tmp->next(tmp2);
196 front(tmp);
197 cursor(tmp); //curosr moved to the front
198 }
199
200 sizeup();
201
202 return ;
203 }
204 /* ----- end of template function insert_front ----- */
205
206
207 template < class T >
208 void List<T>::insert ( T val, Node<T> *&node_in_front )
209 {
210 //If there is no node sent, attach it to the end
211 Node<T> * tmp = new Node<T>(val);
212 if(!front()){
213 front(tmp);
214 endd(tmp);
215 cursor(tmp);
216 sizeup();
217 return;
218 }
219
220 if(!node_in_front){
221 endd()->next(tmp);
222 endd(tmp);
223 cursor(tmp); //Set Cursor to the end
224 }else{
225 tmp->next(node_in_front->next());
226 node_in_front->next(tmp);
227 cursor(tmp);
228 if(node_in_front == endd())
229 endd(tmp);
230 }
231 sizeup();
232
233 return ;
234 } /* ----- end of method List<T>::insert ----- */
235
236 template < class T >
237 void List<T>::insert ( T val )
238 {
239 if(!front()){
240 Node<T> * tmp = new Node<T>(val);
241 front(tmp);
242 endd(tmp);
243 cursor(tmp);
244 sizeup();
245 return;
246 }else{
247 Node<T> * tmp = new Node<T>(val, endd());
248 endd()->next(tmp);
249 endd(tmp);
250 cursor(tmp);
251 sizeup();
252 return;
253 }
254 } /* --- end of method List<T>::insert ---- */
255
256
257 template < class T >
258 void List<T>::insert_end ( T val )
259 {
260 insert(val);
261 }
262
263 template < class T >
264 void List<T>::display ()
265 {
266 // std::cout << "*********DISPLAYING ENTIRE LIST************" << std::endl;
267 if(endd() == 0){
268 std::cout << "Empty List" << std::endl;
269 return;
270 }
271
272 cursor() = front();
273 while(cursor() != endd() ){
274 std::cout << *(cursor()->value()) << std::endl;
275 cursor(cursor()->next());
276 }
277 std::cout << *(cursor()->value()) << std::endl; //display the end
278
279
280 return ;
281 } /* ----- end of method List<T>::display ----- */
282
283 template < class T >
284 void List<T>::find_value(T val)
285 {
286 cursor() = front();
287 while(cursor() != endd()){
288 if (*(cursor()->value()) == val)
289 return;
290 else{
291 cursor(cursor()->next());
292 }
293 }
294 if(*(endd()->value()) == val)
295 return;
296 else{
297 cursor() = 0; //park the cursor when nothing is found
298 }
299 }
300
301 template<class T>
302 void List<T>::remove_front(){
303 //// std::cout << "Removing the Front " << front() << " End of List is "<< endd() << std::endl;
304
305 if(front() == 0){
306 // std::cout << "Front is NULL " << front() << std::endl;
307 return;
308 }
309 if(front() == endd()){
310 //
311 // std::cout << "Front is End " << front() << std::endl;
312 Node<T> * tmp = front();
313 delete tmp;
314 front(0);
315 endd(0);
316 cursor() = 0;
317 sizedown();
318 return;
319 }
320
321 // std::cout << "Front is NOT End " << front() << std::endl;
322 Node<T> * tmp = front();
323 front(front()->next());
324 delete tmp;
325 sizedown();
326 cursor() = front();
327 // std::cout << "Next Front returned " << front() << std::endl;
328 return;
329 }
330
331
332
333 template< class T>
334 void List<T>::remove_all(){
335
336 // std::cout << "remove_all " << __LINE__ << std::endl;
337 cursor() = front();
338 while(cursor() != endd()){
339 // std::cout << "remove_all the front line" << __LINE__ << std::endl;
340 remove_front();
341 }
342 // std::cout << "\n\nReached the End\n\n";
343 remove_front();
344 // std::cout << "\n\nDeleted Last Node\n\n";
345 }
346
347 template<class T>
348 List<T>::~List<T>(){
349 remove_all();
350 // std::cout << "Deleted All*************" << __LINE__ << std::endl;
351 }
352
353 template < class T >
354 Node<T>*& List<T>::find_next_value (const T& value, Node<T>*& last_node_searched)
355 {
356 // std::cout << "IN FIND_NEXT_VALUE \n";
357 cursor(last_node_searched);
358 // std::cout << "CURSOR AT " << cursor() << " and END IS AT " << endd() << std::endl;
359 if(cursor() == endd()){
360 cursor() = 0;
361 return cursor();
362 }
363 // std::cout << "Not at the end yet!!\n";
364 cursor() = cursor()->next();
365 // std::cout << "Next Cursor " << cursor() << "\n";
366 // std::cout << "Cursor Value " << *(cursor()->value()) << "\n";
367 while(value != *(cursor()->value()) ){
368 if(cursor() == endd()){
369 if( *(endd()->value()) == value){
370 return endd();
371 }else{
372 cursor() = 0;
373 return cursor();//is this a problem. Does setting the Node * to zero return a zero address on all platforms?
374 }
375 }
376 cursor() = cursor()->next();
377 // std::cout << "Next Cursor " << cursor() << "\n";
378 // std::cout << "CURSOR AT " << cursor() << " and END IS AT " << endd() << std::endl;
379 }
380 return cursor();
381 } /* ----- end of method List<T>::find_next_value ----- */
382
383 template< class T >
384 T& chainlist::List<T>::operator[](unsigned int const index){
385 // std::cout << "Don't INDEX past the end of the file! Use obj_pt->size(): Size => " << size() << "Index=> " << index << std::endl;
386 unsigned int i = 0;
387 if( index >= (unsigned int) size() ){
388 //std::cerr << "Don't INDEX past the end of the file! Use obj_pt->size(): Size => " << size() << "Index=> " << index << std::endl;
389 //std::exit(1) ;
390
391 for(i = size(); i <= index ;++i){
392 insert_end(*(new T));
393 };
394 return *(endd()->value());
395 }
396
397 if(index == 0){
398 // std::cout << "Don't INDEX past the end of the file! Use obj_pt->size(): Size => " << size() << "Index=> " << index << std::endl;
399 cursor() = front();
400 return *(cursor()->value());
401 }
402
403
404 cursor() = front();
405 for(; i < index; ++i){
406 cursor(cursor()->next());
407 }
408 return *(cursor()->value());
409 }
410
411
412
413
414
415 } /* ----- end of namespace chainlist ----- */