Efficient Tree Sort

Question

I'm not really happy with my methods to build a tree structure in my J2ME Application. Can anybody point in a more performant direction? If you need some more code to understand my snippets, just comment below. Java Version is 1.4.

Many thanks,
rAyt

if(companyList != null) {
    companyList.setNodeStructure(null);

    Hashtable nodes = new Hashtable();
    for(Enumeration e = companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company)e.nextElement();
        if(temp_comp.getParentCompanyId() == 0 && temp_comp.getCompanyId() > 0) {
            getSubTree(temp_comp.getCompanyId(), companyList, nodes); 
        }
    }   
    companyList.setNodeStructure(nodes);

Methods

private void getSubTree(int CompanyId, CompanyList _companyList, Hashtable nodes) {
    Vector children = getChildren(CompanyId, _companyList);
    if(children.size() > 0) {
        nodes.put(new Integer(CompanyId), children);
        for(Enumeration e = children.elements(); e.hasMoreElements();) {
            Company temp_comp = (Company)e.nextElement();
            getSubTree(temp_comp.getCompanyId(), _companyList, nodes);
        }
    }
}

private Vector getChildren(int CompanyId, CompanyList _companyList) {
    Vector temp = new Vector();
    for(Enumeration e = _companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company)e.nextElement();
            if(temp_comp.getParentCompanyId() == CompanyId) {
                temp.addElement(temp_comp);
            }
        }
    temp.trimToSize();
    return temp;
}

Answer 1

getChildren() could be much more efficient. It looks like, every time you call it, you're iterating through the entire CompanyList to find the ones whose parent matches the given CompanyId. That just screams for a Hashtable filled with Vectors. The Hashtable keys would be the parent ID, not the original ID; the values would be vectors that contain the company's whose parent ID matches the given parent ID. Then you have:

private Vector getChildren(int CompanyId, Hashtable companyParentLoookup) {
    return (Vector) companyParentLookup.get(CompanyId);
}

Of course, it looks like your objective in writing getSubTree is actually to construct the Hashtable I just described. The problem here is that you're trying to construct it company-ID by company-ID, rather than Company by Company. You could try this instead, to construct the companyParentLookup:

private Hashtable calcLookupTable(CompanyList _companyList) {
    Hashtable retval = new Hashtable();
    for (Enumeration e = _companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company) e.nextElement();
        Integer parent_id = temp_comp.getParentCompanyID();

        if (retval.containsKey(parent_id) == false) {
            retval.put(parent_id, new Vector());
        }
        retval.get(parent_id).add(temp_comp);
    }
    return retval;
}

You can then stick the companyParentLookup structure directly into companyList's nodeStructure.

EDIT: The relevant point here is that you can lazy-initialize the Hashtable's vector entries as you need them; each time you can just check if the Hashtable has the needed entry, and if it doesn't, you just throw it in. This is what allows you to create the Hashtable by iterating on the companies as children rather than iterating on them as parents. If you really can't use anything but Hashtables and Vectors, then this is not a bad way to implement a tree; it's roughly equivalent to keeping a graph data structure using adjacency lists. I actually wrote something that looks very much like this for a graph data structure, albeit with HashMaps.

Er, does that help?