OpenClonk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
C4ValueArray.cpp
Go to the documentation of this file.
1 /*
2  * OpenClonk, http://www.openclonk.org
3  *
4  * Copyright (c) 2001-2009, RedWolf Design GmbH, http://www.clonk.de/
5  * Copyright (c) 2009-2016, The OpenClonk Team and contributors
6  *
7  * Distributed under the terms of the ISC license; see accompanying file
8  * "COPYING" for details.
9  *
10  * "Clonk" is a registered trademark of Matthes Bender, used with permission.
11  * See accompanying file "TRADEMARK" for details.
12  *
13  * To redistribute this file separately, substitute the full license texts
14  * for the above references.
15  */
16 #include "C4Include.h"
17 #include "script/C4ValueArray.h"
18 #include <algorithm>
19 
20 #include "script/C4Aul.h"
21 #include "object/C4FindObject.h"
22 
24  : pData(nullptr), iSize(0), iCapacity(0), constant(false)
25 {
26 }
27 
29  : pData(nullptr), iSize(0), iCapacity(0), constant(false)
30 {
31  SetSize(inSize);
32 }
33 
35  : pData(nullptr), iSize(0), iCapacity(0), constant(false)
36 {
37  SetSize(ValueArray2.GetSize());
38  for (int32_t i = 0; i < iSize; i++)
39  pData[i].Set(ValueArray2.GetItem(i));
40 }
41 
43 {
44  delete[] pData; pData = nullptr;
45  iSize = iCapacity = 0;
46 }
47 
49 {
50  this->SetSize(ValueArray2.GetSize());
51  for (int32_t i = 0; i < iSize; i++)
52  pData[i].Set(ValueArray2.GetItem(i));
53  return *this;
54 }
55 
57 {
58 private:
59  C4SortObject &rSorter;
60 
61 public:
62  C4SortObjectSTL(C4SortObject &rSorter) : rSorter(rSorter) {}
63  bool operator ()(const C4Value &v1, const C4Value &v2) { return rSorter.Compare(v1._getObj(), v2._getObj()) > 0; }
64 };
65 
67 {
68 private:
69  C4SortObject &rSorter;
70  C4Value *pVals;
71 
72 public:
73  C4SortObjectSTLCache(C4SortObject &rSorter, C4Value *pVals) : rSorter(rSorter), pVals(pVals) {}
74  bool operator ()(int32_t n1, int32_t n2) { return rSorter.CompareCache(n1, n2, pVals[n1]._getObj(), pVals[n2]._getObj()) > 0; }
75 };
76 
77 void C4ValueArray::Sort(class C4SortObject &rSort)
78 {
79  assert(!constant);
80  if (rSort.PrepareCache(this))
81  {
82  // Initialize position array
83  intptr_t i, *pPos = new intptr_t[iSize];
84  for (i = 0; i < iSize; i++) pPos[i] = i;
85  // Sort
86  std::stable_sort(pPos, pPos+iSize, C4SortObjectSTLCache(rSort, pData));
87  // Save actual object pointers in array (hacky).
88  for (i = 0; i < iSize; i++)
89  pPos[i] = reinterpret_cast<intptr_t>(pData[pPos[i]]._getObj());
90  // Set the values
91  for (i = 0; i < iSize; i++)
92  pData[i].SetPropList(reinterpret_cast<C4PropList *>(pPos[i]));
93  delete [] pPos;
94  }
95  else
96  // Be sure to use stable sort, as otherweise the algorithm isn't garantueed
97  // to produce identical results on all platforms!
98  std::stable_sort(pData, pData+iSize, C4SortObjectSTL(rSort));
99 }
100 
102 {
103  bool operator ()(const C4Value &v1, const C4Value &v2)
104  {
105  if (v1.getStr() && v2.getStr())
106  return std::strcmp(v1._getStr()->GetCStr(), v2._getStr()->GetCStr()) < 0;
107  return v2.getStr() != nullptr;
108  }
109 };
110 
112 {
113  assert(!constant);
114  std::stable_sort(pData, pData+iSize, C4ValueArraySortStringscomp());
115 }
116 
118 {
119  bool operator ()(const C4Value &v1, const C4Value &v2)
120  {
121  // sort by whatever type the values have
122  if (v1.getStr() && v2.getStr()) return v1._getStr()->GetData() < v2._getStr()->GetData();
123  if (v1.CheckConversion(C4V_Int) && v2.CheckConversion(C4V_Int)) return v1._getInt() < v2._getInt();
124  return false;
125  }
126 };
127 
128 void C4ValueArray::Sort(bool descending)
129 {
130  assert(!constant);
131  // sort by whatever type the values have
132  std::stable_sort(pData, pData+iSize, C4ValueArraySortcomp());
133  if (descending) std::reverse(pData, pData+iSize);
134 }
135 
137 {
139  C4ValueArraySortPropertycomp(C4String *prop_name) : prop_name(prop_name) {}
140  bool operator ()(const C4Value &v1, const C4Value &v2)
141  {
142  C4Value p1,p2;
143  if (!v1._getPropList()->GetPropertyByS(prop_name, &p1)) p1.Set0();
144  if (!v2._getPropList()->GetPropertyByS(prop_name, &p2)) p2.Set0();
145  return value_sort(p1,p2);
146  }
147 };
148 
149 bool C4ValueArray::SortByProperty(C4String *prop_name, bool descending)
150 {
151  assert(!constant);
152  // expect this to be an array of proplists and sort by given property
153  // make sure we're all proplists before
154  for (int32_t i=0; i<iSize; ++i)
155  if (!pData[i].getPropList())
156  return false;
157  // now sort
158  std::stable_sort(pData, pData+iSize, C4ValueArraySortPropertycomp(prop_name));
159  if (descending) std::reverse(pData, pData+iSize);
160  return true;
161 }
162 
164 {
166  C4ValueArraySortArrayElementcomp(int32_t element_idx) : element_idx(element_idx) {}
167  bool operator ()(const C4Value &v1, const C4Value &v2)
168  {
169  return value_sort(v1._getArray()->GetItem(element_idx), v2._getArray()->GetItem(element_idx));
170  }
171 };
172 
173 bool C4ValueArray::SortByArrayElement(int32_t element_idx, bool descending)
174 {
175  assert(element_idx>=0);
176  assert(!constant);
177  // expect this to be an array of arrays and sort by given element
178  // make sure we're all arrays before
179  for (int32_t i=0; i<iSize; ++i)
180  {
181  if (!pData[i].getArray())
182  return false;
183  if (pData[i]._getArray()->GetSize() <= element_idx)
184  return false;
185  }
186  // now sort
187  std::stable_sort(pData, pData+iSize, C4ValueArraySortArrayElementcomp(element_idx));
188  if (descending) std::reverse(pData, pData+iSize);
189  return true;
190 }
191 
193 {
194  assert(iElem < MaxSize);
195  assert(iElem >= 0);
196  assert(!constant);
197  if (iElem >= iSize && iElem < MaxSize) this->SetSize(iElem + 1);
198  // out-of-memory? This might not get caught, but it's better than a segfault
199  assert(iElem < iSize);
200  // return
201  return pData[iElem];
202 }
203 
204 void C4ValueArray::SetItem(int32_t iElem, const C4Value &Value)
205 {
206  assert(!constant);
207  // enlarge
208  if (iElem < -iSize)
209  throw C4AulExecError("array access: index out of range");
210  else if (iElem < 0)
211  iElem = iSize + iElem;
212  else if (iElem >= iSize && iElem < MaxSize) this->SetSize(iElem + 1);
213  // out-of-memory? This might not get caught, but it's better than a segfault
214  if (iElem >= iSize)
215  throw C4AulExecError("array access: index too large");
216  // set
217  pData[iElem]=Value;
218 }
219 
220 void C4ValueArray::SetSize(int32_t inSize)
221 {
222  if(inSize == iSize) return;
223  assert(!constant);
224 
225  // array not larger than allocated memory? Well, just ignore the additional allocated mem then
226  if (inSize <= iCapacity)
227  {
228  // free values in undefined area, do nothing if new is larger than old
229  for (int i=inSize; i<iSize; i++) pData[i].Set0();
230  iSize=inSize;
231  return;
232  }
233 
234  // bounds check
235  if (inSize > MaxSize) return;
236 
237  // create new array
238  C4Value* pnData = new C4Value [inSize];
239  if (!pnData) return;
240 
241  // move existing values
242  int32_t i;
243  for (i=0; i<iSize; i++)
244  pnData[i] = pData[i];
245 
246  // replace
247  delete[] pData;
248  pData = pnData;
249  iSize = iCapacity = inSize;
250 }
251 
252 bool C4ValueArray::operator==(const C4ValueArray& IntList2) const
253 {
254  for (int32_t i=0; i<std::max(iSize, IntList2.GetSize()); i++)
255  if (GetItem(i) != IntList2.GetItem(i))
256  return false;
257 
258  return true;
259 }
260 
262 {
263  delete[] pData; pData = nullptr;
264  iSize = iCapacity = 0;
265 }
266 
268 {
269  for (int32_t i = 0; i < iSize; i++)
270  pData[i].Denumerate(numbers);
271 }
272 
274 {
275  int32_t inSize = iSize;
276  // Size. Reset if not found.
277  try
278  { pComp->Value(inSize); }
279  catch (StdCompiler::NotFoundException *pExc)
280  { Reset(); delete pExc; return; }
281  // Separator
283  // Allocate
284  if (pComp->isDeserializer()) this->SetSize(inSize);
285  // Values
286  pComp->Value(mkArrayAdaptMap(pData, iSize, C4Value(), mkParAdaptMaker(numbers)));
287 }
288 
289 enum { C4VALUEARRAY_DEBUG = 0 };
290 
291 C4ValueArray * C4ValueArray::GetSlice(int32_t startIndex, int32_t endIndex)
292 {
293  // adjust indices so that the default end index works and that negative numbers count backwards from the end of the string
294  if (startIndex > iSize) startIndex = iSize;
295  else if (startIndex < -iSize) throw C4AulExecError("array slice: start index out of range");
296  else if (startIndex < 0) startIndex += iSize;
297 
298  if (endIndex > iSize) endIndex = iSize; // this also processes the MAX_INT default if no parameter is given in script
299  else if (endIndex < -iSize) throw C4AulExecError("array slice: end index out of range");
300  else if (endIndex < 0) endIndex += iSize;
301 
302  C4ValueArray* NewArray = new C4ValueArray(std::max(0, endIndex - startIndex));
303  for (int i = startIndex; i < endIndex; ++i)
304  NewArray->pData[i - startIndex] = pData[i];
305  return NewArray;
306 }
307 
308 
309 void C4ValueArray::SetSlice(int32_t startIndex, int32_t endIndex, const C4Value &Val)
310 {
311  // maximum bounds
312  if(startIndex >= MaxSize) throw C4AulExecError("array slice: start index exceeds maximum capacity");
313 
314  // index from back
315  if(startIndex < 0) startIndex += iSize;
316  if(endIndex < 0) endIndex += iSize;
317 
318  // ensure relevant bounds
319  if(startIndex < 0) throw C4AulExecError("array slice: start index out of range");
320  if(endIndex < 0) throw C4AulExecError("array slice: end index out of range");
321  if(endIndex < startIndex)
322  endIndex = startIndex;
323 
324  // setting an array?
325  if(Val.GetType() == C4V_Array)
326  {
327  const C4ValueArray &Other = *Val._getArray(); // Remember that &Other could be equal to this, carefull with modifying pData
328 
329  // Calculcate new size
330  int32_t iNewEnd = std::min(startIndex + Other.GetSize(), (int32_t)MaxSize);
331  int32_t iNewSize = iNewEnd;
332  if(endIndex < iSize)
333  iNewSize += iSize - endIndex;
334  iNewSize = std::min(iNewSize, (int32_t)MaxSize);
335  int32_t iOtherSize = Other.GetSize();
336 
337  if(iNewSize != iSize)
338  {
339  int32_t i,j;
340  C4Value* pnData = pData;
341 
342  if(iNewSize > iCapacity)
343  {
344  pnData = new C4Value [iNewSize];
345 
346  // Copy first part of old array
347  for(i = 0; i < startIndex && i < iSize; ++i)
348  pnData[i] = pData[i];
349  }
350 
351  // Copy the second slice of the new array
352  for(i = iNewEnd, j = endIndex; i < iNewSize; ++i, ++j)
353  {
354  assert(j < iSize);
355  pnData[i] = pData[j];
356  }
357 
358  // Copy the data
359  // Since pnData and pData can be the same, we can not copy with
360  //for(i = startIndex, j = 0; i < iNewEnd; ++i, ++j)
361  // but have to start from the end of the copied sequence. That works, since j <= i
362  for(i = iNewEnd - 1, j = iNewEnd - startIndex - 1; i >= startIndex; --i, --j)
363  {
364  assert(j < iOtherSize);
365  pnData[i] = Other.pData[j];
366  }
367 
368  // Other values should have been initialized to 0 by new
369  if(pData != pnData)
370  {
371  delete [] pData;
372  pData = pnData;
373  iCapacity = iSize = iNewSize;
374  }
375  else
376  {
377  // "ignore" the now unused part
378  for(i = iNewSize; i < iSize; ++i)
379  pData[i].Set0();
380  iSize = iNewSize;
381  }
382 
383  } else // slice has the same size as inserted array
384  // Copy the data. changing pData does not break because if &Other == this and iNewSize == iSize, nothing happens at all
385  for(int32_t i = startIndex, j = 0; j < iOtherSize; i++, j++)
386  pData[i] = Other.pData[j];
387 
388  } else /* if(Val.GetType() != C4V_Array) */ {
389  if(endIndex > MaxSize) endIndex = iSize;
390 
391  // Need resize?
392  if(endIndex > iSize) SetSize(endIndex);
393 
394  // Fill
395  for(int32_t i = startIndex; i < endIndex; i++)
396  pData[i] = Val;
397 
398  }
399 
400 }
virtual bool Separator(Sep eSep=SEP_SEP)
Definition: StdCompiler.h:129
StdStrBuf GetData() const
Definition: C4StringTable.h:50
void SetItem(int32_t iElemNr, const C4Value &Value)
C4ValueArraySortArrayElementcomp(int32_t element_idx)
C4String * getStr() const
Definition: C4Value.h:117
bool SortByArrayElement(int32_t array_idx, bool descending=false)
void Denumerate(C4ValueNumbers *)
void SortStrings()
const char * GetCStr() const
Definition: C4StringTable.h:49
C4String * _getStr() const
Definition: C4Value.h:126
void Set0()
Definition: C4Value.h:336
StdParameterAdaptMaker< P > mkParAdaptMaker(P &&rPar)
Definition: StdAdaptors.h:469
virtual int32_t Compare(C4Object *pObj1, C4Object *pObj2)=0
bool operator()(const C4Value &v1, const C4Value &v2)
bool operator()(const C4Value &v1, const C4Value &v2)
const C4Value & GetItem(int32_t iElem) const
Definition: C4ValueArray.h:38
ALWAYS_INLINE bool CheckConversion(C4V_Type vtToType) const
Definition: C4Value.h:189
C4ValueArray * _getArray() const
Definition: C4Value.h:127
C4ValueArraySortcomp value_sort
C4SortObjectSTL(C4SortObject &rSorter)
C4ValueArraySortcomp value_sort
bool SortByProperty(C4String *prop_name, bool descending=false)
C4V_Type GetType() const
Definition: C4Value.h:161
C4Object * _getObj() const
Definition: C4Value.cpp:75
virtual bool GetPropertyByS(const C4String *k, C4Value *pResult) const
Definition: C4PropList.cpp:734
bool operator()(int32_t n1, int32_t n2)
int32_t _getInt() const
Definition: C4Value.h:122
void SetSize(int32_t inSize)
C4ValueArraySortPropertycomp(C4String *prop_name)
void SetSlice(int32_t startIndex, int32_t endIndex, const C4Value &Val)
void Value(const T &rStruct)
Definition: StdCompiler.h:171
int32_t GetSize() const
Definition: C4ValueArray.h:36
void Sort(class C4SortObject &rSort)
virtual bool isDeserializer()
Definition: StdCompiler.h:63
bool operator()(const C4Value &v1, const C4Value &v2)
bool operator()(const C4Value &v1, const C4Value &v2)
C4ValueArray & operator=(const C4ValueArray &)
C4SortObjectSTLCache(C4SortObject &rSorter, C4Value *pVals)
virtual bool PrepareCache(const C4ValueArray *pObjs)
Definition: C4FindObject.h:411
void CompileFunc(class StdCompiler *pComp, C4ValueNumbers *)
C4ValueArray * GetSlice(int32_t startIndex, int32_t endIndex)
bool operator()(const C4Value &v1, const C4Value &v2)
C4PropList * _getPropList() const
Definition: C4Value.h:129
StdArrayAdapt< T, M > mkArrayAdaptMap(T *pArray, int iSize, M &&map)
Definition: StdAdaptors.h:311
bool operator==(const C4ValueArray &) const
virtual int32_t CompareCache(int32_t iObj1, int32_t iObj2, C4Object *pObj1, C4Object *pObj2)
Definition: C4FindObject.h:412
C4Value operator[](int32_t iElem) const
Definition: C4ValueArray.h:53
int iSize
Definition: TstC4NetIO.cpp:35