1/*
2 * LegacyClonk
3 *
4 * Copyright (c) RedWolf Design
5 * Copyright (c) 2017-2022, The LegacyClonk 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
17#include <C4Include.h>
18#include <C4FindObject.h>
19
20#include <C4Object.h>
21#include <C4Game.h>
22#include <C4Wrappers.h>
23#include <C4Random.h>
24
25#include <algorithm>
26#include <numeric>
27#include <ranges>
28#include <utility>
29
30// *** C4FindObject
31
32C4FindObject::~C4FindObject()
33{
34 delete pSort;
35}
36
37C4FindObject *C4FindObject::CreateByValue(const C4Value &DataVal, C4SortObject **ppSortObj)
38{
39 // Must be an array
40 C4ValueArray *pArray = C4Value(DataVal).getArray();
41 if (!pArray) return nullptr;
42
43 const C4ValueArray &Data = *pArray;
44 const auto iType = Data[0].getInt();
45 if (Inside<decltype(iType)>(ival: iType, lbound: C4SO_First, rbound: C4SO_Last))
46 {
47 // this is not a FindObject but a sort condition!
48 // sort condition not desired here?
49 if (!ppSortObj) return nullptr;
50 // otherwise, create it!
51 *ppSortObj = C4SortObject::CreateByValue(iType, Data);
52 // done
53 return nullptr;
54 }
55
56 switch (iType)
57 {
58 case C4FO_Not:
59 {
60 // Create child condition
61 C4FindObject *pCond = C4FindObject::CreateByValue(DataVal: Data[1]);
62 if (!pCond) return nullptr;
63 // wrap
64 return new C4FindObjectNot(pCond);
65 }
66
67 case C4FO_And: case C4FO_Or:
68 {
69 // Trivial case (one condition)
70 if (Data.GetSize() == 2)
71 return C4FindObject::CreateByValue(DataVal: Data[1]);
72 // Create all childs
73 C4FindObject **ppConds = new C4FindObject *[Data.GetSize() - 1];
74 for (int32_t i = 0; i < Data.GetSize() - 1; i++)
75 ppConds[i] = C4FindObject::CreateByValue(DataVal: Data[i + 1]);
76 // Count real entries, move them to start of list
77 int32_t iSize = 0;
78 for (int32_t i = 0; i < Data.GetSize() - 1; i++)
79 if (ppConds[i])
80 if (iSize++ != i)
81 ppConds[iSize - 1] = ppConds[i];
82 // Create
83 if (iType == C4FO_And)
84 return new C4FindObjectAnd(iSize, ppConds);
85 else
86 return new C4FindObjectOr(iSize, ppConds);
87 }
88
89 case C4FO_Exclude:
90 return new C4FindObjectExclude(Data[1].getObj());
91
92 case C4FO_ID:
93 return new C4FindObjectID(Data[1].getC4ID());
94
95 case C4FO_InRect:
96 return new C4FindObjectInRect(C4Rect(Data[1].getInt(), Data[2].getInt(), Data[3].getInt(), Data[4].getInt()));
97
98 case C4FO_AtPoint:
99 return new C4FindObjectAtPoint(Data[1].getInt(), Data[2].getInt());
100
101 case C4FO_AtRect:
102 return new C4FindObjectAtRect(Data[1].getInt(), Data[2].getInt(), Data[3].getInt(), Data[4].getInt());
103
104 case C4FO_OnLine:
105 return new C4FindObjectOnLine(Data[1].getInt(), Data[2].getInt(), Data[3].getInt(), Data[4].getInt());
106
107 case C4FO_Distance:
108 return new C4FindObjectDistance(Data[1].getInt(), Data[2].getInt(), Data[3].getInt());
109
110 case C4FO_OCF:
111 return new C4FindObjectOCF(Data[1].getInt());
112
113 case C4FO_Category:
114 return new C4FindObjectCategory(Data[1].getInt());
115
116 case C4FO_Action:
117 {
118 C4String *pStr = Data[1].getStr();
119 if (!pStr) return nullptr;
120 // Don't copy, it should be safe
121 return new C4FindObjectAction(pStr->Data.getData());
122 }
123
124 case C4FO_Func:
125 {
126 // Get function name
127 C4String *pStr = Data[1].getStr();
128 if (!pStr) return nullptr;
129 // Construct
130 C4FindObjectFunc *pFO = new C4FindObjectFunc(pStr->Data.getData());
131 // Add parameters
132 for (int i = 2; i < Data.GetSize(); i++)
133 pFO->SetPar(i: i - 2, val: Data[i]);
134 // Done
135 return pFO;
136 }
137
138 case C4FO_ActionTarget:
139 {
140 int32_t index = 0;
141 if (Data.GetSize() >= 3)
142 index = static_cast<decltype(index)>(BoundBy<C4ValueInt>(bval: Data[2].getInt(), lbound: 0, rbound: 1));
143 return new C4FindObjectActionTarget(Data[1].getObj(), index);
144 }
145
146 case C4FO_Container:
147 return new C4FindObjectContainer(Data[1].getObj());
148
149 case C4FO_AnyContainer:
150 return new C4FindObjectAnyContainer();
151
152 case C4FO_Owner:
153 return new C4FindObjectOwner(Data[1].getInt());
154
155 case C4FO_Controller:
156 return new C4FindObjectController(Data[1].getInt());
157
158 case C4FO_Layer:
159 return new C4FindObjectLayer(Data[1].getObj());
160 }
161 return nullptr;
162}
163
164int32_t C4FindObject::Count(const C4ObjectList &Objs)
165{
166 // Trivial cases
167 if (IsImpossible())
168 return 0;
169 if (IsEnsured())
170 return Objs.ObjectCount();
171 // Count
172 int32_t iCount = 0;
173 for (C4ObjectLink *pLnk = Objs.First; pLnk; pLnk = pLnk->Next)
174 if (pLnk->Obj->Status)
175 if (Check(pObj: pLnk->Obj))
176 iCount++;
177 return iCount;
178}
179
180C4Object *C4FindObject::Find(const C4ObjectList &Objs)
181{
182 // Trivial case
183 if (IsImpossible())
184 return nullptr;
185 // Search
186 // Double-check object status, as object might be deleted after Check()!
187 C4Object *pBestResult = nullptr;
188 for (C4ObjectLink *pLnk = Objs.First; pLnk; pLnk = pLnk->Next)
189 if (pLnk->Obj->Status)
190 if (Check(pObj: pLnk->Obj))
191 if (pLnk->Obj->Status)
192 {
193 // no sorting: Use first object found
194 if (!pSort) return pLnk->Obj;
195 // Sorting: Check if found object is better
196 if (!pBestResult || pSort->Compare(pObj1: pLnk->Obj, pObj2: pBestResult) > 0)
197 if (pLnk->Obj->Status)
198 pBestResult = pLnk->Obj;
199 }
200 return pBestResult;
201}
202
203C4ValueArray *C4FindObject::FindMany(const C4ObjectList &Objs)
204{
205 // Trivial case
206 if (IsImpossible())
207 return new C4ValueArray();
208 // Set up array
209 std::vector<C4Object *> result;
210 // Search
211 for (C4ObjectLink *pLnk = Objs.First; pLnk; pLnk = pLnk->Next)
212 if (pLnk->Obj->Status)
213 if (Check(pObj: pLnk->Obj))
214 {
215 result.push_back(x: pLnk->Obj);
216 }
217 // Recheck object status (may shrink array again)
218 CheckObjectStatus(objects&: result);
219 // Apply sorting
220 if (pSort)
221 {
222 pSort->SortObjects(result);
223 CheckObjectStatusAfterSort(objects&: result);
224 }
225 return new C4ValueArray{std::span{result}};
226}
227
228int32_t C4FindObject::Count(const C4ObjectList &Objs, const C4LSectors &Sct)
229{
230 // Trivial cases
231 if (IsImpossible())
232 return 0;
233 if (IsEnsured())
234 return Objs.ObjectCount();
235 // Check bounds
236 C4Rect *pBounds = GetBounds();
237 if (!pBounds)
238 return Count(Objs);
239 else if (UseShapes())
240 {
241 // Get area
242 C4LArea Area(&Game.Objects.Sectors, *pBounds); C4LSector *pSct;
243 C4ObjectList *pLst = Area.FirstObjectShapes(ppSct: &pSct);
244 // Check if a single-sector check is enough
245 if (!Area.Next(pPrev: pSct))
246 return Count(Objs: pSct->ObjectShapes);
247 // Create marker, count over all areas
248 uint32_t iMarker = ::Game.Objects.GetNextMarker();
249 int32_t iCount = 0;
250 for (; pLst; pLst = Area.NextObjectShapes(pPrev: pLst, ppSct: &pSct))
251 for (C4ObjectLink *pLnk = pLst->First; pLnk; pLnk = pLnk->Next)
252 if (pLnk->Obj->Status)
253 if (pLnk->Obj->Marker != iMarker)
254 {
255 pLnk->Obj->Marker = iMarker;
256 if (Check(pObj: pLnk->Obj))
257 iCount++;
258 }
259 return iCount;
260 }
261 else
262 {
263 // Count objects per area
264 C4LArea Area(&Game.Objects.Sectors, *pBounds); C4LSector *pSct;
265 int32_t iCount = 0;
266 for (C4ObjectList *pLst = Area.FirstObjects(ppSct: &pSct); pLst; pLst = Area.NextObjects(pPrev: pLst, ppSct: &pSct))
267 iCount += Count(Objs: *pLst);
268 return iCount;
269 }
270}
271
272C4Object *C4FindObject::Find(const C4ObjectList &Objs, const C4LSectors &Sct)
273{
274 // Trivial case
275 if (IsImpossible())
276 return nullptr;
277 C4Object *pBestResult = nullptr;
278 // Check bounds
279 C4Rect *pBounds = GetBounds();
280 if (!pBounds)
281 return Find(Objs);
282 // Traverse areas, return first matching object w/o sort or best with sort
283 else if (UseShapes())
284 {
285 C4LArea Area(&Game.Objects.Sectors, *pBounds); C4LSector *pSct;
286 C4Object *pObj;
287 for (C4ObjectList *pLst = Area.FirstObjectShapes(ppSct: &pSct); pLst; pLst = Area.NextObjectShapes(pPrev: pLst, ppSct: &pSct))
288 if (pObj = Find(Objs: *pLst))
289 if (!pSort)
290 return pObj;
291 else if (!pBestResult || pSort->Compare(pObj1: pObj, pObj2: pBestResult) > 0)
292 if (pObj->Status)
293 pBestResult = pObj;
294 }
295 else
296 {
297 C4LArea Area(&Game.Objects.Sectors, *pBounds); C4LSector *pSct;
298 C4Object *pObj;
299 for (C4ObjectList *pLst = Area.FirstObjects(ppSct: &pSct); pLst; pLst = Area.NextObjects(pPrev: pLst, ppSct: &pSct))
300 if (pObj = Find(Objs: *pLst))
301 if (!pSort)
302 return pObj;
303 else if (!pBestResult || pSort->Compare(pObj1: pObj, pObj2: pBestResult) > 0)
304 if (pObj->Status)
305 pBestResult = pObj;
306 }
307 return pBestResult;
308}
309
310C4ValueArray *C4FindObject::FindMany(const C4ObjectList &Objs, const C4LSectors &Sct)
311{
312 // Trivial case
313 if (IsImpossible())
314 return new C4ValueArray();
315 C4Rect *pBounds = GetBounds();
316 if (!pBounds)
317 return FindMany(Objs);
318
319 std::vector<C4Object *> result;
320 // Check shape lists?
321 if (UseShapes())
322 {
323 // Get area
324 C4LArea Area(&Game.Objects.Sectors, *pBounds); C4LSector *pSct;
325 C4ObjectList *pLst = Area.FirstObjectShapes(ppSct: &pSct);
326 // Check if a single-sector check is enough
327 if (!Area.Next(pPrev: pSct))
328 return FindMany(Objs: pSct->ObjectShapes);
329 // Set up array
330 // Create marker, search all areas
331 uint32_t iMarker = ::Game.Objects.GetNextMarker();
332 for (; pLst; pLst = Area.NextObjectShapes(pPrev: pLst, ppSct: &pSct))
333 for (C4ObjectLink *pLnk = pLst->First; pLnk; pLnk = pLnk->Next)
334 if (pLnk->Obj->Status)
335 if (pLnk->Obj->Marker != iMarker)
336 {
337 pLnk->Obj->Marker = iMarker;
338 if (Check(pObj: pLnk->Obj))
339 {
340 result.push_back(x: pLnk->Obj);
341 }
342 }
343 }
344 else
345 {
346 // Search
347 C4LArea Area(&Game.Objects.Sectors, *pBounds); C4LSector *pSct;
348 for (C4ObjectList *pLst = Area.FirstObjects(ppSct: &pSct); pLst; pLst = Area.NextObjects(pPrev: pLst, ppSct: &pSct))
349 for (C4ObjectLink *pLnk = pLst->First; pLnk; pLnk = pLnk->Next)
350 if (pLnk->Obj->Status)
351 if (Check(pObj: pLnk->Obj))
352 {
353 result.push_back(x: pLnk->Obj);
354 }
355 }
356 // Recheck object status (may shrink array again)
357 CheckObjectStatus(objects&: result);
358 // Apply sorting
359 if (pSort)
360 {
361 pSort->SortObjects(result);
362 CheckObjectStatusAfterSort(objects&: result);
363 }
364 return new C4ValueArray{std::span{result}};
365}
366
367void C4FindObject::CheckObjectStatus(std::vector<C4Object *> &objects)
368{
369 std::erase_if(cont&: objects, pred: [](C4Object *const obj) { return !obj->Status; });
370}
371
372void C4FindObject::CheckObjectStatusAfterSort(std::vector<C4Object *> &objects)
373{
374 std::ranges::replace_if(objects, [](C4Object *const obj) { return !obj->Status; }, nullptr);
375}
376
377void C4FindObject::SetSort(C4SortObject *pToSort)
378{
379 delete pSort;
380 pSort = pToSort;
381}
382
383// *** C4FindObjectNot
384
385C4FindObjectNot::~C4FindObjectNot()
386{
387 delete pCond;
388}
389
390bool C4FindObjectNot::Check(C4Object *pObj)
391{
392 return !pCond->Check(pObj);
393}
394
395// *** C4FindObjectAnd
396
397C4FindObjectAnd::C4FindObjectAnd(int32_t inCnt, C4FindObject **ppConds, bool fFreeArray)
398 : iCnt(inCnt), ppConds(ppConds), fHasBounds(false), fUseShapes(false), fFreeArray(fFreeArray)
399{
400 // Filter ensured entries
401 for (int32_t i = 0; i < iCnt;)
402 if (ppConds[i]->IsEnsured())
403 {
404 delete ppConds[i];
405 iCnt--;
406 for (int32_t j = i; j < iCnt; j++)
407 ppConds[j] = ppConds[j + 1];
408 }
409 else
410 i++;
411 // Intersect all child bounds
412 for (int32_t i = 0; i < iCnt; i++)
413 {
414 C4Rect *pChildBounds = ppConds[i]->GetBounds();
415 if (pChildBounds)
416 {
417 // some objects might be in an rect and at a point not in that rect
418 // so do not intersect an atpoint bound with an rect bound
419 fUseShapes = ppConds[i]->UseShapes();
420 if (fUseShapes)
421 {
422 Bounds = *pChildBounds;
423 fHasBounds = true;
424 break;
425 }
426 if (fHasBounds)
427 Bounds.Intersect(r2: *pChildBounds);
428 else
429 {
430 Bounds = *pChildBounds;
431 fHasBounds = true;
432 }
433 }
434 }
435}
436
437C4FindObjectAnd::~C4FindObjectAnd()
438{
439 for (int32_t i = 0; i < iCnt; i++)
440 delete ppConds[i];
441 if (fFreeArray)
442 delete[] ppConds;
443}
444
445bool C4FindObjectAnd::Check(C4Object *pObj)
446{
447 for (int32_t i = 0; i < iCnt; i++)
448 if (!ppConds[i]->Check(pObj))
449 return false;
450 return true;
451}
452
453bool C4FindObjectAnd::IsImpossible()
454{
455 for (int32_t i = 0; i < iCnt; i++)
456 if (ppConds[i]->IsImpossible())
457 return true;
458 return false;
459}
460
461// *** C4FindObjectOr
462
463C4FindObjectOr::C4FindObjectOr(int32_t inCnt, C4FindObject **ppConds)
464 : iCnt(inCnt), ppConds(ppConds), fHasBounds(false)
465{
466 // Filter impossible entries
467 for (int32_t i = 0; i < iCnt;)
468 if (ppConds[i]->IsImpossible())
469 {
470 delete ppConds[i];
471 iCnt--;
472 for (int32_t j = i; j < iCnt; j++)
473 ppConds[j] = ppConds[j + 1];
474 }
475 else
476 i++;
477 // Sum up all child bounds
478 for (int32_t i = 0; i < iCnt; i++)
479 {
480 C4Rect *pChildBounds = ppConds[i]->GetBounds();
481 if (!pChildBounds) { fHasBounds = false; break; }
482 // Do not optimize atpoint: It could lead to having to search multiple
483 // sectors. An object's shape can be in multiple sectors. We do not want
484 // to find the same object twice.
485 if (ppConds[i]->UseShapes())
486 {
487 fHasBounds = false; break;
488 }
489 if (fHasBounds)
490 Bounds.Add(r2: *pChildBounds);
491 else
492 {
493 Bounds = *pChildBounds;
494 fHasBounds = true;
495 }
496 }
497}
498
499C4FindObjectOr::~C4FindObjectOr()
500{
501 for (int32_t i = 0; i < iCnt; i++)
502 delete ppConds[i];
503 delete[] ppConds;
504}
505
506bool C4FindObjectOr::Check(C4Object *pObj)
507{
508 for (int32_t i = 0; i < iCnt; i++)
509 if (ppConds[i]->Check(pObj))
510 return true;
511 return false;
512}
513
514bool C4FindObjectOr::IsEnsured()
515{
516 for (int32_t i = 0; i < iCnt; i++)
517 if (ppConds[i]->IsEnsured())
518 return true;
519 return false;
520}
521
522// *** C4FindObject* (primitive conditions)
523
524bool C4FindObjectExclude::Check(C4Object *pObj)
525{
526 return pObj != pExclude;
527}
528
529bool C4FindObjectID::Check(C4Object *pObj)
530{
531 return pObj->id == id;
532}
533
534bool C4FindObjectID::IsImpossible()
535{
536 C4Def *pDef = C4Id2Def(id);
537 return !pDef || !pDef->Count;
538}
539
540bool C4FindObjectInRect::Check(C4Object *pObj)
541{
542 return rect.Contains(iX: pObj->x, iY: pObj->y);
543}
544
545bool C4FindObjectInRect::IsImpossible()
546{
547 return !rect.Wdt || !rect.Hgt;
548}
549
550bool C4FindObjectAtPoint::Check(C4Object *pObj)
551{
552 return pObj->Shape.Contains(iX: bounds.x - pObj->x, iY: bounds.y - pObj->y);
553}
554
555bool C4FindObjectAtRect::Check(C4Object *pObj)
556{
557 C4Rect rcShapeBounds = pObj->Shape;
558 rcShapeBounds.x += pObj->x; rcShapeBounds.y += pObj->y;
559 return !!rcShapeBounds.Overlap(rTarget&: bounds);
560}
561
562bool C4FindObjectOnLine::Check(C4Object *pObj)
563{
564 return pObj->Shape.IntersectsLine(iX: x - pObj->x, iY: y - pObj->y, iX2: x2 - pObj->x, iY2: y2 - pObj->y);
565}
566
567bool C4FindObjectDistance::Check(C4Object *pObj)
568{
569 return (pObj->x - x) * (pObj->x - x) + (pObj->y - y) * (pObj->y - y) <= r2;
570}
571
572bool C4FindObjectOCF::Check(C4Object *pObj)
573{
574 return !!(pObj->OCF & ocf);
575}
576
577bool C4FindObjectOCF::IsImpossible()
578{
579 return !ocf;
580}
581
582bool C4FindObjectCategory::Check(C4Object *pObj)
583{
584 return !!(pObj->Category & iCategory);
585}
586
587bool C4FindObjectCategory::IsEnsured()
588{
589 return !iCategory;
590}
591
592bool C4FindObjectAction::Check(C4Object *pObj)
593{
594 return SEqual(szStr1: pObj->Action.Name, szStr2: szAction);
595}
596
597bool C4FindObjectActionTarget::Check(C4Object *pObj)
598{
599 assert(index >= 0 && index <= 1);
600 if (index == 0)
601 return pObj->Action.Target == pActionTarget;
602 else if (index == 1)
603 return pObj->Action.Target2 == pActionTarget;
604 else
605 return false;
606}
607
608bool C4FindObjectContainer::Check(C4Object *pObj)
609{
610 return pObj->Contained == pContainer;
611}
612
613bool C4FindObjectAnyContainer::Check(C4Object *pObj)
614{
615 return !!pObj->Contained;
616}
617
618bool C4FindObjectOwner::Check(C4Object *pObj)
619{
620 return pObj->Owner == iOwner;
621}
622
623bool C4FindObjectOwner::IsImpossible()
624{
625 return iOwner != NO_OWNER && !ValidPlr(plr: iOwner);
626}
627
628bool C4FindObjectController::Check(C4Object *pObj)
629{
630 return pObj->Controller == controller;
631}
632
633bool C4FindObjectController::IsImpossible()
634{
635 return controller != NO_OWNER && !ValidPlr(plr: controller);
636}
637
638// *** C4FindObjectFunc
639
640C4FindObjectFunc::C4FindObjectFunc(const char *szFunc)
641{
642 pFunc = Game.ScriptEngine.GetFirstFunc(Name: szFunc);
643}
644
645void C4FindObjectFunc::SetPar(int i, const C4Value &Par)
646{
647 // Over limit?
648 if (i >= C4AUL_MAX_Par) return;
649 // Set parameter
650 Pars[i] = Par;
651}
652
653bool C4FindObjectFunc::Check(C4Object *pObj)
654{
655 // Function not found?
656 if (!pFunc) return false;
657 // Search same-name-list for appropriate function
658 C4AulFunc *pCallFunc = pFunc->FindSameNameFunc(pScope: pObj->Def);
659 if (!pCallFunc) return false;
660 // Call
661 return static_cast<bool>(pCallFunc->Exec(pObj, pPars: Pars, fPassErrors: true));
662}
663
664bool C4FindObjectFunc::IsImpossible()
665{
666 return !pFunc;
667}
668
669// *** C4FindObjectLayer
670
671bool C4FindObjectLayer::Check(C4Object *pObj)
672{
673 return pObj->pLayer == pLayer;
674}
675
676bool C4FindObjectLayer::IsImpossible()
677{
678 return false;
679}
680
681// *** C4SortObject
682
683C4SortObject *C4SortObject::CreateByValue(const C4Value &DataVal)
684{
685 // Must be an array
686 const C4ValueArray *pArray = C4Value(DataVal).getArray();
687 if (!pArray) return nullptr;
688 const C4ValueArray &Data = *pArray;
689 return CreateByValue(iType: Data[0].getInt(), Data);
690}
691
692C4SortObject *C4SortObject::CreateByValue(C4ValueInt iType, const C4ValueArray &Data)
693{
694 switch (iType)
695 {
696 case C4SO_Reverse:
697 {
698 // create child sort
699 C4SortObject *pChildSort = C4SortObject::CreateByValue(DataVal: Data[1]);
700 if (!pChildSort) return nullptr;
701 // wrap
702 return new C4SortObjectReverse(pChildSort);
703 }
704
705 case C4SO_Multiple:
706 {
707 // Trivial case (one sort)
708 if (Data.GetSize() == 2)
709 {
710 return C4SortObject::CreateByValue(DataVal: Data[1]);
711 }
712 // Create all children
713 C4SortObject **ppSorts = new C4SortObject *[Data.GetSize() - 1];
714 for (int32_t i = 0; i < Data.GetSize() - 1; i++)
715 {
716 ppSorts[i] = C4SortObject::CreateByValue(DataVal: Data[i + 1]);
717 }
718 // Count real entries, move them to start of list
719 int32_t iSize = 0;
720 for (int32_t i = 0; i < Data.GetSize() - 1; i++)
721 if (ppSorts[i])
722 if (iSize++ != i)
723 ppSorts[iSize - 1] = ppSorts[i];
724 // Create
725 return new C4SortObjectMultiple(iSize, ppSorts);
726 }
727
728 case C4SO_Distance:
729 return new C4SortObjectDistance(Data[1].getInt(), Data[2].getInt());
730
731 case C4SO_Random:
732 return new C4SortObjectRandom();
733
734 case C4SO_Speed:
735 return new C4SortObjectSpeed();
736
737 case C4SO_Mass:
738 return new C4SortObjectMass();
739
740 case C4SO_Value:
741 return new C4SortObjectValue();
742
743 case C4SO_Func:
744 {
745 // Get function name
746 C4String *pStr = Data[1].getStr();
747 if (!pStr) return nullptr;
748 // Construct
749 C4SortObjectFunc *pSO = new C4SortObjectFunc(pStr->Data.getData());
750 // Add parameters
751 for (int i = 2; i < Data.GetSize(); i++)
752 pSO->SetPar(i: i - 2, val: Data[i]);
753 // Done
754 return pSO;
755 }
756 }
757 return nullptr;
758}
759
760namespace
761{
762 class C4SortObjectSTL
763 {
764 private:
765 C4SortObject &rSorter;
766
767 public:
768 C4SortObjectSTL(C4SortObject &rSorter) : rSorter(rSorter) {}
769 bool operator()(C4Object *const v1, C4Object *const v2) { return rSorter.Compare(pObj1: v1, pObj2: v2) > 0; }
770 };
771
772 class C4SortObjectSTLCache
773 {
774 private:
775 C4SortObject &rSorter;
776 std::vector<C4Object *> &values;
777
778 public:
779 C4SortObjectSTLCache(C4SortObject &rSorter, std::vector<C4Object *> &values) : rSorter(rSorter), values{values} {}
780 bool operator()(int32_t n1, int32_t n2) { return rSorter.CompareCache(iObj1: n1, iObj2: n2, pObj1: values[n1], pObj2: values[n2]) > 0; }
781 };
782}
783
784void C4SortObject::SortObjects(std::vector<C4Object *> &result)
785{
786 if (PrepareCache(objects&: result))
787 {
788 auto positions = std::make_unique_for_overwrite<std::intptr_t[]>(num: result.size());
789 std::span positionsSpan{positions.get(), result.size()};
790
791 // Initialize position array
792 std::iota(first: positionsSpan.begin(), last: positionsSpan.end(), value: 0);
793 // Sort
794 std::ranges::stable_sort(positionsSpan, C4SortObjectSTLCache{*this, result});
795 // Save actual object pointers in array (hacky).
796 for (std::size_t i{0}; i < result.size(); ++i)
797 {
798 positions[i] = reinterpret_cast<std::intptr_t>(result[positions[i]]);
799 }
800 // Set the values
801 for (std::size_t i{0}; i < result.size(); ++i)
802 {
803 result[i] = reinterpret_cast<C4Object *>(positions[i]);
804 }
805 }
806 else
807 {
808 // Be sure to use stable sort, as otherweise the algorithm isn't garantueed
809 // to produce identical results on all platforms!
810 std::ranges::stable_sort(result, C4SortObjectSTL{*this});
811 }
812}
813
814// *** C4SortObjectByValue
815
816C4SortObjectByValue::C4SortObjectByValue()
817 : C4SortObject() {}
818
819bool C4SortObjectByValue::PrepareCache(std::vector<C4Object *> &objects)
820{
821 // Clear old cache
822
823 values.clear();
824 values.reserve(n: objects.size());
825
826 std::ranges::copy(objects | std::views::transform([this](C4Object *const obj)
827 {
828 return CompareGetValue(pOf: obj);
829 }), std::back_inserter(x&: values));
830
831 return true;
832}
833
834int32_t C4SortObjectByValue::Compare(C4Object *pObj1, C4Object *pObj2)
835{
836 // this is rather slow, should only be called in special cases
837
838 // make sure to hardcode the call order, as it might lead to desyncs otherwise [Icewing]
839 int32_t iValue1 = CompareGetValue(pOf: pObj1);
840 int32_t iValue2 = CompareGetValue(pOf: pObj2);
841 return iValue2 - iValue1;
842}
843
844int32_t C4SortObjectByValue::CompareCache(int32_t iObj1, int32_t iObj2, C4Object *pObj1, C4Object *pObj2)
845{
846 assert(iObj1 >= 0 && std::cmp_less(iObj1, values.size())); assert(iObj2 >= 0 && std::cmp_less(iObj2, values.size()));
847 // Might overflow for large values...!
848 return values[iObj2] - values[iObj1];
849}
850
851C4SortObjectReverse::~C4SortObjectReverse()
852{
853 delete pSort;
854}
855
856int32_t C4SortObjectReverse::Compare(C4Object *pObj1, C4Object *pObj2)
857{
858 return pSort->Compare(pObj1: pObj2, pObj2: pObj1);
859}
860
861bool C4SortObjectReverse::PrepareCache(std::vector<C4Object *> &objects)
862{
863 return pSort->PrepareCache(objects);
864}
865
866int32_t C4SortObjectReverse::CompareCache(int32_t iObj1, int32_t iObj2, C4Object *pObj1, C4Object *pObj2)
867{
868 return pSort->CompareCache(iObj1: iObj2, iObj2: iObj1, pObj1: pObj2, pObj2: pObj1);
869}
870
871C4SortObjectMultiple::~C4SortObjectMultiple()
872{
873 for (int32_t i = 0; i < iCnt; ++i) delete ppSorts[i];
874 if (fFreeArray) delete[] ppSorts;
875}
876
877int32_t C4SortObjectMultiple::Compare(C4Object *pObj1, C4Object *pObj2)
878{
879 // return first comparison that's nonzero
880 int32_t iCmp;
881 for (int32_t i = 0; i < iCnt; ++i)
882 if (iCmp = ppSorts[i]->Compare(pObj1, pObj2))
883 return iCmp;
884 // all comparisons equal
885 return 0;
886}
887
888bool C4SortObjectMultiple::PrepareCache(std::vector<C4Object *> &objects)
889{
890 bool fCaches = false;
891 for (int32_t i = 0; i < iCnt; ++i)
892 fCaches |= ppSorts[i]->PrepareCache(objects);
893 // return wether a sort citerion uses a cache
894 return fCaches;
895}
896
897int32_t C4SortObjectMultiple::CompareCache(int32_t iObj1, int32_t iObj2, C4Object *pObj1, C4Object *pObj2)
898{
899 // return first comparison that's nonzero
900 int32_t iCmp;
901 for (int32_t i = 0; i < iCnt; ++i)
902 if (iCmp = ppSorts[i]->CompareCache(iObj1, iObj2, pObj1, pObj2))
903 return iCmp;
904 // all comparisons equal
905 return 0;
906}
907
908int32_t C4SortObjectDistance::CompareGetValue(C4Object *pFor)
909{
910 int32_t dx = pFor->x - iX, dy = pFor->y - iY;
911 return dx * dx + dy * dy;
912}
913
914int32_t C4SortObjectRandom::CompareGetValue(C4Object *pFor)
915{
916 return Random(iRange: 1 << 16);
917}
918
919int32_t C4SortObjectSpeed::CompareGetValue(C4Object *pFor)
920{
921 return pFor->xdir * pFor->xdir + pFor->ydir * pFor->ydir;
922}
923
924int32_t C4SortObjectMass::CompareGetValue(C4Object *pFor)
925{
926 return pFor->Mass;
927}
928
929int32_t C4SortObjectValue::CompareGetValue(C4Object *pFor)
930{
931 return pFor->GetValue(pInBase: nullptr, iForPlayer: NO_OWNER);
932}
933
934C4SortObjectFunc::C4SortObjectFunc(const char *szFunc)
935{
936 pFunc = Game.ScriptEngine.GetFirstFunc(Name: szFunc);
937}
938
939void C4SortObjectFunc::SetPar(int i, const C4Value &Par)
940{
941 // Over limit?
942 if (i >= C4AUL_MAX_Par) return;
943 // Set parameter
944 Pars[i] = Par;
945}
946
947int32_t C4SortObjectFunc::CompareGetValue(C4Object *pObj)
948{
949 // Function not found?
950 if (!pFunc) return false;
951 // Search same-name-list for appropriate function
952 C4AulFunc *pCallFunc = pFunc->FindSameNameFunc(pScope: pObj->Def);
953 if (!pCallFunc) return false;
954 // Call
955 return pCallFunc->Exec(pObj, pPars: Pars, fPassErrors: true).getInt();
956}
957