gwnavruntime/kernel/SF_Range.h Source File

SF_Range.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 /**************************************************************************
8 
9 PublicHeader: Kernel
10 Filename : KY_Range.h
11 Content : Range template types and functions
12 Created : April 17, 2007
13 Authors : Artyom Bolgar, Maxim Shemanarev
14 
15 **************************************************************************/
16 
17 #ifndef INC_KY_Kernel_Range_H
18 #define INC_KY_Kernel_Range_H
19 
20 #include "gwnavruntime/kernel/SF_Types.h"
21 #include "gwnavruntime/kernel/SF_Debug.h"
22 #include "gwnavruntime/kernel/SF_Memory.h"
23 #include "gwnavruntime/kernel/SF_Math.h"
24 #include "gwnavruntime/kernel/SF_Array.h"
25 
26 namespace Kaim {
27 
28 class Range
29 {
30 public:
31  SPInt Index;
32  UPInt Length;
33 
34  enum BoundsType { Min, Max };
35 
36  Range():Index(0), Length(0) {}
37  explicit Range(UPInt count) { SetRange(count); }
38  Range(SPInt index, UPInt length) { SetRange(index, length); }
39  Range(const Range &r) { SetRange(r); }
40  Range(BoundsType bt) { SetRange(bt); }
41 
42  // *** Initialization
43 
44  void SetRange(UPInt count) { Index = 0; Length = count; }
45  // first and last inclusive
46  void SetRange(SPInt index, UPInt length)
47  {
48  Index = index;
49  Length = length;
50  }
51  void SetRange(const Range &r) { SetRange(r.Index, r.Length); }
52  void SetRange(BoundsType bt)
53  {
54  switch (bt)
55  {
56  case Min: SetRange(0, 0); break;
57  case Max: SetRange(0, KY_MAX_UPINT); break;
58  }
59  }
60 
61  // moves index and decrease the length, thus NextIndex remains same.
62  // Positive delta shows direct direction, negative - reverse.
63  SPInt MoveIndex(SPInt delta)
64  {
65  delta = (delta > SPInt(Length)) ? SPInt(Length) : delta;
66  Index += delta;
67  Length = (UPInt)(Length - delta);
68  return Index;
69  }
70  // moves whole range keeping the original length
71  SPInt MoveRange(SPInt delta)
72  {
73  Index += delta;
74  return Index;
75  }
76 
77  // Shrink range's length
78  UPInt ShrinkRange(UPInt lengthDelta)
79  {
80  if (lengthDelta > Length)
81  Length = 0;
82  else
83  Length -= lengthDelta;
84  return Length;
85  }
86  UPInt ExpandRange(UPInt lengthDelta)
87  {
88  Length += lengthDelta;
89  return Length;
90  }
91 
92  // returns the next available index after the range
93  SPInt NextIndex() const { return Index + Length; }
94  // returns the last included index in the range
95  SPInt LastIndex() const { return Index + Length - 1; }
96  SPInt FirstIndex() const { return Index; }
97  bool IsEmpty() const { return Length == 0; }
98 
99  // Reset the range to first = 0 and count = 0
100  void Clear() { SetRange(Min); }
101 
102  // *** Intersection
103 
104  // Tests whether a value is inside the range
105  bool Contains(SPInt index) const { return (index >= Index && index <= LastIndex()); }
106  // Tests whether the range is completely inside this one
107  bool Contains(const Range &r) const { return (r.Index >= Index && r.LastIndex() <= LastIndex()); }
108 
109  // Tests whether the range intersects this one
110  bool Intersects(const Range &r) const { return (r.LastIndex() >= FirstIndex()) && (LastIndex() >= r.FirstIndex()); }
111 
112  int CompareTo(SPInt index) const
113  {
114  if (Contains(index))
115  return 0;
116  if (index < Index)
117  return int(Index - index);
118  else
119  return int(LastIndex() - index);
120  }
121 };
122 
123 template <class T>
124 class RangePrimData : public Range
125 {
126  T Data;
127 public:
128  RangePrimData():Range() {}
129  // reference dowsn't work for primitive types' constants
130  //??RangeData(SPInt index, UPInt length, const T& data):Range(index, length),Data(data) {}
131  RangePrimData(SPInt index, UPInt length, const T data):Range(index, length),Data(data) {}
132 
133  T GetData() const { return Data; }
134  void SetData(T data) { Data = data; }
135  bool IsDataEqual(T data) const { return Data == data; }
136 };
137 
138 template <class T>
139 class RangeData : public Range
140 {
141  T Data;
142 public:
143  RangeData():Range() {}
144  RangeData(SPInt index, UPInt length, const T& data):Range(index, length),Data(data) {}
145 
146  T& GetData() { return Data; }
147  const T& GetData() const { return Data; }
148  T& operator->() { return Data; }
149  const T& operator->() const { return Data; }
150  T& operator*() { return Data; }
151  const T& operator*() const { return Data; }
152  void SetData(const T& data) { Data = data; }
153  bool IsDataEqual(const T& data) const { return Data == data; }
154 };
155 
156 template <class T, class Array = Kaim::Array<RangeData<T> > >
157 class RangeDataArray
158 {
159  UPInt FindRangeIndex(SPInt index) const;
160  UPInt FindNearestRangeIndex(SPInt index) const;
161 public:
162  typedef RangeData<T> TypedRangeData;
163  typedef Array RangeArrayType;
164 
165  RangeArrayType Ranges;
166 
167  // just returns range at the specified position in Ranges array
168  TypedRangeData& operator[](UPInt position) { return Ranges[position]; }
169  const TypedRangeData& operator[](UPInt position) const { return Ranges[position]; }
170  UPInt Count() const { return Ranges.GetSize(); }
171 
172  void SetRange(SPInt index, UPInt length, const T& data)
173  {
174  SetRange(TypedRangeData(index, length, data));
175  }
176  void SetRange(const TypedRangeData& range);
177  // just clears the range w/o collapsing the array
178  void ClearRange(SPInt index, UPInt length);
179 
180  TypedRangeData& Append(UPInt length, const T& data);
181  void InsertRange(SPInt startPos, UPInt length, const T& pdata);
182  void ExpandRange(SPInt startPos, UPInt length);
183  // removes range and collapse the range array, thus no new hole is produced
184  void RemoveRange(SPInt startPos, UPInt length);
185  void RemoveAll() { Ranges.Resize(0); }
186 
187  class Iterator
188  {
189  friend class RangeDataArray<T, Array>;
190  RangeDataArray<T, Array>* pArray;
191  SPInt Index;
192 
193  explicit Iterator(RangeDataArray<T, Array>& arr) : pArray(&arr), Index(0) {}
194  Iterator(RangeDataArray<T, Array>& arr, bool) : pArray(&arr), Index(pArray->Count() - 1) {}
195 
196  // inserts a range at the current position
197  void InsertBefore(const TypedRangeData& range);
198  void InsertAfter(const TypedRangeData& range);
199  // remove one range at the current position
200  void Remove();
201 
202  public:
203  Iterator(const Iterator& it) : pArray(it.pArray), Index(it.Index) {}
204  Iterator():pArray(0), Index(-1) {}
205 
206  Iterator& operator++()
207  {
208  if (Index < (SPInt)pArray->Count())
209  ++Index;
210  return *this;
211  }
212  Iterator operator++(int)
213  {
214  Iterator it(*this);
215  if (Index < (SPInt)pArray->Count())
216  ++Index;
217  return it;
218  }
219  Iterator& operator--()
220  {
221  if (Index >= 0)
222  --Index;
223  return *this;
224  }
225  Iterator operator--(int)
226  {
227  Iterator it(*this);
228  if (Index >= 0)
229  --Index;
230  return it;
231  }
232  TypedRangeData& operator*() { return (*pArray)[Index]; }
233  TypedRangeData* operator->() { return &(*pArray)[Index]; }
234  TypedRangeData* GetPtr() { return (Index < (SPInt)pArray->Count()) ? &(*pArray)[Index] : NULL; }
235  bool operator==(const Iterator& it) const
236  {
237  return (pArray == it.pArray && Index == it.Index);
238  }
239  Iterator operator+(SPInt delta) const
240  {
241  Iterator it(*this);
242  if (Index + delta < 0)
243  it.Index = 0;
244  else if (UPInt(Index + delta) >= pArray->Count())
245  it.Index = pArray->Count() - 1;
246  else
247  it.Index += delta;
248 
249  return it;
250  }
251  bool IsFinished() const { return Index < 0 || UPInt(Index) >= pArray->Count(); }
252  };
253  Iterator Begin() { return Iterator(*this); }
254  Iterator Last() { return Iterator(*this, true); }
255  Iterator GetIteratorAt(SPInt index);
256  Iterator GetIteratorByNearestIndex(SPInt index);
257 
258  class ConstIterator
259  {
260  friend class RangeDataArray<T, Array>;
261  const RangeDataArray<T, Array>* pArray;
262  SPInt Index;
263 
264  explicit ConstIterator(const RangeDataArray<T, Array>& arr) : pArray(&arr), Index(0) {}
265  ConstIterator(const RangeDataArray<T, Array>& arr, bool) : pArray(&arr), Index(pArray->Count() - 1) {}
266 
267  public:
268  ConstIterator(const ConstIterator& it) : pArray(it.pArray), Index(it.Index) {}
269  ConstIterator():pArray(0), Index(-1) {}
270 
271  ConstIterator& operator++()
272  {
273  if (Index < (SPInt)pArray->Count())
274  ++Index;
275  return *this;
276  }
277  ConstIterator operator++(int)
278  {
279  ConstIterator it(*this);
280  if (Index < (SPInt)pArray->Count())
281  ++Index;
282  return it;
283  }
284  ConstIterator& operator--()
285  {
286  if (Index >= 0)
287  --Index;
288  return *this;
289  }
290  ConstIterator operator--(int)
291  {
292  ConstIterator it(*this);
293  if (Index >= 0)
294  --Index;
295  return it;
296  }
297  const TypedRangeData& operator*() const { return (*pArray)[Index]; }
298  const TypedRangeData* operator->() const { return &(*pArray)[Index]; }
299  const TypedRangeData* GetPtr() const { return (Index < (SPInt)pArray->Count()) ? &(*pArray)[Index] : NULL; }
300  bool operator==(const ConstIterator& it) const
301  {
302  return (pArray == it.pArray && Index == it.Index);
303  }
304  ConstIterator operator+(SPInt delta) const
305  {
306  ConstIterator it(*this);
307  if (Index + delta < 0)
308  it.Index = 0;
309  else if (UPInt(Index + delta) >= pArray->Count())
310  it.Index = pArray->Count() - 1;
311  else
312  it.Index += delta;
313 
314  return it;
315  }
316  bool IsFinished() const { return Index < 0 || UPInt(Index) >= pArray->Count(); }
317  };
318  ConstIterator Begin() const { return ConstIterator(*this); }
319  ConstIterator Last() const { return ConstIterator(*this, true); }
320  ConstIterator GetIteratorAt(SPInt index) const;
321  ConstIterator GetIteratorByNearestIndex(SPInt index) const;
322 
323  class ConstPositionIterator
324  {
325  friend class RangeDataArray<T, Array>;
326  ConstIterator Iter;
327  const TypedRangeData* pCurrentRange;
328  SPInt CurrentPos;
329  SPInt EndPos;
330  public:
331  ConstPositionIterator(const RangeDataArray<T, Array>& rangeArray) : Iter(rangeArray.Begin())
332  {
333  if (!Iter.IsFinished())
334  {
335  CurrentPos = Iter->FirstIndex();
336  pCurrentRange = Iter.GetPtr();
337  EndPos = rangeArray[rangeArray.Count() - 1].LastIndex();
338  }
339  else
340  {
341  CurrentPos = 0;
342  pCurrentRange = NULL;
343  EndPos = -1;
344  }
345  }
346  ConstPositionIterator(const RangeDataArray<T, Array>& rangeArray, SPInt startIndex, UPInt length) :
347  Iter(rangeArray.GetIteratorByNearestIndex(startIndex)), CurrentPos(startIndex),
348  EndPos(CurrentPos + length - 1)
349  {
350  if (!Iter.IsFinished())
351  {
352  pCurrentRange = Iter.GetPtr();
353  }
354  else
355  {
356  pCurrentRange = NULL;
357  }
358  }
359 
360  bool IsFinished() const { return CurrentPos > EndPos; }
361 
362  const TypedRangeData* operator*() const { return GetPtr(); }
363  const TypedRangeData* operator->() const
364  {
365  return GetPtr();
366  }
367  const TypedRangeData* GetPtr() const
368  {
369  if (pCurrentRange)
370  {
371  if (pCurrentRange->Contains(CurrentPos))
372  return pCurrentRange;
373  }
374  return NULL;
375  }
376 
377  ConstPositionIterator& operator++()
378  {
379  if (CurrentPos <= EndPos)
380  {
381  SPInt oldPos = CurrentPos++;
382  if (pCurrentRange)
383  {
384  if (pCurrentRange->Contains(oldPos) && !pCurrentRange->Contains(CurrentPos))
385  {
386  ++Iter;
387  if (!Iter.IsFinished())
388  pCurrentRange = Iter.GetPtr();
389  else
390  pCurrentRange = NULL;
391  }
392  }
393  }
394  return *this;
395  }
396  ConstPositionIterator operator++(int)
397  {
398  ConstIterator it(*this);
399  operator++();
400  return it;
401  }
402  };
403 
404  /*void set_heap(HeapType& heap)
405  {
406  Ranges.set_heap(heap);
407  }
408  void set_heap(HeapType* pheap)
409  {
410  Ranges.set_heap(pheap);
411  } */
412 
413 #ifdef KY_CONFIG_DEBUG
414  void CheckIntegrity();
415 #else
416  void CheckIntegrity() {}
417 #endif
418 protected:
419 
420 };
421 
422 // inserts a range at the current position
423 template <class T, class Array>
424 void RangeDataArray<T, Array>::Iterator::InsertBefore(const TypedRangeData& range)
425 {
426  pArray->Ranges.InsertAt(Index, range);
427 }
428 
429 template <class T, class Array>
430 void RangeDataArray<T, Array>::Iterator::InsertAfter(const TypedRangeData& range)
431 {
432  pArray->Ranges.InsertAt(Index+1, range);
433 }
434 
435 // remove one range at the current position
436 template <class T, class Array>
437 void RangeDataArray<T, Array>::Iterator::Remove()
438 {
439  if (Index >= 0 && UPInt(Index) < pArray->Count())
440  pArray->Ranges.RemoveAt(Index);
441 }
442 
443 template <class T, class Array>
444 UPInt RangeDataArray<T, Array>::FindRangeIndex(SPInt index) const
445 {
446  // do a binary search
447  const UPInt count = Count();
448 
449  UPInt lower = 0;
450  UPInt upper = count - 1;
451 
452  while (lower < upper && upper != (UPInt)-1)
453  {
454  UPInt middle = (lower + upper)/2;
455  int cmpRes = Ranges[middle].CompareTo(index);
456  if (cmpRes == 0) { // equal
457  return middle;
458  }
459  if (cmpRes < 0) // *mpArray[middle] < *elem
460  lower = middle+1;
461  else
462  upper = middle-1;
463  }
464 
465  if (lower == upper && Ranges[lower].CompareTo(index) == 0)
466  return lower;
467  return KY_MAX_UPINT;
468 }
469 
470 
471 template <class T, class Array>
472 typename RangeDataArray<T, Array>::Iterator RangeDataArray<T, Array>::GetIteratorAt(SPInt index)
473 {
474  UPInt rangeIndex = FindRangeIndex(index);
475  if (rangeIndex != KY_MAX_UPINT)
476  return Begin() + rangeIndex;
477  return Iterator();
478 }
479 
480 template <class T, class Array>
481 typename RangeDataArray<T, Array>::ConstIterator RangeDataArray<T, Array>::GetIteratorAt(SPInt index) const
482 {
483  UPInt rangeIndex = FindRangeIndex(index);
484  if (rangeIndex != KY_MAX_UPINT)
485  return Begin() + rangeIndex;
486  return ConstIterator();
487 }
488 
489 template <class T, class Array>
490 UPInt RangeDataArray<T, Array>::FindNearestRangeIndex(SPInt index) const
491 {
492  // do a binary search
493  const UPInt count = Count();
494  if (count == 0)
495  {
496  return 0;
497  }
498 
499  UPInt lower = 0;
500  UPInt upper = count - 1;
501  UPInt lowest = 0;
502 
503  while (lower < upper && upper != (UPInt)-1) {
504  UPInt middle = (lower + upper)/2;
505  int cmpRes = Ranges[middle].CompareTo(index);
506  if (cmpRes == 0) { // equal
507  return middle;
508  }
509  if (cmpRes < 0) // *mpArray[middle] < *elem
510  {
511  lowest = lower;
512  lower = middle+1;
513  }
514  else
515  upper = middle-1;
516  }
517 
518  if (lower == upper && Ranges[lower].CompareTo(index) == 0)
519  return lower;
520  while(lowest < upper && Ranges[lowest + 1].CompareTo(index) < 0)
521  ++lowest;
522  return lowest;
523 }
524 
525 template <class T, class Array>
526 typename RangeDataArray<T, Array>::Iterator RangeDataArray<T, Array>::GetIteratorByNearestIndex(SPInt index)
527 {
528  return Begin() + FindNearestRangeIndex(index);
529 }
530 
531 template <class T, class Array>
532 typename RangeDataArray<T, Array>::ConstIterator RangeDataArray<T, Array>::GetIteratorByNearestIndex(SPInt index) const
533 {
534  return Begin() + FindNearestRangeIndex(index);
535 }
536 
537 template <class T, class Array>
538 void RangeDataArray<T, Array>::SetRange(const TypedRangeData& range)
539 {
540  if (Count() > 0)
541  {
542  Iterator it = GetIteratorByNearestIndex(range.Index);
543  Iterator insertionPoint;
544 
545  // split the first range
546  if (it->Contains(range))
547  {
548  // inserting range is inside the existing range?
549  if (it->Index == range.Index)
550  {
551  // beginnings of ranges are same?
552  // |=======||====| - array
553  // |+++| - range
554  // |+++|===||====| - result
555  it->MoveIndex(range.Length);
556 
557  if (it->IsEmpty())
558  {
559  *it = range;
560  }
561  else
562  it.InsertBefore(range);
563  insertionPoint = it;
564  ++it;
565  }
566  else if (it->NextIndex() > range.NextIndex())
567  {
568  // |==========||====| - array
569  // |+++| - range
570  // |==|+++|===||====| - result
571  // inserting range is completely inside the current range
572  // split the current range by 3 parts and replace the middle one by "range"
573  TypedRangeData r = *it;
574  SPInt endIndex = it->NextIndex();
575  it->ShrinkRange(endIndex - range.Index);
576  r.MoveIndex(it->Length + range.Length);
577  it.InsertAfter(range);
578  ++it;
579  insertionPoint = it;
580  it.InsertAfter(r);
581  ++it;
582  }
583  else
584  {
585  // |==========||====| - array
586  // |+++| - range
587  // |======|+++||====| - result
588  // inserting range intersects the current range
589  it->ShrinkRange(range.Length);
590  insertionPoint = ++it;
591  it.InsertBefore(range);
592  ++it;
593  }
594  }
595  else if (it->Contains(range.Index))
596  {
597  // inserting range intersects the current range
598  // |==========||====| - array
599  // |+++++++| - range
600  // |======| ||====| - result at this stage
601  it->ShrinkRange(it->NextIndex() - range.Index);
602  insertionPoint = ++it;
603  it.InsertBefore(range);
604  ++it;
605  }
606  else
607  {
608  // beginning of inserting range is on empty space
609  // |==========| |====| - array
610  // |+++++++| - range
611  // or
612  // |====| - array
613  // |+++++++| - range
614  // or
615  // |====| - array
616  // |+++++++| - range
617  if (it->CompareTo(range.Index) > 0)
618  {
619  it.InsertBefore(range);
620  insertionPoint = it;
621  }
622  else
623  {
624  it.InsertAfter(range);
625  insertionPoint = ++it;
626  }
627  ++it;
628  }
629  // remove all ranges in between
630  while(!it.IsFinished() && range.Contains(*it))
631  {
632  it.Remove();
633  }
634  // shrink the last range
635  if (!it.IsFinished() && it->Contains(range.NextIndex() - 1))
636  {
637  // |==========||======| - array
638  // |+++++++| - range
639  // |==========| |===| - result
640  it->MoveIndex(range.NextIndex() - it->Index);
641  }
642  // check if is it possible to unite ranges
643  Iterator firstRangeIt = insertionPoint;
644  --firstRangeIt;
645  // check the previous range
646  if (!firstRangeIt.IsFinished())
647  {
648  if (firstRangeIt->IsEmpty())
649  firstRangeIt.Remove();
650  else if (firstRangeIt->NextIndex() == range.Index && firstRangeIt->IsDataEqual(insertionPoint->GetData()))
651  {
652  // expand first range by the range.Length
653  firstRangeIt->ExpandRange(range.Length);
654  insertionPoint.Remove();
655  insertionPoint = firstRangeIt;
656  }
657  }
658  // check the next range
659  Iterator nextIt = insertionPoint;
660  ++nextIt;
661  if (!nextIt.IsFinished())
662  {
663  if (nextIt->IsEmpty())
664  nextIt.Remove();
665  else if (insertionPoint->NextIndex() == nextIt->Index && insertionPoint->IsDataEqual(nextIt->GetData()))
666  {
667  // expand range by the length of nextIt
668  insertionPoint->ExpandRange(nextIt->Length);
669  nextIt.Remove();
670  }
671  }
672  }
673  else
674  {
675  Begin().InsertBefore(range);
676  }
677  CheckIntegrity();
678 }
679 
680 template <class T, class Array>
681 typename RangeDataArray<T, Array>::TypedRangeData& RangeDataArray<T, Array>::Append(UPInt length, const T& data)
682 {
683  // check data at the last element in the array: if same as our, then just expand existing range by length
684  UPInt count = Count();
685  TypedRangeData* pLastRange = NULL;
686  if (count > 0)
687  {
688  pLastRange = &Ranges[count - 1];
689  if (count > 0 && pLastRange->IsDataEqual(data))
690  {
691  pLastRange->Length += length;
692  return *pLastRange;
693  }
694  }
695  // otherwise, create a new range
696  Ranges.Resize(count + 1);
697  TypedRangeData& newRange = Ranges[count];
698  if (pLastRange)
699  {
700  newRange.Index = pLastRange->Index + pLastRange->Length;
701  }
702  else
703  {
704  // insert new range as first one
705  newRange.Index = 0;
706  }
707  newRange.Length = length;
708  newRange.SetData(data);
709  CheckIntegrity();
710  return newRange;
711 }
712 
713 template <class T, class Array>
714 void RangeDataArray<T, Array>::InsertRange(SPInt startPos, UPInt length, const T& data)
715 {
716  ExpandRange(startPos, length);
717  SetRange(startPos, length, data);
718  CheckIntegrity();
719 }
720 
721 template <class T, class Array>
722 void RangeDataArray<T, Array>::ExpandRange(SPInt startPos, UPInt length)
723 {
724  if (Count() > 0)
725  {
726  Iterator it = GetIteratorByNearestIndex(startPos);
727  TypedRangeData* pnearest = it.GetPtr();
728  if (pnearest)
729  {
730  if (pnearest->Contains(startPos) || pnearest->NextIndex() == startPos)
731  pnearest->Length += length;
732  }
733  // update indices for all following ranges
734  for(++it; !it.IsFinished(); ++it)
735  {
736  it->MoveRange((SPInt)length);
737  }
738  }
739  CheckIntegrity();
740 }
741 
742 template <class T, class Array>
743 void RangeDataArray<T, Array>::RemoveRange(SPInt startPos, UPInt length)
744 {
745  CheckIntegrity();
746  if (Count() > 0)
747  {
748  Iterator it = GetIteratorByNearestIndex(startPos);
749  Iterator removalPoint;
750 
751  if (length == KY_MAX_UPINT) // special case, remove everything till the end
752  length = KY_MAX_SPINT - startPos;
753 
754  TypedRangeData range(startPos, length, T());
755  TypedRangeData& r = *it;
756  // split the first range
757  if (r.Contains(range))
758  {
759  // is inserting range inside the existing range?
760  if (r.Index == range.Index)
761  {
762  // beginnings of ranges are the same?
763  // |0123456||====| - array
764  // |+++| - range
765  // |3456||====| - result at this stage
766  r.MoveIndex(range.Length);
767 
768  if (r.IsEmpty())
769  it.Remove();
770  removalPoint = it;
771  }
772  else if (r.NextIndex() > range.NextIndex())
773  {
774  // |1234567890||====| - array
775  // |+++| - range
776  // |1237890| |====| - result at this stage
777  // inserting range is completely inside the current range
778  // split the current range by 3 parts and replace the middle one by "range"
779  r.ShrinkRange(range.Length);
780  if (r.IsEmpty())
781  it.Remove();
782  else
783  ++it;
784  removalPoint = it;
785  }
786  else
787  {
788  // |==========||====| - array
789  // |+++| - range
790  // |======| |====| - result at this stage
791  // inserting range intersects the current range
792  r.ShrinkRange(range.Length);
793  removalPoint = ++it;
794  ++it;
795  }
796  }
797  else if (r.Contains(range.Index))
798  {
799  // inserting range intersects the current range
800  // |==========||====| - array
801  // |+++++++| - range
802  // |======| ||====| - result at this stage
803  r.ShrinkRange(r.NextIndex() - range.Index);
804  if (r.IsEmpty())
805  it.Remove();
806  else
807  ++it;
808  removalPoint = it;
809  }
810  else
811  {
812  // beginning of inserting range is on empty space
813  // |==========| |====| - array
814  // |+++++++| - range
815  // or
816  // |====| - array
817  // |+++++++| - range
818  // or
819  // |====| - array
820  // |+++++++| - range
821  if (r.CompareTo(range.Index) > 0)
822  {
823  removalPoint = it;
824  }
825  else
826  {
827  removalPoint = ++it;
828  }
829  }
830  // remove all ranges in between
831  while(!it.IsFinished() && range.Contains(*it))
832  {
833  it.Remove();
834  }
835  // shrink the last range
836  if (!it.IsFinished() && it->Contains(range.NextIndex() - 1))
837  {
838  // |==========||======| - array
839  // |+++++++| - range
840  // |==========| |===| - result
841  it->MoveIndex(range.NextIndex() - it->Index);
842  }
843 
844  Iterator firstRangeIt = removalPoint;
845  --firstRangeIt;
846  // check, can we unite ranges
847  if (!firstRangeIt.IsFinished() && !removalPoint.IsFinished() &&
848  firstRangeIt->NextIndex() == removalPoint->Index - SPInt(length) &&
849  firstRangeIt->IsDataEqual(removalPoint->GetData()))
850  {
851  // we can
852  firstRangeIt->ExpandRange(removalPoint->Length);
853  removalPoint.Remove();
854  }
855 
856  // update indices for all following ranges
857  for(; !removalPoint.IsFinished(); ++removalPoint)
858  {
859  removalPoint->MoveRange(-((SPInt)length));
860  }
861  }
862  CheckIntegrity();
863 }
864 
865 // TODO!
866 template <class T, class Array>
867 void RangeDataArray<T, Array>::ClearRange(SPInt startPos, UPInt length)
868 {
869  CheckIntegrity();
870  if (Count() > 0)
871  {
872  Iterator it = GetIteratorByNearestIndex(startPos);
873  Iterator removalPoint;
874 
875  if (length == KY_MAX_UPINT) // special case, remove everything till the end
876  length = KY_MAX_SPINT - startPos;
877 
878  TypedRangeData range(startPos, length, T());
879  // split the first range
880  if (it->Contains(range))
881  {
882  // is inserting range inside the existing range?
883  if (it->Index == range.Index)
884  {
885  // beginnings of ranges are the same?
886  // |=======||====| - array
887  // |+++| - range
888  // |===||====| - result
889  it->MoveIndex(range.Length);
890 
891  removalPoint = it;
892  if (it->IsEmpty())
893  it.Remove();
894  else
895  ++it;
896  }
897  else if (it->NextIndex() > range.NextIndex())
898  {
899  // |==========||====| - array
900  // |+++| - range
901  // |==| |===||====| - result
902  // inserting range is completely inside the current range
903  // split the current range by 3 parts and replace the middle one by "range"
904  TypedRangeData r = *it;
905  SPInt endIndex = it->NextIndex();
906  it->ShrinkRange(endIndex - range.Index);
907  r.MoveIndex(it->Length + range.Length);
908  ++it;
909  removalPoint = it;
910  it.InsertBefore(r);
911  ++it;
912  }
913  else
914  {
915  // |==========||====| - array
916  // |+++| - range
917  // |======| |====| - result
918  // inserting range intersects the current range
919  it->ShrinkRange(range.Length);
920  removalPoint = ++it;
921  ++it;
922  }
923  }
924  else if (it->Contains(range.Index))
925  {
926  // inserting range intersects the current range
927  // |==========||====| - array
928  // |+++++++| - range
929  // |======| ||====| - result at this stage
930  it->ShrinkRange(it->NextIndex() - range.Index);
931  removalPoint = ++it;
932  ++it;
933  }
934  else
935  {
936  // beginning of inserting range is on empty space
937  // |==========| |====| - array
938  // |+++++++| - range
939  // or
940  // |====| - array
941  // |+++++++| - range
942  // or
943  // |====| - array
944  // |+++++++| - range
945  if (it->CompareTo(range.Index) > 0)
946  {
947  removalPoint = it;
948  ++it;
949  }
950  else
951  {
952  removalPoint = ++it;
953  }
954  }
955  // remove all ranges in between
956  while(!it.IsFinished() && range.Contains(*it))
957  {
958  it.Remove();
959  }
960  // shrink the last range
961  if (!it.IsFinished() && it->Contains(range.NextIndex() - 1))
962  {
963  // |==========||======| - array
964  // |+++++++| - range
965  // |==========| |===| - result
966  it->MoveIndex(range.NextIndex() - it->Index);
967  }
968  }
969  CheckIntegrity();
970 }
971 
972 #ifdef KY_CONFIG_DEBUG
973 template <class T, class Array>
974 void RangeDataArray<T, Array>::CheckIntegrity()
975 {
976  SPInt curIndex = KY_MIN_SPINT;
977  TypedRangeData* pprev = NULL;
978  for (UPInt i = 0, n = Ranges.GetSize(); i < n; ++i)
979  {
980  TypedRangeData& r = Ranges[i];
981  if (pprev)
982  {
983  if (pprev->Index + (SPInt)pprev->Length == r.Index)
984  KY_ASSERT(pprev->GetData() != r.GetData()); // detect not united ranges
985  }
986  KY_ASSERT(r.Length); // detect empty ranges
987  KY_ASSERT(curIndex <= r.FirstIndex());
988  curIndex = r.NextIndex();
989  pprev = &r;
990  }
991 }
992 #endif
993 
994 } // Scaleform
995 
996 #endif // INC_KY_Kernel_Range_H
997 
SF_Types.h
SF_Memory.h
SF_Array.h
SF_Debug.h
Kaim
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
Kaim::operator*
Vec2f operator*(KyFloat32 s, const Vec2f &v)
scalar * vec operator
Definition: vec2f.h:120
SF_Math.h
Please send us your comment about this page