cgma
DLList.cpp
Go to the documentation of this file.
00001 //- Class: DLList
00002 //- Owner: Greg Sjaardema
00003 //- Checked by:
00004 //- Version: $Id: 
00005 
00006 #include "DLList.hpp"
00007 
00008 
00009 //- Constructor: Create a list with initial size {increment}. The list
00010 //- will be grown by {increment} each time it is filled. Memory for the
00011 //- list is not allocated until the first element is inserted using
00012 //- {insertLink}. 
00013 //- If {increment} is zero, the default increment ({INCREMENT}) will be used
00014 //- From an efficiency standpoint, it is very important that the 
00015 //- increment be set large enough to reduce the number of list 
00016 //- growths, but small enough to not waste memory.
00017 //- It is more efficient to sligthly overestimate the increment than 
00018 //- to underestimate the increment.
00019 DLList::DLList ( int increment ): ArrayBasedContainer( increment )
00020 {
00021   index      = 0;
00022   nullItem   = 0;
00023 }
00024 
00025 //- Copy Constructor
00026 DLList::DLList(const DLList& from) : ArrayBasedContainer ( from )
00027 {
00028   index = from.index;
00029   listIsSorted = CUBIT_FALSE;
00030 }
00031 
00032 DLList::~DLList()
00033 {
00034 }
00035 
00036 //- put new item in list after current item and make it current
00037 void DLList::insert_link ( void* new_item )
00038 {
00039   assert(new_item != NULL);
00040   // see if the list must be lengthened
00041   if ( itemCount == listLength )
00042   {
00043       lengthen_list();
00044   }
00045   
00046   // set new index
00047   
00048   if ( itemCount )
00049   {
00050       index++;
00051   }
00052   else
00053   {
00054       index = 0;
00055   }
00056   
00057   // the item must be put in the current index, all higher
00058   // indexes must be bubbled up one spot
00059   
00060   for ( int i = itemCount; i > index; i-- )
00061   {
00062       listArray[i] = listArray[i-1];
00063   }
00064   
00065   listArray[index] = new_item;
00066   itemCount++;
00067 }
00068 
00069 //- merge the input list, merge_list, with the current list, making
00070 //- sure not to add duplicate items into the current list
00071 void DLList::merge_unique ( DLList& merge_list, int merge_list_unique )
00072 {
00073    // MJP Note:
00074    // This procedure could be much more efficient if sorted lists
00075    // are used. However, I need this procedure at this time to merge
00076    // DLLists that already exist. These were not created as sorted
00077    // lists (SDLLists) and it would be painful to convert them to
00078    // SDLLists. It would be a lot easier if one could simply sort 
00079    // a DLList based on the numeric values of its items.
00080    
00081    // Save the current index of the merge_list
00082    int current_index = merge_list.index;
00083    int old_size = size();   
00084    int i, j, check_index;
00085    void* new_item = NULL;   
00086 
00087    for (i = 0; i < merge_list.size(); i++)
00088    {
00089       // Get the item from the merge_list and insert it into "this"
00090       // list if it doesn't already exist there.
00091       new_item = merge_list.get_item_and_step();
00092       check_index = merge_list_unique ? old_size : size();
00093       
00094       for ( j = 0; j < check_index; j++ )
00095       {
00096         if ( listArray[j] == new_item )
00097         {
00098           check_index = -1;
00099           break;
00100         }
00101       }
00102       
00103       if ( check_index != -1 )
00104         append_link(new_item);
00105    }
00106    
00107    // Restore the original index of the merge_list
00108    merge_list.index = current_index;
00109 }
00110 
00111 
00112 //- put new item in list at index 0 and make it current
00113 void DLList::insert_link_first(void* new_item)
00114 {
00115   // set index to -1 ... index will be set to 0 in insert_link
00116 
00117   index = -1;
00118   insert_link(new_item);
00119 }
00120 
00121 //- remove the item at the current location and return a pointer to it.
00122 //- The next node becomes the current node
00123 //- Returns {NULL} if there are no items in list
00124 void* DLList::cut_link ()
00125 {
00126     if ( !itemCount )
00127     {
00128         PRINT_WARNING("Attempted link removal from empty DLList\n");
00129         return NULL;
00130     }
00131 
00132     // save the current value
00133 
00134     void *temp = listArray[index];
00135 
00136     // compress memory
00137 
00138     for ( int i = index; i < itemCount-1; i++ )
00139     {
00140         listArray[i] = listArray[i+1];
00141     }
00142 
00143     itemCount--;
00144     if ( index >= itemCount )
00145     {
00146         index = 0;
00147     }
00148 
00149     return temp;
00150 }
00151 
00152 
00153 //- remove the item at the current location and return a pointer to it.
00154 //- used for efficiency in cases where preservation of list order is not
00155 //- important.  moves last list item (itemCount - 1) to current index and
00156 //- decrements itemCount.  eliminates the need to perform the list bubble
00157 //- down (i.e. cut_link) but sacrifices list order in the process.  this
00158 //- function should not be used when up-stream order from the removed node is
00159 //- important.  when processing a list using this function the user should
00160 //- reset the list to the head (index = 0) before beginning to ensure all
00161 //- list nodes are processed properly.
00162 //- Returns {NULL} if there are no items in list
00163 void* DLList::extract_link ()
00164 {
00165     if ( !itemCount ) {
00166       PRINT_WARNING("Attempted link removal from empty DLList\n");
00167       return NULL;
00168     }
00169     
00170     // save the current value
00171     void *temp = listArray[index];
00172     
00173     // assign last node to the current index
00174     listArray[index] = listArray[itemCount - 1];
00175     
00176     // decrement itemCount
00177     itemCount--;
00178     if ( index == itemCount && index != 0) {
00179       // The choices here are index at beginning or end.
00180       // End seems to work better when 'extract' is being used
00181       // with calls to 'move_to_item'. 
00182       index--;
00183     }
00184     
00185     return temp;
00186 }
00187 
00188 
00189 //+//Added so list removals don't disturb current position. PRK 05-23-94
00190 //+//Corrected for omitting the last item in the list. PRK 09-16-94
00191 //+//Corrected for omitting before the current position. PRK 10-07-94
00192 //- Finds instance of item by matching pointer and deleting all instances
00193 //- of it from the list. The current position of the list is not changed.
00194 //- Returns CUBIT_TRUE if the item was found and deleted, CUBIT_FALSE if not.
00195 CubitBoolean DLList::omit_link(void *oldObjPtr)
00196 {
00197     int scan_index;
00198     int squeeze_index = 0;
00199     CubitBoolean found = CUBIT_FALSE;
00200     for(scan_index = 0; scan_index < itemCount; ++scan_index)
00201     {
00202         if(listArray[scan_index] == oldObjPtr)
00203         {
00204             found = CUBIT_TRUE;
00205             if(index == scan_index) index = squeeze_index - 1;
00206         }
00207         else 
00208         {
00209             if(scan_index != squeeze_index)
00210             {
00211                 listArray[squeeze_index] = listArray[scan_index];
00212                 if(index == scan_index) index = squeeze_index;
00213             }
00214             ++squeeze_index;
00215         }
00216     }
00217 
00218     if(found)
00219     {
00220         itemCount = squeeze_index;
00221 //+//   If the first item was deleted and index pointed to it, make an
00222 //+//   adjustment here. If itemCount is zero, don't assign -1 again.
00223         if (index < 0)
00224       index = (itemCount) ? (itemCount - 1) : 0 ;
00225     if (index >= itemCount)
00226       index = (itemCount) ? (itemCount - 1) : 0 ;
00227     }
00228 
00229     return found;
00230 }
00231 
00232 
00233 //- Change the current item to a null pointer and return a pointer
00234 //- to the item (before nulled). See the discussion for {nullItem}.
00235 void* DLList::nullify_link ()
00236 {
00237     if ( !itemCount )
00238     {
00239         PRINT_WARNING("Attempted link nullify from empty DLList\n");
00240         return NULL;
00241     }
00242 
00243     // save the current value
00244       nullItem = listArray[index];
00245       listArray[index] = 0;
00246     return nullItem;
00247 }
00248 
00249 void *DLList::prev_item ( int n )  const
00250 {
00251     if ( !itemCount )
00252     {
00253         PRINT_WARNING("Attempted prev of empty DLList\n");
00254         return NULL;
00255     }
00256 
00257     // return the proper index
00258     // beware of negative n
00259     int new_index = index - n;
00260 
00261     while (new_index < 0)
00262       new_index += itemCount;
00263     // beware of negative n leading to new_index >itemCount
00264     new_index = new_index%itemCount;
00265 
00266     assert(listArray[new_index] != NULL);
00267     return listArray[new_index];
00268 }
00269 
00270 void *DLList::step_and_get_item () 
00271 {
00272     if ( !itemCount )
00273     {
00274         PRINT_WARNING("Attempted step_and_get from empty DLList\n");
00275         return NULL;
00276     }
00277 
00278     if (++index == itemCount)
00279       index=0;
00280     void *temp = listArray[index];
00281     assert(temp != NULL);
00282     return temp;
00283 }
00284 
00285 void *DLList::get_item_and_back ()
00286 {
00287     if ( !itemCount )
00288     {
00289         PRINT_WARNING("Attempted get_and_back from empty DLList\n");
00290         return NULL;
00291     }
00292     void *temp = listArray[index--];
00293     if (index < 0) index=itemCount-1;
00294     assert(temp != NULL);
00295     return temp;
00296 }
00297 
00298 // move_to_and_remove_item searches for item and removes it from the list.
00299 // If the item was found and removed it is returned, else NULL is returned.
00300 void* DLList::move_to_and_remove_item(void* item)
00301 {
00302   if (move_to_item(item))
00303     return cut_link();
00304   else
00305     return (void*) NULL;
00306 }
00307 
00308 int DLList::distance_to_nearby_item(void* body)
00309 {
00310   int old_index = index;
00311   move_to_nearby_item( body );
00312   int distance = abs(index - old_index);
00313   if ( distance > itemCount / 2 )
00314     distance = itemCount - distance;
00315   index = old_index;
00316   return distance;
00317 }
00318 
00319 
00320 CubitBoolean DLList::move_to_nearby_item ( void* item )
00321 {
00322       // empty list
00323   if (itemCount == 0) 
00324     return CUBIT_FALSE;
00325   
00326   // Search current item first...
00327   void **ptr_up = &(listArray[index]);
00328   if (*ptr_up == item) 
00329     return CUBIT_TRUE;
00330 
00331   int i_up, i_down;
00332   i_up = i_down = index;
00333   void **ptr_down = ptr_up;
00334   while (1) 
00335   {
00336       // check forward in the list
00337       // increment
00338     if ( ++i_up < itemCount )
00339       ptr_up++;
00340     else
00341     {
00342       i_up = 0;
00343       ptr_up = listArray;
00344     }
00345       // check
00346     if ( *ptr_up == item )
00347     {
00348       index = i_up;
00349       return CUBIT_TRUE;
00350     }
00351     if ( i_up == i_down )
00352     {
00353       return CUBIT_FALSE;
00354     }
00355     
00356       // check backward in the list
00357       // increment
00358     if ( --i_down >= 0 )
00359       ptr_down--;
00360     else
00361     {
00362       i_down = itemCount-1;
00363       ptr_down = &(listArray[i_down]);
00364     }
00365       // check
00366     if ( *ptr_down == item )
00367     {
00368       index = i_down;
00369       return CUBIT_TRUE;
00370     }
00371     if ( i_up == i_down )
00372     {
00373       return CUBIT_FALSE;
00374     }
00375     
00376   }
00377 }
00378 
00379 CubitBoolean DLList::move_to_item ( void* item )
00380 {
00381   int item_position = where_is_item( item );
00382   if ( item_position >= 0 ) {
00383     index = item_position;
00384     return CUBIT_TRUE;
00385   }
00386   return CUBIT_FALSE;
00387 }
00388 
00389 int DLList::where_is_item( void *item ) const
00390 {
00391   // test for null input item
00392   assert(item != NULL);
00393 
00394   if (itemCount == 0) return -1;
00395   
00396   // loop through list searching for item ...
00397   // if found set index and return true
00398 
00399   // Search current item first...
00400   void **ptr = &(listArray[index]);
00401   if (*ptr == item) return index;
00402 
00403   // Now, search from current index to end of array
00404   int i;
00405   for (i=index+1; i < itemCount; i++) {
00406     ptr++;
00407     if ( *ptr == item) {
00408         // check if move_to_nearby would have been better
00409         //if ( i - index > 1000 )
00410         // PRINT_INFO(" Found, i = %d, index = %d, itemCount = %d.\n",
00411         //           i, index, itemCount);
00412       return i;
00413     }
00414   }
00415   
00416   // Now search from beginning of array to index...
00417   ptr = listArray;
00418   for (i = 0; i < index; i++) {
00419     if (*ptr == item) {
00420         // check if move_to_nearby would have been better
00421         // if ( i + itemCount - index > 1000 )
00422         // PRINT_INFO(" Found, i = %d, index = %d, itemCount = %d.\n",
00423         //           i, index, itemCount);
00424       return i;
00425     }
00426     ptr++;
00427   }
00428   
00429   // item is not in array, return false
00430   return -1;
00431 }
00432 
00433 // Special care for size two lists, so that wrap around is used only when
00434 // needed.  This works faster than the original (commented out below) for
00435 // long lists
00436 CubitBoolean DLList::move_between_items(void *item1, void *item2)
00437 {
00438   
00439   assert(item1 != NULL && item2 != NULL);
00440   if ( !itemCount )
00441       return CUBIT_FALSE;
00442   
00443   for ( int i = 0; i < itemCount; i++ )
00444     {
00445       if ( listArray[i] == item1 )
00446         {
00447       //dance around looking for item2
00448       if ( i+1 < itemCount ) {
00449         if ( listArray[i+1] == item2 ) {
00450           index = i+1;
00451           return CUBIT_TRUE;
00452         }
00453       }
00454       if ( i > 0 ) {
00455         if ( listArray[i-1] == item2 ) {
00456           index = i;
00457           return CUBIT_TRUE;
00458         }
00459       }
00460       if ( ( i+1 == itemCount && listArray[0] == item2 ) 
00461            || ( i == 0 && listArray[itemCount-1] == item2 ) )
00462         {
00463           index = 0;
00464           return CUBIT_TRUE;
00465         }
00466     }
00467     }
00468   return CUBIT_FALSE;
00469 }
00470 
00471  
00474 //int DLList::move_between_items(void *item1, void *item2)
00475 //{
00476 //if ( !itemCount )
00477 //return CUBIT_FALSE;
00478 //
00479 //int match = 0; //which item did the previous index match?
00480 //
00482 //for ( int i = itemCount+1; i > 0; i--, step())
00483 //{
00484 //    if ( listArray[index] == item1 )
00485 //      if (match == 2)
00486 //  return CUBIT_TRUE;
00487 //      else 
00488 //  match = 1;
00489 //    else if ( listArray[index] == item2 )
00490 //      if (match == 1)
00491 //  return CUBIT_TRUE;
00492 //      else 
00493 //  match = 2;
00494 //    else 
00495 //      match = 0;
00496 //} 
00497 //
00499 //return CUBIT_FALSE;
00500 //}
00501 
00502 
00503 void* DLList::change_item_to ( void *new_item )
00504 {
00505   assert(new_item != NULL);
00506   if ( !itemCount )
00507     {
00508       PRINT_WARNING("DLList: Attempted update of empty list\n");
00509       return NULL;
00510     }
00511   void *temp = listArray[index];
00512     listArray[index] = new_item;
00513   return temp;
00514 }
00515 
00516 DLList& DLList::operator=(const DLList& from)
00517 {
00518   if (this != &from) {
00519     ArrayBasedContainer::operator=(from);
00520     index = from.index;
00521   }
00522   return *this;
00523 }
00524 
00525 void DLList::compress()
00526 { 
00527    int j = 0; 
00528    int i;
00529    int new_index = index;
00530 
00531    for ( i = 0; i < itemCount; i++ )
00532       if (listArray[i] != NULL)
00533       {
00534          listArray[j++] = listArray[i];
00535          if (i < index)
00536             new_index--;
00537       }
00538    
00539    itemCount = j; 
00540    index = new_index;
00541    if (index >= itemCount)
00542       index = 0;
00543    nullItem = 0;
00544 }
00545 
00546 void DLList::reverse()
00547 {
00548   int front = 0; 
00549   int tail  = itemCount-1;
00550   void *temp;
00551   
00552   while (front < tail) {
00553     temp             = listArray[front];
00554     listArray[front] = listArray[tail];
00555     listArray[tail]  = temp;
00556     tail--;
00557     front++;
00558   }
00559 }
00560 
00561 
00562 
00563 
00564 int DLList::operator<(  const DLList& list ) const
00565 {
00566     return (itemCount < list.itemCount) && (list >= *this);
00567 }
00568 
00569 int DLList::operator>(  const DLList& list ) const
00570 {
00571     return (itemCount > list.itemCount) && (*this >= list);
00572 }
00573 
00574 int DLList::operator<=( const DLList& list ) const
00575 {
00576     return list >= *this;
00577 }
00578 
00579 int DLList::operator>=( const DLList& list ) const
00580 {
00581     if( itemCount < list.itemCount ) return 0;
00582     
00583     DLList temp_list = list;
00584     for( int i = 0; i < itemCount; i++ )
00585         if( temp_list.move_to_item( listArray[i] ) ) temp_list.extract_link();
00586     
00587     return temp_list.itemCount == 0;  
00588 }
00589 
00590 int DLList::operator==( const DLList& list ) const
00591 {
00592     return (itemCount == list.itemCount) && (list >= *this);
00593 }
00594 
00595 int DLList::operator!=( const DLList& list ) const
00596 {
00597     return (itemCount != list.itemCount) || !(list >= *this);
00598 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines