• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision442 (tree)
Time2022-02-16 04:10:59
Authorquiret

Log Message

- commutativity improvements for eir::Map and eir::Set regarding the comparator
- made the noexcept specifications for eir::Map and eir::Set methods more clear
- fixed eir::nothrow_constructible_from

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 441)
+++ common/sdk/AVLTree.h (revision 442)
@@ -62,26 +62,31 @@
6262 };
6363 };
6464
65+template <typename dispatcherType, typename valueType>
66+concept AVLNodeDispatcherNodeLeftComparableWith =
67+ requires ( const AVLNode *L, const valueType& R ) { (eir::eCompResult)dispatcherType::CompareNodeWithValue( L, R ); };
6568
6669 template <typename dispatcherType, typename valueType>
70+concept AVLNodeDispatcherNodeRightComparableWith =
71+ requires ( const valueType& L, const AVLNode *R ) { (eir::eCompResult)dispatcherType::CompareNodeWithValue( L, R ); };
72+
73+template <typename dispatcherType, typename valueType>
6774 concept AVLNodeDispatcherNodeComparableWith =
68- requires ( const AVLNode *L, const valueType& R ) { (eir::eCompResult)dispatcherType::CompareNodeWithValue( L, R ); };
75+ AVLNodeDispatcherNodeLeftComparableWith <dispatcherType, valueType> ||
76+ AVLNodeDispatcherNodeRightComparableWith <dispatcherType, valueType>;
6977
70-template <typename dispatcherType, bool nodestackInsertOrAppend = true>
78+template <typename dispatcherType>
79+concept AVLNodeDispatcher =
80+ std::is_invocable_r <eir::eCompResult, decltype(dispatcherType::CompareNodes), const AVLNode*, const AVLNode*>::value;
81+
82+template <AVLNodeDispatcher dispatcherType, bool nodestackInsertOrAppend = true>
7183 struct AVLTree
7284 {
7385 // This class is NOT THREAD-SAFE.
7486
75-private:
76- // Here is a list of things we want to query the dispatcherType for.
77- static AINLINE eir::eCompResult compare_nodes( const AVLNode *node, const AVLNode *compareWith ) noexcept(noexcept(dispatcherType::CompareNodes( node, compareWith )))
78- {
79- return dispatcherType::CompareNodes( node, compareWith );
80- }
8187 // other (optional) methods:
8288 // - template <typename valueType> static eir::eCompResult CompareNodeWithValue( const AVLNode *left, const valueType& right )
8389
84-public:
8590 inline AVLTree( void ) noexcept
8691 {
8792 this->root = nullptr;
@@ -336,7 +341,7 @@
336341 }
337342 }
338343
339- AINLINE AVLNode* ScanForNodePosition( AVLNode *node, AVLNode**& iterPtrOut, AVLNode*& parentOut ) noexcept(noexcept(compare_nodes( node, node )))
344+ AINLINE AVLNode* ScanForNodePosition( AVLNode *node, AVLNode**& iterPtrOut, AVLNode*& parentOut ) noexcept(noexcept(dispatcherType::CompareNodes( node, node )))
340345 {
341346 // Find the position to insert our new node at.
342347 AVLNode *parent = nullptr;
@@ -354,7 +359,7 @@
354359 AVLNode *newParent = iter;
355360
356361 // Check key condition.
357- eir::eCompResult cmpRes = compare_nodes( node, iter );
362+ eir::eCompResult cmpRes = dispatcherType::CompareNodes( node, iter );
358363
359364 if ( cmpRes == eir::eCompResult::LEFT_LESS )
360365 {
@@ -902,8 +907,8 @@
902907
903908 // Calls the function for each node-stack member of the node.
904909 // Should be used if you want to iterate over absolutely every node of a tree.
905- template <typename callbackType>
906- static AINLINE void call_for_each_node_for_nodestack( AVLNode *walkNode, const callbackType& cb ) noexcept(noexcept(cb( nullptr )))
910+ template <typename callbackType> requires ( std::is_invocable <callbackType, AVLNode*>::value )
911+ static AINLINE void call_for_each_node_for_nodestack( AVLNode *walkNode, callbackType&& cb ) noexcept(noexcept(cb( nullptr )))
907912 {
908913 nodestack_iterator iter( walkNode );
909914
@@ -1019,8 +1024,8 @@
10191024
10201025 // Goes through each node in sorted order.
10211026 // This is just a helper for the entire tree.
1022- template <typename callbackType>
1023- inline void Walk( const callbackType& cb ) noexcept(noexcept(call_for_each_node_for_nodestack( nullptr, cb )))
1027+ template <typename callbackType> requires ( std::is_invocable <callbackType, AVLNode*>::value )
1028+ inline void Walk( callbackType&& cb ) noexcept(noexcept(call_for_each_node_for_nodestack( nullptr, cb )))
10241029 {
10251030 diff_node_iterator iter( this->GetSmallestNode() );
10261031
@@ -1037,7 +1042,7 @@
10371042 }
10381043
10391044 // Goes through each node in reverse sorted ordner.
1040- template <typename callbackType>
1045+ template <typename callbackType> requires ( std::is_invocable <callbackType, AVLNode*>::value )
10411046 inline void WalkReverse( const callbackType& cb ) noexcept(noexcept(call_for_each_node_for_nodestack( nullptr, cb )))
10421047 {
10431048 diff_node_iterator iter( this->GetBiggestNode() );
@@ -1167,8 +1172,17 @@
11671172 while ( walkNode )
11681173 {
11691174 // Walk to the next node.
1170- eir::eCompResult cmpRes = dispatcherType::CompareNodeWithValue( walkNode, theValue );
1175+ eir::eCompResult cmpRes;
11711176
1177+ if constexpr ( AVLNodeDispatcherNodeLeftComparableWith <dispatcherType, valueType> )
1178+ {
1179+ cmpRes = dispatcherType::CompareNodeWithValue( walkNode, theValue );
1180+ }
1181+ else
1182+ {
1183+ cmpRes = eir::flip_comp_result( dispatcherType::CompareNodeWithValue( theValue, walkNode ) );
1184+ }
1185+
11721186 if ( cmpRes != eir::eCompResult::LEFT_GREATER )
11731187 {
11741188 walkNode = walkNode->right;
@@ -1195,7 +1209,16 @@
11951209 while ( curNode )
11961210 {
11971211 // Check which one to go for next.
1198- eir::eCompResult cmpRes = customDispatcherType::CompareNodeWithValue( curNode, value );
1212+ eir::eCompResult cmpRes;
1213+
1214+ if constexpr ( AVLNodeDispatcherNodeLeftComparableWith <customDispatcherType, valueType> )
1215+ {
1216+ cmpRes = customDispatcherType::CompareNodeWithValue( curNode, value );
1217+ }
1218+ else
1219+ {
1220+ cmpRes = eir::flip_comp_result( customDispatcherType::CompareNodeWithValue( value, curNode ) );
1221+ }
11991222
12001223 if ( cmpRes == eir::eCompResult::LEFT_LESS )
12011224 {
@@ -1233,8 +1256,8 @@
12331256 }
12341257
12351258 private:
1236- template <typename callbackType>
1237- AINLINE AVLNode* _FindAnyNodeByCriteriaFromNode( AVLNode *curNode, const callbackType& cb ) noexcept(noexcept(cb( curNode )))
1259+ template <typename callbackType> requires ( std::is_invocable_r <eir::eCompResult, callbackType, AVLNode*>::value )
1260+ AINLINE AVLNode* _FindAnyNodeByCriteriaFromNode( AVLNode *curNode, const callbackType& cb ) noexcept(std::is_nothrow_invocable_r <eir::eCompResult, callbackType, AVLNode>::value)
12381261 {
12391262 while ( curNode )
12401263 {
@@ -1260,7 +1283,7 @@
12601283
12611284 public:
12621285 // Returns any node that matches our criteria.
1263- template <typename callbackType>
1286+ template <typename callbackType> requires ( std::is_invocable_r <eir::eCompResult, callbackType, AVLNode*>::value )
12641287 AINLINE AVLNode* FindAnyNodeByCriteria( const callbackType& cb ) noexcept(noexcept(_FindAnyNodeByCriteriaFromNode( nullptr, cb )))
12651288 {
12661289 return _FindAnyNodeByCriteriaFromNode( this->root, cb );
@@ -1271,7 +1294,7 @@
12711294 // classes of values.
12721295 // IMPORTANT: node classes are supposed to be contiguous! meaning there cannot be a node not in the class between two
12731296 // nodes that instead are.
1274- template <typename callbackType>
1297+ template <typename callbackType> requires ( std::is_invocable_r <eir::eCompResult, callbackType, AVLNode*>::value )
12751298 inline AVLNode* FindMinimumNodeByCriteria( const callbackType& cb ) noexcept(noexcept(_FindAnyNodeByCriteriaFromNode( nullptr, cb )))
12761299 {
12771300 // NOTE: cb is a virtual "right value-span". it is pretty complicated but just roll with it.
@@ -1292,7 +1315,7 @@
12921315 return curNode;
12931316 }
12941317
1295- template <typename callbackType>
1318+ template <typename callbackType> requires ( std::is_invocable_r <eir::eCompResult, callbackType, AVLNode*>::value )
12961319 inline AVLNode* FindMaximumNodeByCriteria( const callbackType& cb ) noexcept(noexcept(_FindAnyNodeByCriteriaFromNode( nullptr, cb )))
12971320 {
12981321 AVLNode *curNode = FindAnyNodeByCriteria( cb );
@@ -1328,11 +1351,11 @@
13281351 {
13291352 if ( parent->left == node )
13301353 {
1331- FATAL_ASSERT( compare_nodes( node, parent ) == eir::eCompResult::LEFT_LESS );
1354+ FATAL_ASSERT( dispatcherType::CompareNodes( node, parent ) == eir::eCompResult::LEFT_LESS );
13321355 }
13331356 else if ( parent->right == node )
13341357 {
1335- FATAL_ASSERT( compare_nodes( parent, node ) == eir::eCompResult::LEFT_LESS );
1358+ FATAL_ASSERT( dispatcherType::CompareNodes( parent, node ) == eir::eCompResult::LEFT_LESS );
13361359 }
13371360 else
13381361 {
@@ -1343,13 +1366,13 @@
13431366 if ( AVLNode *leftNode = node->left )
13441367 {
13451368 FATAL_ASSERT( leftNode->parent == node );
1346- FATAL_ASSERT( compare_nodes( leftNode, node ) == eir::eCompResult::LEFT_LESS );
1369+ FATAL_ASSERT( dispatcherType::CompareNodes( leftNode, node ) == eir::eCompResult::LEFT_LESS );
13471370 }
13481371
13491372 if ( AVLNode *rightNode = node->right )
13501373 {
13511374 FATAL_ASSERT( rightNode->parent == node );
1352- FATAL_ASSERT( compare_nodes( node, rightNode ) == eir::eCompResult::LEFT_LESS );
1375+ FATAL_ASSERT( dispatcherType::CompareNodes( node, rightNode ) == eir::eCompResult::LEFT_LESS );
13531376 }
13541377
13551378 // TODO: verify the height.
@@ -1356,7 +1379,6 @@
13561379 });
13571380 }
13581381
1359-
13601382 private:
13611383 AVLNode *root;
13621384 };
--- common/sdk/Allocation.h (revision 441)
+++ common/sdk/Allocation.h (revision 442)
@@ -21,7 +21,7 @@
2121 namespace eir
2222 {
2323
24-// Friendship resistant replacement for std::constructible_from (it is buggy as shit).
24+// Friendship resistant replacement for std::constructible_from (it is buggy as shit, woof meow).
2525 template <typename T, typename... cArgTypes>
2626 concept constructible_from =
2727 requires ( cArgTypes&&... cArgs ) { new (nullptr) T( std::forward <cArgTypes> ( cArgs )... ); };
@@ -28,9 +28,7 @@
2828
2929 template <typename T, typename... cArgTypes>
3030 concept nothrow_constructible_from =
31- // Unfortunately I have no idea how to implement it without compiler constructs...
32- // This is subject to friend-boundary restrictions so this implementation is buggy in rare cases.
33- std::is_nothrow_constructible <T, cArgTypes...>::value;
31+ requires ( cArgTypes&&... cArgs ) { { new (nullptr) T( std::forward <cArgTypes> ( cArgs )... ) } noexcept; };
3432
3533 template <typename T>
3634 concept trivially_moveable =
--- common/sdk/Map.h (revision 441)
+++ common/sdk/Map.h (revision 442)
@@ -33,6 +33,8 @@
3333 namespace eir
3434 {
3535
36+typedef GenericDefaultComparator MapDefaultComparator;
37+
3638 #define MAP_TEMPLINST \
3739 template <typename keyType, typename valueType, MemoryAllocator allocatorType, CompareCompatibleComparator <keyType, keyType> comparatorType = MapDefaultComparator, typename exceptMan = eir::DefaultExceptionManager>
3840 #define MAP_TEMPLARGS \
@@ -61,28 +63,35 @@
6163 inline Node& operator = ( Node&& right ) = delete;
6264
6365 // The public access stuff.
64- inline const keyType& GetKey( void ) const
66+ inline const keyType& GetKey( void ) const noexcept
6567 {
6668 return this->key;
6769 }
6870
69- inline valueType& GetValue( void )
71+ inline valueType& GetValue( void ) noexcept
7072 {
7173 return this->value;
7274 }
7375
74- inline const valueType& GetValue( void ) const
76+ inline const valueType& GetValue( void ) const noexcept
7577 {
7678 return this->value;
7779 }
7880
79- template <typename comparatorType>
81+ template <CompareCompatibleComparator <keyType, keyType> comparatorType>
8082 struct avlKeyNodeDispatcher
8183 {
82- template <typename subFirstKeyType, typename subSecondKeyType>
83- static AINLINE eCompResult compare_keys( const subFirstKeyType& left, const subSecondKeyType& right ) noexcept(noexcept(comparatorType::compare_values( left, right)))
84+ template <typename subFirstKeyType, typename subSecondKeyType> requires ( CompareCompatibleComparator <comparatorType, subFirstKeyType, subSecondKeyType> )
85+ static AINLINE eCompResult compare_keys( const subFirstKeyType& left, const subSecondKeyType& right ) noexcept(NothrowCompareCompatibleComparator <comparatorType, subFirstKeyType, subSecondKeyType>)
8486 {
85- return ( comparatorType::compare_values( left, right ) );
87+ if constexpr ( CompareCompatibleRegularComparator <comparatorType, subFirstKeyType, subSecondKeyType> )
88+ {
89+ return ( comparatorType::compare_values( left, right ) );
90+ }
91+ else
92+ {
93+ return flip_comp_result( comparatorType::compare_values( right, left ) );
94+ }
8695 }
8796
8897 static inline eCompResult CompareNodes( const AVLNode *left, const AVLNode *right ) noexcept(std::is_nothrow_invocable <decltype(compare_keys <keyType, keyType>), keyType, keyType>::value)
@@ -125,8 +134,6 @@
125134 };
126135
127136 } // namespace MapUtils
128-
129-typedef GenericDefaultComparator MapDefaultComparator;
130137
131138 MAP_TEMPLINST
132139 struct Map
@@ -139,7 +146,9 @@
139146
140147 typedef MapUtils::Node <keyType, valueType> Node;
141148
142- inline Map( void ) noexcept
149+ inline Map( void )
150+ noexcept(nothrow_constructible_from <allocatorType>)
151+ requires ( constructible_from <allocatorType> )
143152 {
144153 // Really nothing to do, I swear!
145154 return;
@@ -234,8 +243,10 @@
234243 }
235244
236245 public:
237- template <typename... Args>
238- inline Map( constr_with_alloc _, Args... allocArgs ) : data( std::tuple( MapAVLTree() ), std::tuple( std::forward <Args> ( allocArgs )... ) )
246+ template <typename... Args> requires ( constructible_from <allocatorType, Args...> )
247+ inline Map( constr_with_alloc _, Args&&... allocArgs )
248+ noexcept(nothrow_constructible_from <allocatorType, Args...>)
249+ : data( std::tuple( MapAVLTree() ), std::tuple( std::forward <Args> ( allocArgs )... ) )
239250 {
240251 return;
241252 }
@@ -349,7 +360,7 @@
349360
350361 // Removes a specific node that was previously found.
351362 // The code must make sure that the node really belongs to this tree.
352- inline void RemoveNode( Node *theNode )
363+ inline void RemoveNode( Node *theNode ) noexcept
353364 {
354365 this->data.avlKeyTree.RemoveByNodeFast( &theNode->sortedByKeyNode );
355366
@@ -358,7 +369,7 @@
358369
359370 // Erases any Node by key.
360371 template <typename queryType> requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> )
361- inline void RemoveByKey( const queryType& key )
372+ inline void RemoveByKey( const queryType& key ) noexcept(NothrowCompareCompatibleComparator <comparatorType, keyType, queryType>)
362373 {
363374 AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key );
364375
@@ -395,7 +406,7 @@
395406 }
396407
397408 // Returns the minimum key of this map.
398- inline Node* GetMinimumByKey( void )
409+ inline Node* GetMinimumByKey( void ) noexcept
399410 {
400411 if ( AVLNode *avlExistingNode = this->data.avlKeyTree.GetSmallestNode() )
401412 {
@@ -405,7 +416,7 @@
405416 return nullptr;
406417 }
407418
408- inline const Node* GetMinimumByKey( void ) const
419+ inline const Node* GetMinimumByKey( void ) const noexcept
409420 {
410421 if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.GetSmallestNode() )
411422 {
@@ -416,7 +427,7 @@
416427 }
417428
418429 // Returns the maximum key of this map.
419- inline Node* GetMaximumByKey( void )
430+ inline Node* GetMaximumByKey( void ) noexcept
420431 {
421432 if ( AVLNode *avlExistingNode = this->data.avlKeyTree.GetBiggestNode() )
422433 {
@@ -426,7 +437,7 @@
426437 return nullptr;
427438 }
428439
429- inline const Node* GetMaximumByKey( void ) const
440+ inline const Node* GetMaximumByKey( void ) const noexcept
430441 {
431442 if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.GetBiggestNode() )
432443 {
@@ -437,7 +448,7 @@
437448 }
438449
439450 template <typename queryType> requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> )
440- inline Node* Find( const queryType& key )
451+ inline Node* Find( const queryType& key ) noexcept(NothrowCompareCompatibleComparator <comparatorType, keyType, queryType> )
441452 {
442453 if ( AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key ) )
443454 {
@@ -448,7 +459,7 @@
448459 }
449460
450461 template <typename queryType> requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> )
451- inline const Node* Find( const queryType& key ) const
462+ inline const Node* Find( const queryType& key ) const noexcept(NothrowCompareCompatibleComparator <comparatorType, keyType, queryType> )
452463 {
453464 if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key ) )
454465 {
@@ -459,11 +470,11 @@
459470 }
460471
461472 // Special finding function that uses a comparison function instead of mere "is_less_than".
462- template <typename comparisonCallbackType>
463- inline Node* FindByCriteria( const comparisonCallbackType& cb )
473+ template <typename comparisonCallbackType> requires ( std::is_invocable_r <eCompResult, comparisonCallbackType, Node*>::value )
474+ inline Node* FindByCriteria( const comparisonCallbackType& cb ) noexcept(std::is_nothrow_invocable_r <eCompResult, comparisonCallbackType, Node*>::value)
464475 {
465476 if ( AVLNode *avlExistingNode = this->data.avlKeyTree.FindAnyNodeByCriteria(
466- [&]( AVLNode *left )
477+ [&]( AVLNode *left ) -> eCompResult
467478 {
468479 Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
469480
@@ -476,11 +487,11 @@
476487 return nullptr;
477488 }
478489
479- template <typename comparisonCallbackType>
480- inline const Node* FindByCriteria( const comparisonCallbackType& cb ) const
490+ template <typename comparisonCallbackType> requires ( std::is_invocable_r <eCompResult, comparisonCallbackType, const Node*>::value )
491+ inline const Node* FindByCriteria( const comparisonCallbackType& cb ) const noexcept(std::is_nothrow_invocable_r <eCompResult, comparisonCallbackType, const Node*>::value)
481492 {
482493 if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.FindAnyNodeByCriteria(
483- [&]( const AVLNode *left )
494+ [&]( const AVLNode *left ) -> eCompResult
484495 {
485496 const Node *leftNode = AVL_GETITEM( constNode, left, sortedByKeyNode );
486497
@@ -493,11 +504,11 @@
493504 return nullptr;
494505 }
495506
496- template <typename comparisonCallbackType>
497- inline Node* FindMinimumByCriteria( const comparisonCallbackType& cb )
507+ template <typename comparisonCallbackType> requires ( std::is_invocable_r <eCompResult, comparisonCallbackType, Node*>::value )
508+ inline Node* FindMinimumByCriteria( const comparisonCallbackType& cb ) noexcept(std::is_nothrow_invocable_r <eCompResult, comparisonCallbackType, Node*>::value)
498509 {
499510 if ( AVLNode *avlExistingNode = this->data.avlKeyTree.FindMinimumNodeByCriteria(
500- [&]( AVLNode *left )
511+ [&]( AVLNode *left ) -> eCompResult
501512 {
502513 Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
503514
@@ -510,11 +521,11 @@
510521 return nullptr;
511522 }
512523
513- template <typename comparisonCallbackType>
514- inline const Node* FindMinimumByCriteria( const comparisonCallbackType& cb ) const
524+ template <typename comparisonCallbackType> requires ( std::is_invocable_r <eCompResult, comparisonCallbackType, const Node*>::value )
525+ inline const Node* FindMinimumByCriteria( const comparisonCallbackType& cb ) const noexcept(std::is_nothrow_invocable_r <eCompResult, comparisonCallbackType, const Node*>::value)
515526 {
516527 if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.FindMinimumNodeByCriteria(
517- [&]( const AVLNode *left )
528+ [&]( const AVLNode *left ) -> eCompResult
518529 {
519530 const Node *leftNode = AVL_GETITEM( constNode, left, sortedByKeyNode );
520531
@@ -527,11 +538,11 @@
527538 return nullptr;
528539 }
529540
530- template <typename comparisonCallbackType>
531- inline Node* FindMaximumByCriteria( const comparisonCallbackType& cb )
541+ template <typename comparisonCallbackType> requires ( std::is_invocable_r <eCompResult, comparisonCallbackType, Node*>::value )
542+ inline Node* FindMaximumByCriteria( const comparisonCallbackType& cb ) noexcept(std::is_nothrow_invocable_r <eCompResult, comparisonCallbackType, Node*>::value)
532543 {
533544 if ( AVLNode *avlExistingNode = this->data.avlKeyTree.FindMaximumNodeByCriteria(
534- [&]( AVLNode *left )
545+ [&]( AVLNode *left ) -> eCompResult
535546 {
536547 Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
537548
@@ -544,11 +555,11 @@
544555 return nullptr;
545556 }
546557
547- template <typename comparisonCallbackType>
548- inline const Node* FindMaximumByCriteria( const comparisonCallbackType& cb ) const
558+ template <typename comparisonCallbackType> requires ( std::is_invocable_r <eCompResult, comparisonCallbackType, const Node*>::value )
559+ inline const Node* FindMaximumByCriteria( const comparisonCallbackType& cb ) const noexcept(std::is_nothrow_invocable_r <eCompResult, comparisonCallbackType, const Node*>::value)
549560 {
550561 if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.FindMaximumNodeByCriteria(
551- [&]( const AVLNode *left )
562+ [&]( const AVLNode *left ) -> eCompResult
552563 {
553564 const Node *leftNode = AVL_GETITEM( constNode, left, sortedByKeyNode );
554565
@@ -562,7 +573,7 @@
562573 }
563574
564575 template <typename queryType> requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> )
565- inline Node* FindJustAbove( const queryType& key )
576+ inline Node* FindJustAbove( const queryType& key ) noexcept(NothrowCompareCompatibleComparator <comparatorType, keyType, queryType>)
566577 {
567578 if ( AVLNode *avlJustAboveNode = this->data.avlKeyTree.GetJustAboveNode( key ) )
568579 {
@@ -572,7 +583,7 @@
572583 }
573584
574585 template <typename queryType> requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> )
575- inline const Node* FindJustAbove( const queryType& key ) const
586+ inline const Node* FindJustAbove( const queryType& key ) const noexcept(NothrowCompareCompatibleComparator <comparatorType, keyType, queryType>)
576587 {
577588 if ( const AVLNode *avlJustAboveNode = this->data.avlKeyTree.GetJustAboveNode( key ) )
578589 {
@@ -582,8 +593,8 @@
582593 }
583594
584595 template <typename queryType>
585- requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> && std::is_default_constructible <valueType>::value )
586- inline valueType FindOrDefault( const queryType& key )
596+ requires ( CompareCompatibleComparator <comparatorType, keyType, queryType> && constructible_from <valueType> )
597+ inline valueType FindOrDefault( const queryType& key ) noexcept(nothrow_constructible_from <valueType> && NothrowCompareCompatibleComparator <comparatorType, keyType, valueType>)
587598 {
588599 if ( auto *findNode = this->Find( key ) )
589600 {
@@ -594,7 +605,7 @@
594605 }
595606
596607 // Returns true if there is nothing inside this Map/the AVL tree.
597- inline bool IsEmpty( void ) const
608+ inline bool IsEmpty( void ) const noexcept
598609 {
599610 return ( this->data.avlKeyTree.GetRootNode() == nullptr );
600611 }
--- common/sdk/Set.h (revision 441)
+++ common/sdk/Set.h (revision 442)
@@ -65,13 +65,20 @@
6565 }
6666
6767 // Helper for AVLTree.
68- template <typename comparatorType>
68+ template <CompareCompatibleComparator <valueType, valueType> comparatorType>
6969 struct avlKeyNodeDispatcher
7070 {
7171 template <typename subFirstValueType, typename subSecondValueType> requires CompareCompatibleComparator <comparatorType, subFirstValueType, subSecondValueType>
72- static AINLINE eCompResult compare_values( const subFirstValueType& left, const subSecondValueType& right ) noexcept(noexcept(comparatorType::compare_values( left, right )))
72+ static AINLINE eCompResult compare_values( const subFirstValueType& left, const subSecondValueType& right ) noexcept(NothrowCompareCompatibleComparator <comparatorType, subFirstValueType, subSecondValueType>)
7373 {
74- return ( comparatorType::compare_values( left, right ) );
74+ if constexpr ( CompareCompatibleRegularComparator <comparatorType, subFirstValueType, subSecondValueType> )
75+ {
76+ return ( comparatorType::compare_values( left, right ) );
77+ }
78+ else
79+ {
80+ return flip_comp_result( comparatorType::compare_values( right, left ) );
81+ }
7582 }
7683
7784 static inline eCompResult CompareNodes( const AVLNode *left, const AVLNode *right ) noexcept(std::is_nothrow_invocable <decltype(compare_values <valueType, valueType>), valueType, valueType>::value)
@@ -121,7 +128,9 @@
121128 // Make templates friends of each-other.
122129 template <typename TWC, MemoryAllocator, CompareCompatibleComparator <TWC, TWC>, typename> friend struct Set;
123130
124- inline Set( void ) noexcept
131+ inline Set( void )
132+ noexcept(nothrow_constructible_from <allocatorType>)
133+ requires ( constructible_from <allocatorType> )
125134 {
126135 // Really nothing to do, I swear!
127136 return;
@@ -200,8 +209,10 @@
200209 }
201210
202211 public:
203- template <typename... Args>
204- inline Set( constr_with_alloc _, Args&&... allocArgs ) : data( std::tuple( SetAVLTree() ), std::tuple( std::forward <Args> ( allocArgs )... ) )
212+ template <typename... Args> requires ( constructible_from <allocatorType, Args...> )
213+ inline Set( constr_with_alloc _, Args&&... allocArgs )
214+ noexcept(nothrow_constructible_from <allocatorType, Args...>)
215+ : data( std::tuple( SetAVLTree() ), std::tuple( std::forward <Args> ( allocArgs )... ) )
205216 {
206217 return;
207218 }
@@ -346,12 +357,14 @@
346357 // Removes a node from visibility, moves the value out of internal structures and returns it to
347358 // the caller. Should be used for final removal, NOT for updates of the key!
348359 inline valueType ExtractNode( const Node *theNode )
360+ noexcept(nothrow_constructible_from <valueType, valueType&&>)
361+ requires ( constructible_from <valueType, valueType&&> )
349362 {
350363 Node *mutableNode = const_cast <Node*> ( theNode );
351364
352365 this->data.avlValueTree.RemoveByNodeFast( &mutableNode->sortedByValueNode );
353366
354- valueType val = std::move( mutableNode->value );
367+ valueType val( std::move( mutableNode->value ) );
355368
356369 dismantle_node( this, mutableNode );
357370
@@ -359,7 +372,7 @@
359372 }
360373
361374 // Enters update-mode for a node by pointer.
362- inline valueType& BeginNodeUpdate( const Node *theNode )
375+ inline valueType& BeginNodeUpdate( const Node *theNode ) noexcept
363376 {
364377 Node *mutableNode = const_cast <Node*> ( theNode );
365378
@@ -369,7 +382,7 @@
369382 }
370383
371384 // Commits an update to a node.
372- inline void EndNodeUpdate( const Node *theNode )
385+ inline void EndNodeUpdate( const Node *theNode ) noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, valueType>)
373386 {
374387 #ifdef _DEBUG
375388 FATAL_ASSERT( this->data.avlValueTree.IsNodeInsideTree( (AVLNode*)&theNode->sortedByValueNode ) == false );
@@ -382,7 +395,7 @@
382395
383396 // Removes a specific node that was previously found.
384397 // The code must make sure that the node really belongs to this tree.
385- inline void RemoveNode( Node *theNode )
398+ inline void RemoveNode( Node *theNode ) noexcept
386399 {
387400 this->data.avlValueTree.RemoveByNodeFast( &theNode->sortedByValueNode );
388401
@@ -390,8 +403,8 @@
390403 }
391404
392405 // Erases any Node by value.
393- template <typename queryType>
394- inline void Remove( const queryType& value )
406+ template <typename queryType> requires ( CompareCompatibleComparator <comparatorType, valueType, queryType> )
407+ inline void Remove( const queryType& value ) noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
395408 {
396409 AVLNode *avlExistingNode = this->data.avlValueTree.FindNode( value );
397410
@@ -427,7 +440,7 @@
427440 return count;
428441 }
429442
430- inline Node* GetAny( void )
443+ inline Node* GetAny( void ) noexcept
431444 {
432445 if ( AVLNode *avlAnyNode = this->data.avlValueTree.GetRootNode() )
433446 {
@@ -437,12 +450,12 @@
437450 return nullptr;
438451 }
439452
440- inline const Node* GetAny( void ) const
453+ inline const Node* GetAny( void ) const noexcept
441454 {
442455 return const_cast <Set*> ( this )->GetAny();
443456 }
444457
445- inline Node* GetMinimum( void )
458+ inline Node* GetMinimum( void ) noexcept
446459 {
447460 if ( AVLNode *avlMinimumNode = this->data.avlValueTree.GetSmallestNode() )
448461 {
@@ -452,12 +465,12 @@
452465 return nullptr;
453466 }
454467
455- inline const Node* GetMinimum( void ) const
468+ inline const Node* GetMinimum( void ) const noexcept
456469 {
457470 return const_cast <Set*> ( this )->GetMinimum();
458471 }
459472
460- inline Node* GetMaximum( void )
473+ inline Node* GetMaximum( void ) noexcept
461474 {
462475 if ( AVLNode *avlMaximumNode = this->data.avlValueTree.GetBiggestNode() )
463476 {
@@ -467,13 +480,13 @@
467480 return nullptr;
468481 }
469482
470- inline const Node* GetMaximum( void ) const
483+ inline const Node* GetMaximum( void ) const noexcept
471484 {
472485 return const_cast <Set*> ( this )->GetMaximum();
473486 }
474487
475488 template <typename queryType> requires CompareCompatibleComparator <comparatorType, valueType, queryType>
476- inline Node* Find( const queryType& value )
489+ inline Node* Find( const queryType& value ) noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
477490 {
478491 if ( AVLNode *avlExistingNode = this->data.avlValueTree.FindNode( value ) )
479492 {
@@ -484,13 +497,13 @@
484497 }
485498
486499 template <typename queryType> requires CompareCompatibleComparator <comparatorType, valueType, queryType>
487- inline const Node* Find( const queryType& value ) const
500+ inline const Node* Find( const queryType& value ) const noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
488501 {
489502 return const_cast <Set*> ( this )->Find( value );
490503 }
491504
492- template <typename queryType>
493- inline Node* FindJustAboveOrEqual( const queryType& value )
505+ template <typename queryType> requires CompareCompatibleComparator <comparatorType, valueType, queryType>
506+ inline Node* FindJustAboveOrEqual( const queryType& value ) noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
494507 {
495508 if ( AVLNode *avlAboveOrEqual = this->data.avlValueTree.GetJustAboveOrEqualNode( value ) )
496509 {
@@ -500,14 +513,14 @@
500513 return nullptr;
501514 }
502515
503- template <typename queryType>
504- inline const Node* FindJustAboveOrEqual( const queryType& value ) const
516+ template <typename queryType> requires CompareCompatibleComparator <comparatorType, valueType, queryType>
517+ inline const Node* FindJustAboveOrEqual( const queryType& value ) const noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
505518 {
506519 return const_cast <Set*> ( this )->FindJustAboveOrEqual( value );
507520 }
508521
509- template <typename queryType>
510- inline Node* FindJustAbove( const queryType& value )
522+ template <typename queryType> requires CompareCompatibleComparator <comparatorType, valueType, queryType>
523+ inline Node* FindJustAbove( const queryType& value ) noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
511524 {
512525 if ( AVLNode *avlJustAbove = this->data.avlValueTree.GetJustAboveNode( value ) )
513526 {
@@ -517,14 +530,14 @@
517530 return nullptr;
518531 }
519532
520- template <typename queryType>
521- inline const Node* FindJustAbove( const queryType& value ) const
533+ template <typename queryType> requires CompareCompatibleComparator <comparatorType, valueType, queryType>
534+ inline const Node* FindJustAbove( const queryType& value ) const noexcept(NothrowCompareCompatibleComparator <comparatorType, valueType, queryType>)
522535 {
523536 return const_cast <Set*> ( this )->FindJustAbove( value );
524537 }
525538
526539 // Returns true if there is nothing inside this Set/the AVL tree.
527- inline bool IsEmpty( void ) const
540+ inline bool IsEmpty( void ) const noexcept
528541 {
529542 return ( this->data.avlValueTree.GetRootNode() == nullptr );
530543 }
--- common/sdk/avlsetmaputil.h (revision 441)
+++ common/sdk/avlsetmaputil.h (revision 442)
@@ -16,6 +16,8 @@
1616 #include "MacroUtils.h"
1717 #include "AVLTree.h"
1818
19+#include <type_traits>
20+
1921 #define MAKE_SETMAP_ITERATOR( iteratorName, hostType, nodeType, nodeRedirNode, treeMembPath, avlTreeType ) \
2022 struct iteratorName \
2123 { \
@@ -59,8 +61,29 @@
5961 {
6062
6163 template <typename comparatorType, typename LT, typename RT>
62-concept CompareCompatibleComparator = requires ( LT l, RT r ) { (eCompResult)comparatorType::compare_values( l, r ); };
64+concept CompareCompatibleRegularComparator =
65+ requires ( const LT& L, const RT& R ) { { comparatorType::compare_values( L, R ) } -> std::same_as <eCompResult>; };
66+template <typename comparatorType, typename LT, typename RT>
67+concept CompareCompatibleInverseComparator =
68+ requires ( const LT& R, const RT& L ) { { (eCompResult)comparatorType::compare_values( L, R ) } -> std::same_as <eCompResult>; };
6369
70+template <typename comparatorType, typename LT, typename RT>
71+concept CompareCompatibleComparator =
72+ CompareCompatibleRegularComparator <comparatorType, LT, RT> ||
73+ CompareCompatibleInverseComparator <comparatorType, LT, RT>;
74+
75+template <typename comparatorType, typename LT, typename RT>
76+concept NothrowCompareCompatibleRegularComparator =
77+ requires ( const LT& L, const RT& R ) { { comparatorType::compare_values( L, R ) } noexcept -> std::same_as <eCompResult>; };
78+template <typename comparatorType, typename LT, typename RT>
79+concept NothrowCompareCompatibleInverseComparator =
80+ requires ( const LT& R, const RT& L ) { { comparatorType::compare_values( L, R ) } noexcept -> std::same_as <eCompResult>; };
81+
82+template <typename comparatorType, typename LT, typename RT>
83+concept NothrowCompareCompatibleComparator =
84+ ( CompareCompatibleRegularComparator <comparatorType, LT, RT> == false || NothrowCompareCompatibleRegularComparator <comparatorType, LT, RT> ) &&
85+ ( CompareCompatibleInverseComparator <comparatorType, LT, RT> == false || NothrowCompareCompatibleInverseComparator <comparatorType, LT, RT> );
86+
6487 // Default comparator for objects inside the Map/Set.
6588 struct GenericDefaultComparator
6689 {
--- unittests/src/map.cpp (revision 441)
+++ unittests/src/map.cpp (revision 442)
@@ -75,6 +75,57 @@
7575 }
7676 printf( "ok.\n" );
7777
78+ printf( "testing map commutative comparator..." );
79+ {
80+ struct spctype
81+ {
82+ explicit spctype( int v ) noexcept : myval( v ) {}
83+
84+ int myval;
85+ };
86+
87+ struct left_commutative_comparator
88+ {
89+ static AINLINE eir::eCompResult compare_values( int L, int R ) noexcept
90+ {
91+ return eir::DefaultValueCompare( L, R );
92+ }
93+
94+ static AINLINE eir::eCompResult compare_values( const spctype& L, int R ) noexcept
95+ {
96+ return eir::DefaultValueCompare( L.myval, R );
97+ }
98+
99+ static AINLINE eir::eCompResult compare_values( const spctype& L, const spctype& R ) noexcept
100+ {
101+ return eir::DefaultValueCompare( L.myval, R.myval );
102+ }
103+ };
104+
105+ // One way.
106+ {
107+ eir::Map <int, int, CRTHeapAllocator, left_commutative_comparator> set;
108+
109+ set.Set( 33, 1 );
110+ set.Set( 99, 1 );
111+
112+ assert( set.Find( 33 ) != nullptr );
113+ assert( set.Find( spctype( 33 ) ) != nullptr );
114+ }
115+
116+ // Other way.
117+ {
118+ eir::Map <spctype, int, CRTHeapAllocator, left_commutative_comparator> set;
119+
120+ set.Set( spctype( 33 ), 1 );
121+ set.Set( spctype( 99 ), 1 );
122+
123+ assert( set.Find( 33 ) != nullptr );
124+ assert( set.Find( spctype( 33 ) ) != nullptr );
125+ }
126+ }
127+ printf( "ok.\n" );
128+
78129 printf( "testing map node walking..." );
79130 {
80131 MapWithHeap map;
--- unittests/src/set.cpp (revision 441)
+++ unittests/src/set.cpp (revision 442)
@@ -228,6 +228,57 @@
228228 }
229229 printf( "ok.\n" );
230230
231+ printf( "testing set comparator commutativity..." );
232+ {
233+ struct spctype
234+ {
235+ explicit spctype( int v ) noexcept : myval( v ) {}
236+
237+ int myval;
238+ };
239+
240+ struct left_commutative_comparator
241+ {
242+ static AINLINE eir::eCompResult compare_values( int L, int R ) noexcept
243+ {
244+ return eir::DefaultValueCompare( L, R );
245+ }
246+
247+ static AINLINE eir::eCompResult compare_values( const spctype& L, int R ) noexcept
248+ {
249+ return eir::DefaultValueCompare( L.myval, R );
250+ }
251+
252+ static AINLINE eir::eCompResult compare_values( const spctype& L, const spctype& R ) noexcept
253+ {
254+ return eir::DefaultValueCompare( L.myval, R.myval );
255+ }
256+ };
257+
258+ // One way.
259+ {
260+ eir::Set <int, CRTHeapAllocator, left_commutative_comparator> set;
261+
262+ set.Insert( 33 );
263+ set.Insert( 99 );
264+
265+ assert( set.Find( 33 ) != nullptr );
266+ assert( set.Find( spctype( 33 ) ) != nullptr );
267+ }
268+
269+ // Other way.
270+ {
271+ eir::Set <spctype, CRTHeapAllocator, left_commutative_comparator> set;
272+
273+ set.Insert( spctype( 33 ) );
274+ set.Insert( spctype( 99 ) );
275+
276+ assert( set.Find( 33 ) != nullptr );
277+ assert( set.Find( spctype( 33 ) ) != nullptr );
278+ }
279+ }
280+ printf( "ok.\n" );
281+
231282 printf( "testing set extract node..." );
232283 {
233284 struct extractible
Show on old repository browser