[FoRK] Data Structures Question

[Andy Armstrong]

On 3 Apr 2007, at 05:33, Reza B'Far wrote:
> However, I purposefully am trying not to treat it as a "logic"  
> question.  I
> want to load n expressions into a structure, such as a tree, that  
> has the
> properties that support the decomposition that I want.   
> Essentially, what I
> want is to explode the boolean (Andy refers to this) but with some  
> added
> constraints... Get all the "anded" terms together in one single  
> expression.
> So, the subexpressions should only have AND's.

That /is/ a sum of products then... If you rewrite your original
expression in SoP form you get

(e1 && e2 && e5) || (e3 && e5) || (e4 && e5)

which is just your three AND terms ORed together.

> So, to summarize, I'm trying to find a structure that has this  
> inherently
> built in... which by several degrees of indirection means  
> significantly
> improved performance if you have n expressions and need to find the
> subexpressions and the path that was necessary to navigate to each
> randomly... basically, looking for the canonical solution... don't  
> know if
> one exists or not.

I'm obviously having YASD[1] but I'm still not really clear what you
mean. For your example does the tree look like this?

                           ( or )
                          /   |  \
                         /    |   \
                        /   (and)  \
                       /     / \    \
                    (and)   e3 e5  (and)
                    / |  \          / \
                  e1  e2  e5       e4  e5

It might be worth looking at this:

   http://www.dei.isep.ipp.pt/~acc/bfunc/

Unfortunately it's binary-only but, if nothing else, some of the
links might be useful. I recently used it in conjunction with a
little Perl wrapper to semi-automatically refactor a bunch of complex
business rules.

[1] Yet Another Stupid Day

-- 
Andy Armstrong, hexten.net