C++ main module for emicrom Package  1.0
CORE_ArrayList.hpp
Go to the documentation of this file.
1 #ifndef CORE_ArrayList_HPP
2 #define CORE_ArrayList_HPP
3 
4 #include <CORE_ArrayList.h>
5 
6 using namespace std;
7 
8 
9 template<class T>
10 template<class Q>
11 void CORE_ArrayList<T>::push_back(const Q& obj) {
12  //new dimension of array
13  const tUIndex& dim=CORE_Array<T>::getSize();
14 
15  //get the capacity
17  const tFlag& capF=getCapacityFactor();
18  if (dim>=cap) {//capacity too small
19  if ( (capF==1) || (cap==0) ) CORE_Array<T>::reserve(dim+1);
20  else CORE_Array<T>::reserve(cap*capF);
21  }
22  //set at the end
23  (*this)[dim]=obj;
24 
25  //set the size
27 }
28 
29 
30 
31 template<class T>
33 
34 
35  //number of copied
36  tUIndex k=0;
37  //pointer to the element to replace
38  T *pK=&(*this)[0];
39  //pointer of the element to test
40  const T *pI=&(*this)[0];
41 
42  //get the size
44  for (tUIndex i=0;i<s;i++) {
45 
46  if (*pI!=obj) {
47  //copy the element
48  *pK=*pI;
49  //set the number of copied elements
50  k++;
51  //next copied element
52  pK++;
53  }
54  //next test element
55  pI++;
56  }
57 
58  if (s!=k) {
59  s=k;
60  return true;
61  }
62  return false;
63 }
64 
65 template<class T>
67 
69  //no element
70  if (s==0) return;
71  //index too big
72  if (index>=s) return;
73 
74 
75  //new size
76  s--;
77 
78  //no element to transfert
79  if (index==s) return;
80 
81  //copy from index to mSize -1
82  T *pI=&(*this)[index];
83  const T *pS=&(*this)[index+1];
84  //copy the elemetnt at index i+1 to array at index i
85  for (tUIndex i=index;i<s;i++) {
86  *pI=*pS;
87  pI++;
88  pS++;
89  }
90 
91 }
92 
93 template<class T>
95 
97  //test if there is no change
98  if (n>=s) return;
99  //test if clear
100  if (n==0) {
103  return;
104  }
105  //copy the last element to the first elements
106  const T *v=&(*this)[s-n];
107  T *newV=&(*this)[0];
108  for (tUIndex i=0;i<n;i++) {
109  *newV=*v;
110  v++;
111  newV++;
112  }
113  //set the size
114  s=n;
115 
116  //fit the array
118 }
119 
120 
121 template<class T>
122 void CORE_ArrayList<T>::insertAtIndex(const tUIndex& i,const T& v) {
124  //add at the end
125 
126  if (i>=s) {
127  push_back(v);
128  return;
129  }
130 
131  //reallocate the array if necessary
132  tUIndex dim=s+1;
133 
134  //get the capacity
135  const tUIndex& cap=CORE_Array<T>::getCapacity();
136  const tFlag& capF=getCapacityFactor();
137  if (dim>=cap) {//capacity too small
138  if ( (capF==1) || (cap==0) ) CORE_Array<T>::reserve(dim+1);
139  else CORE_Array<T>::reserve(cap*capF);
140  }
141 
142  //move the element at index k to index k+1
143  //k=mSize
144  T* newV=&(*this)[s];
145  const T* vs=&(*this)[s-1];
146  for (tUIndex k=s;k>i;k--) {
147  *newV=*vs;
148  newV--;
149  vs--;
150 
151  }
152  //set the v
153  (*newV)=v;
154 
155  //new size
156  s=dim;
157 
158 }
159 
160 
161 
162 
163 
164 
165 template<class T>
167 
169 
170  //start index
171  tUIndex si=0;
172  //end index
174 
175  //empty array case
176  if (sf==0) {
177  push_back(obj);
178  return 0;
179  }
180 
181  //set the end included index
182  sf--;
183 
184 
185  if (CORE_List::compare(obj,(*this)[0],mOrder)) {//obj is before mValues[0] with respect to order
186  //insert at O
187  insertAtIndex(0,obj);
188  return 0;
189  }
190 
191  if (CORE_List::compare((*this)[sf],obj,mOrder)) {//values[sf] is before values[sf] with respect to order
192  //add at the end
193  push_back(obj);
194  return s;
195  }
196 
197  tUIndex i=0;
198  while (sf-si>1) {
199  i=(si+sf)/2;
200  //values[i] is before obj
201  if (CORE_List::compare((*this)[i],obj,mOrder)) si=i;
202  else sf=i;
203  }
204 
205  //sf=si
206  insertAtIndex(sf,obj);
207  return sf;
208 }
209 
210 
211 
214 template<class T>
216  const tUIndex& N,
217  const tFlag& order) {
218 
219  tUIndex h=1;
220  tUIndex i,j;
221  T v;
222  do h=3*h+1;
223  while (h<=N);
224  do {
225  h/=3;
226  for (i=h;i<N;++i) {
227  if (CORE_List::compare(items[i],
228  items[i-h],
229  order)) {
230  v=items[i];
231  j=i;
232  do {
233  items[j]=items[j-h];
234  j=j-h;
235  }
236  while ((j>=h) && (!CORE_List::compare(items[j-h],
237  v,
238  order)));
239  items[j]=v;
240  }
241  }
242  }
243  while (h>1);
244 }
245 
246 
247 template<class T>
249 
250  const tUIndex& n=CORE_Array<T>::getSize();
251  if (n==0) return;
252 
253  //mid index
254  tUIndex i,mid=n/2;
255 
256  //end element
257  T *e=&(*this)[n-1];
258  //first element
259  T *s=&(*this)[0];
260 
261  for (i=0;i<mid;i++) {
262  std::swap(*e,*s);
263  e--;
264  s++;
265  }
266 
267  //reverse the order
268  CORE_List::reverse(mOrder);
269 }
270 
271 
272 template<class T>
273 tBoolean CORE_ArrayList<T>::search(const T* values, const tUIndex& n,const tFlag& order,
274  const T& obj,
275  tUIndex& index) {
276 
277  tIndex si=0;
278  tIndex sf=n;
279  index=0;
280 
281  if (sf==0) {
282  return false;
283  }
284  sf--;
285 
286  // min
287  if (compare(obj,values[0],order)) {
288  return false;
289  }
290 
291  // max
292  if (compare(values[sf],obj,order)) {
293  return false;
294  }
295 
296  //eq
297  if (compare(values[0],obj,CORE_List::EQ)) {
298  return true;
299  }
300  if (compare(values[sf],obj,CORE_List::EQ)) {
301  index=sf;
302  return true;
303  }
304 
305 
306 
307  int i=0;
308  while (sf-si>1) {
309  i=(si+sf)/2;
310  if (compare(values[i],obj,CORE_List::EQ)) {
311  index=i;
312  return true;
313  } else if (compare(values[i],obj,order)) {//values[i] is before obj with respect of order
314  si=i;
315  } else sf=i;
316  }
317  if (compare(obj,values[sf],CORE_List::EQ)) {
318  index=sf;
319  return true;
320  }
321  if (compare(obj,values[si],CORE_List::EQ)) {
322  index=si;
323  return true;
324  }
325  return false;
326 }
327 template<class T>
329  // size of array to merge
330  const tUIndex& p=array.getSize();
331 
333 
334  //set the size
335  tUIndex dim=n+p;
336 
337  //get the capacity
338  const tUIndex& cap=CORE_Array<T>::getCapacity();
339  const tFlag& capF=getCapacityFactor();
340  if (dim>=cap) {//capacity too small
341  if ( (capF==1) || (cap==0) ) CORE_Array<T>::reserve(dim+1);
342  else CORE_Array<T>::reserve(cap*capF);
343  }
344 
345  //copy the values
346  T * vs=&CORE_Array<T>::getValues()[n];
347  const T* as=&array[0];
348  for (i=n;i<p;i++) {
349  *vs=*as;
350  as++;
351  vs++;
352  }
353 
354 
355 }
356 
357 #endif
void reverse()
reverse the array
Definition: CORE_ArrayList.hpp:248
const tUIndex & getSize() const
return the size of the array for reading
Definition: CORE_Array.h:1018
virtual void clear()
clear the array : desallocate the array
Definition: CORE_Array.h:300
void reserve(const tUIndex &cap)
reserve the capacity
Definition: CORE_Array.h:147
void contractToLastElements(const tUIndex &n)
keep only the last n elements of the array and set its capacity also to n
Definition: CORE_ArrayList.hpp:94
#define tBoolean
Definition: types.h:139
static tBoolean search(const T *values, const tUIndex &n, const tFlag &order, const T &value, tUIndex &index)
search the value in values array ordered in order
Definition: CORE_ArrayList.hpp:273
void insertAtIndex(const tUIndex &i, const T &v)
insert the object at index i
Definition: CORE_ArrayList.hpp:122
static tFlag reverse(const tFlag &oder)
return the reverse order
Definition: CORE_List.cpp:17
void setSize(const tUIndex &n)
set the size
Definition: CORE_Array.h:292
static const tFlag EQ
Definition: CORE_List.h:21
void push_back(const Q &v)
Definition: CORE_ArrayList.hpp:11
void append(const CORE_ArrayList< T > &array)
add the arry list at the end
Definition: CORE_ArrayList.hpp:328
void removeAtIndex(const tUIndex &i)
remove the element at index
Definition: CORE_ArrayList.hpp:66
tBoolean remove(const T &v)
remove all the element with the value
Definition: CORE_ArrayList.hpp:32
#define tIndex
Definition: types.h:129
const T * getValues() const
get the values of the array for reading
Definition: CORE_Array.h:930
virtual void fitToSize()
fit the array alocation exactly to size fit the allocation of the array to its size ...
Definition: CORE_Array.hpp:128
#define tUIndex
Definition: types.h:126
void sort()
sort the array in an increasing order obj[i-1] is obj[i] with respect to getOrder ...
Definition: CORE_ArrayList.h:264
tUIndex insert(const T &v)
insert the element in the array with respect to the order of the list
Definition: CORE_ArrayList.hpp:166
Definition: CORE_ArrayList.h:12
const tUIndex & getCapacity() const
get the capacity
Definition: CORE_Array.h:1012
static tBoolean compare(const Q &a, const Q &b, const tFlag &order)
compare 2 object a & b
Definition: CORE_List.h:55
#define tFlag
Definition: types.h:74