• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision178 (tree)
Time2018-12-27 07:59:08
Authorquiret

Log Message

- added GetTightBound method to MathSlice.h which returns the tightly-bordering bound to another
- fixed the AreBoundsTight method to acuretely returns results instead of estimating them
- fixed some bugs with corner-cases in bounds (related to number-domain transformation)
- robustness improvements to SortedSliceSector
-

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 177)
+++ common/sdk/AVLTree.h (revision 178)
@@ -1134,7 +1134,7 @@
11341134 template <typename valueType>
11351135 inline const AVLNode* FindNode( const valueType& value ) const { return FindNodeCustom <dispatcherType> ( value ); }
11361136
1137-private:
1137+ // Returns any node that matches our criteria.
11381138 template <typename callbackType>
11391139 AINLINE AVLNode* FindAnyNodeByCriteria( const callbackType& cb )
11401140 {
@@ -1162,7 +1162,6 @@
11621162 return curNode;
11631163 }
11641164
1165-public:
11661165 // Finds the minimum node that matches certain criteria.
11671166 // Returning eCompResult::EQUAL indicates a match but in this function multiple nodes are allowed to be equal, forming
11681167 // classes of values.
--- common/sdk/MathSlice.h (revision 177)
+++ common/sdk/MathSlice.h (revision 178)
@@ -23,6 +23,10 @@
2323 namespace eir
2424 {
2525
26+// Forward declarations for inter-changeability.
27+template <typename numberType> struct lowerBound;
28+template <typename numberType> struct upperBound;
29+
2630 // Definition of an upper bound.
2731 template <typename numberType>
2832 struct upperBound
@@ -99,6 +103,7 @@
99103 #endif //_MSC_VER
100104 }
101105 }
106+ AINLINE upperBound( const lowerBound <numberType>& value, bool isIncluded ) noexcept(std::is_floating_point <numberType>::value);
102107
103108 AINLINE upperBound( const upperBound& ) = default;
104109 AINLINE upperBound( upperBound&& ) = default;
@@ -378,7 +383,7 @@
378383 {
379384 if ( isIncluded == false )
380385 {
381- if ( value == std::numeric_limits <numberType>::min() )
386+ if ( value == std::numeric_limits <numberType>::max() )
382387 {
383388 throw eir_exception();
384389 }
@@ -400,6 +405,7 @@
400405 #endif //_MSC_VER
401406 }
402407 }
408+ AINLINE lowerBound( const upperBound <numberType>& value, bool isIncluded ) noexcept(std::is_floating_point <numberType>::value);
403409
404410 AINLINE lowerBound( const lowerBound& ) = default;
405411 AINLINE lowerBound( lowerBound&& ) = default;
@@ -563,6 +569,129 @@
563569
564570 // *** Methods that work in combination of both lowerBound and upperBound.
565571
572+// Cross-domain constructor for upperBound.
573+template <typename numberType>
574+AINLINE upperBound <numberType>::upperBound( const lowerBound <numberType>& value, bool isIncluded ) noexcept(std::is_floating_point <numberType>::value)
575+{
576+ if constexpr ( std::is_integral <numberType>::value )
577+ {
578+ numberType low_value = value.get_value();
579+
580+ if constexpr ( std::is_unsigned <numberType>::value )
581+ {
582+ if ( isIncluded == false )
583+ {
584+ // Special case: treat max() as -1.
585+ if ( low_value == 0 )
586+ {
587+ low_value = std::numeric_limits <numberType>::max();
588+ }
589+ else
590+ {
591+ low_value--;
592+ }
593+ }
594+ else
595+ {
596+ // This value is not displayable in this domain.
597+ if ( low_value == std::numeric_limits <numberType>::max() )
598+ {
599+ throw eir_exception();
600+ }
601+ }
602+
603+ this->data.value = low_value;
604+ }
605+ else
606+ {
607+ if ( isIncluded == false )
608+ {
609+ if ( low_value == std::numeric_limits <numberType>::min() )
610+ {
611+ throw eir_exception();
612+ }
613+
614+ low_value--;
615+ }
616+
617+ this->data.value = low_value;
618+ }
619+ }
620+ else if constexpr ( std::is_floating_point <numberType>::value )
621+ {
622+ this->data.value = value.get_value();
623+ this->data.isIncluded = isIncluded;
624+ }
625+ else
626+ {
627+#ifdef _MSC_VER
628+ static_assert( false, "no cross-domain constructor for upperBound at numberType" );
629+#endif //_MSC_VER
630+ }
631+}
632+
633+// Cross-domain constructor for lowerBound.
634+template <typename numberType>
635+AINLINE lowerBound <numberType>::lowerBound( const upperBound <numberType>& value, bool isIncluded ) noexcept(std::is_floating_point <numberType>::value)
636+{
637+ if constexpr ( std::is_integral <numberType>::value )
638+ {
639+ numberType highValue = value.get_value();
640+
641+ if constexpr ( std::is_unsigned <numberType>::value )
642+ {
643+ if ( isIncluded == false )
644+ {
645+ // Special case: treat max as -1.
646+ if ( highValue == std::numeric_limits <numberType>::max() )
647+ {
648+ highValue = 0;
649+ }
650+ else
651+ {
652+ highValue++;
653+ }
654+ }
655+ else
656+ {
657+ // Special case: since max is actually -1 and -1 is not in the domain of lowerBound,
658+ // we must bail here.
659+ if ( highValue == std::numeric_limits <numberType>::max() )
660+ {
661+ throw eir_exception();
662+ }
663+ }
664+
665+ this->data.value = highValue;
666+ }
667+ else
668+ {
669+ if ( isIncluded == false )
670+ {
671+ if ( highValue == std::numeric_limits <numberType>::max() )
672+ {
673+ throw eir_exception();
674+ }
675+
676+ highValue++;
677+ }
678+
679+ this->data.value = highValue;
680+ }
681+ }
682+ else if constexpr ( std::is_floating_point <numberType>::value )
683+ {
684+ this->data.value = value.get_value();
685+ this->data.isIncluded = isIncluded;
686+ }
687+ else
688+ {
689+#ifdef _MSC_VER
690+ static_assert( false, "no cross-domain constructor for lowerBound at numberType" );
691+#endif //_MSC_VER
692+ }
693+}
694+
566695 // Returns the difference between upper border and lower border of an interval.
567696 template <typename numberType>
568697 AINLINE numberType get_bound_span( const lowerBound <numberType>& low, const upperBound <numberType>& high ) noexcept
@@ -724,7 +853,7 @@
724853 return false;
725854 }
726855
727- if ( left.is_included() || right.is_included() )
856+ if ( left.is_included() == false || right.is_included() == false )
728857 {
729858 return false;
730859 }
@@ -747,6 +876,70 @@
747876 return operator != ( right, left );
748877 }
749878
879+// Returns the border that tightly aligns on another border.
880+template <typename numberType>
881+AINLINE upperBound <numberType> GetTightBound( const lowerBound <numberType>& border )
882+{
883+ return upperBound( border, !border.is_included() );
884+}
885+
886+template <typename numberType>
887+AINLINE lowerBound <numberType> GetTightBound( const upperBound <numberType>& border )
888+{
889+ return lowerBound( border, !border.is_included() );
890+}
891+
892+// Sometimes there is no tight bound.
893+template <typename numberType>
894+AINLINE bool HasTightBound( const lowerBound <numberType>& border )
895+{
896+ if constexpr ( std::is_integral <numberType>::value )
897+ {
898+ if constexpr ( std::is_unsigned <numberType>::value )
899+ {
900+ return true;
901+ }
902+ else
903+ {
904+ // Due to the inclusive-optimization we have to make sure.
905+ return ( border.get_value() > std::numeric_limits <numberType>::min() );
906+ }
907+ }
908+ else if constexpr ( std::is_floating_point <numberType>::value )
909+ {
910+ return true;
911+ }
912+ else
913+ {
914+ return false;
915+ }
916+}
917+
918+template <typename numberType>
919+AINLINE bool HasTightBound( const upperBound <numberType>& border )
920+{
921+ if constexpr ( std::is_integral <numberType>::value )
922+ {
923+ if constexpr ( std::is_unsigned <numberType>::value )
924+ {
925+ return true;
926+ }
927+ else
928+ {
929+ // Same as for above.
930+ return ( border.get_value() < std::numeric_limits <numberType>::max() );
931+ }
932+ }
933+ else if constexpr ( std::is_floating_point <numberType>::value )
934+ {
935+ return true;
936+ }
937+ else
938+ {
939+ return false;
940+ }
941+}
942+
750943 enum eIntersectionResult
751944 {
752945 INTERSECT_EQUAL,
@@ -779,12 +972,18 @@
779972 template <typename numberType>
780973 class mathSlice
781974 {
782- AINLINE mathSlice( numberType startOffset, numberType endOffset, bool startIncluded, bool endIncluded ) noexcept
975+ AINLINE mathSlice( numberType startOffset, numberType endOffset, bool startIncluded, bool endIncluded )
783976 : startBound( startOffset, startIncluded ), endBound( endOffset, endIncluded )
784977 {
785978 return;
786979 }
787980
981+ AINLINE mathSlice( const lowerBound <numberType>& low, const upperBound <numberType>& high ) noexcept
982+ : startBound( low ), endBound( high )
983+ {
984+ return;
985+ }
986+
788987 public:
789988 AINLINE mathSlice( void ) noexcept : startBound( 0 ), endBound( 0, false )
790989 {
@@ -797,14 +996,14 @@
797996 }
798997
799998 // Note that both offsets are inclusive.
800- static AINLINE mathSlice fromOffsets( numberType startOffset, numberType endOffset, bool startIncluded = true, bool endIncluded = true ) noexcept
999+ static AINLINE mathSlice fromOffsets( numberType startOffset, numberType endOffset, bool startIncluded = true, bool endIncluded = true )
8011000 {
8021001 return mathSlice( startOffset, endOffset, startIncluded, endIncluded );
8031002 }
8041003
805- static AINLINE mathSlice fromBounds( const lowerBound <numberType>& low, const upperBound <numberType>& high )
1004+ static AINLINE mathSlice fromBounds( const lowerBound <numberType>& low, const upperBound <numberType>& high ) noexcept
8061005 {
807- return mathSlice( low.get_value(), high.get_value(), low.is_included(), high.is_included() );
1006+ return mathSlice( low, high );
8081007 }
8091008
8101009 AINLINE bool IsEmpty( void ) const noexcept
@@ -1030,13 +1229,13 @@
10301229 else if ( intResult == INTERSECT_BORDER_START )
10311230 {
10321231 // Just return the remainder.
1033- const mathSlice remainder = fromOffsets( subEndBound.get_value(), ourEndBound.get_value(), !subEndBound.is_included(), ourEndBound.is_included() );
1232+ const mathSlice remainder = fromBounds( GetTightBound( subEndBound ), ourEndBound );
10341233
10351234 cb( remainder, true );
10361235 }
10371236 else if ( intResult == INTERSECT_BORDER_END )
10381237 {
1039- const mathSlice remainder = fromOffsets( ourStartBound.get_value(), subStartBound.get_value(), ourStartBound.is_included(), !subStartBound.is_included() );
1238+ const mathSlice remainder = fromBounds( ourStartBound, GetTightBound( subStartBound ) );
10401239
10411240 cb( remainder, true );
10421241 }
@@ -1045,7 +1244,7 @@
10451244 // Since we are enclosing the subtractBy, we could have both region before and region after subtractBy.
10461245 if ( ourStartBound < subStartBound )
10471246 {
1048- mathSlice leftRegion = fromOffsets( ourStartBound.get_value(), subStartBound.get_value(), ourStartBound.is_included(), !subStartBound.is_included() );
1247+ mathSlice leftRegion = fromBounds( ourStartBound, GetTightBound( subStartBound ) );
10491248
10501249 cb( leftRegion, true );
10511250 }
@@ -1052,7 +1251,7 @@
10521251
10531252 if ( ourEndBound > subEndBound )
10541253 {
1055- mathSlice rightRegion = fromOffsets( subEndBound.get_value(), ourEndBound.get_value(), !subEndBound.is_included(), ourEndBound.is_included() );
1254+ mathSlice rightRegion = fromBounds( GetTightBound( subEndBound ), ourEndBound );
10561255
10571256 cb( rightRegion, false );
10581257 }
@@ -1076,7 +1275,7 @@
10761275
10771276 // Neighborhood function.
10781277 template <typename leftNumberType, typename rightNumberType>
1079-AINLINE bool IsNumberInNeighborhood( const leftNumberType& left, const rightNumberType& right )
1278+AINLINE bool IsNumberInNeighborhood( const leftNumberType& left, const rightNumberType& right ) noexcept
10801279 {
10811280 if constexpr ( std::is_floating_point <leftNumberType>::value || std::is_floating_point <rightNumberType>::value )
10821281 {
@@ -1111,16 +1310,16 @@
11111310 }
11121311
11131312 template <typename numberType>
1114-AINLINE bool AreBoundsTight( const upperBound <numberType>& left, const lowerBound <numberType>& right )
1313+AINLINE bool AreBoundsTight( const upperBound <numberType>& left, const lowerBound <numberType>& right ) noexcept
11151314 {
1116- // Actually allow no room between numbers.
1117- // This is achieved if at least one bound is wanting to dock onto the other.
1118- if ( left.is_included() == false && right.is_included() == false )
1315+ // If we are at the maximum already then do not bother.
1316+ if ( HasTightBound( left ) == false )
11191317 {
11201318 return false;
11211319 }
11221320
1123- return IsNumberInNeighborhood( left.get_value(), right.get_value() );
1321+ // There always is a tight bound so meow.
1322+ return ( right == GetTightBound( left ) );
11241323 }
11251324
11261325 } //namespace eir
--- common/sdk/SortedSliceSector.h (revision 177)
+++ common/sdk/SortedSliceSector.h (revision 178)
@@ -162,13 +162,13 @@
162162 {
163163 // Check if our request would overlap with anything.
164164 // If it would then we have to merge instead.
165- AVLNode *avlBeginMergeWithNode = this->data.avlSliceTree.FindMinimumNodeByCriteria(
165+ AVLNode *avlAnyMergeWithNode = this->data.avlSliceTree.FindAnyNodeByCriteria(
166166 [&]( AVLNode *leftNode )
167167 {
168168 return _CompareNodeWithSlice( leftNode, slice, true );
169169 });
170170
171- if ( avlBeginMergeWithNode )
171+ if ( avlAnyMergeWithNode )
172172 {
173173 // Collect the region that our new slice should be at.
174174 lowerBound <numberType> regionMin = slice.GetSliceStartBound();
@@ -186,7 +186,7 @@
186186 sectorSlice_t nodesToSubtractSlices[ 2 ];
187187 size_t numNodesToSubtract = 0;
188188 {
189- AVLNode *avlIntersectNode = avlBeginMergeWithNode;
189+ AVLNode *avlIntersectNode = avlAnyMergeWithNode;
190190 bool hasIntersectNode = true;
191191
192192 while ( true )
@@ -194,7 +194,7 @@
194194 // To remove certain redundancy checking.
195195 if ( !hasIntersectNode )
196196 {
197- avlIntersectNode = this->data.avlSliceTree.FindMinimumNodeByCriteria(
197+ avlIntersectNode = this->data.avlSliceTree.FindAnyNodeByCriteria(
198198 [&]( AVLNode *leftNode )
199199 {
200200 return _CompareNodeWithSlice( leftNode, slice, true );
@@ -249,7 +249,9 @@
249249
250250 bool hasRegistered = false;
251251
252- if ( isCoveredIntersect( intResult ) == false )
252+ // Graceful cleanup to handle the unknown case.
253+
254+ if ( isCoveredIntersect( intResult ) == false && intResult != INTERSECT_UNKNOWN )
253255 {
254256 #ifdef _DEBUG
255257 assert( numNodesToSubtract < 2 );
@@ -512,10 +514,7 @@
512514 // If we have a region prior to our region, then we must report it.
513515 if ( curStartBound < curSlice.GetSliceStartBound() )
514516 {
515- const sectorSlice_t unavailSlice = sectorSlice_t::fromOffsets(
516- curStartBound.get_value(), curSlice.GetSliceStartPoint(),
517- curStartBound.is_included(), !curSlice.IsStartIncluded()
518- );
517+ const sectorSlice_t unavailSlice = sectorSlice_t::fromBounds( curStartBound, GetTightBound( curSlice.GetSliceStartBound() ) );
519518
520519 cb( unavailSlice, false );
521520 }
@@ -523,7 +522,7 @@
523522 // Update the current start point.
524523 if ( curStartBound <= curSlice.GetSliceEndBound() )
525524 {
526- curStartBound = lowerBound <numberType> ( curSlice.GetSliceEndPoint(), !curSlice.IsEndIncluded() );
525+ curStartBound = GetTightBound( curSlice.GetSliceEndBound() );
527526 }
528527 }
529528
--- unittests/src/mathslice.cpp (revision 177)
+++ unittests/src/mathslice.cpp (revision 178)
@@ -127,6 +127,16 @@
127127 }
128128 printf( "ok.\n" );
129129
130+ printf( "testing lowerBound GetTightBound..." );
131+ {
132+ assert(
133+ GetTightBound( eir::lowerBound <unsigned int> ( std::numeric_limits <unsigned int>::max(), true ) )
134+ ==
135+ eir::upperBound <unsigned int> ( std::numeric_limits <unsigned int>::max() - 1, true )
136+ );
137+ }
138+ printf( "ok.\n" );
139+
130140 static_assert( sizeof(eir::upperBound <int>) == sizeof(int), "eir::upperBound with integral no good memory guarrantee" );
131141
132142 printf( "testing upperBound construction..." );
@@ -308,6 +318,12 @@
308318 }
309319 }
310320 printf( "ok.\n" );
321+
322+ printf( "testing upperBound GetTightBound..." );
323+ {
324+ assert( GetTightBound( eir::upperBound <unsigned int> ( std::numeric_limits <unsigned int>::max(), true ) ) == eir::lowerBound <unsigned int> ( 0, true ) );
325+ }
326+ printf( "ok.\n" );
311327 }
312328
313329 void MATHSLICE_TESTS( void )
Show on old repository browser