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 Node<T> * tmp = new Node<T>(val);
267 front(tmp);
268 endd(tmp);
269 cursor(tmp);
270 sizeup();
271 return;
272 }else{
273 Node<T> * tmp = new Node<T>(val, endd());
274 // endd()->next(tmp); // redundant
275 endd(tmp);
276 cursor(tmp);
277 sizeup();
278 return;
279 }
280 } /* --- end of method List<T>::insert ---- */
281
282
283 template < class T >
284 void List<T>::insert_end ( T val )
285 {
286 insert(val);
287 }
288
289 template < class T >
290 void List<T>::display ()
291 {
292 // std::cout << "*********DISPLAYING ENTIRE LIST************" << std::endl;
293 if(endd() == 0){
294 std::cout << "Empty List" << std::endl;
295 return;
296 }
297
298 cursor() = front();
299 while(cursor() != endd() ){
300 std::cout << *(cursor()->value()) << std::endl;
301 cursor(cursor()->next());
302 }
303 std::cout << *(cursor()->value()) << std::endl; //display the end
304
305
306 return ;
307 } /* ----- end of method List<T>::display ----- */
308
309 template < class T >
310 void List<T>::find_value(T val)
311 {
312 cursor() = front();
313 while(cursor() != endd()){
314 if (*(cursor()->value()) == val)
315 return;
316 else{
317 cursor(cursor()->next());
318 }
319 }
320 if(*(endd()->value()) == val)
321 return;
322 else{
323 cursor() = 0; //park the cursor when nothing is found
324 }
325 }
326
327 template<class T>
328 void List<T>::remove_front(){
329 //// std::cout << "Removing the Front " << front() << " End of List is "<< endd() << std::endl;
330
331 if(front() == 0){
332 // std::cout << "Front is NULL " << front() << std::endl;
333 return;
334 }
335 if(front() == endd()){
336 //
337 // std::cout << "Front is End " << front() << std::endl;
338 Node<T> * tmp = front();
339 delete tmp;
340 front(0);
341 endd(0);
342 cursor() = 0;
343 sizedown();
344 return;
345 }
346
347 // std::cout << "Front is NOT End " << front() << std::endl;
348 Node<T> * tmp = front();
349 front(front()->next());
350 delete tmp;
351 sizedown();
352 cursor() = front();
353 // std::cout << "Next Front returned " << front() << std::endl;
354 return;
355 }
356
357
358
359 template< class T>
360 void List<T>::remove_all(){
361
362 // std::cout << "remove_all " << __LINE__ << std::endl;
363 cursor() = front();
364 while(cursor() != endd()){
365 // std::cout << "remove_all the front line" << __LINE__ << std::endl;
366 remove_front();
367 }
368 // std::cout << "\n\nReached the End\n\n";
369 remove_front();
370 // std::cout << "\n\nDeleted Last Node\n\n";
371 }
372
373 template<class T>
374 List<T>::~List<T>(){
375 remove_all();
376 // std::cout << "Deleted All*************" << __LINE__ << std::endl;
377 }
378
379 template < class T >
380 Node<T>*& List<T>::find_next_value (const T& value, Node<T>*& last_node_searched)
381 {
382 // std::cout << "IN FIND_NEXT_VALUE \n";
383 cursor(last_node_searched);
384 // std::cout << "CURSOR AT " << cursor() << " and END IS AT " << endd() << std::endl;
385 if(cursor() == endd()){
386 cursor() = 0;
387 return cursor();
388 }
389 // std::cout << "Not at the end yet!!\n";
390 cursor() = cursor()->next();
391 // std::cout << "Next Cursor " << cursor() << "\n";
392 // std::cout << "Cursor Value " << *(cursor()->value()) << "\n";
393 while(value != *(cursor()->value()) ){
394 if(cursor() == endd()){
395 if( *(endd()->value()) == value){
396 return endd();
397 }else{
398 cursor() = 0;
399 return cursor();//is this a problem. Does setting the Node * to zero return a zero address on all platforms?
400 }
401 }
402 cursor() = cursor()->next();
403 // std::cout << "Next Cursor " << cursor() << "\n";
404 // std::cout << "CURSOR AT " << cursor() << " and END IS AT " << endd() << std::endl;
405 }
406 return cursor();
407 } /* ----- end of method List<T>::find_next_value ----- */
408
409 template< class T >
410 T& chainlist::List<T>::operator[](unsigned int const index){
411 // std::cout << "Don't INDEX past the end of the file! Use obj_pt->size(): Size => " << size() << "Index=> " << index << std::endl;
412 unsigned int i = 0;
413 if( index >= (unsigned int) size() ){
414 //std::cerr << "Don't INDEX past the end of the file! Use obj_pt->size(): Size => " << size() << "Index=> " << index << std::endl;
415 //std::exit(1) ;
416 T *dump;
417 for(i = size(); i <= index ;++i){
418 dump = new T();
419 insert(*dump);
420 delete dump;
421 };
422 return *(endd()->value());
423 }
424
425 if(index == 0){
426 // std::cout << "Don't INDEX past the end of the file! Use obj_pt->size(): Size => " << size() << "Index=> " << index << std::endl;
427 cursor() = front();
428 return *(cursor()->value());
429 }
430
431
432 cursor() = front();
433 for(; i < index; ++i){
434 cursor(cursor()->next());
435 }
436 return *(cursor()->value());
437 }
438
439 template <class T>
440 void List<T>::sort ( List <T> & v )
441 {
442 const size_t n = v.size();
443
444 for (int gap = n/2; 0<gap; gap/=2){
445 //cout << " gap==> " << gap << " n ==> " << n << endl;
446 for (int i = gap;i < int(n);i++){
447 //cout << "i ==> " << i << " gap==> " << gap << " n ==> " << n << endl;
448 for (int j=i-gap;0<=j ;j-=gap ){
449 //cout << "COMPARE::i ==> " << i << " j==> " << j << " gap==> " << gap << " n ==> " << n << endl;
450 //cout << "***Comparing " << j+gap << " and " << j << endl;
451 if(v[j+gap]<v[j]){
452 T temp = v[j];
453 v[j] = v[j+gap];
454 v[j+gap] = temp;
455 }
456 }
457 }
458 }
459 }
460
461
462
463
464
465
466 } /* ----- end of namespace chainlist ----- */
467 #endif /* LINKLIST_H */