source: trunk/gli/src/org/greenstone/gatherer/msm/MSMUtils.java@ 6318

/**
 *#########################################################################
 *
 * A component of the Gatherer application, part of the Greenstone digital
 * library suite from the New Zealand Digital Library Project at the
 * University of Waikato, New Zealand.
 *
 * Author: John Thompson, Greenstone Digital Library, University of Waikato
 *
 * Copyright (C) 1999 New Zealand Digital Library Project
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *########################################################################
 */
package org.greenstone.gatherer.msm;

/**************************************************************************************
 * Title:        Gatherer
 * Description:  The Gatherer: a tool for gathering and enriching a digital collection.
 * Company:      The University of Waikato
 * Written:        /  /01
 * Revised:      16/08/02 Improved 
 *               06/08/03 Bug fixes
 * @author John Thompson, Greenstone Digital Libraries
 * @version 2.3
 **************************************************************************************/
import java.io.*;
import java.util.*;
import org.greenstone.gatherer.Gatherer;
import org.greenstone.gatherer.cdm.CommandTokenizer;
import org.greenstone.gatherer.mem.Attribute;
import org.greenstone.gatherer.msm.MetadataSet;
import org.greenstone.gatherer.util.ArrayTools;
import org.greenstone.gatherer.util.StaticStrings;
import org.greenstone.gatherer.util.Utility;
import org.greenstone.gatherer.valuetree.GValueModel;
import org.w3c.dom.*;
/** This class contains a plethora of methods associated with handling the content of <strong>MetadataSet</strong>s and the <strong>Element</strong>s within. For example this is where you will find methods for comparing various parts of two <strong>MetadataSet</strong>s for equality. It also has methods for extracting common and useful data from <strong>Element</strong>s such as the AssignedValue nodes.
 * @author John Thompson, Greenstone Digital Libraries
 * @version 2.3
 */
public class MSMUtils {
    /** Used to order metadata according to set standard element order then alphabetically by value. */
    static public MetadataComparator METADATA_COMPARATOR = new MetadataComparator();
    /** An element of the enumeration of type filter. */
    static public final int NONE = 0;
    /** An element of the enumeration of type filter. */
    static public final int VALUES = 1;
    /** An element of the enumeration of type filter. */
    static public final int ALIASES = 2;
    /** An element of the enumeration of type filter. */
    static public final int BOTH = 3;
    /** The character used to separate name space from metadata element. */
    static public final char NS_SEP= '.';
    /** The character used to separate subfields from metadata element. */
    static public final String SF_SEP= "#";
    /** Method to add one node as a child of another, after migrating into the target document.
     * @param parent The <strong>Node</strong> we are inserting into.
     * @param child The original <strong>Node</strong> we are inserting. Must first be cloned into the parents document.
     */
    static final public void add(Node parent, Node child) {
    Document document = parent.getOwnerDocument();
    Node new_child = document.importNode(child, true);
    parent.appendChild(new_child);
    } 

    static final public void addElementAttribute(Node node, String name, String language, String value) {
    Document document = node.getOwnerDocument();
    Element attribute_node = document.createElementNS("", "Attribute");
    attribute_node.setAttribute("name", name);
    attribute_node.setAttribute("language", language);
    node.appendChild(attribute_node);
    Node attribute_text = document.createTextNode(value);
    attribute_node.appendChild(attribute_text);
    }

    /** A method for comparing two AssignedValues trees. This compares not only the Subject hierarchies but also the values themselves.
     * @param avt A <strong>Node</strong> which is the root of an AssignedValues tree.
     * @param bvt The <strong>Node</strong> which is the root of the tree we wish to compare it to.
     * @return <i>true</i> if the two trees are equal, <i>false</i> otherwise.
     */
    static final public boolean assignedValuesEqual(Node avt, Node bvt) {
    if(avt == null && bvt == null) {
        return true; // Both are null so both are equal.
    }
    else if(avt == null || bvt == null) {
                // One is null and the other isn't.
        return false;
    }
    else {
        Hashtable a_map = new Hashtable();
        getValueMappings(avt, null, a_map);
        Hashtable b_map = new Hashtable();
        getValueMappings(bvt, null, b_map);
        if(a_map.size() == b_map.size()) {
        /** @TODO - Figure out what to do now. */
        return true;
        }
    }
    return false;
    }
    /** A method for comparing two attribute nodes of type Node not Attr as you might think. Attr objects are used to describe the attributes of tags themselves, while in a metadata set we intend attribute nodes to describe qualities of metadata elements. It's just confusing because the two systems (DOM model and Dublin Core) are quite similar.
     * @param an A <strong>Node</strong> representing some attribute of an element.
     * @param bn The <strong>Node</strong> we wish to compare it to.
     * @return <i>true</i> if and only if the attributes are equal.
     */
    static final public boolean attributesEqual(Node an, Node bn) {
    // Check we are comparing apples and apples...
    if(an.getNodeName().equals("Attribute") && bn.getNodeName().equals("Attribute")) {
        Element ae = (Element) an;
        Element be = (Element) bn;
                // Ensure we are comparing the same type of attribute.
        if(ae.getAttribute("name").equals(be.getAttribute("name"))) {
        // And finally retrieve and compare the values.
        if(getValue(ae).equals(getValue(be))) {
            // We have a match.
            return true;
        }
        }
    }
    // And if anything goes wrong we can't be dealing with equal attributes.
    return false;
    }

    /** Remove all of the child nodes from a certain node. */
    static final public void clear(Node parent) {
    while(parent.hasChildNodes()) {
        parent.removeChild(parent.getFirstChild());
    }
    }

    /** Method to determine if a certain path of elements can be found in another tree. This method tests by comparing node names, and finally the #text node past the leaf end of the path.
     * @param tree The root <strong>Node</strong> of the tree to be searched.
     * @param path The <strong>Node[]</strong> path to be found.
     * @return <i>true</i> if the path was found (including matching #text elements at the leaf), or <i>false</i> otherwise.
     */
    /* static final private boolean containsPath(Node tree, Node path[]) {
    // If there is no tree then there are no values.
    if(tree == null) {
        return false;
    }
    // Ensure we are comparing equivent things.
    if(tree.getNodeName().equals("AssignedValues") && path[0].getNodeName().equals("AssignedValues")) {
        int index = 1;
        while(index < path.length && tree != null) {
        Node next = null;
        for(Node n = tree.getFirstChild(); n != null && next == null; n = n.getNextSibling()) {
            if(n.getNodeName().equals(path[index].getNodeName())) {
            next = n;
            index++;
            }
            tree = next;
        }
        }
                // Tree may now be pointing at the same node as 
                // path[path.length - 1] so we should test their child text nodes.
        if(tree != null) {
        Node tree_text = tree.getFirstChild();
        Node path_text = path[path.length - 1].getFirstChild();
        if(tree_text.getNodeValue().equals(path_text.getNodeValue())) {
            // Path found!
            return true;
        }
        }
    }
    return false;        
    } */
    /** Method to compare two metadata elements (of type Element, which is bound to get more than a bit confusing) for equality. This test may only check the structural (ie pretty much unchanging) consistancy, or may include the AssignedValue tree as well (which will be different for each collection I'd imagine).
     * @param a_set The <strong>MetadataSet</strong> a comes from.
     * @param a An <strong>Element</strong>.
     * @param b_set The <strong>MetadataSet</strong> b comes from.
     * @param b The <strong>Element</strong> to compare it to.
     * @param values <i>true</i> if the AssignedValues tree should also be compared, <i>false</i> otherwise.
     * @return <i>true</i> if the elements are equal, <i>false</i> otherwise.
     */
    static final public boolean elementsEqual(MetadataSet a_set, Element ae, MetadataSet b_set, Element be, boolean values) {
    // Compare Element Attr(ibutes) within the DOM, not to be confused with comparing element attributes in a Dublin Core sense...
    NamedNodeMap aas = ae.getAttributes();
    NamedNodeMap bas = be.getAttributes();
    // For each attribute in a...
    for(int i = 0; i < aas.getLength(); i++) {
        Attr aa = (Attr)aas.item(i);
                // Try to retrieve an attribute of the same name from b.
        Attr ba = (Attr)bas.getNamedItem(aa.getNodeName());
                // Now if there was no such attribute, or if the values for the
                // two attributes are different the structures different.
        if(ba == null || (!aa.getValue().equals(ba.getValue()))) {
        //ystem.err.println("Attributes are not equal");
        return false;
        }
    }
    // Quickest test of children is to see we have the same number in
    // each. Remember to modify for missing AssignedValues which have
    // nothing to do with structure.
    int anc = getAttributeCount(ae);
    int bnc = getAttributeCount(be);
    if(anc != bnc) {
        return false;
    }
    // Now we compare the child nodes of the two Elements taking into 
    // account three special cases...
    // 1. We don't test the AssignedValues element here.
    // 2. Remember OptionList node.
    // 3. The Attributes of each metadata element.
    // For each child node of a.
    for(Node an = ae.getFirstChild(); an !=null; an =an.getNextSibling()) {
        if(an.getNodeName().equals("OptionList")) {
        //ystem.err.println("Matching OptionLists.");
        Node bn = getNodeFromNamed(be, "OptionList");
        if(bn == null || !optionListsEqual(an, bn)) {
            //ystem.err.println("OptionLists are not equal");
            return false;
        }
        }
                // Matching attributes.
        else if(an.getNodeName().equals("Attribute")) {
        //ystem.err.println("Matching Attributes.");
        boolean matched = false;
        for(Node bn = be.getFirstChild(); bn != null && !matched;
            bn = bn.getNextSibling()) {
            if(bn.getNodeName().equals("Attribute")) {
            matched = attributesEqual(an, bn);
            }
        }
        if(!matched) {
            //ystem.err.println("Cannot match attribute.");
            return false;
        }
        }
    }
    // Finally, if we've been asked to compares value trees (for some unknown reason) go ahead and compare them too.
    if(values) {
        GValueModel avt = a_set.getValueTree(new ElementWrapper(ae));
        GValueModel bvt = b_set.getValueTree(new ElementWrapper(be));
        return assignedValuesEqual(avt.getDocument().getDocumentElement(), bvt.getDocument().getDocumentElement());
    }
    // If we've got this far the elements match!
    return true;
    }   
    /** This method extracts the assigned value trees details, if any, from a certain element and stores them in an array ready to be passed as arguments to the Dictionary.
     * @param element The <strong>Element</strong> whose values we wish to view.
     * @return A <strong>String[]</strong> containing the details of the assigned values tree.
     * @see org.greenstone.gatherer.Dictionary
     */
    static final public String[] getAssignedValuesDetails(MetadataSet mds, Element element) {
    String details[] = null;
    //Node avt = getNodeFromNamed(element, "AssignedValues");
    GValueModel avt = mds.getValueTree(new ElementWrapper(element));
    if(avt != null) {
        Hashtable mapping = new Hashtable();
        getValueMappings(avt.getDocument().getDocumentElement(), null, mapping);
        ArrayList values = new ArrayList(mapping.keySet());
        Collections.sort(values);
        details = new String[1];
        for(int i = 0; i < values.size(); i++) {
        if(details[0] == null) {
            details[0] = "   " + values.get(i);
        }
        else {
            details[0] = details[0] + "\n   " + values.get(i);
        }
        }
        mapping = null;
        values = null;
    }
    avt = null;
    return details;
    }

    static final public TreeSet getAttributes(Element element) {
    TreeSet attributes = new TreeSet();
    for(Node n = element.getFirstChild(); n != null; n = n.getNextSibling()) {
        if(n.getNodeName().equals("Attribute")) {
        Element e = (Element)n;
        attributes.add(new Attribute(e.getAttribute("name"), e.getAttribute("language"), getValue(e)));
        }
    }
    return attributes;
    }

    /** Method to count the number of Attribute nodes under a certain Element. This ignores other nodes such as #text, OptionList and AssignedValues nodes.
     * @param element The <strong>Element</strong> whose attributes you want to count.
     * @return An <i>int</i> which is the number of attribute nodes.
     */
    static final public int getAttributeCount(Node element) {
    int count = 0;
    for(Node n = element.getFirstChild(); n != null; 
        n = n.getNextSibling()) {
        if(n.getNodeName().equals("Attribute")) {
        count++;
        }
    }
    return count;
    }

    /*************************************************************************/
    /** This method is a slight variation on getNodeNamed in that it is especially written to retrieve the attribute Nodes of a certain name present under the given element. Note that this method is language specific.
     * @param element The target element <strong>Node</strong>.
     * @param name The name of the attribute you wish to return.
     * @return An <strong>Element[]</strong> containing the attributes you requested, or <i>null</i> if no such attributes exists.
     */
    static final public Element getAttributeNodeNamed(Node element, String name) { 
    Element attribute = null;
    String language_code = Locale.getDefault().getLanguage();
    for(Node n = element.getFirstChild(); n != null; n = n.getNextSibling()) {
        if(n.getNodeName().equals("Attribute")) {
        Element e = (Element)n;
        if(e.getAttribute("name").equals(name)) {
            if(e.getAttribute("language").equalsIgnoreCase(language_code)) {
            return e;
            }
            else if(e.getAttribute("language").equalsIgnoreCase("en")) {
            attribute = e;
            }
            else if(attribute == null) {
            attribute = e;
            }
        }
        e = null;
        }
    }
    return attribute;
    }

    /** This method is a slight variation on getNodeNamed in that it is especially written to retrieve the attribute Nodes of a certain name present under the given element.
     * @param element The target element <strong>Node</strong>.
     * @param name The name of the attribute you wish to return.
     * @return An <strong>Element[]</strong> containing the attributes you requested, or <i>null</i> if no such attributes exists.
     */
    static final public Element[] getAttributeNodesNamed(Node element, String name) { 
    Element attributes[] = null;
    for(Node n = element.getFirstChild(); n != null; n = n.getNextSibling()) {
        if(n.getNodeName().equals("Attribute")) {
        Element e = (Element)n;
        if(e.getAttribute("name").equals(name)) {
            if(attributes == null) {
            attributes = new Element[1];
            attributes[0] = e;
            }
            else {
            Element temp[] = attributes;
            attributes = new Element[temp.length + 1];
            System.arraycopy(temp, 0, attributes, 0, temp.length);
            attributes[temp.length] = e;
            temp = null;
            }
        }
        e = null;
        }
    }
    return attributes;
    }

    /** Method to construct an elements description by retrieving the correct attribute.
     * @param element The <strong>Element</strong> whose name we wish to retrieve.
     * @return A <strong>String</strong> which is the elements description, or an empty string if no description exists.
     */
    static final public String getDescription(Node element) {
    String definition = "";
    Element definition_node = getAttributeNodeNamed(element, "definition");
    if(definition_node != null) {
        definition = getValue(definition_node);
    }
    String comment = "";
    Element comment_node = getAttributeNodeNamed(element, "comment");
    if(comment_node != null) {
        comment = getValue(comment_node);
    }
    if(!definition.endsWith(StaticStrings.SPACE_CHARACTER) && !comment.startsWith(StaticStrings.SPACE_CHARACTER)) {
        comment = StaticStrings.SPACE_CHARACTER + comment;
    }
    String description = definition + comment;
    return Utility.stripNL(description.trim());
    }

    /** Extracts the file name pattern from within a fileset of a Greenstone Directory Metadata model.
     * @param fileset The fileset Node in question.
     * @return The pattern as a String.
     */
    /* static final private String getFileNamePattern(Node fileset) {
    // Locate the child node called filename
    for(Node child = fileset.getFirstChild(); child != null; child = child.getNextSibling()) {
        if(child.getNodeName().equalsIgnoreCase("FileName")) {
        // Find the file string.
        return MSMUtils.getValue(child);
        }
    }         
    return null;
    } */

    /*************************************************************************/
    /** Method to create the fully namespace quantified identifier for this element.
     * @param element The <strong>Node</strong> in question.
     * @return A fully qualified identifier as a <strong>String</strong>
     */
    /* static final private String getFullIdentifier(Node element, String namespace) {
    StringBuffer identifier_buffer = new StringBuffer();
    if(element == null) {
        return "Error";
    }
    // First get the root node.
    Document document = element.getOwnerDocument();
    Element root = document.getDocumentElement();
    document = null;
    // Retrieve this elements identifier
    identifier_buffer.append(getIdentifier(element));
    // Now we check if element has a parent node, other than root. If so we begin building up the full identifier
    Element parent_element = (Element) element.getParentNode();
    while(parent_element != null && parent_element != root) {
        identifier_buffer.insert(0, SF_SEP);
        identifier_buffer.insert(0, getIdentifier(parent_element));
        parent_element = (Element)parent_element.getParentNode();
    }
    parent_element = null;
    // Finally insert the namespace and we are all done.
    if(root != null) {
        namespace = root.getAttribute("namespace");
    } 
    root = null;
    // If no root, or no namespace found, assume its extracted (at least then they can't edit it)
    if(namespace == null || namespace.equals("")) {
        namespace = Utility.EXTRACTED_METADATA_NAMESPACE;
    }
    identifier_buffer.insert(0, NS_SEP);
    identifier_buffer.insert(0, namespace);
    namespace = null;
    return identifier_buffer.toString();
    } */

    /*************************************************************************/
    /** Method to construct an elements fully qualified name. Note that this is different from a nodes identifier. Think of name as a short, unique reference to a metadata element, whereas identifier can be much longer, language specific and non-unique.
     * @param element An <strong>Element</strong> whose name we are interested in.
     * @return A <strong>String</strong> representing this given elements fully namespace qualified name.
     */
    static final public String getFullName(Element element) {
    return getFullName(element, "");

    }
    /*************************************************************************/
    /** Method to construct an elements fully qualified name. Note that this is different from a nodes identifier. Think of name as a short, unique reference to a metadata element, whereas identifier can be much longer, language specific and non-unique.
     * @param element An <strong>Element</strong> whose name we are interested in.
     * @return A <strong>String</strong> representing this given elements fully namespace qualified name.
     */
    static final public String getFullName(Element element, String namespace) {
    StringBuffer name_buffer = new StringBuffer();
    if(element == null) {
        return "Error";
    }
    // First get the root node.
    Document document = element.getOwnerDocument();
    Element root = document.getDocumentElement();
    document = null;
    // Retrieve this elements name
    name_buffer.append(element.getAttribute("name"));
    // Now we check if element has a parent node, other than root. If so we begin building up the full name
    Element parent_element = (Element) element.getParentNode();
    while(parent_element != null && parent_element != root) {
        name_buffer.insert(0, SF_SEP);
        name_buffer.insert(0, parent_element.getAttribute("name"));
        parent_element = (Element)parent_element.getParentNode();
    }
    parent_element = null;
    // Finally insert the namespace and we are all done.
    if(root != null) {
        namespace = root.getAttribute("namespace");
    } 
    root = null;
    // If no root, or no namespace found, assume its extracted (at least then they can't edit it)
    if(namespace == null || namespace.equals("")) {
        namespace = Utility.EXTRACTED_METADATA_NAMESPACE;
    }
    name_buffer.insert(0, NS_SEP);
    name_buffer.insert(0, namespace);
    namespace = null;
    return name_buffer.toString();
    } // static public String getFullName(Element element)

    /** Method to construct an elements identifier by retrieving the correct attribute. Language specific, based on default Locale.
     * @param element The <strong>Element</strong> whose name we wish to retrieve.
     * @return A <strong>String</strong> which is the elements identifier, or an empty string if no identifier exists.
     */
    static final public String getIdentifier(Node element) {
    String identifier = null;
    // Determine locale code.
    String language_code = Locale.getDefault().getLanguage();
    // Get the 'identifier' Element with the correct locale
    for(Node node = element.getFirstChild(); node != null;
        node = node.getNextSibling()) {
        if(node.getNodeName().equals("Attribute")) {
        Element target = (Element)node;
        if(target.getAttribute("name").equals("identifier")) {
            Node text = target.getFirstChild();
            if(target.getAttribute("language").equalsIgnoreCase(language_code)) {
            return text.getNodeValue();
            }
            else if(target.getAttribute("language").equalsIgnoreCase("en")) {
            identifier = text.getNodeValue();
            }
            else if(identifier == null) {
            identifier = text.getNodeValue();
            }
            text = null;
        }
        target = null;
        }
    }
    language_code = null;
    // We may have harvested some identifier from the file.
    if(identifier != null) {
        return identifier;
    }
    // Failing the above we return the nodes name instead.
    return ((Element)element).getAttribute("name");
    }

    /** Retrieve the metadata description element from this fileset node.
     * @param fileset The fileset in question.
     * @return The description node or null if no such node.
     */
    /* static final private Node getMetadataDescription(Node fileset) {
    // Locate the child node called filename
    for(Node child = fileset.getLastChild(); child != null; child = child.getPreviousSibling()) {
        if(child.getNodeName().equalsIgnoreCase("Description")) {
        return child;
        }
    }         
    return null;
    } */

    /** Method to retrieve from the node given, a certain child node with the specified name.
     * @param parent The <strong>Node</strong> whose children should be searched.
     * @param name The required nodes name as a <strong>String</strong>.
     * @return The requested <strong>Node</strong> if it is found, <i>null</i> otherwise.
     */ 
    static final public Node getNodeFromNamed(Node parent, String name) {
    Node child = null;
    for(Node i = parent.getFirstChild(); i != null && child == null; 
        i = i.getNextSibling()) {
        if(i.getNodeName().equals(name)) {
        child = i;
        }
    }
    return child;
    }
    /** Look for the occurances 'field' of the element and return it if found.
     * @return An <i>int</i> which matches the number in the occurances attribute of the element, or 0 if no such attribute.
     */
    static final public int getOccurances(Element element) {
    int count = 0;
    String number = null;
    if((number = element.getAttribute("occurances")) != null) {
        try {
        count = Integer.parseInt(number);
        }
        catch(Exception error) {
        count = 0;
        }
    }
    return count;
    }    
    /** This method extracts the option list details, if any, from a certain element and stores them in an array ready to be passed as arguments to the <strong>Dictionary</strong>.
     * @param element The <strong>Element</strong> whose option list we wish to view.
     * @return A <strong>String[]</strong> containing the details of the option list.
     * TODO implement.
     * @see org.greenstone.gatherer.Dictionary
     */
    static final public String[] getOptionListDetails(Element element) {
    return null;
    }

    /** This method traces the path between the 'root' node given and the target node. This path is returned starting at the root.
     * @param root The root <strong>Node</strong> to start this path at.
     * @param target The final <strong>Node</strong> to end up at.
     * @return A <strong>Node[]</strong> that contains the sequence of nodes from root to target.
     */
    static final public Node[] getPath(Node root, Node target) {
    if(root == target) {
        return ArrayTools.add(null, root);
    }
    else {
        return ArrayTools.add(getPath(root, target.getParentNode()), target);
    }
    }

    /** This method extracts the structural details from a certain element and stores them in an array, all ready for passing to the <strong>Dictionary</strong>.
     * @param element The <Strong>Element</strong> whose details we wish to gather.
     * @return A <strong>String[]</strong> containing the structural details.
     */
    static final public String[] getStructuralDetails(MetadataSet mds, Element element) {
    String details[] = new String[4];
    //Element root = (Element)element.getParentNode();
    //details[0] = root.getAttribute("name");
    //details[1] = root.getAttribute("namespace");
    details[0] = mds.getName();
    details[1] = mds.getNamespace();
    details[2] = getFullName(element);
    details[3] = null;
    // Get attributes
    Vector attributes = new Vector();
    for(Node n=element.getFirstChild(); n!=null; n=n.getNextSibling()) {
        if(n.getNodeName().equals("Attribute")) {
        Element temp = (Element)n;
        attributes.add(temp.getAttribute("name") + "=" + getValue(n));
        }
    }
    // Sort attributes
    Collections.sort(attributes);
    // Add attributes to details.
    for(int i = 0; i < attributes.size(); i++) {
        if(details[3] == null) {
        details[3] = "   " + attributes.get(i);
        }
        else {
        details[3] = details[3] + "\n   " + attributes.get(i);
        }
    }
    return details;
    }

    /** Method to retrieve the value of a given node (not the assigned values tree!).
     * @param element The <strong>Element</strong> whose value we wish to find.
     * @return The value found as a <strong>String</strong>, or <i>null</i> if this element has no value.
     */
    static final public String getValue(Node element) {
    // If we've been given a subject node first retrieve its value node.
    if(element.getNodeName().equals("Subject")) {
        element = getNodeFromNamed(element, "Value");
    }
    // If we've got a value node, then reconstruct the text. Remember that DOM will split text over 256 characters into several text nodes
    if(element != null && element.hasChildNodes()) {
       StringBuffer text_buffer = new StringBuffer();
       NodeList text_nodes = element.getChildNodes();
       for(int i = 0; i < text_nodes.getLength(); i++) {
          Node possible_text = text_nodes.item(i);
          if(possible_text.getNodeName().equals(StaticStrings.TEXT_NODE)) {
         text_buffer.append(possible_text.getNodeValue());
          }
       }
       return text_buffer.toString();
    }
    return "";
    }

    /** Method to traverse the given value tree, and build up a hashtable of mappings between the value path key names and the Subject nodes of the tree.
     * @param current The root <strong>Node</strong> of a subtree of the AssignedValues tree.
     * @param prefix The value path key <strong>String</string>, which shows the path from the root of the AssignedValue tree to <i>current</i>s parent using '\' as a separator.
     * @param values A <strong>Hashtable</strong> containing the mapping discovered so far in our tree traversal.
     */ 
    static final public void getValueMappings(Node current, String prefix, Hashtable values) {
    if(current != null) {
        String name = current.getNodeName();
        String new_prefix = prefix;
                // If we've found the outer layer of a new value, add it to our
                // mapping.
        if(name.equals("Subject")) {
        Node value_node = getNodeFromNamed(current, "Value");
        String value = getValue(value_node);
        if(new_prefix != null) {
            new_prefix = new_prefix + "\\" + value;
        }
        else {
            new_prefix = value;
        }
        values.put(new_prefix, current);
        }
        if(name.equals("Subject") || name.equals("AssignedValues")) {
        for(Node child = current.getFirstChild(); child != null;
            child = child.getNextSibling()) {
            getValueMappings(child, new_prefix, values);
        }
        }
    }
    }
    /** Parses the value tree template file.
     * @return The Document parsed.
     */
    static final public Document getValueTreeTemplate() {
    return Utility.parse(Utility.METADATA_VALUE_TEMPLATE, true);
    }
    /** Method to compare two OptionsLists for equality.
     * @param al A <strong>Node</strong> which represents an OptionList.
     * @param bl The <strong>Node</strong> we wish to test against.
     * @return A <i>boolean</i> which is <i>true</i> if the two option lists are equal, <i>false</i> otherwise.
     * TODO Implementation
     */
    static final public boolean optionListsEqual(Node al, Node bl) {
    // Compare the 'restricted' attribute of the two lists.
    Element ae = (Element) al;
    Element be = (Element) bl;
    if(!ae.getAttribute("restricted").equals
       (be.getAttribute("restricted"))) {
        return false;
    }
    // Compare the Values under each list.
    for(Node an = al.getFirstChild(); an != null; 
        an = an.getNextSibling()){
        if(an.getNodeName().equals("Value")) {
        boolean matched = false;
        for(Node bn = bl.getFirstChild(); bn != null && !matched;
            bn = bn.getNextSibling()) {
            if(bn.getNodeName().equals("Value")) {
            matched = valuesEqual(an, bn);
            }
        }
        if(!matched) {
            return false;
        }
        }
    }
    return true;
    }

    /** can only be used to set the english value */
    static final public void setIdentifier(Node element, String value) {
    // Get the 'identifier' Element
    for(Node node = element.getFirstChild(); node != null;
        node = node.getNextSibling()) {
        if(node.getNodeName().equals("Attribute")) {
        Element target = (Element)node;
        if(target.getAttribute("name").equals("identifier") && target.getAttribute("language").equals("en")) {
            Node text = target.getFirstChild();
            text.setNodeValue(value);
            break;
        }
        }
    }
    }
    /** Set the value of the element attribute occurances.
     * @param element The <strong>Element</strong> to change.
     * @param value The value to change by as an <i>int</i>.
     */
    static final public void setOccurance(Element element, int value) {
    Integer new_value = new Integer(getOccurances(element) + value);
    element.setAttribute("occurances", new_value.toString());
    }

    /** Set the #text node value of some element.
     * @param element the Element whose value we wish to set
     * @param value the new value for the element as a String
     */
    static final public void setValue(Element element, String value) {
    // Remove any existing child node(s)
    clear(element);
    // Add new text node.
    element.appendChild(element.getOwnerDocument().createTextNode(value));
    }

    /** This method also traverses the tree, but this one is used to gather all the values and aliases at once, and to 'prune' the tree if necessary.
     * @param current The current root <strong>Node</strong> of this AssignedValues tree subtree.
     * @param return_filter This <i>int</i> specifies what nodes from the tree should be returned, where;<br>VALUES  = return values only<br>ALIASES = return aliases only<br>BOTH    = return both values and aliases<br>NONE    = return nothing.
     * @param remove_leaves A leaf node is a subject that contains no child subjects. If this <i>boolean</i> is set to <i>true</i> then the leaf nodes will be removed from the tree. 
     * @return A <strong>Node[]</strong> containing whatever values or aliases have been found during the trees traversal.
     */
    static final public Node[] traverseTree(Node current, int return_filter, boolean remove_leaves) {
    Node leaves[] = null;
    String name = current.getNodeName();
    if(name.equals("Value") && (return_filter == VALUES || return_filter == BOTH)) {
        leaves = ArrayTools.add(leaves, current);
    }
    else if(name.equals("Alias") && (return_filter == ALIASES || return_filter == BOTH)) {
        leaves = ArrayTools.add(leaves, current);
    }
    else if(name.equals("Subject")) {
        boolean has_subject_child = false;
        Node children[] = ArrayTools.nodeListToNodeArray(current.getChildNodes());
        for(int i = 0; i < children.length; i++) {
        if(children[i].getNodeName().equals("Subject")) {
            has_subject_child = true;
        }
        leaves = ArrayTools.add(leaves, traverseTree(children[i], return_filter, remove_leaves));
        }
        if(!has_subject_child && remove_leaves) {
        Node parent = current.getParentNode();
        parent.removeChild(current);
        }
    }
    else if(name.equals("AssignedValues")) {
        Node children[] = ArrayTools.nodeListToNodeArray(current.getChildNodes());
        for(int i = 0; i < children.length; i++) {
        leaves = ArrayTools.add(leaves, traverseTree(children[i], return_filter, remove_leaves));
        }
    }                                                             
    return leaves;
    }

    /** This method is used to systematically merge two AssignedValues tree. Both trees have their current values mapped, then the new tree is searched for key paths that don't exist in the current tree. If such a key is found, the Subject <strong>Node</strong> it maps to is retrieved and then imported and added to whatever was the closest available node (in terms of tree path) in the current tree.
     * @param a_set The MetadataSet from which the Element a came from.
     * @param a The Element at the root of the current AssignedValues tree.
     * @param b_set The MetadataSet from which the Element b came from.
     * @param b The root Element of the tree that is being merged.
     * @return A <i>boolean</i> which is <i>true</i> if the trees merged without error, <i>false</i> otherwise.
     */
    static final public boolean updateValueTree(MetadataSet a_set, Element a, MetadataSet b_set, Element b) {
    GValueModel avt = a_set.getValueTree(new ElementWrapper(a));
    GValueModel bvt = b_set.getValueTree(new ElementWrapper(b));
    // If neither element even has a value tree, we're all done.
    if(avt == null && bvt == null) {
        avt = null;
        bvt = null;
        return true;
    }
    // If the new element has no value tree then nothing needs to be done.
    else if(avt != null && bvt == null) {
        avt = null;
        bvt = null;
        return true;
    }
    // If only the new element has a value tree, then add all of its values
    // immediately.
    else if(avt == null && bvt != null) {
        a_set.addValueTree(new ElementWrapper(a), bvt);
        avt = null;
        bvt = null;
        return true;
    }
    // We have both trees for both elements, time to merge.
    else {
        Document document = avt.getDocument();
        Hashtable a_map = new Hashtable();
        getValueMappings(document.getDocumentElement(), null, a_map);
        Hashtable b_map = new Hashtable();
        getValueMappings(bvt.getDocument().getDocumentElement(), null, b_map);
                // For each new entry in b_map
        for(Enumeration b_keys = b_map.keys(); b_keys.hasMoreElements(); ) {
        String b_key = (String)b_keys.nextElement();
        // Test if there is already an entry in a_map.
        if(!a_map.containsKey(b_key)) {
            // If not, search through a_map for the longest match.
            Node target = document.getDocumentElement();
            String last_match = null;
            for(Enumeration a_keys = a_map.keys(); 
            a_keys.hasMoreElements(); ) {
            String a_key = (String)a_keys.nextElement();
            if(b_key.startsWith(a_key)) {
                if(last_match == null || a_key.length() > last_match.length()) {
                last_match = a_key;
                target = (Node)a_map.get(a_key);
                }
            }
            a_key = null;
            }
            // Now import the node at b_key and add it to target.
            Node subtree = (Node)b_map.get(b_key);
            subtree = document.importNode(subtree, true);
            // Find the node to insert before...
            String name = getValue(subtree);
            Node move = null;
            for(Node n = target.getFirstChild(); n != null && move == null; n = n.getNextSibling()) {
            if(n.getNodeName().equals("Subject")) {
                if(name.compareTo(getValue(n)) <= 0) {
                move = n;
                }
            }
            }
            if(move == null) {
            target.appendChild(subtree);
            }
            else {
            target.insertBefore(subtree, move);
            }
            target = null;
            last_match = null;
            subtree = null;
            name = null;
            move = null;
        }
        b_key = null;
        }
        document = null;
        a_map = null;
        b_map = null;
        avt = null;
        bvt = null;
        return true;
    }
    }

    /** Method to determine if two Value nodes are equal.
     * @param av A <strong>Node</strong> representing a value.
     * @param bv The <strong>Node</strong> we want to compare it to.
     * @return A <i>boolean</i> which is <i>true</i> if the two value nodes are equal, <i>false</i> otherwise.
     */
    static final public boolean valuesEqual(Node av, Node bv) {
    // Check we are comparing apples and apples...
    if(av.getNodeName().equals("Value") && 
       bv.getNodeName().equals("Value")) {
        // Retrieve and then compare their text values.
        Node at = av.getFirstChild();
        Node bt = bv.getFirstChild();
        if(at.getNodeValue().equals(bt.getNodeValue())) {
        return true;
        }
    }
    return false;
    }

    /** A comparator for sorting metadata element-value pairs into their standard order (elements) then alphabetical order (values). */
    static final private class MetadataComparator
    implements Comparator {
    /** Compares its two arguments for order. */
    public int compare(Object o1, Object o2) {
        int result = 0;
        ElementWrapper e1 = null;
        ElementWrapper e2 = null;
        String v1 = null;
        String v2 = null;
        if(o1 instanceof Metadata && o2 instanceof Metadata) {
        Metadata m1 = (Metadata) o1;
        Metadata m2 = (Metadata) o2;
        ///ystem.err.println("MSMUtils.compare(" + m1 + ", " + m2 + ") = ");
        e1 = m1.getElement();
        e2 = m2.getElement();
        v1 = m1.getValue().toLowerCase();
        v2 = m2.getValue().toLowerCase();
        }
        else if(o1 instanceof ElementWrapper && o2 instanceof ElementWrapper) {
        e1 = (ElementWrapper) o1;
        e2 = (ElementWrapper) o2;
        }
        if(e1 != null && e2 != null) {
        // First we compare the namespaces
        result = e1.getNamespace().compareTo(e2.getNamespace());
        if(result == 0 && Gatherer.c_man != null && Gatherer.c_man.ready() && e1.getNamespace() != null) {
            // Now, given both elements are in the same set, we compare the element ordering using methods in MetadataSet
            MetadataSet set = Gatherer.c_man.getCollection().msm.getSet(e1.getNamespace());
            ///ystem.err.print("MetadataSet.compare(" + e1 + ", " + e2 + ") = ");
            if(set != null) {
            result = set.compare(e1.getElement(), e2.getElement());
            ///ystem.err.println(result);
            if(result == 0 && v1 != null && v2 != null) {
                // Finally we compare the values alphabetically.
                result = v1.compareTo(v2);
            }
            }
            else {
            return 0;
            }
        }
        }
        else {
        result = o1.toString().compareTo(o2.toString());
        }
        ///ystem.err.println("Result: " + result);
        return result;
    }
          
    /** Indicates whether some other object is "equal to" this Comparator. */
    public boolean equals(Object obj) { 
        return compare(this, obj) == 0;
    }
    }
}