Branch data Line data Source code
1 : : //- Class: SDLList
2 : : //- Description: SDLList is a doubly linked list class that accepts generic
3 : : //- pointers to any object. It is controlled by a macro that
4 : : //- substitutes the specific pointer definitions in the class
5 : : //- declaration. The list is implemented as an array that is
6 : : //- grown by a specified amount when the list becomes full.
7 : : //- Insertions and deletions at any point other than the end
8 : : //- of the list are handled inefficiently at the current time
9 : : //- since all data from that point to the end is bubbled
10 : : //- down/up to fill/create the void. Operators {+} and {+=}
11 : : //- are provided as an efficient means of assigning one list
12 : : //- to another or appending one list onto another.
13 : : //-
14 : : //- The macro {SDLListdeclare(name,typePtr)} is defined to
15 : : //- create specific instances of the SDLList class.
16 : : //- {name} is the name of the SDLList class created, and
17 : : //- {typePtr} is the type of elements stored in the list.
18 : : //- The macro also defines the functions {push(item)} and
19 : : //- {pop()} which allow {SDLLists} to perform like stacks.
20 : : //-
21 : : //- Assumptions: All data are stored contiguously in the array with
22 : : //- empty slots at the end of the array.
23 : : //-
24 : : //- Owner: Greg Sjaardema
25 : : //- Checked by: Jim Hipp, 3/28/94
26 : : //- Version: $Id:
27 : :
28 : : #ifndef SDLLIST_HPP
29 : : #define SDLLIST_HPP
30 : :
31 : : #include "DLList.hpp"
32 : : #include "CubitDefines.h"
33 : : #include "CubitMessage.hpp"
34 : : #include <cstring>
35 : : #include <cassert>
36 : : #include "CGMUtilConfigure.h"
37 : :
38 : : const int ORDER_ASCENDING = 0;
39 : : const int ORDER_DESCENDING = 1;
40 : : //- sort direction specifiers for the SSDLListDeclare Constructor
41 : :
42 : : class CUBIT_UTIL_EXPORT SDLList : public DLList
43 : : {
44 : : public:
45 : :
46 : : SDLList (int size);
47 : : //- Constructor: Create a list with initial size {size}. The list
48 : : //- will be grown by {size} each time it is filled. Memory for the
49 : : //- list is not allocated until the first element is inserted using
50 : : //- {insertLink}.
51 : : //- If {size} is zero, the default increment ({INCREMENT}) will be used
52 : : //- From an efficiency standpoint, it is very important that the
53 : : //- increment be set large enough to reduce the number of list
54 : : //- growths, but small enough to not waste memory.
55 : : //- It is more efficient to sligthly overestimate the size than
56 : : //- to underestimate the size.
57 : :
58 : : SDLList(const SDLList& copy_from); //- Copy Constructor
59 : : SDLList(const DLList& copy_from); //- Copy Constructor
60 : :
61 : : virtual ~SDLList();
62 : : //- Destructor: Free all resources used by this list.
63 : :
64 : : SDLList& operator=(const SDLList&);
65 : : //- Create a copy of a list.
66 : :
67 : : virtual void merge_unique(DLList& merge_list, int merge_list_unique );
68 : : //- Merges the contents of the list, merge_list, with those of "this"
69 : : //- list, ensuring that items that are being added do not already
70 : : //- exist in "this" list. If the items are known to appear in the
71 : : //- merge_list only once, then it can be done faster.
72 : :
73 : 0 : SetDynamicMemoryAllocation(memoryManager)
74 : : //- overloaded new and delete operators
75 : :
76 : : protected:
77 : :
78 : : void insert_link(void* newBody);
79 : : //- put new item in list after current item and make it current
80 : :
81 : : void insert_link_first(void* new_item);
82 : : //- put new item in list at index 0 and make it current
83 : :
84 : : void append_link(void* newBody);
85 : : //- put new item at end of list and keep pointer where it is.
86 : : //- This call should be used to add items to a list if order
87 : : //- of items is not important.
88 : :
89 : : void* extract_link();
90 : : //- remove the item at the current location and return a pointer to it.
91 : : //- used for efficiency in cases where preservation of list order is not
92 : : //- important. moves last list item (itemCount - 1) to current index and
93 : : //- decrements itemCount. eliminates the need to perform the list bubble
94 : : //- down (i.e. cut_link) but sacrifices list order in the process. this
95 : : //- function should not be used when up-stream order from the removed node
96 : : //- is important. when processing a list using this function the user
97 : : //- should reset the list to the head (index = 0) before beginning to
98 : : //- ensure all list nodes are processed properly.
99 : : //- Returns {NULL} if there are no items in list
100 : :
101 : : void *change_item_to(void* newBody);
102 : : //- Sets the item at the current index value to {newBody} and
103 : : //- returns the old value at that location.
104 : : //- Returns {NULL} if there are no items in list
105 : :
106 : : void sort_list();
107 : : //- sort_list sorts SDLLists in an ascending or descending fashion
108 : : //- (depending on the assignment of compare_order function pointer). The
109 : : //- list is sorted using a standard Heap Sort algorithm.
110 : :
111 : : CubitBoolean move_to_item_sorted(void* value);
112 : : //- move_to_item_sorted performs a binary search on the list to locate
113 : : //- the item (object) that has functionType functionName() = value
114 : : //- (see SSDLListdeclare macro for description of functionType and
115 : : //- functionName). If a matching item is found then the current
116 : : //- index is set to the matching item index and TRUE is returned. If the
117 : : //- object is not found then index is unchanged and FALSE is returned.
118 : :
119 : : void insert_item_sorted(void* value, void* new_item);
120 : : //- insert_item_sorted uses compare function (compare_order) to perform a
121 : : //- binary search to find the insert index in the list. The function then
122 : : //- calls insert_link after setting the index to the insert position - 1.
123 : :
124 : : void* move_to_and_remove_item_sorted(void* value);
125 : : //- move_to_and_remove_item_sorted uses move_to_item_sorted function to
126 : : //- perform a binary search to locate the item's index which has
127 : : //- functionType functionName() = value. If found, remove_link is called
128 : : //- to remove and return the item from the list. Otherwise, NULL is
129 : : //- returned.
130 : :
131 : : int (*compare_order_obj)(void* object_1, void* object_2);
132 : : int (*compare_order)(void* object_1, void* object_2);
133 : : int (*compare_equal)(void* object_1, void* object_2);
134 : : //- compare function pointers are assigned within the macro definition
135 : : //- SSDLListDeclare
136 : :
137 : : void set_sorted_flag(const int sorted_flag);
138 : : //- set listIsSorted flag
139 : :
140 : : CubitBoolean where_is_item_sorted( void *value, int &item_index );
141 : : //- Return True if item with given value is in the list, else false.
142 : : //- Return in item_index the index of item of that value in list,
143 : : //- or -1 if an item of that value is not in the list.
144 : : //- This information should never be passed outside the class.
145 : :
146 : : private:
147 : :
148 : : void binary_search(int* min_location, int* max_location, void* item) const;
149 : : //- binary_search performs a standard array based binary search (essentially
150 : : //- bisection) to bracket/locate an insert/search position.
151 : :
152 : : static MemoryManager memoryManager;
153 : : //- memory management static objects for performing block allocation
154 : : };
155 : :
156 : : // *** inline function definitions *******************************************
157 : :
158 : : //- Add item to end of list, do not change current index value.
159 : : //- This function used to reduce time required to do an insert
160 : : //- followed by a move_to back to where we were.
161 : 558 : inline void SDLList::append_link ( void* new_item )
162 : : {
163 [ - + ]: 558 : assert(new_item != NULL);
164 : : // see if the list must be lengthened
165 : :
166 [ + + ]: 558 : if ( itemCount == listLength )
167 : 126 : lengthen_list();
168 : :
169 : 558 : listArray[itemCount++] = new_item;
170 : 558 : }
171 : :
172 : 852 : inline void SDLList::set_sorted_flag(const int sorted_flag)
173 : : {
174 : 852 : listIsSorted = sorted_flag;
175 : 852 : }
176 : :
177 : :
178 : : // *** macro definitions *****************************************************
179 : :
180 : : // Three separate derived classes are possible from SDLList all of which are
181 : : // defined by one of the following macros:
182 : : //
183 : : // SDLListdeclare(name, typePtr)
184 : : // SSDLListdeclare(name, typePtr, functionName, functionType)
185 : : // SSDLListIntrinsicdeclare(name, typePtr)
186 : : //
187 : : // The first is the standard SDLList declaration macro, the second provides
188 : : // sorting/searching functionality, and the third provides sorting/searching
189 : : // functionallity for simple intrinsic data lists. All three are described in
190 : : // more detail below. Two support macros
191 : : //
192 : : // CommonDefine(typePtr, notSorted)
193 : : // CommonSortedDefine(name, typePtr)
194 : : //
195 : : // are also defined but are not meant to be utilized externally. They simply
196 : : // collect class definitions that are common to the three list defintions
197 : : // macros described above
198 : :
199 : : // The following macro defintion provides the core functionality for the
200 : : // standard SDLListdeclare as-well-as the sorted SSDLListdeclare macros.
201 : : // typePtr is still the type pointer of the data stored by the list.
202 : : // notSorted is simply a semi-colon (;) for the standard list (if white space
203 : : // is used for the parameter the CPP outputs a warning message that a NULL
204 : : // string is being substituted for the parameter ... the proper outcome but
205 : : // the excessive warning messages are a real nuisance) and a call to the
206 : : // set_sort_flag function (with an argument of False) for the sorted lists.
207 : : #define CommonDefine2(typePtr, notSorted) \
208 : : \
209 : : typePtr remove() {return (typePtr) cut_link();} \
210 : : int omit(typePtr objPtr) {return omit_link((void*) objPtr);} \
211 : : typePtr get() const {return (typePtr) get_item();} \
212 : : typePtr next() const {return (typePtr) next_item();} \
213 : : typePtr next( int n ) const {return (typePtr) next_item(n);} \
214 : : typePtr prev() const {return (typePtr) prev_item();} \
215 : : typePtr prev(int n) const {return (typePtr) prev_item(n);} \
216 : : typePtr get_and_step() {return (typePtr) get_item_and_step();} \
217 : : typePtr get_and_back() {return (typePtr) get_item_and_back();} \
218 : : typePtr step_and_get() {return (typePtr) step_and_get_item();} \
219 : : \
220 : : int move_between(typePtr objPtr1, typePtr objPtr2) \
221 : : { \
222 : : if (nullItem && (((typePtr) nullItem == objPtr1) || \
223 : : ((typePtr) nullItem == objPtr2) )) \
224 : : return CUBIT_FALSE; \
225 : : else \
226 : : return (move_between_items(((void*) objPtr1), ((void*) objPtr2))); \
227 : : } \
228 : : typePtr pop() {last(); return remove();} \
229 : : typePtr push(typePtr objPtr) \
230 : : { last(); append(objPtr); return objPtr; } \
231 : : \
232 : : void insert_first(typePtr objPtr) \
233 : : { notSorted insert_link_first((void*) objPtr); } \
234 : : void append(typePtr objPtr) \
235 : : { notSorted append_link((void*) objPtr); } \
236 : : typePtr extract() \
237 : : { notSorted return (typePtr) extract_link(); } \
238 : : typePtr nullify() \
239 : : { notSorted return (typePtr) nullify_link(); } \
240 : : typePtr change_to(typePtr objPtr) \
241 : : { notSorted return (typePtr) change_item_to((void*) objPtr); } \
242 : : \
243 : :
244 : :
245 : : // The macro CommonSortedDefine contains common public functions used by
246 : : // SSDLListdeclare and SSDLListIntrinsicdeclare
247 : : #define CommonSortedDefine(name, typePtr) \
248 : : \
249 : : name(int size_in = 0, int direction = ORDER_ASCENDING) : SDLList(size_in) \
250 : : { \
251 : : assert(sizeof(typePtr) == sizeof(void*)); \
252 : : if (direction == ORDER_DESCENDING) \
253 : : { \
254 : : compare_order = &name::compare_descend; \
255 : : compare_order_obj = &name::compare_descend_obj; \
256 : : } \
257 : : else \
258 : : { \
259 : : compare_order = &name::compare_ascend; \
260 : : compare_order_obj = &name::compare_ascend_obj; \
261 : : } \
262 : : compare_equal = &name::compare_equate; \
263 : : set_sorted_flag(CUBIT_TRUE); \
264 : : } \
265 : : \
266 : : void sort() { sort_list(); } \
267 : : void set_list_order_ascend() \
268 : : { \
269 : : compare_order_obj = &name::compare_ascend_obj; \
270 : : compare_order = &name::compare_ascend; sort_list(); \
271 : : } \
272 : : void set_list_order_descend() \
273 : : { \
274 : : compare_order_obj = &name::compare_descend_obj; \
275 : : compare_order = &name::compare_descend; sort_list(); \
276 : : } \
277 : :
278 : : // The sorted SDLList declaration macro creates an ordered list class that
279 : : // is derived from SDLList. The class (name) stores pointers to data of
280 : : // type typePtr. List ordering is provided by sorting the objects based
281 : : // on the returned value of one of the objects functions (functionName()).
282 : : // The return type of functionName is functionType. Searching functionality
283 : : // is provided (with move_to) to locate the object (typePtr objPtr) or a
284 : : // value (functionType value) of the object utilizing an binary search.
285 : : #define SDLListdeclare(name, typePtr, functionName, functionType) \
286 : : \
287 : : class name : public SDLList \
288 : : { \
289 : : \
290 : : public: \
291 : : \
292 : : CommonSortedDefine(name, typePtr) \
293 : : CommonDefine(typePtr, set_sorted_flag(CUBIT_FALSE);) \
294 : : \
295 : : void insert(typePtr objPtr) \
296 : : { \
297 : : functionType value = objPtr->functionName(); \
298 : : insert_item_sorted((void*) &value, (void*) objPtr); \
299 : : } \
300 : : typePtr remove(typePtr objPtr) \
301 : : { \
302 : : assert(objPtr != NULL); \
303 : : functionType value = objPtr->functionName(); \
304 : : return (typePtr) move_to_and_remove_item_sorted((void*) &value); \
305 : : } \
306 : : typePtr remove(functionType value) \
307 : : { \
308 : : return (typePtr) move_to_and_remove_item_sorted((void*) &value); \
309 : : } \
310 : : CubitBoolean move_to(typePtr objPtr) \
311 : : { \
312 : : if (nullItem && ((typePtr) nullItem == objPtr)) \
313 : : return CUBIT_FALSE; \
314 : : else \
315 : : { \
316 : : assert(objPtr != NULL); \
317 : : functionType value = objPtr->functionName(); \
318 : : return move_to_item_sorted((void*) &value); \
319 : : } \
320 : : } \
321 : : CubitBoolean move_to(functionType value) \
322 : : { \
323 : : return move_to_item_sorted((void*) &value); \
324 : : } \
325 : : int is_in_list(functionType value) \
326 : : { \
327 : : int item_index; \
328 : : int return_value = \
329 : : where_is_item_sorted((void*) &value, item_index) ? \
330 : : item_index + 1 : 0; \
331 : : return return_value; \
332 : : } \
333 : : int is_in_list(typePtr objPtr) \
334 : : { \
335 : : if (nullItem && ((typePtr) nullItem == objPtr)) \
336 : : return CUBIT_FALSE; \
337 : : else \
338 : : { \
339 : : assert(objPtr != NULL); \
340 : : functionType value = objPtr->functionName(); \
341 : : return is_in_list( value ); \
342 : : } \
343 : : } \
344 : : \
345 : : private: \
346 : : \
347 : : static int compare_ascend_obj(void* object_1, void* object_2) \
348 : : { \
349 : : return (((typePtr) object_1)->functionName() >= \
350 : : ((typePtr) object_2)->functionName()); \
351 : : } \
352 : : static int compare_descend_obj(void* object_1, void* object_2) \
353 : : { \
354 : : return (((typePtr) object_1)->functionName() <= \
355 : : ((typePtr) object_2)->functionName()); \
356 : : } \
357 : : \
358 : : static int compare_ascend(void* value, void* object) \
359 : : { \
360 : : return (*((functionType*) value) >= \
361 : : ((typePtr) object)->functionName()); \
362 : : } \
363 : : static int compare_descend(void* value, void* object) \
364 : : { \
365 : : return (*((functionType*) value) <= \
366 : : ((typePtr) object)->functionName()); \
367 : : } \
368 : : static int compare_equate(void* value, void* object) \
369 : : { \
370 : : return (*((functionType*) value) == \
371 : : ((typePtr) object)->functionName()); \
372 : : } \
373 : : }; \
374 : :
375 : :
376 : : // The sorted Intrinsic SDLList declaration macro creates an ordered intrinsic
377 : : // list class that is derived from SDLList. The class (name) stores values of
378 : : // typePtr through casting to void* pointers. This macro only works for lists
379 : : // of integers or floats. No capability is currently supported for lists of
380 : : // doubles.
381 : : #define SSDLListIntrinsicdeclare(name, typePtr) \
382 : : \
383 : : class name : public SDLList \
384 : : { \
385 : : \
386 : : public: \
387 : : \
388 : : CommonSortedDefine(name, typePtr) \
389 : : CommonDefine(typePtr, set_sorted_flag(CUBIT_FALSE);) \
390 : : \
391 : : void insert(typePtr objPtr) \
392 : : { \
393 : : insert_item_sorted((void*) objPtr, (void*) objPtr); \
394 : : } \
395 : : typePtr remove(typePtr objPtr) \
396 : : { \
397 : : return (typePtr) move_to_and_remove_item_sorted((void*) objPtr); \
398 : : } \
399 : : int move_to(typePtr objPtr) \
400 : : { \
401 : : return move_to_item_sorted((void*) objPtr); \
402 : : } \
403 : : int is_in_list(typePtr objPtr) \
404 : : { \
405 : : int item_index; \
406 : : int return_value = \
407 : : where_is_item_sorted((void*) &objPtr, item_index) ? \
408 : : item_index + 1 : 0; \
409 : : return return_value; \
410 : : } \
411 : : \
412 : : private: \
413 : : \
414 : : static int compare_ascend_obj(void* object_1, void* object_2) \
415 : : { \
416 : : return (((typePtr) object_1) >= ((typePtr) object_2)); \
417 : : } \
418 : : static int compare_descend_obj(void* object_1, void* object_2) \
419 : : { \
420 : : return (((typePtr) object_1) <= ((typePtr) object_2)); \
421 : : } \
422 : : \
423 : : static int compare_ascend(void* object_1, void* object_2) \
424 : : { \
425 : : return (((typePtr) object_1) >= ((typePtr) object_2)); \
426 : : } \
427 : : static int compare_descend(void* object_1, void* object_2) \
428 : : { \
429 : : return (((typePtr) object_1) <= ((typePtr) object_2)); \
430 : : } \
431 : : static int compare_equate(void* object_1, void* object_2) \
432 : : { \
433 : : return (((typePtr) object_1) == ((typePtr) object_2)); \
434 : : } \
435 : : }; \
436 : :
437 : : #endif //- SDLLIST_HPP
438 : :
|
