What does Equivalence of instances mean?

Question
21

This bit me in the ass when I was trying to count the unique nodes in a tree using a BFS search. Counting the nodes means count the number of memory allocated nodes. I want to show (to my students) that algorithm X is more efficient than algorithm Y by counting the residual nodes as a result of algorithm X vs Y. BFS must keep a visited set. I was using a Set[Bdd], but afterwards I realized that the Set was being uniquified accorder to == which turns out to not be what I want.

Is there a way for me to have a Set[A] which does not use the equals of A but rather uses a given equivalence function? eq in my case?

22

And another question, which I might be confused about. In my class hierarchy I have two singleton objects called BddTrue and BddFalse which inherit from BddTerm which inherits from Bdd. The only one other instantiatable class is BddNode which inherits from Bdd. If I have a Set[Bdd] then that set will be necessarily inhabited by various nodes of BddNode and at most one BddTrue and one BddFalse. Which equivalence function is used to uniquify the BddNode instances? Is it the equals of BddTerm or is it the equals of Bdd ?

23

Java has java.util.IdentityHashMap - uses eq for comparing keys. Remember that eq in Scala is the same as == in Java when reading the documentation: IdentityHashMap (Java Platform SE 8 )

equals method is virtual just like any other non-static and non-private method in Java (and Scala): Virtual function - Wikipedia
With virtual methods reference type is only used to check if a method exists on receiver. Actual implementation of method that is invoked depends on instance type, not reference type.

1 Like