>I don't think it is NP-complete. Perhaps you are thinking about a
>general graph isomorphism problem, but the problem we have is easier (in
>the sense that edges are labeled.)
>
>But you raised a good point about the overhead of computing
>hashCode/equality. Since we have to traverse the entire sub-tree, it
>seems like the cost could be very expensive (even if the theoretical
>complexity is not NP-complete.)
googling suggests its NP but not (known to be) NP-complete in general
http://www.cs.kent.ac.uk/people/staff/sjt/Bctcs12/toran.html
I hadn't realised that the edges were labelled so agree that it won't be
that complex in most cases, but on the other hand general deep-equality of
objects would be (?) because there'd be no labels for some edges
class A {
Set children;
...
}
(but Sets of elements don't seem to be supported in XML?)
Also came across this (which doesn't actually deal with cyclic structures)
http://citeseer.nj.nec.com/grogono00copying.html
I had no idea it was potentially this complicated.. :)
>I don't consider it as "such a rarity." As I pointed out, ID/IDREFs
>introduce cycles and they are quite common.
ok, i am understanding a lot more why this isn't in JAXB :)
>It will break as soon as you start modifying those XML elements.
>Could you also elaborate on why you want to put those on Set?
sure - i'm dealing with a situation where you are keeping two xml files
(source and target) in sync. with each other. We can't simply copy source
to target since source may contain information that target isn't allowed to
know about, so we need to merge some elements from the source into the
target (while filtering out other elements). Both files are instances of
the same schema, and the section being merged is a conceptually a set of a
elements (in practice the generated class representation has a field of
type java.util.List to represent the set - I'm not sure if there is a way
to change this?).
The set container element is an element which contains an unbounded choice
of other elements (it can't include itself). To do the merging it would be
nice to write code like
ContainerElement containerElement = ... from object tree ...
Set srcset = new
HashSet(containerElement.getItem1_Or_Item2_Or_Item3()); //
getItem1_Or_Item2_Or_Item3 returns a java.util.List of objects of type
Item1 or Item2 or Item3 ...
Set tgtset = ... similar ...
filter_out_sensitive_things(srcset); // alters set
srcset.removeAll(tgtset); // here equality / hashCode removes
elements that really are identical
// add everything remaining in srcset to the target XML's
"getItem1_Or..." java.util.List
Since the files are processed pairwise (and each file can only occur in
exactly one pair) its guaranteed that its safe to alter the target xml
object tree (the source xml is not altered at all). We also do not alter
any of the object trees generated from Item1 etc.. XML, so they are really
being treated as values.
I've written a little program that can operate on the generated java source
generated by JAXB, its quite short (it needs the original sources to be
compiled first so it can get the field information via reflection rather
than parsing) but very specific to the application I'm looking at (mostly
because it assumes all field of type List need Set equality).
The source code is below just to give an idea of what I'm trying to do.
I've not yet tested that equality/hashCode do actually do what I intend but
the JAXB-generated source files are being updated and compiling. Its not
pretty but the only alternative i could see was to write methods like
public boolean ELEMENTXs_are_equals(ELEMENTX e1, ELEMENTX e2) {
}
and do the Set operations manually.
thanks,
Andrew
import java.io.*;
import java.lang.reflect.*;
public class GenEquals {
public static void main(String [] arg) throws Exception {
File source = new File("h:/java/wh/src"); // new File(arg[0]);
- the directory containing the root of the source tree
String _package = "warehouse.operations.jaxb.wxml.impl"; //
arg[1]; - the JAXB implementation package name
File src = new File(source, _package.replace('.','/'));
File[] child = src.listFiles();
for(int i=0; i<child.length; i++) {
String name = child[i].getName();
if(name.toLowerCase().endsWith(".java")) {
name = name.substring(0,name.indexOf("."));
System.out.println(" "+name);
process(child[i], _package+"."+name);
}
}
}
public static void process(File sourceFile, String fqcn) throws
ClassNotFoundException, IOException {
StringBuffer result = new StringBuffer();
StringBuffer equalsMethod = new StringBuffer();
StringBuffer hashCodeMethod = new StringBuffer();
Class c = Class.forName(fqcn); // assume current JAXB generated
classes are compiled and on the classpath
Field[] fs = c.getDeclaredFields();
Class java_util_list = Class.forName("java.util.List");
BufferedReader br = new BufferedReader(new
FileReader(sourceFile));
for(String line; (line=br.readLine())!=null; )
result.append(line+"\n");
br.close();
equalsMethod.append(" public boolean equals(Object o) {\n");
// from Object API: For any non-null reference value x,
x.equals(null) should return false
equalsMethod.append(" if(o==null) return false;\n");
equalsMethod.append(" if(o==this) return true;\n");
equalsMethod.append(" boolean result = true;\n");
equalsMethod.append(" "+c.getName()+" other
= ("+c.getName()+") o;\n");
hashCodeMethod.append(" public int hashCode(Object o) {\n");
hashCodeMethod.append(" int result = 0;\n");
for(int i=0; i<fs.length; i++) {
if(!Modifier.isStatic(fs[i].getModifiers())) {
Class type = fs[i].getType();
String name = fs[i].getName();
// this section is a bit specific to the app. I'm
working on:
// we know that every List generated by JAXB is
representing a set in reality*
// and so any subclass of java.util.List is
converted to a set and uses its definition
// of equality.
if(java_util_list.isAssignableFrom(type)) {
equalsMethod.append(" result &= new
java.util.HashSet(other."+name+").equals(new
java.util.HashSet("+name+"));\n");
hashCodeMethod.append(" result += new
java.util.HashSet("+name+").hashCode();\n");
} else {
equalsMethod.append(" result &=
other."+name+".equals("+name+"); // "+type+"\n");
hashCodeMethod.append(" result
+= "+name+".hashCode(); // "+type+"\n");
}
//System.out.println(" "+fs[i].getName() + "
"+fs[i].getType());
}
}
hashCodeMethod.append(" return result;\n");
hashCodeMethod.append(" }\n");
equalsMethod.append(" return result;\n");
equalsMethod.append(" }\n");
result.insert(result.lastIndexOf("}"), equalsMethod+"\n");
result.insert(result.lastIndexOf("}"), hashCodeMethod);
FileWriter fw = new FileWriter(sourceFile);
fw.write(result.toString());
fw.close();
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe_at_jaxb.dev.java.net
For additional commands, e-mail: users-help_at_jaxb.dev.java.net