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

© 2007-2017 Witold Gantzke and Kirill Lepskiy