ICF 3.1.1.10
Technical documentation of ICF Libraries
TRanges.h
Go to the documentation of this file.
1/********************************************************************************
2** This file is part of the ICF Framework. Copyright (C) Witold Gantzke & Kirill Lepskiy
3** ICF Framework may be used under the terms of the LGPL License v. 2.1 by the Free Software Foundation.
4********************************************************************************/
5
6#pragma once
7
8
9// STL includes
10#include <set>
11
12// Qt includes
13#include <QtCore/QList>
14
15// ICF includes
16#include <istd/TRange.h>
17
18
19namespace istd
20{
21
22
28template <typename ValueType>
30{
31public:
32 typedef QList< TRange<ValueType> > RangeList;
33 typedef std::set<ValueType> SwitchPoints;
34
38 TRanges();
39
43 explicit TRanges(const istd::TRange<ValueType>& range);
44
48 void Reset();
49
54 bool IsEmpty() const;
55
59 const SwitchPoints& GetSwitchPoints() const;
64
70 void InsertSwitchPoint(ValueType point);
71
76 bool GetBeginState() const;
82 void SetBeginState(bool state);
83
87 bool IsInside(ValueType point) const;
88
92 bool IsInside(const TRange<ValueType>& range) const;
93
97 bool IsInside(const TRanges<ValueType>& rangesList) const;
98
102 void GetInverted(TRanges<ValueType>& result, const TRange<ValueType>* clipRangePtr) const;
103
107 void Invert(const TRange<ValueType>* clipRangePtr);
108
112 TRanges<ValueType> GetUnion(const TRanges<ValueType>& rangesList) const;
113
118 void GetUnion(const TRanges<ValueType>& rangesList, TRanges<ValueType>& result) const;
119
124 void Union(const TRanges<ValueType>& rangesList);
125
130 void Union(const TRange<ValueType>& range, bool isInverted = false);
131
136
141 void GetIntersection(const TRanges<ValueType>& rangesList, TRanges<ValueType>& result) const;
142
147 void Intersection(const TRanges<ValueType>& rangesList);
148
153 void Intersection(const TRange<ValueType>& range, bool isInverted = false);
154
160 void Erode(ValueType leftValue, ValueType rightValue);
161
167 void Dilate(ValueType leftValue, ValueType rightValue);
174 void RemoveGaps(ValueType value, bool gapState = false);
175
179 void ShiftRanges(ValueType offset);
180
187 void GetAsList(const TRange<ValueType>& range, RangeList& result) const;
188
189 bool operator==(const TRanges<ValueType>& ranges) const;
190 bool operator!=(const TRanges<ValueType>& ranges) const;
191
192private:
193 SwitchPoints m_switchPoints;
194
195 bool m_beginState;
196};
197
198
199template <typename ValueType>
201: m_beginState(false)
202{
203}
204
205
206template <typename ValueType>
208 : m_beginState(false)
209{
210 if (!range.IsEmpty()) {
211 m_switchPoints.insert(range.GetMinValue());
212 m_switchPoints.insert(range.GetMaxValue());
213 }
214}
215
216
217template <typename ValueType>
219{
220 m_switchPoints.clear();
221 m_beginState = false;
222}
223
224
225template <typename ValueType>
227{
228 return m_switchPoints.empty() && (m_beginState == false);
229}
230
231
232template <typename ValueType>
234{
235 return m_switchPoints;
236}
237
238
239template <typename ValueType>
241{
242 return m_switchPoints;
243}
244
245
246template <typename ValueType>
248{
249 std::pair<typename SwitchPoints::iterator, bool> insertionStatus = m_switchPoints.insert(point);
250 if (!insertionStatus.second) {
251 m_switchPoints.erase(insertionStatus.first);
252 }
253}
254
255
256template <typename ValueType>
258{
259 return m_beginState;
260}
261
262
263template <typename ValueType>
265{
266 m_beginState = state;
267}
268
269
270template <typename ValueType>
271bool TRanges<ValueType>::IsInside(ValueType point) const
272{
273 bool state = m_beginState;
274 for (typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
275 iter != m_switchPoints.end();
276 ++iter) {
277 if (*iter > point) {
278 break;
279 }
280
281 state = !state;
282 }
283
284 return state;
285}
286
287
288template <typename ValueType>
290{
291 bool state = m_beginState;
292 for (typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
293 iter != m_switchPoints.end();
294 ++iter) {
295 if (*iter > range.GetMinValue()) {
296 if (state) {
297 ++iter;
298
299 // is the next switch out of checked range?
300 return (iter == m_switchPoints.end()) || (*iter >= range.GetMaxValue());
301 }
302 else {
303 return false;
304 }
305 }
306
307 state = !state;
308 }
309
310 return state;
311}
312
313
314template <typename ValueType>
316{
317 typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
318 typename SwitchPoints::const_iterator listIter = rangesList.m_switchPoints.begin();
319
320 bool state = m_beginState;
321 bool listState = rangesList.m_beginState;
322
323 for (;;) {
324 bool isListCovered = state || !listState;
325 if (!isListCovered) {
326 return false;
327 }
328
329 if (iter != m_switchPoints.end()) {
330 ValueType point = *iter;
331
332 if (listIter != rangesList.m_switchPoints.end()) {
333 ValueType listPoint = *listIter;
334
335 if (point <= listPoint) {
336 ++iter;
337 state = !state;
338 }
339
340 if (listPoint <= point) {
341 ++listIter;
342 listState = !listState;
343 }
344 }
345 else {
346 return true;
347 }
348 }
349 else {
350 // if no more segments in this list, check if no more switch is inside
351 return listIter == rangesList.m_switchPoints.end();
352 }
353 }
354}
355
356
357template <typename ValueType>
359{
360 if (clipRangePtr != nullptr) {
361 result.Reset();
362 result.m_beginState = false;
363
364 int prevPosition = clipRangePtr->GetMinValue();
365
366 bool state = m_beginState;
367
368 for (typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
369 iter != m_switchPoints.end();
370 ++iter) {
371 ValueType position = *iter;
372 if (position >= clipRangePtr->GetMaxValue()) {
373 break;
374 }
375
376 if (position > prevPosition) {
377 if (!state) {
378 result.m_switchPoints.insert(prevPosition);
379 result.m_switchPoints.insert(position);
380 }
381
382 prevPosition = position;
383 }
384
385 state = !state;
386 }
387
388 if (!state) {
389 result.m_switchPoints.insert(prevPosition);
390 result.m_switchPoints.insert(clipRangePtr->GetMaxValue());
391 }
392 }
393 else {
394 result.m_switchPoints = m_switchPoints;
395 result.m_beginState = !m_beginState;
396 }
397}
398
399
400template <typename ValueType>
402{
403 if (clipRangePtr != nullptr) {
404 int prevPosition = clipRangePtr->GetMinValue();
405
406 bool state = m_beginState;
407
408 // remove all points before
409 for (typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
410 (iter != m_switchPoints.end()) && (*iter < prevPosition);
411 m_switchPoints.erase(iter++)) {
412 state = !state;
413 }
414
415 typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
416
417 if (!state) {
418 if ((iter != m_switchPoints.end()) && (*iter > prevPosition)) { // no first element? add it!
419 m_switchPoints.insert(prevPosition);
420 }
421 }
422
423 for (; iter != m_switchPoints.end(); ++iter) {
424 ValueType position = *iter;
425 if (position >= clipRangePtr->GetMaxValue()) { // remove all points after
426 m_switchPoints.erase(iter, m_switchPoints.end());
427
428 break;
429 }
430
431 state = !state;
432 }
433
434 if (!state) {
435 m_switchPoints.insert(clipRangePtr->GetMaxValue());
436 }
437
438 m_beginState = false;
439 }
440 else {
441 m_beginState = !m_beginState;
442 }
443}
444
445
446template <typename ValueType>
448{
449 TRanges<ValueType> retVal;
450
451 GetUnion(rangesList, retVal);
452
453 return retVal;
454}
455
456
457template <typename ValueType>
459{
460 typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
461 typename SwitchPoints::const_iterator listIter = rangesList.m_switchPoints.begin();
462
463 bool state = m_beginState;
464 bool listState = rangesList.m_beginState;
465
466 bool resultState = state || listState;
467
468 result.m_beginState = resultState;
469 result.m_switchPoints.clear();
470
471 for (;;) {
472 if (iter != m_switchPoints.end()) {
473 ValueType point = *iter;
474
475 if (listIter != rangesList.m_switchPoints.end()) {
476 ValueType listPoint = *listIter;
477
478 if (point <= listPoint) {
479 ++iter;
480 state = !state;
481 }
482
483 if (listPoint <= point) {
484 ++listIter;
485 listState = !listState;
486 }
487
488 bool unitedStateAfter = state || listState;
489 if (unitedStateAfter != resultState) {
490 result.m_switchPoints.insert(qMin(point, listPoint));
491
492 resultState = unitedStateAfter;
493 }
494 }
495 else {
496 if (!listState) {
497 result.m_switchPoints.insert(iter, m_switchPoints.end());
498 }
499
500 return;
501 }
502 }
503 else {
504 if (!state && (listIter != rangesList.m_switchPoints.end())) {
505 result.m_switchPoints.insert(listIter, rangesList.m_switchPoints.end());
506 }
507
508 return;
509 }
510 }
511}
512
513
514template <typename ValueType>
516{
517 typename SwitchPoints::iterator iter = m_switchPoints.begin();
518 typename SwitchPoints::const_iterator listIter = rangesList.m_switchPoints.begin();
519
520 bool state = m_beginState;
521 bool listState = rangesList.m_beginState;
522
523 m_beginState = state || listState;
524
525 for (;;) {
526 if (iter != m_switchPoints.end()) {
527 ValueType point = *iter;
528
529 if (listIter != rangesList.m_switchPoints.end()) {
530 ValueType listPoint = *listIter;
531
532 if (point == listPoint) {
533 ++iter;
534 state = !state;
535 ++listIter;
536 listState = !listState;
537 }
538 else if (point < listPoint) {
539 if (listState) {
540 iter = m_switchPoints.remove(iter);
541 }
542 else {
543 ++iter;
544 }
545 state = !state;
546 }
547 else {
548 if (!state) {
549 iter = m_switchPoints.insert(iter, listPoint);
550 }
551 ++listIter;
552 listState = !listState;
553 }
554 }
555 else {
556 if (listState) {
557 m_switchPoints.remove(iter, m_switchPoints.end());
558 }
559
560 return;
561 }
562 }
563 else {
564 if (!state && (listIter != rangesList.m_switchPoints.end())) {
565 m_switchPoints.insert(listIter, rangesList.m_switchPoints.end());
566 }
567
568 return;
569 }
570 }
571}
572
573
574template <typename ValueType>
575void TRanges<ValueType>::Union(const TRange<ValueType>& range, bool isInverted)
576{
577 if (range.IsEmpty()) {
578 return;
579 }
580
581 bool firstPointState = m_beginState;
582 typename SwitchPoints::const_iterator firstIter = m_switchPoints.begin();
583 for (; firstIter != m_switchPoints.end(); ++firstIter) {
584 if (*firstIter >= range.GetMinValue()) {
585 break;
586 }
587
588 firstPointState = !firstPointState;
589 }
590
591 bool secondPointState = firstPointState;
592 typename SwitchPoints::const_iterator secondIter = firstIter;
593 for (; secondIter != m_switchPoints.end(); ++secondIter) {
594 if (*secondIter >= range.GetMaxValue()) {
595 break;
596 }
597
598 secondPointState = !secondPointState;
599 }
600
601 if (firstIter != secondIter) {
602 // if there are some points in range...
603 if (isInverted) {
604 m_switchPoints.erase(m_switchPoints.begin(), firstIter); // remove all points before
605 m_switchPoints.erase(m_switchPoints.begin(), secondIter); // remove all points after
606 }
607 else {
608 m_switchPoints.erase(firstIter, secondIter); // remove all points before
609 }
610 }
611 else {
612 if (isInverted) {
613 m_switchPoints.clear();
614 }
615 }
616
617 m_beginState = m_beginState || isInverted;
618
619 if (firstPointState == isInverted) {
620 m_switchPoints.insert(range.GetMinValue());
621 }
622
623 if (secondPointState == isInverted) {
624 m_switchPoints.insert(range.GetMaxValue());
625 }
626}
627
628
629template <typename ValueType>
631{
632 TRanges<ValueType> retVal;
633
634 GetIntersection(rangesList, retVal);
635
636 return retVal;
637}
638
639
640template <typename ValueType>
642{
643 typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
644 typename SwitchPoints::const_iterator listIter = rangesList.m_switchPoints.begin();
645
646 bool state = m_beginState;
647 bool listState = rangesList.m_beginState;
648
649 bool resultState = state && listState;
650
651 result.m_beginState = resultState;
652 result.m_switchPoints.clear();
653
654 for (;;) {
655 if (iter != m_switchPoints.end()) {
656 ValueType point = *iter;
657
658 if (listIter != rangesList.m_switchPoints.end()) {
659 ValueType listPoint = *listIter;
660
661 if (point <= listPoint) {
662 ++iter;
663 state = !state;
664 }
665
666 if (listPoint <= point) {
667 ++listIter;
668 listState = !listState;
669 }
670
671 bool unitedStateAfter = state && listState;
672 if (unitedStateAfter != resultState) {
673 result.m_switchPoints.insert(qMin(point, listPoint));
674
675 resultState = unitedStateAfter;
676 }
677 }
678 else {
679 if (listState) {
680 result.m_switchPoints.insert(iter, m_switchPoints.end());
681 }
682
683 return;
684 }
685 }
686 else {
687 if (state && (listIter != rangesList.m_switchPoints.end())) {
688 result.m_switchPoints.insert(listIter, rangesList.m_switchPoints.end());
689 }
690
691 return;
692 }
693 }
694}
695
696
697template <typename ValueType>
699{
700 typename SwitchPoints::iterator iter = m_switchPoints.begin();
701 typename SwitchPoints::const_iterator listIter = rangesList.m_switchPoints.begin();
702
703 bool state = m_beginState;
704 bool listState = rangesList.m_beginState;
705
706 m_beginState = state && listState;
707
708 for (;;) {
709 if (iter != m_switchPoints.end()) {
710 ValueType point = *iter;
711
712 if (listIter != rangesList.m_switchPoints.end()) {
713 ValueType listPoint = *listIter;
714
715 if (point == listPoint) {
716 ++iter;
717 state = !state;
718 ++listIter;
719 listState = !listState;
720 }
721 else if (point < listPoint) {
722 if (!listState) {
723 iter = m_switchPoints.remove(iter);
724 }
725 else {
726 ++iter;
727 }
728 state = !state;
729 }
730 else {
731 if (state) {
732 iter = m_switchPoints.insert(iter, listPoint);
733 }
734 ++listIter;
735 listState = !listState;
736 }
737 }
738 else {
739 if (!listState) {
740 m_switchPoints.remove(iter, m_switchPoints.end());
741 }
742
743 return;
744 }
745 }
746 else {
747 if (state && (listIter != rangesList.m_switchPoints.end())) {
748 m_switchPoints.insert(listIter, rangesList.m_switchPoints.end());
749 }
750
751 return;
752 }
753 }
754}
755
756
757template <typename ValueType>
758void TRanges<ValueType>::Intersection(const TRange<ValueType>& range, bool isInverted)
759{
760 m_beginState = !m_beginState;
761
762 Union(range, !isInverted);
763
764 m_beginState = !m_beginState;
765}
766
767
768template <typename ValueType>
769void TRanges<ValueType>::Erode(ValueType leftValue, ValueType rightValue)
770{
771 TRanges<ValueType>::Dilate(-leftValue, -rightValue);
772}
773
774
775template <typename ValueType>
776void TRanges<ValueType>::Dilate(ValueType leftValue, ValueType rightValue)
777{
778 if (leftValue * rightValue < 0) { // do 2 steps for complex dilatation
779 Dilate(leftValue, 0);
780 Dilate(0, rightValue);
781
782 return;
783 }
784
785 ValueType absoluteSum = qAbs(leftValue + rightValue);
786 if (absoluteSum <= 0) {
787 return; // nothing to do
788 }
789
790 bool isErosion = (leftValue + rightValue < 0);
791 ValueType leftValueCorr = qAbs(leftValue);
792 ValueType rightValueCorr = qAbs(rightValue);
793
794 bool state = m_beginState;
795
796 typename SwitchPoints::iterator iter = m_switchPoints.begin();
797 while (iter != m_switchPoints.end()) {
798 ValueType point = *iter;
799
800 state = !state;
801
802 if (!state == isErosion) {
803 // move point back
804 if (iter != m_switchPoints.begin()) {
805 typename SwitchPoints::iterator prevIter = iter;
806 --prevIter;
807
808 if (*prevIter > point - absoluteSum) {
809 // previous range should be removed - is smaller than the erosion kernel
810 m_switchPoints.erase(prevIter);
811 m_switchPoints.erase(iter++);
812
813 continue;
814 }
815 }
816
817 // range can be moved using kernel size
818 if (rightValueCorr > 0) {
819 m_switchPoints.erase(iter++);
820 iter = m_switchPoints.insert(iter, point - rightValueCorr);
821 }
822 }
823 else {
824 // move point forward
825 typename SwitchPoints::iterator nextIter = iter;
826 ++nextIter;
827
828 if (nextIter != m_switchPoints.end()) {
829 if (*nextIter < point + absoluteSum) {
830 // following range should be removed - is smaller than the erosion kernel
831 m_switchPoints.erase(iter++);
832 m_switchPoints.erase(iter++);
833
834 continue;
835 }
836 }
837
838 if (leftValueCorr > 0) {
839 // range can be moved using kernel size
840 m_switchPoints.erase(iter++);
841 iter = m_switchPoints.insert(iter, point + leftValueCorr);
842 }
843 }
844
845 ++iter;
846 }
847}
848
849
850template <typename ValueType>
851void TRanges<ValueType>::RemoveGaps(ValueType value, bool gapState)
852{
853 if (gapState) {
854 Dilate(value, value);
855 Erode(value, value);
856 }
857 else {
858 Erode(value, value);
859 Dilate(value, value);
860 }
861}
862
863
864template <typename ValueType>
866{
867 SwitchPoints newSwitchPoints;
868 for (typename SwitchPoints::iterator iter = m_switchPoints.begin();
869 iter != m_switchPoints.end();
870 ++iter) {
871 newSwitchPoints.insert(*iter + offset);
872 }
873
874 m_switchPoints.swap(newSwitchPoints);
875}
876
877
878template <typename ValueType>
880{
881 int prevPosition = range.GetMinValue();
882
883 bool state = m_beginState;
884
885 for (typename SwitchPoints::const_iterator iter = m_switchPoints.begin();
886 iter != m_switchPoints.end();
887 ++iter) {
888 ValueType position = *iter;
889 if (position >= range.GetMaxValue()) {
890 break;
891 }
892
893 if (position > prevPosition) {
894 if (state) {
895 result.push_back(TRange<ValueType>(prevPosition, position));
896 }
897
898 prevPosition = position;
899 }
900
901 state = !state;
902 }
903
904 if (state) {
905 result.push_back(TRange<ValueType>(prevPosition, range.GetMaxValue()));
906 }
907}
908
909
910template <typename ValueType>
912{
913 return (m_beginState == ranges.m_beginState) && (m_switchPoints == ranges.m_switchPoints);
914}
915
916
917template <typename ValueType>
919{
920 return (m_beginState != ranges.m_beginState) || (m_switchPoints != ranges.m_switchPoints);
921}
922
923
924// typedefs
925
928
929
930// related global functions
931
932template <typename ValueType>
933inline size_t qHash(const TRanges<ValueType>& key, size_t seed = 0)
934{
935 size_t retVal = seed;
936
937 if (key.GetBeginState()) {
938 retVal++;
939 }
940
941 for (const auto& pos : key.GetSwitchPoints()) {
942 retVal = retVal ^ size_t(pos);
943 }
944
945 return retVal;
946}
947
948
949} // namespace istd
950
951
Implementation of a abstract range defined by two values - minimum and maximum.
Definition TRange.h:22
ValueType GetMaxValue() const
Get the top value.
Definition TRange.h:356
ValueType GetMinValue() const
Get the bottom value.
Definition TRange.h:335
bool IsEmpty() const
Return true if the bottom value is equal to the top value.
Definition TRange.h:321
Set of ranges.
Definition TRanges.h:30
void Invert(const TRange< ValueType > *clipRangePtr)
Invert this range in place.
Definition TRanges.h:401
bool IsInside(ValueType point) const
Check if some point belongs to set.
Definition TRanges.h:271
void Dilate(ValueType leftValue, ValueType rightValue)
Calculate dilatation of this range list.
Definition TRanges.h:776
SwitchPoints & GetSwitchPointsRef()
Allows access to stored switch points.
Definition TRanges.h:240
void SetBeginState(bool state)
Set begin state.
Definition TRanges.h:264
void InsertSwitchPoint(ValueType point)
Insert new switch point.
Definition TRanges.h:247
bool IsEmpty() const
Check if this set is empty.
Definition TRanges.h:226
void Erode(ValueType leftValue, ValueType rightValue)
Calculate erosion of this range list.
Definition TRanges.h:769
bool operator==(const TRanges< ValueType > &ranges) const
Definition TRanges.h:911
bool GetBeginState() const
Get begin state.
Definition TRanges.h:257
QList< TRange< ValueType > > RangeList
Definition TRanges.h:32
TRanges< ValueType > GetUnion(const TRanges< ValueType > &rangesList) const
Get union of two range list.
Definition TRanges.h:447
void ShiftRanges(ValueType offset)
ShiftRanges all points in this set using specified offset.
Definition TRanges.h:865
std::set< ValueType > SwitchPoints
Definition TRanges.h:33
bool operator!=(const TRanges< ValueType > &ranges) const
Definition TRanges.h:918
const SwitchPoints & GetSwitchPoints() const
Get stored switch points.
Definition TRanges.h:233
void RemoveGaps(ValueType value, bool gapState=false)
Remove gaps with some length.
Definition TRanges.h:851
TRanges()
Default constructor initializing this set to be empty.
Definition TRanges.h:200
void Union(const TRanges< ValueType > &rangesList)
Calculate union of this range list and the other one.
Definition TRanges.h:515
void Intersection(const TRanges< ValueType > &rangesList)
Calculate intersection of this range list and the other one.
Definition TRanges.h:698
void Reset()
Set this set to be empty.
Definition TRanges.h:218
void GetInverted(TRanges< ValueType > &result, const TRange< ValueType > *clipRangePtr) const
Get inverted range.
Definition TRanges.h:358
void GetAsList(const TRange< ValueType > &range, RangeList &result) const
Get this set as list of istd::TRange objects.
Definition TRanges.h:879
TRanges< ValueType > GetIntersection(const TRanges< ValueType > &rangesList) const
Get intersection of two range list.
Definition TRanges.h:630
Standard library.
Definition IComponent.h:17
TRanges< double > CRanges
Definition TRanges.h:926
size_t qHash(const CVarIndex &index, size_t seed=0)
TRanges< int > CIntRanges
Definition TRanges.h:927

© Witold Gantzke and Kirill Lepskiy