cgma
SDLList.cpp
Go to the documentation of this file.
00001 //- Class: SDLList
00002 //- Owner: Greg Sjaardema
00003 //- Checked by:
00004 //- Version: $Id: 
00005 
00006 #include "SDLList.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 SDLList::SDLList ( int increment ): DLList( increment )
00020 {}
00021 
00022 //- Copy Constructor
00023 SDLList::SDLList(const SDLList& from) : DLList(from)
00024 {
00025   listIsSorted = from.listIsSorted;
00026 }
00027 
00028 //- Copy Constructor
00029 SDLList::SDLList(const DLList& from) : DLList(from)
00030 {
00031   listIsSorted = CUBIT_FALSE;
00032 }
00033 
00034 SDLList::~SDLList()
00035 {
00036 }
00037 
00038 //- put new item in list after current item and make it current
00039 void SDLList::insert_link ( void* new_item )
00040 {
00041   DLList::insert_link(new_item);
00042   listIsSorted = CUBIT_FALSE;
00043 }
00044 
00045 //- merge the input list, merge_list, with the current list, making
00046 //- sure not to add duplicate items into the current list
00047 void SDLList::merge_unique ( DLList& merge_list, int merge_list_unique )
00048 {
00049   DLList::merge_unique(merge_list, merge_list_unique);
00050   listIsSorted = CUBIT_FALSE;
00051 }
00052 
00053 //- put new item in list at index 0 and make it current
00054 void SDLList::insert_link_first(void* new_item)
00055 {
00056   DLList::insert_link_first(new_item);
00057   listIsSorted = CUBIT_FALSE;
00058 }
00059 
00060 //- remove the item at the current location and return a pointer to it.
00061 //- used for efficiency in cases where preservation of list order is not
00062 //- important.  moves last list item (itemCount - 1) to current index and
00063 //- decrements itemCount.  eliminates the need to perform the list bubble
00064 //- down (i.e. cut_link) but sacrifices list order in the process.  this
00065 //- function should not be used when up-stream order from the removed node is
00066 //- important.  when processing a list using this function the user should
00067 //- reset the list to the head (index = 0) before beginning to ensure all
00068 //- list nodes are processed properly.
00069 //- Returns {NULL} if there are no items in list
00070 void* SDLList::extract_link ()
00071 {
00072   listIsSorted = CUBIT_FALSE;
00073   return DLList::extract_link();
00074 }
00075 
00076 
00077 void* SDLList::change_item_to ( void *new_item )
00078 {
00079   listIsSorted = CUBIT_FALSE;
00080   return DLList::change_item_to(new_item);
00081 }
00082 
00083 // sort_list sorts ordered lists in an ascending or descending fashion
00084 // (depending on the assignment of compare_order function pointer).  The
00085 // list is sorted using a standard Heap Sort algorithm ("Algorithms in C++",
00086 // Robert Sedgewick).
00087 void SDLList::sort_list()
00088 {
00089   listIsSorted = CUBIT_TRUE;
00090   if (itemCount > 1)
00091   {
00092     int mid = (itemCount >> 1) + 1;
00093     int ir = itemCount;
00094     void* temp_element = NULL;
00095 
00096     while(CUBIT_TRUE)
00097     {
00098       if (mid > 1)
00099       {
00100     mid--;
00101     temp_element = listArray[mid - 1];
00102       }
00103       else
00104       {
00105     ir--;
00106     temp_element = listArray[ir];
00107     listArray[ir] = listArray[0];
00108     if (ir == 1)
00109     {
00110       listArray[0] = temp_element;
00111       return;
00112     }
00113       }
00114 
00115       int i = mid;
00116       int j = mid + mid;
00117 
00118       while (j <= ir)
00119       {
00120     if (j < ir)
00121     {
00122        if ((*compare_order_obj)(listArray[j], listArray[j - 1])) j++;
00123     }
00124     if ((*compare_order_obj)(listArray[j - 1], temp_element))
00125     {
00126       listArray[i - 1] = listArray[j - 1];
00127       i = j;
00128       j += j;
00129     }
00130     else
00131     {
00132       j = ir + 1;
00133     }
00134       }
00135 
00136       listArray[i - 1] = temp_element;
00137     }
00138   }
00139 }
00140 
00141 // binary_search performs a standard array based binary search (essentially
00142 // bisection) to bracket/locate an insert/search position.
00143 void SDLList::binary_search(int* min_location, int* max_location, void* item) 
00144   const
00145 {
00146   // sort the list if necessary and initialize binary search parameters
00147   assert( listIsSorted );
00148 
00149   *min_location = 0;
00150   *max_location = itemCount - 1;
00151   int bracket_width = *max_location;
00152   int compare_location = itemCount >> 1;
00153 
00154     // bracket the location (binary search)
00155 
00156   while(bracket_width > 1)
00157   {
00158     if ((*compare_order)(item, listArray[compare_location]))
00159     {
00160       *min_location     = compare_location;
00161       bracket_width     = *max_location - *min_location;
00162       compare_location += (bracket_width >> 1);
00163     }
00164     else
00165     {
00166       *max_location     = compare_location;
00167       bracket_width     = *max_location - *min_location;
00168       compare_location -= (bracket_width >> 1);
00169     }
00170   }
00171 
00172     // if there are duplicate entries in the list, bracket them with min_location
00173     // and max_location
00174   while (  *min_location > 0 && (*compare_equal)(item, listArray[*min_location-1]))
00175     (*min_location)--;
00176 
00177     // (max_location already backets the item)
00178   
00179 }
00180 
00181 // move_to_item_sorted finds the index of the given value, then sets the 
00182 // current index there
00183 CubitBoolean SDLList::move_to_item_sorted(void* value)
00184 {
00185   int item_index;
00186   CubitBoolean item_exists = where_is_item_sorted( value, item_index );
00187   index = item_index; // always
00188   return item_exists;
00189 }
00190 
00191 
00192 // where_is_item_sorted performs a binary search on the list to locate value.
00193 // If the item with value is found then the current index is set to the item's
00194 // index and TRUE is returned.  If item is not found then index is set to 
00195 // just before where the item would be, and FALSE is returned.
00196 CubitBoolean SDLList::where_is_item_sorted( void *value, int &insert_index ) 
00197 {
00198   // if entries exist then find insertion index
00199 
00200   if ( 0 == itemCount ) {
00201     insert_index = 0;
00202     return CUBIT_FALSE;
00203   }
00204   
00205   if (!listIsSorted)
00206   {
00207     sort_list();
00208   }
00209 
00210   // perform the binary search
00211   
00212   int min_location, max_location;
00213   binary_search(&min_location, &max_location, value);
00214   
00215   // if item occupies a place in the list then min_location and/or
00216   // max_location specifies the location ... otherwise item was not found
00217   
00218   if ((*compare_equal)(value, listArray[min_location]))
00219     {
00220       insert_index = min_location;
00221       return CUBIT_TRUE;
00222     }
00223   else if ((*compare_equal)(value, listArray[max_location]))
00224     {
00225       insert_index = max_location;
00226       return CUBIT_TRUE;
00227     }  
00228   // else not found, 
00229   insert_index = min_location;
00230   // is it beyond the end?
00231   if (itemCount == max_location ) {
00232     if ((*compare_order)(value, listArray[max_location]))
00233       insert_index = itemCount;
00234   }
00235   return CUBIT_FALSE;
00236 }
00237 
00238 
00239 // insert_item_sorted performs a binary search to find the insert
00240 // index in the list for new_item. The function then calls insert_link
00241 // after setting the index to the insert position - 1.
00242 void SDLList::insert_item_sorted(void* value, void* new_item)
00243 {
00244   assert(new_item != NULL);
00245 
00246   // if entries exist then find insertion index
00247 
00248   if ( itemCount > 0)
00249   {
00250     // perform the binary search and set index to the min_location
00251 
00252     int min_location, max_location;
00253     if (!listIsSorted)
00254     {
00255       sort_list();
00256     }
00257     binary_search(&min_location, &max_location, value);
00258     index = min_location;
00259 
00260     // test for special cases (insert first or last)
00261 
00262     if (index == 0)
00263     {
00264       // if new_items value < first (ascending) or new_items value > first
00265       // (descending) then insert as first item (index = -1)
00266 
00267       if (!(*compare_order)(value, listArray[index]))
00268       {
00269         index--;
00270       }
00271     }
00272     if (index == (itemCount - 2))
00273     {
00274       // if new_items value > last (ascending) or new_items value < last
00275       // (descending) then insert as last item (index = itemCount - 1)
00276 
00277       if ((*compare_order)(value, listArray[index + 1]))
00278       {
00279         index++;
00280       }
00281     }
00282   }
00283 
00284   // insert new_item
00285   insert_link(new_item);
00286   listIsSorted = CUBIT_TRUE;
00287 }
00288 
00289 // move_to_and_remove_item_sorted uses move_to_item_sorted function to perform
00290 // a binary search to locate the objects's index for which the objects
00291 // functionName() = value.  If found, the objects index is set as the current
00292 // index. Then cut_link is called to remove the object from the list.
00293 void* SDLList::move_to_and_remove_item_sorted(void* value)
00294 {
00295   if (move_to_item_sorted(value))
00296     return cut_link();
00297   else
00298     return (void*) NULL;
00299 }
00300 
00301 
00302 SDLList& SDLList::operator=(const SDLList& from)
00303 {
00304   if (this != &from) {
00305     DLList::operator=(from);
00306   }
00307   return *this;
00308 }
00309 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines