FEI Package Browser (Single Doxygen Collection) Version of the Day
Loading...
Searching...
No Matches
fei_ArrayUtils.hpp
Go to the documentation of this file.
1#ifndef _fei_ArrayUtils_hpp_
2#define _fei_ArrayUtils_hpp_
3
4/*--------------------------------------------------------------------*/
5/* Copyright 2005 Sandia Corporation. */
6/* Under the terms of Contract DE-AC04-94AL85000, there is a */
7/* non-exclusive license for use of this work by or on behalf */
8/* of the U.S. Government. Export of this program may require */
9/* a license from the United States Government. */
10/*--------------------------------------------------------------------*/
11
12#include "fei_fwd.hpp"
13
14#include <algorithm>
15
16namespace fei {
17
18
22 template<typename T>
23 inline int lowerBound(const T& item,
24 const T* list,
25 int len)
26 {
27 //The correctness of this function is tested in
28 // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().
29
30 if (len < 1) return 0;
31
32 unsigned start = 0;
33 unsigned end = len - 1;
34
35 while(end - start > 23) {
36 unsigned mid = (start + end) >> 1;
37 if (list[mid] < item) start = mid;
38 else end = mid;
39 }
40
41 while (start+7<=end ) {
42 if ( item <= list[start+0] ) return start+0;
43 if ( item <= list[start+1] ) return start+1;
44 if ( item <= list[start+2] ) return start+2;
45 if ( item <= list[start+3] ) return start+3;
46 if ( item <= list[start+4] ) return start+4;
47 if ( item <= list[start+5] ) return start+5;
48 if ( item <= list[start+6] ) return start+6;
49 if ( item <= list[start+7] ) return start+7;
50 start+=8;
51 }
52
53 while (start<=end && item > list[start] )
54 start++;
55
56 return(start);
57 }
58
67 template<typename T>
68 inline int binarySearch(const T& item,
69 const T* list,
70 int len)
71 {
72 int result = lowerBound(item,list,len);
73 if ( result < len && item == list[result] )
74 return result;
75 return -1;
76 }
77
81 template<typename T>
82 inline void insertion_sort_with_companions(int len, int* array, T* companions)
83 {
84 int i, j, index;
85 T companion;
86
87 for (i=1; i < len; i++) {
88 index = array[i];
89 companion = companions[i];
90 j = i;
91 while ((j > 0) && (array[j-1] > index))
92 {
93 array[j] = array[j-1];
94 companions[j] = companions[j-1];
95 j = j - 1;
96 }
97 array[j] = index;
98 companions[j] = companion;
99 }
100 }
101
102
114 template<typename T>
115 inline int binarySearch(const T& item,
116 const T* list,
117 int len,
118 int& insertPoint)
119 {
120 //The correctness of this function is tested in src/utils/test_Set.C,
121 //in the function test_Set::test2.
122 insertPoint = lowerBound(item,list,len);
123 if ( insertPoint < len && item == list[insertPoint] )
124 return insertPoint;
125 return -1;
126 }
127
130 template<typename T>
131 inline int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
132 {
133 if (list.size() == 0) {
134 insertPoint = 0;
135 return(-1);
136 }
137 return( binarySearch(item, &list[0], list.size(), insertPoint) );
138 }
139
142 template<typename T>
143 inline int binarySearch(const T& item, const std::vector<T>& list)
144 {
145 if (list.size() == 0) return(-1);
146 return( binarySearch(item, &list[0], list.size()) );
147 }
148
160 template<typename T>
161 inline int binarySearch(const T& item, const T* list, int /*listLength*/,
162 int start, int end, int& insertPoint)
163 {
164 int result = binarySearch(item,list+start,end-start+1,insertPoint);
165 if ( result >= 0 )
166 return result+start;
167 insertPoint+= start;
168 return -1;
169 }
170
181 template<typename T>
182 inline int binarySearch(int numItems, const T* items, int* offsets,
183 const T* list, int listLength)
184 {
185 int i;
186 if (numItems < 1 || listLength < 1) {
187 if (listLength < 1) {
188 for(i=0; i<numItems; ++i) offsets[i] = -1;
189 }
190 }
191
192 int tmp, start = 0;
193 int end = listLength -1;
194 int insertPoint = -1;
195 for(i=0; i<numItems; ++i) {
196 tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
197 start = tmp > -1 ? tmp : insertPoint;
198 offsets[i] = tmp;
199 }
200
201 return(0);
202 }
203
208 template<class T>
209 inline int sortedListInsert(const T& item, std::vector<T>& list)
210 {
211 typename std::vector<T>::iterator iter =
212 std::lower_bound(list.begin(), list.end(), item);
213
214 if (iter == list.end() || *iter != item) {
215 iter = list.insert(iter, item);
216 return( iter - list.begin() );
217 }
218
219 return(-1);
220 }
221
224 template<class T>
225 inline int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
226 {
227 int i, insertPoint = -1;
228 int index = binarySearch(item, list, len, insertPoint);
229 if (index < 0) {
230 if (len >= allocLen) {
231 allocLen = len+2;
232 T* newlist = new T[allocLen];
233 for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
234 newlist[insertPoint] = item;
235 for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
236 delete [] list;
237 list = newlist;
238 }
239 else {
240 for(i=len; i>insertPoint; --i) {
241 list[i] = list[i-1];
242 }
243 list[insertPoint] = item;
244 }
245 ++len;
246 return(insertPoint);
247 }
248
249 return(-1);
250 }
251
254 template<class T>
255 inline int listInsert(const T& item, int offset, T*& list,
256 int& usedLength, int& allocatedLength,
257 int allocChunkSize=200)
258 {
259 if (offset < 0 || offset > usedLength) {
260 return(-1);
261 }
262
263 if (usedLength < allocatedLength) {
264 for(int i=usedLength; i>offset; --i) {
265 list[i] = list[i-1];
266 }
267 list[offset] = item;
268 ++usedLength;
269 return(0);
270 }
271
272 T* newlist = new T[allocatedLength+allocChunkSize];
273
274 allocatedLength += allocChunkSize;
275 int i;
276 for(i=0; i<offset; ++i) {
277 newlist[i] = list[i];
278 }
279
280 newlist[offset] = item;
281
282 for(i=offset+1; i<=usedLength; ++i) {
283 newlist[i] = list[i-1];
284 }
285
286 ++usedLength;
287 delete [] list;
288 list = newlist;
289 return(0);
290 }
291
295 template<class T>
296 inline int searchList(const T& item, const T* list, int len)
297 {
298 for(int i=0; i<len; ++i) {
299 if (list[i] == item) {
300 return(i);
301 }
302 }
303 return(-1);
304 }
305
306} //namespace fei
307
308#endif // _fei_ArrayUtils_hpp_
309
int lowerBound(const T &item, const T *list, int len)
int searchList(const T &item, const T *list, int len)
int listInsert(const T &item, int offset, T *&list, int &usedLength, int &allocatedLength, int allocChunkSize=200)
int binarySearch(const T &item, const T *list, int len)
int sortedListInsert(const T &item, std::vector< T > &list)
void insertion_sort_with_companions(int len, int *array, T *companions)