CombinatoryFilters

Functional filter abstraction for creating, applying, mapping, and reducing combinatory filter structures

Installation

dotnet add package ExtremeAndy.CombinatoryFilters

Usage

1. Define your filter interface(s) and/or class(es). Here's an example of a simple filter which checks whether an integer is between UpperBound and LowerBound.

publicclassNumericRangeFilter:Filter<int>{publicNumericRangeFilter(intlowerBound,intupperBound){LowerBound=lowerBound;UpperBound=upperBound;}publicintLowerBound{get;}publicintUpperBound{get;}publicoverrideboolIsMatch(intitem)=>LowerBound<=item&&item<=UpperBound;}

2. Optionally implement IEquatable<TFilter> on your filter class. If this is not done, then calling .Equals() on an IFilterNode in your filter tree will default to value/reference equality when comparing your leaf filters.

   Example code

   publicclassNumericRangeFilter:Filter<int>,IEquatable<NumericRangeFilter>{publicNumericRangeFilter(intlowerBound,intupperBound){LowerBound=lowerBound;UpperBound=upperBound;}publicintLowerBound{get;}publicintUpperBound{get;}publicoverrideboolIsMatch(intitem)=>LowerBound<=item&&item<=UpperBound;publicboolEquals(NumericRangeFilterother){if(otherisnull){returnfalse;}returnLowerBound==other.LowerBound&&UpperBound==other.UpperBound;}publicoverrideboolEquals(objectobj)=>objisNumericRangeFilterother&&Equals(other);publicoverrideintGetHashCode(){unchecked{return(LowerBound.GetHashCode()*397)^UpperBound.GetHashCode();}}}

3. Optionally implement IComparable<TFilter> on your filter class. This will allow the Sort() method to be used without passing an explicit IComparer<TFilter>.

4. Create an instance of your filter and apply it to some values

varfilter=newNumericRangeFilter(5,10);varfilterNode=filter.ToLeafFilterNode();varvalues=new[]{1,3,5,9,11};varexpectedFilteredValues=new[]{5,9};varfilterPredicate=filterNode.GetPredicate<NumericRangeFilter,int>();varfilteredValues=values.Where(filterPredicate);Assert.Equal(expectedFilteredValues,filteredValues);

Complex filters

You can assemble arbitrarily complex filters as follows:

varfilter5To10=newNumericRangeFilter(5,10);varfilter8To15=newNumericRangeFilter(8,15);varfilter5To10Or8To15=newCombinationFilterNode<NumericRangeFilter>(new[]{filter5To10,filter8To15},CombinationOperator.Any);varfilter9To12=newNumericRangeFilter(9,12);varfilter=newCombinationFilterNode<NumericRangeFilter>(newIFilterNode<NumericRangeFilter>[]{filter5To10Or8To15,filter9To12.ToLeafFilterNode()},CombinationOperator.All);

Inversion

Any filter can be inverted using .Invert().

Testing a single value

You can test a single value as follows:

varfilter5To10=newNumericRangeFilter(5,10);varfilter8To15=newNumericRangeFilter(8,15);varcombinationFilter=newCombinationFilterNode<NumericRangeFilter>(new[]{filter5To10,filter8To15});varisMatch=combinationFilter.IsMatch(7);

However, IsMatch causes an allocation and is not recommended for testing many items. Instead, use filter.GetPredicate:

varfilter5To10=newNumericRangeFilter(5,10);varfilter8To15=newNumericRangeFilter(8,15);varcombinationFilter=newCombinationFilterNode<NumericRangeFilter>(new[]{filter5To10,filter8To15});varfilterPredicate=combinationFilter.GetPredicate<NumericRangeFilter,int>();varlotsOfIntegers=Enumerable.Range(0,1000000);varmatches=lotsOfIntegers.Where(filterPredicate);

Preserving ordering of filters

CombinationFilterNode stores Nodes in the same order they are passed in. Operations such as Collapse should still preserve the order of Nodes, but this is not well tested.

Advanced usage

IFilterNode<> supports Map, Match and Aggregate for mapping and reducing filters.

Map usage

In this example, we reduce the range of the leaf node filters by increasing the lower bound by 1 and decreasing the upper bound by 1. The structure of all the All, Any and Invert operations remains unchanged.

varshortenedFilters=filter.Map(f =>{varnewLowerBound=f.LowerBound+1;varnewUpperBound=f.UpperBound-1;returnnewNumericRangeFilter(newLowerBound,newUpperBound);});

Aggregate usage

In this example, we want to compute the length of the longest filter interval, or infinity if any filter is inverted.

varlongestIntervalLength=filter.Aggregate<double>((lengths,_)=>lengths.Max(),
length =>double.PositiveInfinity,
f =>f.Filter.UpperBound-f.Filter.LowerBound);

GetPartial usage

GetPartial provides a way to compute a partial filter, which is a kind of subset of a filter. When applied, a partial filter is guaranteed to return a superset of the result that the original filter would have returned when applied. This is a special case of the Relax operation, where leaf nodes are maximally relaxed (i.e. replaced with True) if the predicate is satisfied.

This is useful for performing pre-filtering on an incomplete dataset that doesn't (yet) contain all the information required to apply the final filter.

This is normally quite a trivial problem, but when there are InvertedFilters and CombinationFilters in the mix, computing the minimal partial filter is not intuitive or easy to demonstrate.

Here is a contrived example (note: this doesn't do anything useful, just demonstrates usage):

// All the numbers from -5 to 10, excluding numbers from 2 to 6varfilter=newCombinationFilterNode<NumericRangeFilter>(newIFilterNode<NumericRangeFilter>[]{newNumericRangeFilter(-5,10).ToLeafFilterNode(),newNumericRangeFilter(2,6).ToLeafFilterNode().Invert()},CombinationOperator.All);// Exclude filters with negative valuesvarpartialFilter=filter.GetPartial(f =>f.LowerBound>=0);// Initially we only have positive numbersvarpositiveValues=new[]{1,3,5,7,12};varprefilteredValues=positiveValues.Where(partialFilter.GetPredicate<NumericRangeFilter,int>()).ToList();Assert.Equal(new[]{1,7,12},prefilteredValues);// Now we include some additional valuesvaradditionalValues=new[]{-7,-4,11};varcombinedValues=prefilteredValues.Concat(additionalValues);// Finally we apply our 'full' filtervarfinalValues=combinedValues.Where(filter.GetPredicate<NumericRangeFilter,int>());Assert.Equal(new[]{1,7,-4},finalValues);

Relax usage

Relax provides a way to relax a filter by relaxing its leaf nodes.

Example TBD.