Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Simplify isfilled #22

Open
Whebon opened this issue May 6, 2024 · 0 comments
Open

Simplify isfilled #22

Whebon opened this issue May 6, 2024 · 0 comments

Comments

@Whebon
Copy link
Contributor

Whebon commented May 6, 2024

Current implementation

#HerbCore
"""
    isfilled(node::AbstractRuleNode)::Bool

Returns whether the [`AbstractRuleNode`] holds a single rule.
Holes are considered to be "filled" iff their domain size is exactly 1.
"""
isfilled(rn::RuleNode)::Bool = true
isfilled(hole::UniformHole)::Bool = (sum(hole.domain) == 1)
isfilled(hole::Hole)::Bool = (sum(hole.domain) == 1)

#HerbConstaints
function HerbCore.isfilled(hole::StateHole)::Bool
    return size(hole.domain) == 1
end

Target implementation

#HerbCore
"""
    isfilled(node::AbstractRuleNode)::Bool

Returns whether the [`AbstractRuleNode`] holds a single rule.
Holes are considered to be "filled" iff their domain size is exactly 1.
"""
isfilled(rn::RuleNode)::Bool = true
isfilled(hole::AbstractHole)::Bool = false

#HerbConstaints
function HerbCore.isfilled(hole::StateHole)::Bool
    return size(hole.domain) == 1
end

The GenericSolver automatically replaces filled holes with a rulenode, so UniformHoles and Holes will in practice always be not filled. Propagators often check this property by calling isfilled function, which currently takes $O(n)$ (for BitVectors).

We can exploit this by redefining isfilled(hole::AbstractHole)::Bool = false. However, this might cause bugs if the implementation of the GenericSolver changes.

For StateHoles, isfilled must remain the way it is, because state holes are not getting replaced by a rule node on fill. Also, for a statehole, size(hole.domain) is $O(1)$.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant