-
Notifications
You must be signed in to change notification settings - Fork 44
Description
-
Complexity - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/implementation/complexity.html )
In "Table 1.15. Time Complexity of Addition",interval set/separate interval set/split interval set/interval map/split interval map += interval_sets/interval_maps's time complexity isO(m log(n+m)), but this time complexity should be at leastinterval set/separate interval set/split interval set/interval map/split interval map += T::segment_type's time complexity (O(n)). Example: theinterval_sets/interval_mapscontains only one big interval (whose type isT::segment_type), and this interval makesinterval set/separate interval set/split interval set/interval map/split interval map += T::segment_type's time complexityO(n). -
Addition - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/addition.html )
In "Table 1.23. Time Complexity for inplace Addition on interval containers",interval_set/separate_interval_set += interval_sets,split_interval_set += interval_setsandinterval_maps += interval_mapshave wrong time complexity. -
Subtraction - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/subtraction.html )
In "Table 1.26. Time Complexity for inplace Subtraction on interval containers",interval_sets -= interval setsandinterval_maps -= interval sets/interval mapshave wrong time complexity. -
Insertion - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/insertion.html )
In "Table 1.29. Time Complexity for inplace insertion on interval containers",insert(interval_set/separate_interval_set, interval sets),insert(split_interval_set, interval sets)andinsert(interval_maps, interval maps)have wrong time complexity.. -
Intersection - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/intersection.html )
In "Table 1.36. Time Complexity for inplace intersection on interval containers",interval_sets &= interval setsandinterval_maps &= interval sets/interval mapshave wrong time complexity. -
Symmetric Difference - 1.84.0 (https://www.boost.org/doc/libs/1_84_0/libs/icl/doc/html/boost_icl/function_reference/symmetric_difference.html )
In "Table 1.39. Time Complexity for inplace symmetric difference on interval containers",interval_sets ^= interval setsandinterval_maps ^= interval sets/interval mapshave wrong time complexity.