I think the following feature would make it much easier to both (a) make robust scene object and graph tests, and (b) create utilities to optimize scene graphs by identifying multiple objects which could be replaced by a single shared object. I would make use of benefit (a) ASAP to add unit tests to verify that graphs reconstituted by XMLImporter have the same definition as what was saved by XMLExporter.
The idea is to implement a SpatialDefinitionComparator which would compare any specified objects that implement SpatialDefinition. Unlike hashCode(), equals(), and the default compareTo(); SpatialDefinitionComparator would return 0 if two spatials have equivalent definitions/settings (as opposed to if they are the same instance). SpatialDefinitionComparator would make use of a hash code encompassing only those attributes which are intrinsic to the Spatial definition. Example: different pixel color or node scale would make two spatial definitions differ; but having different parent nodes or worldspace locations or current visibility would not.
What follows is an implementation detail which only matters if we are to proceed with this idea.
I don’t think we should change .hashCode() or .equals() because that could have drastic effects on use of Spatials in collections. It looks like String has overridden .hashCode(), but this is only because Strings are immutable and we would not expect set.add(“one”); set.add(“on” + “e”) to insert 2 elements.
Simply implementing Comparable for Spatials (i.e., the natural Comparable for Spatials) would be easier, but since we don’t want to change equals(), the Comparable implementation would not be consistent with equals, and would therefore suffer from the Set and Map idiosyncracies described at http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html.
Therefore, I think a generics-narrowed Comparable or a Comparable sub-interface is called for, so that the compiler would enforce that the user specify the new comparator for sorts. (By comparison, if we implement the natural Comparable and the user specified no comparator, the natural comparator would be applied with the side-effects previously referred to).
Its a good idea to make better use of JUnit tests.
different pixel color or node scale would make two spatial definitions differ; but having different parent nodes or worldspace locations or current visibility would not
i guess this makes sense.
What if we just leave those attribute out of the hashCode and equal methods and still use the default Comparable interface?
Core-Dump said:
Its a good idea to make better use of JUnit tests.
different pixel color or node scale would make two spatial definitions differ; but having different parent nodes or worldspace locations or current visibility would not
i guess this makes sense.
What if we just leave those attribute out of the hashCode and equal methods and still use the default Comparable interface?
Because that would lead to serious backwards-compatibility issues and very non-intuitive behavior of all hash-based collections. Developers need to depend on it that if they store different Spatials which happen to have the same settings to a Collection, that they will all be inserted. Example of what will happen if we make hashCode() or equals() less specific:
sphere1 = new Sphere("name I like to use");
sphere2 = new Sphere("name I like to use");
node13.attachChild(sphere1);
node28.attachChild(sphere2);
Set<Sphere> sphereSet = new HashSet<Sphere>();
sphereSet.add(sphere1);
sphereSet.add(sphere2);
// At this point sphereSet.size() is 1!
FYI, I don't expect the code above to compile. I don't wish to spend the time to validate it.
Provisional new Definitions.Comparable implementation. Please share any
objections, criticisms, or suggestions for improvement. I want to get this
committed so I can use it for other work.
POSTNOTE 2009-03-22T13:48UTC: Updated impl. just to allow for class to
specify whether sequence of each aggregated member list is significant.
Major additions to unit tests including aggregation tests, runtime change
detection, more.
As discussed in this topic, the purpose is to allow for easy and definitive
comparison of the complete definitions/settings for two objects, independent
of the runtime context. The main use cases that I can think of are
- To test persistence and restoration of any object. This can be used to easily and thoroughly test binary, cache, and XML storage of scene graphs.
- To allow for easy detection of multiple instances with the same exact settings, allowing for optimization by replacing duplicates with shared objects. I have written a Comparator to make this use case even simpler, but for reasons I won't detail here, I will only add that if somebody expresses interest in using it.
Here are developments since my earlier post, mostly from learning by getting it to work.
- The Comparator is unnecessary for the basic purpose of adding a new
.equals()-like operator. While the comparator could also be useful
(as noted above), the way to use it with the Java collections classes
is somewhat nonintuitive, due to what I assert are design flaws in the
Java collections. (What is essential for the equals is the Comparable). - This design is very lightweight. I have added infrastructure plus
utilities to greatly simplify the management of prime numbers which is
required for traditional generation of custom hash codes. As you can see
in the unit test, about 3 lines of boilerplate plus the hash-code
generation method needs to be added to target classes. The boilerplate
is required due to lack of multiple inheritance in Java. - The design is very general and applicable to any custom objects where you
would want to compare just the settings/definitions of instances (as
opposed to instance equality item1 == item2.
The end goal is the ability to run spatial1.definitionEquals(spatial2).
Unit test:
import static org.junit.Assert.*;
import java.util.List;
import java.util.ArrayList;
public class DefinitionsTest {
public static void main(String args[]) {
org.junit.runner.JUnitCore.main(DefinitionsTest.class.getName());
}
Sphere sphere1 = null;
Sphere sphere2 = null;
Rock rock1 = null;
Rock rock2 = null;
Sphere sphere1twin = null;
Rock rock2twin = null;
Bubble bubbleLikeRock1 = null;
Bubble bubble1 = null;
Bubble bubble2 = null;
@org.junit.Before
public void instantiations() {
sphere1 = new Sphere("sphere1", 3.3, Color.BLUE, 3, 4);
sphere2 = new Sphere("sphere2", 9.9, Color.RED, 9, 10);
rock1 = new Rock("rock1", 5.5, Color.RED, 5, 6, 22, true);
rock2 = new Rock("rock2", 7.7, Color.RED, 7, 8, 33, true);
sphere1twin = new Sphere("sphere1twin", 3.3, Color.BLUE, 8, 9);
rock2twin = new Rock("rock2twin", 7.7, Color.RED, 700, 18, 33, true);
bubbleLikeRock1 = new Bubble("rock1", 5.5, Color.RED, 5, 6, 22);
bubble1 = new Bubble("bubble1", 19.9, Color.YELLOW, 15, 16, 222);
bubble2 = new Bubble("bubble2", 29.9, Color.BLUE, 18, 19, 223);
// N.b.: The twins are only twins with respect to our "definition".
// They are both distinct instances and they have different
// values for fields we have exluded from our "definitions".
}
@org.junit.Test
public void testTopLevelDefComps() {
assertFalse("sphere1 == sphere2", sphere1.definitionEquals(sphere2));
assertFalse("sphere2 == sphere1", sphere2.definitionEquals(sphere1));
assertTrue("sphere1 == sphere1twin", sphere1.definitionEquals(sphere1twin));
assertTrue("sphere1twin == sphere1", sphere1twin.definitionEquals(sphere1));
assertFalse("sphere2 == sphere1twin", sphere2.definitionEquals(sphere1twin));
assertFalse("sphere1twin == sphere2", sphere1twin.definitionEquals(sphere2));
// Modify non-counted settings
sphere1.x = 101;
sphere1twin.y = 102;
assertTrue("sphere1 == sphere1twin", sphere1.definitionEquals(sphere1twin));
assertTrue("sphere1twin == sphere1", sphere1twin.definitionEquals(sphere1));
// Modify a counted setting
sphere1twin.radius = 4d;
assertFalse("sphere1 == sphere1twin", sphere1.definitionEquals(sphere1twin));
assertFalse("sphere1twin == sphere1", sphere1twin.definitionEquals(sphere1));
}
@org.junit.Test
public void testSubclassDefComps() {
assertFalse("rock1 == rock2", rock1.definitionEquals(rock2));
assertFalse("rock2 == rock1", rock2.definitionEquals(rock1));
assertFalse("rock1 == rock2twin", rock1.definitionEquals(rock2twin));
assertFalse("rock2twin == rock1", rock2twin.definitionEquals(rock1));
assertTrue("rock2 == rock2twin", rock2.definitionEquals(rock2twin));
assertTrue("rock2twin == rock2", rock2twin.definitionEquals(rock2));
// Modify non-counted settings
rock2.x = 101;
rock2twin.y = 102;
rock2twin.moss = false;
assertTrue("rock2 == rock2twin", rock2.definitionEquals(rock2twin));
assertTrue("rock2twin == rock2", rock2twin.definitionEquals(rock2));
// Modify a counted setting
rock2twin.radius = 4d;
assertFalse("rock2 == rock2twin", rock2.definitionEquals(rock2twin));
assertFalse("rock2twin == rock2", rock2twin.definitionEquals(rock2));
}
@org.junit.Test
public void testChecksumAlgorithm() {
// rock1 = new Rock("rock1", 5.5, Color.RED, 5, 6, 22, true);
assertEquals("Checksum for rock1",
"Rock".hashCode() + 3l * Double.valueOf(5.5d).hashCode()
+ 2l * Color.RED.hashCode()
+ 5l * + Double.valueOf(22d).hashCode(),
rock1.definitionHashCode());
//sphere1 = new Sphere("sphere1", 3.3, Color.BLUE, 3, 4);
assertEquals("Checksum for sphere1",
"Sphere".hashCode() + 3l * Double.valueOf(3.3d).hashCode()
+ 2l * Color.BLUE.hashCode(),
sphere1.definitionHashCode());
}
@org.junit.Test
public void testPeerSubclasses() {
assertFalse("rock1 == bubbleLikeRock1",
rock1.definitionEquals(bubbleLikeRock1));
assertFalse("bubbleLikeRock1 == rock1",
bubbleLikeRock1.definitionEquals(rock1));
}
@org.junit.Test
public void testAggregation() {
Froth froth1 = new Froth("froth1", "milk", 2.2);
Froth froth2 = new Froth("froth2", "milk", 2.2);
Froth froth1clone = new Froth("froth1clone", "milk", 2.2);
froth1.addBubble(bubble1);
froth1.addBubble(bubble2);
froth1clone.addBubble(bubble1);
froth1clone.addBubble(bubble2);
froth2.addBubble(bubble2);
froth2.addBubble(bubble1);
assertTrue("froth1 == froth1clone",
froth1.definitionEquals(froth1clone));
assertTrue("froth1clone == froth1",
froth1clone.definitionEquals(froth1));
assertFalse("froth1 == froth2", froth1.definitionEquals(froth2));
assertFalse("froth2 == froth1", froth2.definitionEquals(froth1));
assertFalse("froth2 == froth1clone",
froth2.definitionEquals(froth1clone));
assertFalse("froth1clone == froth2",
froth1clone.definitionEquals(froth2));
// Modify an uncounted child setting
froth1clone.name = "newname";
assertTrue("froth1 == froth1clone",
froth1.definitionEquals(froth1clone));
assertTrue("froth1clone == froth1",
froth1clone.definitionEquals(froth1));
// Modify a child item
froth1clone.liquid = "pepsi";
assertFalse("froth1 == froth1clone",
froth1.definitionEquals(froth1clone));
assertFalse("froth1clone == froth1",
froth1clone.definitionEquals(froth1));
}
}
enum Color { YELLOW, GREEN, RED, BLUE }
class Rock extends Sphere { // N.b.: this is a Definitions.Comparable SUBCLASS
double mass; // Definition-significant field
boolean moss; // Definition-insignificant field
Rock(String name, double radius, Color color, int xInt, int yInt,
double mass, boolean moss) {
super(name, radius, color, xInt, yInt);
this.mass = mass;
this.moss = moss;
}
/**
* @see Definitions.Comparable#definitionHashCode()
*/
public long definitionHashCode() {
return super.definitionHashCode()
+ Double.valueOf(mass).hashCode() * Rock.hashPrimes[0];
}
static protected long[] hashPrimes =
Definitions.nextPrimes(1, Sphere.hashPrimes[0]);
}
class Bubble extends Sphere { // N.b.: this is a Definitions.Comparable SUBCLASS
// Purposefully very close to the Rock class, because the goal is to test
// whether the hashCodes differentiate instances of these similar classes.
double shininess;
Bubble(String name, double radius, Color color, int xInt, int yInt,
double shininess) {
super(name, radius, color, xInt, yInt);
this.shininess = shininess;
}
/**
* @see Definitions.Comparable#definitionHashCode()
*/
public long definitionHashCode() {
return super.definitionHashCode()
+ Double.valueOf(shininess).hashCode() * Bubble.hashPrimes[0];
}
static protected long[] hashPrimes =
Definitions.nextPrimes(1, Sphere.hashPrimes[0]);
}
class Sphere implements Definitions.Comparable<Sphere> {
// N.b.: this is a Definitions.Comparable SUPERCLASS
Sphere(String name, double radius, Color color, int xInt, int yInt) {
this.name = name;
this.radius = radius;
this.color = color;
this.x = Integer.valueOf(xInt);
this.y = Integer.valueOf(yInt);
}
String name;
double radius; // Definition-singificant
Color color; // Definition-singificant
Integer x, y;
public String toString() { return (name == null) ? "" : name; }
static protected long[] hashPrimes = Definitions.nextPrimes(2, 1);
/**
* @see Definitions.Comparable#definitionHashCode()
*/
public long definitionHashCode() {
return getClass().getName().hashCode()
+ Double.valueOf(radius).hashCode() * hashPrimes[0]
+ color.hashCode() * hashPrimes[1];
}
/**
* @see Definitions.Comparable#definitionEquals(Object)
*/
public boolean definitionEquals(Sphere other) {
return Definitions.equals(this, other);
}
}
class Froth implements Definitions.Comparable<Froth> {
// N.b.: this is a Definitions.Comparable SUPERCLASS
Froth(String name, String liquid, double volume) {
this.name = name;
this.liquid = liquid;
this.volume = volume;
}
List<Bubble> bubbles = new ArrayList<Bubble>();
String name;
String liquid;
double volume;
public String toString() { return (name == null) ? "" : name; }
static protected long[] hashPrimes = Definitions.nextPrimes(4, 1);
// In this case, we need an extra prime to distinguish order of the
// elements of the aggregated bubble list.
public boolean addBubble(Bubble b) { return bubbles.add(b); }
/**
* @see Definitions.Comparable#definitionHashCode()
*/
public long definitionHashCode() {
long bubbleSum = 0;
for (int i = 0; i < bubbles.size(); i++) {
bubbleSum +=
bubbles.get(i).definitionHashCode() * i * hashPrimes[3];
// The hashPrime multiplier makes the list sequence-specific
// Just skip it for unordered sets
}
return getClass().getName().hashCode()
+ Double.valueOf(volume).hashCode() * hashPrimes[0]
+ liquid.hashCode() * hashPrimes[1]
+ bubbleSum * hashPrimes[2];
}
/**
* @see Definitions.Comparable#definitionEquals(Object)
*/
public boolean definitionEquals(Froth other) {
return Definitions.equals(this, other);
}
}
implementation:
import java.math.BigInteger;
public class Definitions {
/* Possible optimization would be to cache hash codes.
* I prefer generating the hashCode each time, because the former could
* break if a developer changes a field and neglects to mark the cache
* as dirty.
*/
/**
* HOW TO IMPLEMENT A Definitions.Comparable CLASS:
* <OL>
* <LI>Clinit an array containing a prime number for each field
* essential to your instance definitions (plus one for each
* such list which is an ordered list). <UL>
* <LI>Top-level Definitions.Comparable:
* <CODE><PRE>static protected long[] hashPrimes =
* Definitions.nextPrimes(8, 1);
* // over param is always 1 for top-level Comps.</PRE></CODE>
* <LI>Definitions.Comparable subclass:
* <CODE><PRE>static protected long[] hashPrimes =
* Definitions.nextPrimes(8, SuperClassName.hashPrimes[0]);
* </PRE></CODE>
* </UL> The number 8 here indicates 8 unique fields (you don't
* count the class name, because this idiom takes care of
* that automatically).
* <LI>Top-level Definitions.Comparables only:
* <CODE><PRE>
* public boolean definitionEquals(YourSuperClassName other) {
* return Definitions.equals(this, other);
* }
* </PRE></CODE>
* (No need to add this method to Definitions.Comparable subclasses).
* <LI>Implement definitionHashCode() with content like this. <UL>
* <LI>Top-level Definitions.Comparable:
* <CODE><PRE>
* return getClass().getName().hashCode()
* + someField.hashCode() * ThisClass.hashPrimes[0]
* + aComparableField.definitionHashCode() * ThisClass.hasPrimes[1]
* + anEnumField.hashCode() * ThisClass.hashPrimes[2]
* + Double.valueOf(nativeDouble).hashCode() * ThisClass.hashPrimes[3];
* </PRE></CODE>
* <LI> Definitions.Comparable subclasses:
* Exactly the same as for top-level classes, except start with
* <CODE>return super.definitionHashCode()</CODE>
* instead of with <CODE>getClass().getName().hashCode()</CODE>.
* </UL>
* </OL>
* <P>
* Requires that there are no loops in aggregation graphs.
* This is the case for JME Spatials where a Node may not have itself as
* a direct or indirect descendant.
* </P>
*
* @see #nextPrimes(int, long)
*/
static public interface Comparable<T> {
/**
* <B>
* IMPORTANT: There is no reason for subclasses to implement
* definitionEquals. The boilerplate above in any superclass all
* that you need.
* </B>
* <P>
* This is purposefully not named as a JavaBean get*() or is*()
* getter, to prevent persistence frameworks from storing the
* volatile output.
* </P>
*
* @see Definitions.Comparable
*/
boolean definitionEquals(T o);
/**
* Generates a hash-code that is unique for all definition-specific
* fields of the current instance.
* <P>
* <B>
* Unless you have a very unusual use-case, just follow the idiom
* explained in the Definitions.Comparable interface JavaDoc.
* </B>
* </P> <P>
* Generally, this should include the hash of name of specified class,
* plus a prime multiple of hashes for all definition-specific fields.
* If the class aggregates custom class instances
* (Definitions.Comparable or otherwise), the same criterion applies:
* if the definition of this object is different when the aggregated
* instance is different, then this hash code should include a
* prime-multiple of the hash code from that instance.
* </P><P>
* This is purposefully not named as a JavaBean get*()
* getter, to prevent persistence frameworks from storing the
* volatile output.
* </P>
*
* @param Runtime Class. This is to accommodate class-independent
* prime-number usage.
* @see Definitions.Comparable
*/
long definitionHashCode();
}
/**
* Convenience method for Definitions.Comparable classes to use to satisfy
* the definitionEquals() implementation requirement.
*
* @param A non-null Definitions.Comparable instance.
* @param A possibly-null Definitions.Comparable instance.
* @see Definitions.Comparable@definitionEquals(<T> o);
*/
static public boolean equals(
Definitions.Comparable dc1, Definitions.Comparable dc2) {
if (dc2 == null) return false;
return dc1.definitionHashCode() == dc2.definitionHashCode();
}
/**
* Convenience utility to get the next prime.
* Useful for hash code assembly.
*/
static long nextPrime(long l) {
return BigInteger.valueOf(l).nextProbablePrime().longValue();
}
/**
* Returns an array of the next 'howMany' prime numbers over 'over'.
*
* Convenience utility to get the next prime.
* Useful for hash code assembly.
*
* @returns list, in decreasing sequence.
* This way, list[0] always holds the max prime of the list, regardless
* of the length.
* @see Definitions.Comparable
*/
static long[] nextPrimes(int howMany, long over) {
if (howMany < 1) throw new IllegalArgumentException(
"Method nextPrimes called for < 1 prime: " + howMany);
long[] longList = new long[howMany];
long sourcePrime = over;
for (int i = howMany - 1; i >= 0; i--) {
sourcePrime =
BigInteger.valueOf(sourcePrime).nextProbablePrime().longValue();
longList[i] = sourcePrime;
}
return longList;
}
}