rosapps/devutils/vmingw/CList.cpp

   1 /********************************************************************
   2 *       Class:  CList.cpp. This is part of WinUI.
   3 *
   4 *       Purpose:        A simple way to create doubly linked lists.
   5 *
   6 *       Authors:        Originally coded by Claude Catonio.
   7 *
   8 *       License:        Original code was public domain.
   9 *                       Present revised CList classes are covered by GNU General Public License.
  10 *
  11 *       Revisions:
  12 *                       Manu B. 10/05/01        Terms was translated to English.
  13 *                       Manu B. 10/16/01        Add CList::Destroy(CNode *node) method.
  14 *                       Manu B. 11/12/01        Add InsertBefore/InsertAfter methods.
  15 *                       Manu B. 11/17/01        First() & Last() now returns an integer value.
  16 *                       Manu B. 11/19/01        CNode::Destroy() returns next node by default.
  17 *                       Manu B. 12/28/01        Simplify CList, add InsertSorted().
  18 *                       Manu B. 03/13/02        Suppress CNode methods, next and prev are public.
  19 *                       Manu B. 03/28/02        Add Compare().
  20 *
  21 ********************************************************************/
  22 #include "CList.h"
  23
  24 /********************************************************************
  25 *       Class:  CList.
  26 *
  27 *       Purpose:        List management.
  28 *
  29 *       Revisions:
  30 *
  31 ********************************************************************/
  32 CList::~CList(){
  33         //MessageBox (0, "CList", "destructor", MB_OK);
  34         while (first != NULL){
  35                 current = first;
  36                 first = first->next;
  37                 delete current;
  38         }
  39         current = last = first;
  40         count = 0;
  41 }
  42
  43 /********************************************************************
  44 *       Browse the list.
  45 ********************************************************************/
  46 CNode * CList::First(){
  47         current = first;
  48 return current;
  49 }
  50
  51 CNode * CList::Last(){
  52         current = last;
  53 return current;
  54 }
  55
  56 CNode * CList::Prev(){
  57         // Empty list ?
  58         if (first != NULL){
  59                 if(current->prev == NULL){
  60                         // No previous node.
  61                         return NULL;
  62                 }else{
  63                         // A previous one.
  64                         current = current->prev;
  65                         return current;
  66                 }
  67         }
  68 return NULL;
  69 }
  70
  71 CNode * CList::Next(){
  72         // Empty list ?
  73         if (first != NULL){
  74                 if(current->next == NULL){
  75                         // No next node.
  76                         return NULL;
  77                 }else{
  78                         // A next one.
  79                         current = current->next;
  80                         return current;
  81                 }
  82         }
  83 return NULL;
  84 }
  85
  86 /********************************************************************
  87 *       Insert nodes.
  88 ********************************************************************/
  89 void CList::InsertFirst(CNode *node){
  90         if(first == NULL){
  91                 // Empty list.
  92                 first = last = node;
  93         }else{
  94                 // Set node pointers.
  95                 node->prev      = NULL;
  96                 node->next      = first;
  97                 // Insert in the list.
  98                 first->prev             = node;
  99                 first                   = node;
 100         }
 101         // Set current node, increment the node counter.
 102         current = node;
 103         count++;
 104 }
 105
 106 void CList::InsertLast(CNode *node){
 107         if(first == NULL){
 108                 // Empty list.
 109                 first = last = node;
 110         }else{
 111                 // Set node pointers.
 112                 node->prev      = last;
 113                 node->next      = NULL;
 114                 // Insert in the list.
 115                 last->next              = node;
 116                 last                    = node;
 117         }
 118         // Set current node, increment the node counter.
 119         current = node;
 120         count++;
 121 }
 122
 123 void CList::InsertBefore(CNode *node){
 124         if(first == NULL){
 125                 // Empty list.
 126                 first = last = node;
 127         }else{
 128                 if (current == first)
 129                         first = node;
 130                 // Set node pointers.
 131                 node->prev = current->prev;
 132                 node->next = current;
 133                 // Insert in the list.
 134                 if (node->prev)
 135                         node->prev->next = node;
 136                 current->prev = node;
 137         }
 138         // Set current node, increment the node counter.
 139         current = node;
 140         count++;
 141 }
 142
 143 void CList::InsertAfter(CNode *node){
 144         if(first == NULL){
 145                 // Empty list.
 146                 first = last = node;
 147         }else{
 148                 if (current == last)
 149                         last = node;
 150                 // Set node pointers.
 151                 node->prev = current;
 152                 node->next = current->next;
 153                 // Insert in the list.
 154                 if (node->next)
 155                         node->next->prev = node;
 156                 current->next = node;
 157         }
 158         // Set current node, increment the node counter.
 159         current = node;
 160         count++;
 161 }
 162
 163 bool CList::InsertSorted(CNode * newNode){
 164         // Get the current node.
 165         CNode * currentNode = GetCurrent();
 166         int cmpResult;
 167
 168         if(!currentNode){
 169                 // The list is empty, InsertFirst() and return.
 170                 InsertFirst(newNode);
 171                 return true;
 172         }
 173
 174         // Compare new node and current node data to know if we must parse Up
 175         // or Down from current node.
 176         cmpResult = Compare(newNode, currentNode);
 177
 178         // Search Up -----------------------------------------------------------------
 179         if (cmpResult == -1){
 180                 // Parse the list while there's a previous node.
 181                 while (Prev()){
 182                         currentNode = GetCurrent();
 183                         cmpResult = Compare(newNode, currentNode);
 184
 185                         if (cmpResult == 1){
 186                                 // Correct position found.
 187                                 InsertAfter(newNode);
 188                                 return true;
 189                         }else if (cmpResult == 0){
 190                                 // Don't add a file twice.
 191                                 return false;
 192                         }
 193                 }
 194                 // There's no previous node, so insert first.
 195                 InsertFirst(newNode);
 196                 return true;
 197         }
 198         // Search Down --------------------------------------------------------------
 199         else if (cmpResult == 1){
 200                 // Parse the list while there's a next node.
 201                 while (Next()){
 202                         currentNode = GetCurrent();
 203                         cmpResult = Compare(newNode, currentNode);
 204
 205                         if (cmpResult == -1){
 206                                 // Correct position found.
 207                                 InsertBefore(newNode);
 208                                 return true;
 209                         }else if (cmpResult == 0){
 210                                 // Don't add a file twice.
 211                                 return false;
 212                         }
 213                 }
 214                 // There's no next node, so insert last.
 215                 InsertLast(newNode);
 216                 return true;
 217         }
 218         // Don't add a file twice (cmpResult == 0) -------------------------------------
 219 return false;
 220 }
 221
 222
 223 int CList::InsertSorted_New(CNode * newNode){
 224         int cmpResult;
 225
 226         /* Get the current node */
 227         CNode * currentNode = GetCurrent();
 228         if(!currentNode)
 229                 return EMPTY_LIST;
 230
 231         /* Parse up or down ? */
 232         cmpResult = Compare(newNode, currentNode);
 233
 234         /* -Up- */
 235         if (cmpResult == -1){
 236                 // Parse the list while there's a previous node.
 237                 while (Prev()){
 238                         currentNode = GetCurrent();
 239                         cmpResult = Compare(newNode, currentNode);
 240
 241                         if (cmpResult == 1){
 242                                 // Correct position found.
 243                                 return INSERT_AFTER;
 244                         }else if (cmpResult == 0){
 245                                 // Don't add a file twice.
 246                                 return FILE_FOUND;
 247                         }
 248                 }
 249                 // There's no previous node, so insert first.
 250                 return INSERT_FIRST;
 251
 252         /* -Down- */
 253         }else if (cmpResult == 1){
 254                 // Parse the list while there's a next node.
 255                 while (Next()){
 256                         currentNode = GetCurrent();
 257                         cmpResult = Compare(newNode, currentNode);
 258
 259                         if (cmpResult == -1){
 260                                 // Correct position found.
 261                                 return INSERT_BEFORE;
 262                         }else if (cmpResult == 0){
 263                                 // Don't add a file twice.
 264                                 return FILE_FOUND;
 265                         }
 266                 }
 267                 // There's no next node, so insert last.
 268                 return INSERT_LAST;
 269         }
 270         // Don't add a file twice (cmpResult == 0) -------------------------------------
 271 return FILE_FOUND;
 272 }
 273
 274
 275 /********************************************************************
 276 *       Destroy nodes.
 277 ********************************************************************/
 278 void CList::DestroyCurrent(){
 279 //      CNode * node = current;
 280         Destroy(current);
 281 }
 282
 283 void CList::Destroy(CNode * node){
 284         // Empty list ?
 285         if (current != NULL){
 286                 // Detach node from the list.
 287                 if (node->next != NULL)
 288                         node->next->prev = node->prev;
 289                 if (node->prev != NULL)
 290                         node->prev->next = node->next;
 291
 292                 // Set current node.
 293                 if(node->next != NULL)
 294                         current = node->next;
 295                 else
 296                         current = node->prev;
 297
 298                 if (current == NULL){
 299                         // Now, the list is empty.
 300                         first = last = NULL;
 301
 302                 }else if (first == node){
 303                         // Detached node was first.
 304                         first = current;
 305
 306                 }else if (last == node){
 307                         // Detached node was last.
 308                         last = current;
 309                 }
 310                 delete node;
 311                 count--;
 312         }
 313 }
 314
 315 void CList::DestroyList(){
 316         while (first != NULL){
 317                 current = first;
 318                 first = first->next;
 319                 delete current;
 320         }
 321         current = last = first;
 322         count = 0;
 323 }
 324
 325 int CList::Length(){
 326 return count;
 327 }
 328