Branch data Line data Source code
1 : : //- Class: SDLList
2 : : //- Owner: Greg Sjaardema
3 : : //- Checked by:
4 : : //- Version: $Id:
5 : :
6 : : #include "SDLList.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 : SDLList::SDLList ( int increment ): DLList( increment )
20 : 294 : {}
21 : :
22 : : //- Copy Constructor
23 : 0 : SDLList::SDLList(const SDLList& from) : DLList(from)
24 : : {
25 : 0 : listIsSorted = from.listIsSorted;
26 : 0 : }
27 : :
28 : : //- Copy Constructor
29 : 0 : SDLList::SDLList(const DLList& from) : DLList(from)
30 : : {
31 : 0 : listIsSorted = CUBIT_FALSE;
32 : 0 : }
33 : :
34 : 588 : SDLList::~SDLList()
35 : : {
36 [ - + ]: 294 : }
37 : :
38 : : //- put new item in list after current item and make it current
39 : 0 : void SDLList::insert_link ( void* new_item )
40 : : {
41 : 0 : DLList::insert_link(new_item);
42 : 0 : listIsSorted = CUBIT_FALSE;
43 : 0 : }
44 : :
45 : : //- merge the input list, merge_list, with the current list, making
46 : : //- sure not to add duplicate items into the current list
47 : 0 : void SDLList::merge_unique ( DLList& merge_list, int merge_list_unique )
48 : : {
49 : 0 : DLList::merge_unique(merge_list, merge_list_unique);
50 : 0 : listIsSorted = CUBIT_FALSE;
51 : 0 : }
52 : :
53 : : //- put new item in list at index 0 and make it current
54 : 0 : void SDLList::insert_link_first(void* new_item)
55 : : {
56 : 0 : DLList::insert_link_first(new_item);
57 : 0 : listIsSorted = CUBIT_FALSE;
58 : 0 : }
59 : :
60 : : //- remove the item at the current location and return a pointer to it.
61 : : //- used for efficiency in cases where preservation of list order is not
62 : : //- important. moves last list item (itemCount - 1) to current index and
63 : : //- decrements itemCount. eliminates the need to perform the list bubble
64 : : //- down (i.e. cut_link) but sacrifices list order in the process. this
65 : : //- function should not be used when up-stream order from the removed node is
66 : : //- important. when processing a list using this function the user should
67 : : //- reset the list to the head (index = 0) before beginning to ensure all
68 : : //- list nodes are processed properly.
69 : : //- Returns {NULL} if there are no items in list
70 : 0 : void* SDLList::extract_link ()
71 : : {
72 : 0 : listIsSorted = CUBIT_FALSE;
73 : 0 : return DLList::extract_link();
74 : : }
75 : :
76 : :
77 : 0 : void* SDLList::change_item_to ( void *new_item )
78 : : {
79 : 0 : listIsSorted = CUBIT_FALSE;
80 : 0 : return DLList::change_item_to(new_item);
81 : : }
82 : :
83 : : // sort_list sorts ordered lists in an ascending or descending fashion
84 : : // (depending on the assignment of compare_order function pointer). The
85 : : // list is sorted using a standard Heap Sort algorithm ("Algorithms in C++",
86 : : // Robert Sedgewick).
87 : 96 : void SDLList::sort_list()
88 : : {
89 : 96 : listIsSorted = CUBIT_TRUE;
90 [ + + ]: 96 : if (itemCount > 1)
91 : : {
92 : 74 : int mid = (itemCount >> 1) + 1;
93 : 74 : int ir = itemCount;
94 : 74 : void* temp_element = NULL;
95 : :
96 : : while(CUBIT_TRUE)
97 : : {
98 [ + + ]: 730 : if (mid > 1)
99 : : {
100 : 268 : mid--;
101 : 268 : temp_element = listArray[mid - 1];
102 : : }
103 : : else
104 : : {
105 : 462 : ir--;
106 : 462 : temp_element = listArray[ir];
107 : 462 : listArray[ir] = listArray[0];
108 [ + + ]: 462 : if (ir == 1)
109 : : {
110 : 74 : listArray[0] = temp_element;
111 : 74 : return;
112 : : }
113 : : }
114 : :
115 : 656 : int i = mid;
116 : 656 : int j = mid + mid;
117 : :
118 [ + + ]: 1748 : while (j <= ir)
119 : : {
120 [ + + ]: 1092 : if (j < ir)
121 : : {
122 [ + + ]: 848 : if ((*compare_order_obj)(listArray[j], listArray[j - 1])) j++;
123 : : }
124 [ + + ]: 1092 : if ((*compare_order_obj)(listArray[j - 1], temp_element))
125 : : {
126 : 890 : listArray[i - 1] = listArray[j - 1];
127 : 890 : i = j;
128 : 890 : j += j;
129 : : }
130 : : else
131 : : {
132 : 202 : j = ir + 1;
133 : : }
134 : : }
135 : :
136 : 656 : listArray[i - 1] = temp_element;
137 : 656 : }
138 : : }
139 : : }
140 : :
141 : : // binary_search performs a standard array based binary search (essentially
142 : : // bisection) to bracket/locate an insert/search position.
143 : 0 : void SDLList::binary_search(int* min_location, int* max_location, void* item)
144 : : const
145 : : {
146 : : // sort the list if necessary and initialize binary search parameters
147 [ # # ]: 0 : assert( listIsSorted );
148 : :
149 : 0 : *min_location = 0;
150 : 0 : *max_location = itemCount - 1;
151 : 0 : int bracket_width = *max_location;
152 : 0 : int compare_location = itemCount >> 1;
153 : :
154 : : // bracket the location (binary search)
155 : :
156 [ # # ]: 0 : while(bracket_width > 1)
157 : : {
158 [ # # ]: 0 : if ((*compare_order)(item, listArray[compare_location]))
159 : : {
160 : 0 : *min_location = compare_location;
161 : 0 : bracket_width = *max_location - *min_location;
162 : 0 : compare_location += (bracket_width >> 1);
163 : : }
164 : : else
165 : : {
166 : 0 : *max_location = compare_location;
167 : 0 : bracket_width = *max_location - *min_location;
168 : 0 : compare_location -= (bracket_width >> 1);
169 : : }
170 : : }
171 : :
172 : : // if there are duplicate entries in the list, bracket them with min_location
173 : : // and max_location
174 [ # # ][ # # ]: 0 : while ( *min_location > 0 && (*compare_equal)(item, listArray[*min_location-1]))
[ # # ]
175 : 0 : (*min_location)--;
176 : :
177 : : // (max_location already backets the item)
178 : :
179 : 0 : }
180 : :
181 : : // move_to_item_sorted finds the index of the given value, then sets the
182 : : // current index there
183 : 0 : CubitBoolean SDLList::move_to_item_sorted(void* value)
184 : : {
185 : : int item_index;
186 [ # # ]: 0 : CubitBoolean item_exists = where_is_item_sorted( value, item_index );
187 : 0 : index = item_index; // always
188 : 0 : return item_exists;
189 : : }
190 : :
191 : :
192 : : // where_is_item_sorted performs a binary search on the list to locate value.
193 : : // If the item with value is found then the current index is set to the item's
194 : : // index and TRUE is returned. If item is not found then index is set to
195 : : // just before where the item would be, and FALSE is returned.
196 : 0 : CubitBoolean SDLList::where_is_item_sorted( void *value, int &insert_index )
197 : : {
198 : : // if entries exist then find insertion index
199 : :
200 [ # # ]: 0 : if ( 0 == itemCount ) {
201 : 0 : insert_index = 0;
202 : 0 : return CUBIT_FALSE;
203 : : }
204 : :
205 [ # # ]: 0 : if (!listIsSorted)
206 : : {
207 [ # # ]: 0 : sort_list();
208 : : }
209 : :
210 : : // perform the binary search
211 : :
212 : : int min_location, max_location;
213 [ # # ]: 0 : binary_search(&min_location, &max_location, value);
214 : :
215 : : // if item occupies a place in the list then min_location and/or
216 : : // max_location specifies the location ... otherwise item was not found
217 : :
218 [ # # ][ # # ]: 0 : if ((*compare_equal)(value, listArray[min_location]))
219 : : {
220 : 0 : insert_index = min_location;
221 : 0 : return CUBIT_TRUE;
222 : : }
223 [ # # ][ # # ]: 0 : else if ((*compare_equal)(value, listArray[max_location]))
224 : : {
225 : 0 : insert_index = max_location;
226 : 0 : return CUBIT_TRUE;
227 : : }
228 : : // else not found,
229 : 0 : insert_index = min_location;
230 : : // is it beyond the end?
231 [ # # ]: 0 : if (itemCount == max_location ) {
232 [ # # ][ # # ]: 0 : if ((*compare_order)(value, listArray[max_location]))
233 : 0 : insert_index = itemCount;
234 : : }
235 : 0 : return CUBIT_FALSE;
236 : : }
237 : :
238 : :
239 : : // insert_item_sorted performs a binary search to find the insert
240 : : // index in the list for new_item. The function then calls insert_link
241 : : // after setting the index to the insert position - 1.
242 : 0 : void SDLList::insert_item_sorted(void* value, void* new_item)
243 : : {
244 [ # # ]: 0 : assert(new_item != NULL);
245 : :
246 : : // if entries exist then find insertion index
247 : :
248 [ # # ]: 0 : if ( itemCount > 0)
249 : : {
250 : : // perform the binary search and set index to the min_location
251 : :
252 : : int min_location, max_location;
253 [ # # ]: 0 : if (!listIsSorted)
254 : : {
255 [ # # ]: 0 : sort_list();
256 : : }
257 [ # # ]: 0 : binary_search(&min_location, &max_location, value);
258 : 0 : index = min_location;
259 : :
260 : : // test for special cases (insert first or last)
261 : :
262 [ # # ]: 0 : if (index == 0)
263 : : {
264 : : // if new_items value < first (ascending) or new_items value > first
265 : : // (descending) then insert as first item (index = -1)
266 : :
267 [ # # ][ # # ]: 0 : if (!(*compare_order)(value, listArray[index]))
268 : : {
269 : 0 : index--;
270 : : }
271 : : }
272 [ # # ]: 0 : if (index == (itemCount - 2))
273 : : {
274 : : // if new_items value > last (ascending) or new_items value < last
275 : : // (descending) then insert as last item (index = itemCount - 1)
276 : :
277 [ # # ][ # # ]: 0 : if ((*compare_order)(value, listArray[index + 1]))
278 : : {
279 : 0 : index++;
280 : : }
281 : : }
282 : : }
283 : :
284 : : // insert new_item
285 : 0 : insert_link(new_item);
286 : 0 : listIsSorted = CUBIT_TRUE;
287 : 0 : }
288 : :
289 : : // move_to_and_remove_item_sorted uses move_to_item_sorted function to perform
290 : : // a binary search to locate the objects's index for which the objects
291 : : // functionName() = value. If found, the objects index is set as the current
292 : : // index. Then cut_link is called to remove the object from the list.
293 : 0 : void* SDLList::move_to_and_remove_item_sorted(void* value)
294 : : {
295 [ # # ]: 0 : if (move_to_item_sorted(value))
296 : 0 : return cut_link();
297 : : else
298 : 0 : return (void*) NULL;
299 : : }
300 : :
301 : :
302 : 0 : SDLList& SDLList::operator=(const SDLList& from)
303 : : {
304 [ # # ]: 0 : if (this != &from) {
305 : 0 : DLList::operator=(from);
306 : : }
307 : 0 : return *this;
308 : : }
309 : :
|
