superset_elimination.go

package rewriting

import (
	"exprparser/expr"
)

// eliminateSupersets Eliminates supersets from the expression tree
//
// Given the expression:
// (A || B) && (A || B || C) && (A || C)
//
// We want to produce:
// (A || B) && (A || C)
//
// This is because if A || B is true then A || B || C MUST be true.
// If A || B is false then A || B || C is not even checked.
// This is because AND short-circuits logic on false values.
// More specifically: they have identical truth tables.
//
// This same logic also applies to the disjunction of conjunctions:
// Given the expression:
// (A && B) || (A && B && C) || (A && C)
//
// We want to produce:
// (A && B) || (A && C)
//
// This is because if A && B is false then A && B && C MUST be false.
// If A && B is true then A && B && C is not even checked.
// This is because OR short-circuits logic on true values.
// More specifically: they have identical truth tables.
//
// The algorithm works by walking the list of disjunctions
// and removing any that are supersets of the examined disjunction
//
// This is done by walking two pointers along the set of disjunctions and comparing them.
// This means that as you walk along the set the search space gets smaller.
// This results in a complexity of O(n^2) but actual search space is a bit less: (n^2 - n)/2
// So for 8 disjunctions the search space is 28 checks versus 64
// So for 80 disjunctions the search space is 3160 checks versus 6400
//
// Example 1:
// Step 1:
//        ↓1          ↓2
// Check: (A || B) && (A || B || C) && (A || C)
// Result: ↓2 is a superset of ↓1. So remove ↓2.
//
//        ↓1          ↓2
// Check: (A || B) && (A || C)
// Result: ↓2 is not superset of ↓1. So do nothing
//
//        ↓1                   ↓2
// Check: (A || B) && (A || C)
// Result: ↓2 is at the end. Advance ↓1 and reset ↓2 to one past ↓1.
//
//                    ↓1       ↓2
// Check: (A || B) && (A || C)
// Result: ↓2 is at the end. Advance ↓1 and reset ↓2 to one past ↓1.
//
//                             ↓1↓2
// Check: (A || B) && (A || C)
// Result: ↓1 is at the end. We're done.
//
// Example 2:
// Step 1:
//        ↓1               ↓2
// Check: (A || B || C) && (A || B) && (A || C)
// Result: ↓1 is a superset of ↓2. So remove ↓1.
//
//        ↓1          ↓2
// Check: (A || B) && (A || C)
// Result: ↓2 is not superset of ↓1. So do nothing
//
//        ↓1                   ↓2
// Check: (A || B) && (A || C)
// Result: ↓2 is at the end. Advance ↓1 and reset ↓2 to one past ↓1.
//
//                    ↓1       ↓2
// Check: (A || B) && (A || C)
// Result: ↓2 is at the end. Advance ↓1 and reset ↓2 to one past ↓1.
//
//                             ↓1↓2
// Check: (A || B) && (A || C)
// Result: ↓1 is at the end. We're done.
//
// @param Expr $expr
// @return Expr
///
func eliminateSupersets(e *expr.Node) *expr.Node {
	switch e.Type {
	case expr.TypeAnd:
		return eliminateSupersetsImpl(e, expr.TypeAnd, expr.TypeOr)
	case expr.TypeOr:
		return eliminateSupersetsImpl(e, expr.TypeOr, expr.TypeAnd)
	}

	return e
}

func eliminateSupersetsImpl(e *expr.Node, outerType, innerType expr.Type) *expr.Node {
	endIndex := len(e.Children) - 1

	for i := 0; i <= endIndex; i++ {
		// This element was removed so skip checking it
		if e.Children[i] == nil {
			continue
		}

		one := e.Children[i]

		// This is not actually a conjunction / disjunction (based on the parent type) expression so skip it
		if one.Type != innerType {
			continue
		}

		oneSize := len(one.Children)

		// The second pointer is reset and traverses a
		// shrinking subset of the elements from
		// the next position i+1 to endIndex
		for j := i + 1; j <= endIndex; j++ {
			// This element was removed so skip checking it
			if e.Children[j] == nil {
				continue
			}

			two := e.Children[j]

			// This is not actually a conjunction / disjunction (based on the parent type) expression so skip it
			if two.Type != innerType {
				continue
			}

			twoSize := len(two.Children)

			// Count the intersections between $one and $two
			intersections := countIntersections(one, two)

			if intersections == oneSize {
				// two is superset of one, so remove two
				e.Children[j] = nil
			} else if intersections == twoSize {
				// one is superset of two, so remove one
				e.Children[i] = nil

				// go to the next `one` group since we removed the current one group
				break
			}
		}
	}

	return clean(e)
}

// countIntersections Counts common nodes in `a` and `b.
func countIntersections(a, b *expr.Node) int {
	n := 0

	for i := 0; i < len(a.Children); i++ {
		for j := 0; j < len(b.Children); j++ {
			if expr.AreNodesEqual(a.Children[i], b.Children[j]) {
				n++
			}
		}
	}

	return n
}