FEI Package Browser (Single Doxygen Collection) Version of the Day
Loading...
Searching...
No Matches
snl_fei_ArrayUtils.hpp
Go to the documentation of this file.
1#ifndef _snl_fei_ArrayUtils_hpp_
2#define _snl_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 snl_fei {
17
26 template<typename T>
27 int binarySearch(const T& item,
28 const T* list,
29 int len)
30 {
31 if (len < 2) {
32 if (len < 1) {
33 return(-1);
34 }
35
36 if (list[0] != item) {
37 return(-1);
38 }
39 else {
40 return(0);
41 }
42 }
43
44 unsigned start = 0;
45 unsigned end = len - 1;
46
47 while(end - start > 1) {
48 unsigned mid = (start + end) >> 1;
49 if (list[mid] < item) start = mid;
50 else end = mid;
51 }
52
53 if (list[end] == item) return(end);
54 if (list[start] == item) return(start);
55
56 return(-1);
57 }
58
62 template<typename T>
63 void insertion_sort_with_companions(int len, int* array, T* companions)
64 {
65 int i, j, index;
66 T companion;
67
68 for (i=1; i < len; i++) {
69 index = array[i];
70 companion = companions[i];
71 j = i;
72 while ((j > 0) && (array[j-1] > index))
73 {
74 array[j] = array[j-1];
75 companions[j] = companions[j-1];
76 j = j - 1;
77 }
78 array[j] = index;
79 companions[j] = companion;
80 }
81 }
82
86 template<typename T>
87 int lowerBound(const T& item,
88 const T* list,
89 int len)
90 {
91 //The correctness of this function is tested in
92 // fei/test_utils/test_misc.cpp, in test_misc::serialtest2().
93
94 if (len < 1) return 0;
95
96 unsigned start = 0;
97 unsigned end = len - 1;
98
99 while(end - start > 1) {
100 unsigned mid = (start + end) >> 1;
101 if (list[mid] < item) start = mid;
102 else end = mid;
103 }
104
105 if (list[end] < item) {
106 return(end+1);
107 }
108
109 if (list[start] < item) {
110 return(end);
111 }
112
113 return(start);
114 }
115
127 template<typename T>
128 int binarySearch(const T& item,
129 const T* list,
130 int len,
131 int& insertPoint)
132 {
133 //The correctness of this function is tested in src/utils/test_Set.C,
134 //in the function test_Set::test2.
135
136 if (len < 2) {
137 if (len < 1) {
138 insertPoint = 0;
139 return(-1);
140 }
141
142 if (list[0] < item) {
143 insertPoint = 1;
144 return(-1);
145 }
146 if (item < list[0]) {
147 insertPoint = 0;
148 return(-1);
149 }
150 else {
151 return(0);
152 }
153 }
154
155 unsigned start = 0;
156 unsigned end = len - 1;
157
158 while(end - start > 1) {
159 unsigned mid = (start + end) >> 1;
160 if (list[mid] < item) start = mid;
161 else end = mid;
162 }
163
164 if (list[end] < item) {
165 insertPoint = end+1;
166 return(-1);
167 }
168
169 if (item < list[end]) {
170 if (list[start] < item) {
171 insertPoint = end;
172 return(-1);
173 }
174
175 if (item < list[start]) {
176 insertPoint = start;
177 return(-1);
178 }
179 else {
180 return(start);
181 }
182 }
183 else {
184 return(end);
185 }
186 }
187
190 template<typename T>
191 int binarySearch(const T& item, const std::vector<T>& list, int& insertPoint)
192 {
193 if (list.size() == 0) {
194 insertPoint = 0;
195 return(-1);
196 }
197 return( binarySearch(item, &list[0], list.size(), insertPoint) );
198 }
199
202 template<typename T>
203 int binarySearch(const T& item, const std::vector<T>& list)
204 {
205 if (list.size() == 0) return(-1);
206 return( binarySearch(item, &list[0], list.size()) );
207 }
208
220 template<typename T>
221 int binarySearch(const T& item, const T* list, int /*listLength*/,
222 int start, int end, int& insertPoint)
223 {
224 int length = end - start + 1;
225
226 if (length < 2) {
227 if (length < 1) {
228 insertPoint = start;
229 return(-1);
230 }
231
232 if (list[start] < item) {
233 insertPoint = start+1;
234 return(-1);
235 }
236 if (item < list[start]) {
237 insertPoint = start;
238 return(-1);
239 }
240 else {
241 return(start);
242 }
243 }
244
245 unsigned ustart = start;
246 unsigned uend = end;
247
248 while(uend - ustart > 1) {
249 unsigned mid = (ustart + uend) >> 1;
250 if (list[mid] < item) ustart = mid;
251 else uend = mid;
252 }
253
254 //if list[uend] < item, then insertPoint = end+1
255 if (list[uend] < item) {
256 insertPoint = uend+1;
257 return(-1);
258 }
259
260 if (item < list[uend]) {
261 if (list[ustart] < item) {
262 insertPoint = uend;
263 return(-1);
264 }
265
266 if (item < list[ustart]) {
267 insertPoint = ustart;
268 return(-1);
269 }
270 else {
271 //list[ustart] == item
272 return(ustart);
273 }
274 }
275
276 // list[uend] == item
277 return(uend);
278 }
279
290 template<typename T>
291 int binarySearch(int numItems, const T* items, int* offsets,
292 const T* list, int listLength)
293 {
294 int i;
295 if (numItems < 1 || listLength < 1) {
296 if (listLength < 1) {
297 for(i=0; i<numItems; ++i) offsets[i] = -1;
298 }
299 }
300
301 int tmp, start = 0;
302 int end = listLength -1;
303 int insertPoint = -1;
304 for(i=0; i<numItems; ++i) {
305 tmp = binarySearch(items[i], list, listLength, start, end, insertPoint);
306 start = tmp > -1 ? tmp : insertPoint;
307 offsets[i] = tmp;
308 }
309
310 return(0);
311 }
312
317 template<class T>
318 int sortedListInsert(const T& item, std::vector<T>& list)
319 {
320 typename std::vector<T>::iterator iter =
321 std::lower_bound(list.begin(), list.end(), item);
322
323 if (iter == list.end() || *iter != item) {
324 iter = list.insert(iter, item);
325 return( iter - list.begin() );
326 }
327
328 return(-1);
329 }
330
333 template<class T>
334 int sortedListInsert(const T& item, T*& list, int& len, int& allocLen)
335 {
336 int i, insertPoint = -1;
337 int index = binarySearch(item, list, len, insertPoint);
338 if (index < 0) {
339 if (len >= allocLen) {
340 allocLen = len+2;
341 T* newlist = new T[allocLen];
342 for(i=0; i<insertPoint; ++i) newlist[i] = list[i];
343 newlist[insertPoint] = item;
344 for(i=insertPoint; i<len; ++i) newlist[i+1] = list[i];
345 delete [] list;
346 list = newlist;
347 }
348 else {
349 for(i=len; i>insertPoint; --i) {
350 list[i] = list[i-1];
351 }
352 list[insertPoint] = item;
353 }
354 ++len;
355 return(insertPoint);
356 }
357
358 return(-1);
359 }
360
363 template<class T>
364 int listInsert(const T& item, int offset, T*& list,
365 int& usedLength, int& allocatedLength,
366 int allocChunkSize=200)
367 {
368 if (offset < 0 || offset > usedLength) {
369 return(-1);
370 }
371
372 if (usedLength < allocatedLength) {
373 for(int i=usedLength; i>offset; --i) {
374 list[i] = list[i-1];
375 }
376 list[offset] = item;
377 ++usedLength;
378 return(0);
379 }
380
381 T* newlist = new T[allocatedLength+allocChunkSize];
382
383 allocatedLength += allocChunkSize;
384 int i;
385 for(i=0; i<offset; ++i) {
386 newlist[i] = list[i];
387 }
388
389 newlist[offset] = item;
390
391 for(i=offset+1; i<=usedLength; ++i) {
392 newlist[i] = list[i-1];
393 }
394
395 ++usedLength;
396 delete [] list;
397 list = newlist;
398 return(0);
399 }
400
404 template<class T>
405 int searchList(const T& item, const T* list, int len)
406 {
407 for(int i=0; i<len; ++i) {
408 if (list[i] == item) {
409 return(i);
410 }
411 }
412 return(-1);
413 }
414
415} //namespace snl_fei
416
417#endif // _snl_fei_ArrayUtils_hpp_
418
void insertion_sort_with_companions(int len, int *array, T *companions)
int searchList(const T &item, const T *list, int len)
int lowerBound(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 sortedListInsert(const T &item, std::vector< T > &list)
int binarySearch(const T &item, const T *list, int len)