1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
//- Class: SDLList<--- Skipping configuration 'DBL_MAX' since the value of 'DBL_MAX' is unknown. Use -D if you want to check it. You can use -U to skip it explicitly.<--- Skipping configuration 'DBL_MIN' since the value of 'DBL_MIN' is unknown. Use -D if you want to check it. You can use -U to skip it explicitly.<--- Skipping configuration 'M_PI' since the value of 'M_PI' is unknown. Use -D if you want to check it. You can use -U to skip it explicitly.
//- Owner: Greg Sjaardema
//- Checked by:
//- Version: $Id: 

#include "SDLList.hpp"


//- Constructor: Create a list with initial size {increment}. The list
//- will be grown by {increment} each time it is filled. Memory for the
//- list is not allocated until the first element is inserted using
//- {insertLink}. 
//- If {increment} is zero, the default increment ({INCREMENT}) will be used
//- From an efficiency standpoint, it is very important that the 
//- increment be set large enough to reduce the number of list 
//- growths, but small enough to not waste memory.
//- It is more efficient to sligthly overestimate the increment than 
//- to underestimate the increment.
SDLList::SDLList ( int increment ): DLList( increment )<--- Member variable 'SDLList::compare_order_obj' is not initialized in the constructor.<--- Member variable 'SDLList::compare_order' is not initialized in the constructor.<--- Member variable 'SDLList::compare_equal' is not initialized in the constructor.
{}

//- Copy Constructor
SDLList::SDLList(const SDLList& from) : DLList(from)<--- Member variable 'SDLList::compare_order_obj' is not initialized in the constructor.<--- Member variable 'SDLList::compare_order' is not initialized in the constructor.<--- Member variable 'SDLList::compare_equal' is not initialized in the constructor.
{
  listIsSorted = from.listIsSorted;
}

//- Copy Constructor
SDLList::SDLList(const DLList& from) : DLList(from)<--- Member variable 'SDLList::compare_order_obj' is not initialized in the constructor.<--- Member variable 'SDLList::compare_order' is not initialized in the constructor.<--- Member variable 'SDLList::compare_equal' is not initialized in the constructor.
{
  listIsSorted = CUBIT_FALSE;
}

SDLList::~SDLList()
{
}

//- put new item in list after current item and make it current
void SDLList::insert_link ( void* new_item )
{
  DLList::insert_link(new_item);
  listIsSorted = CUBIT_FALSE;
}

//- merge the input list, merge_list, with the current list, making
//- sure not to add duplicate items into the current list
void SDLList::merge_unique ( DLList& merge_list, int merge_list_unique )
{
  DLList::merge_unique(merge_list, merge_list_unique);
  listIsSorted = CUBIT_FALSE;
}

//- put new item in list at index 0 and make it current
void SDLList::insert_link_first(void* new_item)
{
  DLList::insert_link_first(new_item);
  listIsSorted = CUBIT_FALSE;
}

//- remove the item at the current location and return a pointer to it.
//- used for efficiency in cases where preservation of list order is not
//- important.  moves last list item (itemCount - 1) to current index and
//- decrements itemCount.  eliminates the need to perform the list bubble
//- down (i.e. cut_link) but sacrifices list order in the process.  this
//- function should not be used when up-stream order from the removed node is
//- important.  when processing a list using this function the user should
//- reset the list to the head (index = 0) before beginning to ensure all
//- list nodes are processed properly.
//- Returns {NULL} if there are no items in list
void* SDLList::extract_link ()
{
  listIsSorted = CUBIT_FALSE;
  return DLList::extract_link();
}


void* SDLList::change_item_to ( void *new_item )
{
  listIsSorted = CUBIT_FALSE;
  return DLList::change_item_to(new_item);
}

// sort_list sorts ordered lists in an ascending or descending fashion
// (depending on the assignment of compare_order function pointer).  The
// list is sorted using a standard Heap Sort algorithm ("Algorithms in C++",
// Robert Sedgewick).
void SDLList::sort_list()
{
  listIsSorted = CUBIT_TRUE;
  if (itemCount > 1)
  {
    int mid = (itemCount >> 1) + 1;
    int ir = itemCount;
    void* temp_element = NULL;

    while(CUBIT_TRUE)
    {
      if (mid > 1)
      {
	mid--;
	temp_element = listArray[mid - 1];
      }
      else
      {
	ir--;
	temp_element = listArray[ir];
	listArray[ir] = listArray[0];
	if (ir == 1)
	{
	  listArray[0] = temp_element;
	  return;
	}
      }

      int i = mid;
      int j = mid + mid;

      while (j <= ir)
      {
	if (j < ir)
	{
	   if ((*compare_order_obj)(listArray[j], listArray[j - 1])) j++;
	}
	if ((*compare_order_obj)(listArray[j - 1], temp_element))
	{
	  listArray[i - 1] = listArray[j - 1];
	  i = j;
	  j += j;
	}
	else
	{
	  j = ir + 1;
	}
      }

      listArray[i - 1] = temp_element;
    }
  }
}

// binary_search performs a standard array based binary search (essentially
// bisection) to bracket/locate an insert/search position.
void SDLList::binary_search(int* min_location, int* max_location, void* item) 
  const
{
  // sort the list if necessary and initialize binary search parameters
  assert( listIsSorted );

  *min_location = 0;
  *max_location = itemCount - 1;
  int bracket_width = *max_location;
  int compare_location = itemCount >> 1;

    // bracket the location (binary search)

  while(bracket_width > 1)
  {
    if ((*compare_order)(item, listArray[compare_location]))
    {
      *min_location     = compare_location;
      bracket_width     = *max_location - *min_location;
      compare_location += (bracket_width >> 1);
    }
    else
    {
      *max_location     = compare_location;
      bracket_width     = *max_location - *min_location;
      compare_location -= (bracket_width >> 1);
    }
  }

    // if there are duplicate entries in the list, bracket them with min_location
    // and max_location
  while (  *min_location > 0 && (*compare_equal)(item, listArray[*min_location-1]))
    (*min_location)--;

    // (max_location already backets the item)
  
}

// move_to_item_sorted finds the index of the given value, then sets the 
// current index there
CubitBoolean SDLList::move_to_item_sorted(void* value)
{
  int item_index;
  CubitBoolean item_exists = where_is_item_sorted( value, item_index );
  index = item_index; // always
  return item_exists;
}


// where_is_item_sorted performs a binary search on the list to locate value.
// If the item with value is found then the current index is set to the item's
// index and TRUE is returned.  If item is not found then index is set to 
// just before where the item would be, and FALSE is returned.
CubitBoolean SDLList::where_is_item_sorted( void *value, int &insert_index ) 
{
  // if entries exist then find insertion index

  if ( 0 == itemCount ) {
    insert_index = 0;
    return CUBIT_FALSE;
  }
  
  if (!listIsSorted)
  {
    sort_list();
  }

  // perform the binary search
  
  int min_location, max_location;
  binary_search(&min_location, &max_location, value);
  
  // if item occupies a place in the list then min_location and/or
  // max_location specifies the location ... otherwise item was not found
  
  if ((*compare_equal)(value, listArray[min_location]))
    {
      insert_index = min_location;
      return CUBIT_TRUE;
    }
  else if ((*compare_equal)(value, listArray[max_location]))
    {
      insert_index = max_location;
      return CUBIT_TRUE;
    }  
  // else not found, 
  insert_index = min_location;
  // is it beyond the end?
  if (itemCount == max_location ) {
    if ((*compare_order)(value, listArray[max_location]))
      insert_index = itemCount;
  }
  return CUBIT_FALSE;
}


// insert_item_sorted performs a binary search to find the insert
// index in the list for new_item. The function then calls insert_link
// after setting the index to the insert position - 1.
void SDLList::insert_item_sorted(void* value, void* new_item)<--- The function 'insert_item_sorted' is never used.
{
  assert(new_item != NULL);

  // if entries exist then find insertion index

  if ( itemCount > 0)
  {
    // perform the binary search and set index to the min_location

    int min_location, max_location;
    if (!listIsSorted)
    {
      sort_list();
    }
    binary_search(&min_location, &max_location, value);
    index = min_location;

    // test for special cases (insert first or last)

    if (index == 0)
    {
      // if new_items value < first (ascending) or new_items value > first
      // (descending) then insert as first item (index = -1)

      if (!(*compare_order)(value, listArray[index]))
      {
        index--;
      }
    }
    if (index == (itemCount - 2))
    {
      // if new_items value > last (ascending) or new_items value < last
      // (descending) then insert as last item (index = itemCount - 1)

      if ((*compare_order)(value, listArray[index + 1]))
      {
        index++;
      }
    }
  }

  // insert new_item
  insert_link(new_item);
  listIsSorted = CUBIT_TRUE;
}

// move_to_and_remove_item_sorted uses move_to_item_sorted function to perform
// a binary search to locate the objects's index for which the objects
// functionName() = value.  If found, the objects index is set as the current
// index. Then cut_link is called to remove the object from the list.
void* SDLList::move_to_and_remove_item_sorted(void* value)<--- The function 'move_to_and_remove_item_sorted' is never used.
{
  if (move_to_item_sorted(value))
    return cut_link();
  else
    return (void*) NULL;
}


SDLList& SDLList::operator=(const SDLList& from)
{
  if (this != &from) {
    DLList::operator=(from);
  }
  return *this;
}