Branch data Line data Source code
1 : : //- Class: DLList
2 : : //- Owner: Greg Sjaardema
3 : : //- Checked by:
4 : : //- Version: $Id:
5 : :
6 : : #include "DLList.hpp"
7 : :
8 : :
9 : : //- Constructor: Create a list with initial size {increment}. The list
10 : : //- will be grown by {increment} each time it is filled. Memory for the
11 : : //- list is not allocated until the first element is inserted using
12 : : //- {insertLink}.
13 : : //- If {increment} is zero, the default increment ({INCREMENT}) will be used
14 : : //- From an efficiency standpoint, it is very important that the
15 : : //- increment be set large enough to reduce the number of list
16 : : //- growths, but small enough to not waste memory.
17 : : //- It is more efficient to sligthly overestimate the increment than
18 : : //- to underestimate the increment.
19 : 588 : DLList::DLList ( int increment ): ArrayBasedContainer( increment )
20 : : {
21 : 294 : index = 0;
22 : 294 : nullItem = 0;
23 : 294 : }
24 : :
25 : : //- Copy Constructor
26 : 0 : DLList::DLList(const DLList& from) : ArrayBasedContainer ( from )
27 : : {
28 : 0 : index = from.index;
29 : 0 : listIsSorted = CUBIT_FALSE;
30 : 0 : }
31 : :
32 : 588 : DLList::~DLList()
33 : : {
34 [ - + ]: 294 : }
35 : :
36 : : //- put new item in list after current item and make it current
37 : 0 : void DLList::insert_link ( void* new_item )
38 : : {
39 [ # # ]: 0 : assert(new_item != NULL);
40 : : // see if the list must be lengthened
41 [ # # ]: 0 : if ( itemCount == listLength )
42 : : {
43 : 0 : lengthen_list();
44 : : }
45 : :
46 : : // set new index
47 : :
48 [ # # ]: 0 : if ( itemCount )
49 : : {
50 : 0 : index++;
51 : : }
52 : : else
53 : : {
54 : 0 : index = 0;
55 : : }
56 : :
57 : : // the item must be put in the current index, all higher
58 : : // indexes must be bubbled up one spot
59 : :
60 [ # # ]: 0 : for ( int i = itemCount; i > index; i-- )
61 : : {
62 : 0 : listArray[i] = listArray[i-1];
63 : : }
64 : :
65 : 0 : listArray[index] = new_item;
66 : 0 : itemCount++;
67 : 0 : }
68 : :
69 : : //- merge the input list, merge_list, with the current list, making
70 : : //- sure not to add duplicate items into the current list
71 : 0 : void DLList::merge_unique ( DLList& merge_list, int merge_list_unique )
72 : : {
73 : : // MJP Note:
74 : : // This procedure could be much more efficient if sorted lists
75 : : // are used. However, I need this procedure at this time to merge
76 : : // DLLists that already exist. These were not created as sorted
77 : : // lists (SDLLists) and it would be painful to convert them to
78 : : // SDLLists. It would be a lot easier if one could simply sort
79 : : // a DLList based on the numeric values of its items.
80 : :
81 : : // Save the current index of the merge_list
82 : 0 : int current_index = merge_list.index;
83 : 0 : int old_size = size();
84 : : int i, j, check_index;
85 : 0 : void* new_item = NULL;
86 : :
87 [ # # ]: 0 : for (i = 0; i < merge_list.size(); i++)
88 : : {
89 : : // Get the item from the merge_list and insert it into "this"
90 : : // list if it doesn't already exist there.
91 : 0 : new_item = merge_list.get_item_and_step();
92 [ # # ]: 0 : check_index = merge_list_unique ? old_size : size();
93 : :
94 [ # # ]: 0 : for ( j = 0; j < check_index; j++ )
95 : : {
96 [ # # ]: 0 : if ( listArray[j] == new_item )
97 : : {
98 : 0 : check_index = -1;
99 : 0 : break;
100 : : }
101 : : }
102 : :
103 [ # # ]: 0 : if ( check_index != -1 )
104 : 0 : append_link(new_item);
105 : : }
106 : :
107 : : // Restore the original index of the merge_list
108 : 0 : merge_list.index = current_index;
109 : 0 : }
110 : :
111 : :
112 : : //- put new item in list at index 0 and make it current
113 : 0 : void DLList::insert_link_first(void* new_item)
114 : : {
115 : : // set index to -1 ... index will be set to 0 in insert_link
116 : :
117 : 0 : index = -1;
118 : 0 : insert_link(new_item);
119 : 0 : }
120 : :
121 : : //- remove the item at the current location and return a pointer to it.
122 : : //- The next node becomes the current node
123 : : //- Returns {NULL} if there are no items in list
124 : 558 : void* DLList::cut_link ()
125 : : {
126 [ - + ]: 558 : if ( !itemCount )
127 : : {
128 [ # # ][ # # ]: 0 : PRINT_WARNING("Attempted link removal from empty DLList\n");
129 : 0 : return NULL;
130 : : }
131 : :
132 : : // save the current value
133 : :
134 : 558 : void *temp = listArray[index];
135 : :
136 : : // compress memory
137 : :
138 [ - + ]: 558 : for ( int i = index; i < itemCount-1; i++ )
139 : : {
140 : 0 : listArray[i] = listArray[i+1];
141 : : }
142 : :
143 : 558 : itemCount--;
144 [ + - ]: 558 : if ( index >= itemCount )
145 : : {
146 : 558 : index = 0;
147 : : }
148 : :
149 : 558 : return temp;
150 : : }
151 : :
152 : :
153 : : //- remove the item at the current location and return a pointer to it.
154 : : //- used for efficiency in cases where preservation of list order is not
155 : : //- important. moves last list item (itemCount - 1) to current index and
156 : : //- decrements itemCount. eliminates the need to perform the list bubble
157 : : //- down (i.e. cut_link) but sacrifices list order in the process. this
158 : : //- function should not be used when up-stream order from the removed node is
159 : : //- important. when processing a list using this function the user should
160 : : //- reset the list to the head (index = 0) before beginning to ensure all
161 : : //- list nodes are processed properly.
162 : : //- Returns {NULL} if there are no items in list
163 : 0 : void* DLList::extract_link ()
164 : : {
165 [ # # ]: 0 : if ( !itemCount ) {
166 [ # # ][ # # ]: 0 : PRINT_WARNING("Attempted link removal from empty DLList\n");
167 : 0 : return NULL;
168 : : }
169 : :
170 : : // save the current value
171 : 0 : void *temp = listArray[index];
172 : :
173 : : // assign last node to the current index
174 : 0 : listArray[index] = listArray[itemCount - 1];
175 : :
176 : : // decrement itemCount
177 : 0 : itemCount--;
178 [ # # ][ # # ]: 0 : if ( index == itemCount && index != 0) {
179 : : // The choices here are index at beginning or end.
180 : : // End seems to work better when 'extract' is being used
181 : : // with calls to 'move_to_item'.
182 : 0 : index--;
183 : : }
184 : :
185 : 0 : return temp;
186 : : }
187 : :
188 : :
189 : : //+//Added so list removals don't disturb current position. PRK 05-23-94
190 : : //+//Corrected for omitting the last item in the list. PRK 09-16-94
191 : : //+//Corrected for omitting before the current position. PRK 10-07-94
192 : : //- Finds instance of item by matching pointer and deleting all instances
193 : : //- of it from the list. The current position of the list is not changed.
194 : : //- Returns CUBIT_TRUE if the item was found and deleted, CUBIT_FALSE if not.
195 : 0 : CubitBoolean DLList::omit_link(void *oldObjPtr)
196 : : {
197 : : int scan_index;
198 : 0 : int squeeze_index = 0;
199 : 0 : CubitBoolean found = CUBIT_FALSE;
200 [ # # ]: 0 : for(scan_index = 0; scan_index < itemCount; ++scan_index)
201 : : {
202 [ # # ]: 0 : if(listArray[scan_index] == oldObjPtr)
203 : : {
204 : 0 : found = CUBIT_TRUE;
205 [ # # ]: 0 : if(index == scan_index) index = squeeze_index - 1;
206 : : }
207 : : else
208 : : {
209 [ # # ]: 0 : if(scan_index != squeeze_index)
210 : : {
211 : 0 : listArray[squeeze_index] = listArray[scan_index];
212 [ # # ]: 0 : if(index == scan_index) index = squeeze_index;
213 : : }
214 : 0 : ++squeeze_index;
215 : : }
216 : : }
217 : :
218 [ # # ]: 0 : if(found)
219 : : {
220 : 0 : itemCount = squeeze_index;
221 : : //+// If the first item was deleted and index pointed to it, make an
222 : : //+// adjustment here. If itemCount is zero, don't assign -1 again.
223 [ # # ]: 0 : if (index < 0)
224 [ # # ]: 0 : index = (itemCount) ? (itemCount - 1) : 0 ;
225 [ # # ]: 0 : if (index >= itemCount)
226 [ # # ]: 0 : index = (itemCount) ? (itemCount - 1) : 0 ;
227 : : }
228 : :
229 : 0 : return found;
230 : : }
231 : :
232 : :
233 : : //- Change the current item to a null pointer and return a pointer
234 : : //- to the item (before nulled). See the discussion for {nullItem}.
235 : 0 : void* DLList::nullify_link ()
236 : : {
237 [ # # ]: 0 : if ( !itemCount )
238 : : {
239 [ # # ][ # # ]: 0 : PRINT_WARNING("Attempted link nullify from empty DLList\n");
240 : 0 : return NULL;
241 : : }
242 : :
243 : : // save the current value
244 : 0 : nullItem = listArray[index];
245 : 0 : listArray[index] = 0;
246 : 0 : return nullItem;
247 : : }
248 : :
249 : 0 : void *DLList::prev_item ( int n ) const
250 : : {
251 [ # # ]: 0 : if ( !itemCount )
252 : : {
253 [ # # ][ # # ]: 0 : PRINT_WARNING("Attempted prev of empty DLList\n");
254 : 0 : return NULL;
255 : : }
256 : :
257 : : // return the proper index
258 : : // beware of negative n
259 : 0 : int new_index = index - n;
260 : :
261 [ # # ]: 0 : while (new_index < 0)
262 : 0 : new_index += itemCount;
263 : : // beware of negative n leading to new_index >itemCount
264 : 0 : new_index = new_index%itemCount;
265 : :
266 [ # # ]: 0 : assert(listArray[new_index] != NULL);
267 : 0 : return listArray[new_index];
268 : : }
269 : :
270 : 0 : void *DLList::step_and_get_item ()
271 : : {
272 [ # # ]: 0 : if ( !itemCount )
273 : : {
274 [ # # ][ # # ]: 0 : PRINT_WARNING("Attempted step_and_get from empty DLList\n");
275 : 0 : return NULL;
276 : : }
277 : :
278 [ # # ]: 0 : if (++index == itemCount)
279 : 0 : index=0;
280 : 0 : void *temp = listArray[index];
281 [ # # ]: 0 : assert(temp != NULL);
282 : 0 : return temp;
283 : : }
284 : :
285 : 0 : void *DLList::get_item_and_back ()
286 : : {
287 [ # # ]: 0 : if ( !itemCount )
288 : : {
289 [ # # ][ # # ]: 0 : PRINT_WARNING("Attempted get_and_back from empty DLList\n");
290 : 0 : return NULL;
291 : : }
292 : 0 : void *temp = listArray[index--];
293 [ # # ]: 0 : if (index < 0) index=itemCount-1;
294 [ # # ]: 0 : assert(temp != NULL);
295 : 0 : return temp;
296 : : }
297 : :
298 : : // move_to_and_remove_item searches for item and removes it from the list.
299 : : // If the item was found and removed it is returned, else NULL is returned.
300 : 0 : void* DLList::move_to_and_remove_item(void* item)
301 : : {
302 [ # # ]: 0 : if (move_to_item(item))
303 : 0 : return cut_link();
304 : : else
305 : 0 : return (void*) NULL;
306 : : }
307 : :
308 : 0 : int DLList::distance_to_nearby_item(void* body)
309 : : {
310 : 0 : int old_index = index;
311 : 0 : move_to_nearby_item( body );
312 : 0 : int distance = abs(index - old_index);
313 [ # # ]: 0 : if ( distance > itemCount / 2 )
314 : 0 : distance = itemCount - distance;
315 : 0 : index = old_index;
316 : 0 : return distance;
317 : : }
318 : :
319 : :
320 : 0 : CubitBoolean DLList::move_to_nearby_item ( void* item )
321 : : {
322 : : // empty list
323 [ # # ]: 0 : if (itemCount == 0)
324 : 0 : return CUBIT_FALSE;
325 : :
326 : : // Search current item first...
327 : 0 : void **ptr_up = &(listArray[index]);
328 [ # # ]: 0 : if (*ptr_up == item)
329 : 0 : return CUBIT_TRUE;
330 : :
331 : : int i_up, i_down;
332 : 0 : i_up = i_down = index;
333 : 0 : void **ptr_down = ptr_up;
334 : : while (1)
335 : : {
336 : : // check forward in the list
337 : : // increment
338 [ # # ]: 0 : if ( ++i_up < itemCount )
339 : 0 : ptr_up++;
340 : : else
341 : : {
342 : 0 : i_up = 0;
343 : 0 : ptr_up = listArray;
344 : : }
345 : : // check
346 [ # # ]: 0 : if ( *ptr_up == item )
347 : : {
348 : 0 : index = i_up;
349 : 0 : return CUBIT_TRUE;
350 : : }
351 [ # # ]: 0 : if ( i_up == i_down )
352 : : {
353 : 0 : return CUBIT_FALSE;
354 : : }
355 : :
356 : : // check backward in the list
357 : : // increment
358 [ # # ]: 0 : if ( --i_down >= 0 )
359 : 0 : ptr_down--;
360 : : else
361 : : {
362 : 0 : i_down = itemCount-1;
363 : 0 : ptr_down = &(listArray[i_down]);
364 : : }
365 : : // check
366 [ # # ]: 0 : if ( *ptr_down == item )
367 : : {
368 : 0 : index = i_down;
369 : 0 : return CUBIT_TRUE;
370 : : }
371 [ # # ]: 0 : if ( i_up == i_down )
372 : : {
373 : 0 : return CUBIT_FALSE;
374 : : }
375 : :
376 : 0 : }
377 : : }
378 : :
379 : 0 : CubitBoolean DLList::move_to_item ( void* item )
380 : : {
381 : 0 : int item_position = where_is_item( item );
382 [ # # ]: 0 : if ( item_position >= 0 ) {
383 : 0 : index = item_position;
384 : 0 : return CUBIT_TRUE;
385 : : }
386 : 0 : return CUBIT_FALSE;
387 : : }
388 : :
389 : 0 : int DLList::where_is_item( void *item ) const
390 : : {
391 : : // test for null input item
392 [ # # ]: 0 : assert(item != NULL);
393 : :
394 [ # # ]: 0 : if (itemCount == 0) return -1;
395 : :
396 : : // loop through list searching for item ...
397 : : // if found set index and return true
398 : :
399 : : // Search current item first...
400 : 0 : void **ptr = &(listArray[index]);
401 [ # # ]: 0 : if (*ptr == item) return index;
402 : :
403 : : // Now, search from current index to end of array
404 : : int i;
405 [ # # ]: 0 : for (i=index+1; i < itemCount; i++) {
406 : 0 : ptr++;
407 [ # # ]: 0 : if ( *ptr == item) {
408 : : // check if move_to_nearby would have been better
409 : : //if ( i - index > 1000 )
410 : : // PRINT_INFO(" Found, i = %d, index = %d, itemCount = %d.\n",
411 : : // i, index, itemCount);
412 : 0 : return i;
413 : : }
414 : : }
415 : :
416 : : // Now search from beginning of array to index...
417 : 0 : ptr = listArray;
418 [ # # ]: 0 : for (i = 0; i < index; i++) {
419 [ # # ]: 0 : if (*ptr == item) {
420 : : // check if move_to_nearby would have been better
421 : : // if ( i + itemCount - index > 1000 )
422 : : // PRINT_INFO(" Found, i = %d, index = %d, itemCount = %d.\n",
423 : : // i, index, itemCount);
424 : 0 : return i;
425 : : }
426 : 0 : ptr++;
427 : : }
428 : :
429 : : // item is not in array, return false
430 : 0 : return -1;
431 : : }
432 : :
433 : : // Special care for size two lists, so that wrap around is used only when
434 : : // needed. This works faster than the original (commented out below) for
435 : : // long lists
436 : 0 : CubitBoolean DLList::move_between_items(void *item1, void *item2)
437 : : {
438 : :
439 [ # # ][ # # ]: 0 : assert(item1 != NULL && item2 != NULL);
440 [ # # ]: 0 : if ( !itemCount )
441 : 0 : return CUBIT_FALSE;
442 : :
443 [ # # ]: 0 : for ( int i = 0; i < itemCount; i++ )
444 : : {
445 [ # # ]: 0 : if ( listArray[i] == item1 )
446 : : {
447 : : //dance around looking for item2
448 [ # # ]: 0 : if ( i+1 < itemCount ) {
449 [ # # ]: 0 : if ( listArray[i+1] == item2 ) {
450 : 0 : index = i+1;
451 : 0 : return CUBIT_TRUE;
452 : : }
453 : : }
454 [ # # ]: 0 : if ( i > 0 ) {
455 [ # # ]: 0 : if ( listArray[i-1] == item2 ) {
456 : 0 : index = i;
457 : 0 : return CUBIT_TRUE;
458 : : }
459 : : }
460 [ # # ][ # # ]: 0 : if ( ( i+1 == itemCount && listArray[0] == item2 )
461 [ # # ][ # # ]: 0 : || ( i == 0 && listArray[itemCount-1] == item2 ) )
462 : : {
463 : 0 : index = 0;
464 : 0 : return CUBIT_TRUE;
465 : : }
466 : : }
467 : : }
468 : 0 : return CUBIT_FALSE;
469 : : }
470 : :
471 : :
472 : : //// following is somewhat slower for long lists, but if you wanted to search
473 : : //// for long patterns a modification of it would be good
474 : : //int DLList::move_between_items(void *item1, void *item2)
475 : : //{
476 : : //if ( !itemCount )
477 : : //return CUBIT_FALSE;
478 : : //
479 : : //int match = 0; //which item did the previous index match?
480 : : //
481 : : //// search for item1 and item2 consecutive
482 : : //for ( int i = itemCount+1; i > 0; i--, step())
483 : : //{
484 : : // if ( listArray[index] == item1 )
485 : : // if (match == 2)
486 : : // return CUBIT_TRUE;
487 : : // else
488 : : // match = 1;
489 : : // else if ( listArray[index] == item2 )
490 : : // if (match == 1)
491 : : // return CUBIT_TRUE;
492 : : // else
493 : : // match = 2;
494 : : // else
495 : : // match = 0;
496 : : //}
497 : : //
498 : : //// not found consecutive
499 : : //return CUBIT_FALSE;
500 : : //}
501 : :
502 : :
503 : 0 : void* DLList::change_item_to ( void *new_item )
504 : : {
505 [ # # ]: 0 : assert(new_item != NULL);
506 [ # # ]: 0 : if ( !itemCount )
507 : : {
508 [ # # ][ # # ]: 0 : PRINT_WARNING("DLList: Attempted update of empty list\n");
509 : 0 : return NULL;
510 : : }
511 : 0 : void *temp = listArray[index];
512 : 0 : listArray[index] = new_item;
513 : 0 : return temp;
514 : : }
515 : :
516 : 0 : DLList& DLList::operator=(const DLList& from)
517 : : {
518 [ # # ]: 0 : if (this != &from) {
519 : 0 : ArrayBasedContainer::operator=(from);
520 : 0 : index = from.index;
521 : : }
522 : 0 : return *this;
523 : : }
524 : :
525 : 0 : void DLList::compress()
526 : : {
527 : 0 : int j = 0;
528 : : int i;
529 : 0 : int new_index = index;
530 : :
531 [ # # ]: 0 : for ( i = 0; i < itemCount; i++ )
532 [ # # ]: 0 : if (listArray[i] != NULL)
533 : : {
534 : 0 : listArray[j++] = listArray[i];
535 [ # # ]: 0 : if (i < index)
536 : 0 : new_index--;
537 : : }
538 : :
539 : 0 : itemCount = j;
540 : 0 : index = new_index;
541 [ # # ]: 0 : if (index >= itemCount)
542 : 0 : index = 0;
543 : 0 : nullItem = 0;
544 : 0 : }
545 : :
546 : 0 : void DLList::reverse()
547 : : {
548 : 0 : int front = 0;
549 : 0 : int tail = itemCount-1;
550 : : void *temp;
551 : :
552 [ # # ]: 0 : while (front < tail) {
553 : 0 : temp = listArray[front];
554 : 0 : listArray[front] = listArray[tail];
555 : 0 : listArray[tail] = temp;
556 : 0 : tail--;
557 : 0 : front++;
558 : : }
559 : 0 : }
560 : :
561 : :
562 : :
563 : :
564 : 0 : int DLList::operator<( const DLList& list ) const
565 : : {
566 [ # # ][ # # ]: 0 : return (itemCount < list.itemCount) && (list >= *this);
567 : : }
568 : :
569 : 0 : int DLList::operator>( const DLList& list ) const
570 : : {
571 [ # # ][ # # ]: 0 : return (itemCount > list.itemCount) && (*this >= list);
572 : : }
573 : :
574 : 0 : int DLList::operator<=( const DLList& list ) const
575 : : {
576 : 0 : return list >= *this;
577 : : }
578 : :
579 : 0 : int DLList::operator>=( const DLList& list ) const
580 : : {
581 [ # # ]: 0 : if( itemCount < list.itemCount ) return 0;
582 : :
583 [ # # ]: 0 : DLList temp_list = list;
584 [ # # ]: 0 : for( int i = 0; i < itemCount; i++ )
585 [ # # ][ # # ]: 0 : if( temp_list.move_to_item( listArray[i] ) ) temp_list.extract_link();
[ # # ]
586 : :
587 [ # # ]: 0 : return temp_list.itemCount == 0;
588 : : }
589 : :
590 : 0 : int DLList::operator==( const DLList& list ) const
591 : : {
592 [ # # ][ # # ]: 0 : return (itemCount == list.itemCount) && (list >= *this);
593 : : }
594 : :
595 : 0 : int DLList::operator!=( const DLList& list ) const
596 : : {
597 [ # # ][ # # ]: 0 : return (itemCount != list.itemCount) || !(list >= *this);
598 : : }
|
