Thanks for the responses so far. I see that I need to clarify my enquiry. B-Trees and BDDs are not the same. BDDs are an efficient and compact representations for Boolean functions, sometimes used in SAT-solvers and electronics design. The key idea is that since the output must be 0 or 1, you can represent any Boolean function as a tree whose depth is the same as the number of bits in the input.
To make the tree small and efficient, though, you need to eliminate any node whose two children are the same, and to share subtrees, so that you really get a DAG, not a tree. The full name for these efficient compressed trees is “Reduced Order Binary Decision Diagrams”, or ROBDDs. I was hoping that someone else had implemented the algorithms necessary to build this representation. Because sets can be considered to be Booleans functions (true => argument is in the set), you can use ROBDDs to efficiently represent large sets. To be clear, despite the word “diagram” in the name, one is not normally interested in drawing the BDD — except in the documentation for the package ;-). Normally, BDDs they are used to represent sets, or functions, where the drawing would be hopelessly large. The BuDDy package (http://buddy.sourceforge.net/manual/main.html) is an example of what I’m looking for, but unfortunately it’s in C++. Andrew > On 25 Oct 2017, at 21:39 , Stephane Ducasse <stepharo.s...@gmail.com> wrote: > > Hi andrew > > I think that Avi did a package about BDD (but I thought it was special > binary trees) so this is probably the same. > Did you check on Squeaksource? > http://www.squeaksource.com/BTree.html > If this is what you are looking for I can help porting it to Pharo. > > Stef > > > On Wed, Oct 25, 2017 at 9:02 PM, Prof. Andrew P. Black <bl...@cs.pdx.edu> > wrote: >> Does anyone know of a BDD — that’s Binary Decision Diagram — package written >> in Smalltalk? >> >> Andrew >> >> >
