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