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 */