I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find longest prefix (lets call it P) of QUERY which is a member of RULES for which F(P,QUERY) returns true?
That was very generic definition of a problem. The reality is that I have a huge tree of objects. Each object has one of predefined types. I want to have a way to define different views on that tree. Each view is set of rules describing which types of objects are (in)visible in subtree subtree described by that rule. Basically a rule is a pair - path/prefix in tree and map from type to boolean. An object of type T is visible via given view iff the longest rule that has path that is prefix of that objects path has true as an entry for type T.
An example:
Types are {A,B,C}.
Tree contains those objects: /A1, /A2, /A1/B1, /A1/C1, /A1/B1/C1, /A2/B1, /A2/C1
View is defined by those rules: {/; C=>true, A=>true}, {/A1/B1; C=>true}, {/A1; C=>false}, {/A2; B=>true,C=>true}
Objects visible via that view: /A1, /A2, /A1/B1/C1, /A2/B1, /A2/C1
Right now I'm solving this by storing all rules for view in (hash)map - key is path and value is set of rules. When I've checking given object, I start from its full path and check in a loop each of is prefixes by removing top path component and looking it up in (hash)map. When it contains entry for that prefix I check if it contains entry for the type of object - if it does I return it as value of visibility. Otherwise I continue with next shorter prefix. If no rule was found I decide that object is not visible.