Stay organized with collections Save and categorize content based on your preferences.

C++ Reference: class InclusionDetector

Note: This documentation is automatically generated.

Method
AddPotentialSet

Return type: void

Arguments: int index

AddPotentialSubset

Return type: void

Arguments: int index

Adds a candidate set to consider for the next DetectInclusions() call. The argument is an index that will only be used via storage_[index] to get the content of the candidate set. Note that set with no element are just ignored and will never be returned as part of an inclusion.

AddPotentialSuperset

Return type: void

Arguments: int index

DetectInclusions

Return type: void

Arguments: const std::function<void(int subset, int superset)>& process

Finds all subset included in a superset and call "process" on each of the detected inclusion. The std::function argument corresponds to indices passed to the Add*() calls. The order of detection will be by increasing superset size. For superset with the same size, the order will be deterministic but not specified. And similarly, for a given superset, the order of the included subsets is deterministic but not specified. Note that only the candidate marked as such can be a subset/superset. For the candidate than can be both and are duplicates (i.e. same set), only one pair will be returned. We will also never return identity inclusion and we always have subset != superset.

InclusionDetector

Return type: explicit

Arguments: const Storage& storage

IncreaseWorkDone

Return type: void

Arguments: uint64_t increase

The algorithm here can detect many small set included in a big set while only scanning the superset once. So if we do scan the superset in the process function, we can do a lot more work. This is here to reuse the deterministic limit mechanism.

IsInSuperset

Return type: const std::vector<bool>

Function that should only be used from within "process()". Returns the bitset corresponsing to the elements of the current superset passed to the process() function.

num_potential_subsets

Return type: int

Stats.

num_potential_supersets

Return type: int

Reset

Return type: void

Resets the class to an empty state.

SetWorkLimit

Return type: void

Arguments: uint64_t work_limit

By default we will detect all inclusions. It is possible to make sure we don't do more than O(work_limit) operations and eventually abort early by setting this. Note that we don't reset it on Reset(). This is needed, because for m candidates of size n, we can have O(m ^ 2) inclusions, each requiring O(n) work to check.

Stop

Return type: void

StopProcessingCurrentSubset

Return type: void

Function that should only be used from within "process()". Stop will abort the current search. The other two will cause the corresponding candidate set to never appear in any future inclusion.

StopProcessingCurrentSuperset

Return type: void

work_done

Return type: uint64_t