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