FEI Package Browser (Single Doxygen Collection)  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
16 namespace 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 sortedListInsert(const T &item, std::vector< T > &list)
void insertion_sort_with_companions(int len, int *array, T *companions)
int binarySearch(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 searchList(const T &item, const T *list, int len)