16/glist.c

   1 /****************************************************
   2  * William Crenshaw
   3  * 10/27/2014
   4  * GList.cc
   5  *
   6  * Generic list program
   7  ****************************************************/
   8
   9 #include <iostream>
  10 using namespace std;
  11
  12 const int MAX_SIZE = 35;
  13
  14 template <class T>
  15 class List
  16 {
  17         private:
  18                 // list node definition
  19                 struct Node
  20                 {
  21                         T data;
  22                         Node *link;
  23                 };
  24
  25                 Node *head;     // the head of the list
  26                 Node *tail;     // the tail of the list
  27                 Node *curr;     // the current position in the list
  28                 int num_items;  // the number of items in the list
  29
  30         public:
  31                 // constructor
  32                 // remember that an empty list has a "size" of -1 and its "position" is at -1
  33                 List()
  34                 {
  35                         head = NULL;
  36                         tail = NULL;
  37                         curr = NULL;
  38                         num_items = 0;
  39                 }
  40
  41                 // copy constructor
  42                 // clones the list l and sets the last element as the current
  43                 List(const List& l)
  44                 {
  45                         *this = l;
  46                 }
  47
  48                 // copy constructor
  49                 // clones the list l and sets the last element as the current
  50                 void operator=(const List& l)
  51                 {
  52                         head = NULL;
  53                         tail = NULL;
  54                         curr = NULL;
  55                         num_items = 0;
  56
  57                         Node *n = l.head;
  58
  59                         while(n != NULL)
  60                         {
  61                                 InsertAfter(n->data);
  62                                 n = n->link;
  63                         }
  64                 }
  65
  66                 // navigates to the beginning of the list
  67                 void First()
  68                 {
  69                         curr = head;
  70                 }
  71
  72                 // navigates to the end of the list
  73                 // the end of the list is at the last valid item in the list
  74                 void Last()
  75                 {
  76                         curr = tail;
  77                 }
  78
  79                 // navigates to the specified element (0-index)
  80                 // this should not be possible for an empty list
  81                 // this should not be possible for invalid positions
  82                 void SetPos(int pos)
  83                 {
  84                         if(!IsEmpty() && pos >= 0 && pos < GetSize())
  85                         {
  86                                 curr = head;
  87                                 while(pos > 0)
  88                                 {
  89                                         curr = curr->link;
  90                                         pos--;
  91                                 }
  92                         }
  93                 }
  94
  95                 // navigates to the previous element
  96                 // this should not be possible for an empty list
  97                 // there should be no wrap-around
  98                 void Prev()
  99                 {
 100                         if(curr != head)
 101                         {
 102                                 Node *n = head;
 103
 104                                 while(n->link != curr)
 105                                         n = n->link;
 106
 107                                 curr = n;
 108                         }
 109                 }
 110
 111                 // navigates to the next element
 112                 // this should not be possible for an empty list
 113                 // there should be no wrap-around
 114                 void Next()
 115                 {
 116                         if(!IsEmpty() && curr != tail)
 117                                 curr = curr->link;
 118                 }
 119
 120                 // returns the location of the current element (or -1)
 121                 int GetPos()
 122                 {
 123                         if(IsEmpty())
 124                                 return -1;
 125
 126                         int pos = 0;
 127                         Node *n = head;
 128
 129                         while(n != curr)
 130                         {
 131                                 n = n->link;
 132                                 pos++;
 133                         }
 134
 135                         return pos;
 136                 }
 137
 138                 // returns the value of the current element (or -1)
 139                 T GetValue()
 140                 {
 141                         if(!IsEmpty())
 142                                 return curr->data;
 143
 144                         return -1;
 145                 }
 146
 147                 // returns the size of the list
 148                 // size does not imply capacity
 149                 int GetSize()
 150                 {
 151                         return num_items;
 152                 }
 153
 154                 // inserts an item before the current element
 155                 // the new element becomes the current
 156                 // this should not be possible for a full list
 157                 void InsertBefore(T data)
 158                 {
 159                         if(!IsFull())
 160                         {
 161                                 if(IsEmpty())
 162                                         InsertAfter(data);
 163                                 else
 164                                 {
 165                                         Node* n = new Node;
 166                                         n->data = data;
 167                                         n->link = NULL;
 168
 169                                         if(curr == head)
 170                                         {
 171                                                 n->link = head;
 172                                                 head = n;
 173                                                 curr = n;
 174                                                 num_items++;
 175                                         }
 176                                         else
 177                                         {
 178                                                 Prev();
 179                                                 InsertAfter(data);
 180                                         }
 181                                 }
 182                         }
 183                 }
 184
 185                 // inserts an item after the current element
 186                 // the new element becomes the current
 187                 // this should not be possible for a full list
 188                 void InsertAfter(T data)
 189                 {
 190                         if(!IsFull())
 191                         {
 192                                 Node* n = new Node;
 193                                 n->data = data;
 194                                 n->link = NULL;
 195
 196                                 if(IsEmpty())
 197                                 {
 198                                         head = n;
 199                                         tail = n;
 200                                 }
 201                                 else
 202                                 {
 203                                         if(curr == tail)
 204                                         {
 205                                                 curr->link = n;
 206                                                 tail = n;
 207                                         }
 208                                         else
 209                                         {
 210                                                 n->link = curr->link;
 211                                                 curr->link = n;
 212                                         }
 213                                 }
 214
 215                                 curr = n;
 216                                 num_items++;
 217                         }
 218                 }
 219
 220                 // removes the current element (collapsing the list)
 221                 // this should not be possible for an empty list
 222                 void Remove()
 223                 {
 224                         if(!IsEmpty())
 225                         {
 226                                 if(num_items == 1)
 227                                 {
 228                                         head = NULL;
 229                                         tail = NULL;
 230                                         curr = NULL;
 231                                 }
 232                                 else
 233                                 {
 234                                         if(curr == head)
 235                                         {
 236                                                 head = head->link;
 237                                                 curr = head;
 238                                         }
 239                                         else if(curr == tail)
 240                                         {
 241                                                 Prev();
 242                                                 tail = curr;
 243                                                 tail->link = NULL;
 244                                         }
 245                                         else
 246                                         {
 247                                                 Prev();
 248                                                 curr->link = curr->link->link;
 249                                                 Next();
 250                                         }
 251                                 }
 252
 253                                 num_items--;
 254                         }
 255                 }
 256
 257                 // replaces the value of the current element with the specified value
 258                 // this should not be possible for an empty list
 259                 void Replace(int data)
 260                 {
 261                         if(!IsEmpty())
 262                                 curr->data = data;
 263                 }
 264
 265                 // returns if the list is empty
 266                 bool IsEmpty()
 267                 {
 268                         return (num_items == 0);
 269                 }
 270
 271                 // returns if the list is full
 272                 bool IsFull()
 273                 {
 274                         return (num_items == MAX_SIZE);
 275                 }
 276
 277                 // returns the concatenation of two lists
 278                 // l should not be modified
 279                 // l should be concatenated to the end of *this
 280                 // the returned list should not exceed MAX_SIZE elements
 281                 // the last element of the new list is the current
 282                 List operator+(const List& l) const
 283                 {
 284                         List newList = *this;
 285
 286                         Node *n = l.head;
 287
 288                         while(n != NULL)
 289                         {
 290                                 newList.InsertAfter(n->data);
 291                                 n = n->link;
 292                         }
 293
 294                         return newList;
 295                 }
 296
 297                 // returns if two lists are equal (by value)
 298                 bool operator==(const List& l) const
 299                 {
 300                         if(num_items != l.num_items)
 301                                 return false;
 302
 303                         Node *n = head;
 304                         Node *p = l.head;
 305
 306                         while(n != NULL)
 307                         {
 308                                 if(n->data != p->data)
 309                                         return false;
 310
 311                                 n = n->link;
 312                                 p = p->link;
 313                         }
 314
 315                         return true;
 316                 }
 317
 318                 // returns if two lists are not equal (by value)
 319                 bool operator!=(const List& l) const
 320                 {
 321                         return !(*this == l);
 322                 }
 323
 324                 // returns a string representation of the entire list (e.g., 1 2 3 4 5)
 325                 // the string "NULL" should be returned for an empty list
 326                 friend ostream& operator<<(ostream& out, const List &l)
 327                 {
 328                         if(l.num_items == 0)
 329                                 out << "NULL";
 330                         else
 331                         {
 332                                 Node* n = l.head;
 333
 334                                 while(n != NULL)
 335                                 {
 336                                         out << n->data;// << " ";
 337                                         n = n->link;
 338                                 }
 339                         }
 340
 341                         return out;
 342                 }
 343 };