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