Latest revision as of 12:22, 22 December 2012

The Tree Library implements a model of edge-labelled trees, and related tools. It is a shared dependency for the components of a subsystem that provides data access under this model, including the Tree Manager services, the Tree Manager Framework, the Tree Manager Library and its clients.

The library is available in our Maven repositories with the following coordinates:

<groupId>org.gcube.data.access</groupId>
<artifactId>trees</artifactId>
<version>...</version>

Source code and documentation are also available in the repositories as secondary artefacts with classifiers sources and javadoc, respectively:

<groupId>org.gcube.data.access</groupId>
<artifactId>trees</artifactId>
<classifier>sources</code>
<version>...</version>
 
<groupId>org.gcube.data.access</groupId>
<artifactId>trees</artifactId>
<classifier>javadoc</code>
<version>...</version>

Trees

The library implements a model of node-attributed, leaf-valued , edge-labelled, and directed trees. In particular:

• nodes may have an identifier and a number of uniquely named attributes;
• edges have a label;
• leaves may have a value;
• roots may identify the source of origin.

Moreover:

• identifiers, attributes, and leaves have text values;
• attribute names and labels may be namespaced.

The model is implemented in code by the following classes:

Nodes are either InnerNodes or Leafs. InnerNodes have zero or more Edges, each of which has a label and target Node. Attributes and identifiers are common to all Nodes, while only Leafs have values. Trees are InnerNodes with source identifiers, and serve as tree roots.

Instances of model classes are mutable, in that we can:

• add and remove attributes and edges;
• change the value of attributes and leaves;
• change source identifiers;

Note however that node identifiers and edge labels are assigned at creation time and cannot be changed thereafter.

We can also:

• compare instances for equivalence (instances override equals());
• use them as keys in hash-based structures (instances override hashcode());
• publish their state for debugging purposes (instances override toString()).

Building Trees

We can construct trees in a standard object-oriented fashion, using any of the overloaded constructors common to all model classes (including copy constructors), e.g:

Tree tree = new Tree("rootId");
tree.setAttribute(new QName("x"),"...");
tree.setAttribute(new QName("http://foo.org","y"), "...");
tree.setSourceID("sourceId");
Leaf leaf1 = new Leaf("id1");
leaf1.value("..."); 
Leaf leaf2 = new Leaf("...");
leaf2.value("true");
Edge e1 = new Edge(new QName("a"),leaf1);  //unqualified
Edge e2 = new Edge(new QName("http://bar.org","b"),leaf2);
tree.add(e1,e2)

Overloaded constructors simplify object creation, e.g.:

Tree tree = new Tree("rootId",
		new Edge("a", new Leaf("id1","...")),
		new Edge("http://bar.org","b", new Leaf("id2","...")));
 
tree.setAttribute("x","...");
tree.setAttribute("http://foo.org","y","...");
tree.setSourceID("sourceId");

We find details on individual constructors and mutators in the in Javadoc documentation.

Alternatively, we can adopt a more functional style, importing the static builder methods of the Nodes class and composing them in inlined tree expressions, e.g:

import static org.gcube.data.trees.data.Nodes.*;
…
Tree tree = attr(t("sourceId","rootId",
			e("a","..."), 
			e(q("http://bar.org","b"),"...")),
                   a("x",1),a(q("http://foo.org","y"),"..."));

The functional style is far less verbose, and is particularly suited for testing. t(), a(), e(), and q() are examples of Node, attribute, Edge and QName builders, respectively. We use them to avoid the new operator for those types. They also perform object-to-string conversions.

We show some further sample expressions below, while details on all the available builders are in the Javadoc documentation of the Nodes class:

//child-less root: t() is a tree builder
Tree tree = t();
 
//with identifier
tree = t("id1");
 
//with identifier and provenance
tree = t("source","id1");
 
//with a simple child: e() is an edge builder
tree = t(e("a",1));
 
//with a qualified edge label: q() is a QName builder
tree = t(e("http://acme.org","a",1));
 
//with a second, identified simple child: l() is a leaf builder
tree = t(
          e("a",1),
          e("b",l("id2","foo")));
 
//with a complex child: n() is an inner node builder
tree = t(
           e("a",
             n(
               e("b",1))));
 
//with attributes: a() is an attribute builder, attr() is attribute-decorator for nodes
tree = attr( t(....),
             a("a1","3"),
             a(q("http://acme.org","a2"),"foo"));
 
//with an attributed child
tree = t(
          e("a", 
              attr(l("foo"),a("b1","3"),a("b2","bar"))));

We can of course mix object-oriented and functional style.

Inspecting and Traversing Trees

Given any Node, we can:

• inspect its identifier (id());
• inspect its attributes( attributes(), attribute(QName), hasAtttribute(QName));
• inspect its ancestors (ancestors(), ancestorAndSelf())
• move to its parent Node, if any exists ( parent());

note: for convenience, all methods that take QNames are overloaded to accept unqualified names, as well as (namespace,local name) pairs. This also applies to QName-based methods discussed below.

Given an InnerNodes we can also:

• inspect its children (children(),children(QName), children(Class<? extends Node>), <code>children(Class<? extends Node,QName>));
• move to its children (child(QName), child(Class<? extends Node>,QName));
• inspects its descendants along paths of edge labels (descendants(), descendants(QName...), descendants(Class<? extends Node>,QName...));
• move to its descendants along paths of node identifiers (descendant(String...), descendant(Class<? extends Node>, String));
• inspect its edges (edges(), edges(QName));
• move along its edges (edge(QName), hasEdge(QName));
• inspect the labels of its edges (labels(), labels).

note: methods that return non-List values fail with an IllegalStateException whenever the input is ambiguous, e.g. child(QName) fails if there is more than one edge with the given label;

note: methods that take Class<? extends Node> parameters filter the output to contain only instances of the input class, i.e. only InnerNodes or Leafs). For fluency, the constants Nodes#N and Nodes#L can be used in lieu of, respectively, InnerNode.class, Leaf.class, e.g.:

import static org.gcube.data.trees.data.Nodes.*;
 
...
 
Node n = ...
List<InnerNode> complexChildren = n.children(N);
Leaf leaf = n.child(N,"a").child(N,"b").child(L,"c");

note: all methods that take QNames accept regular expressions, both on the namespace and the local name of the label, e.g.:

import static org.gcube.data.trees.data.Nodes.*;
 
...
 
Node n = ...
List<Node> bChildren = n.children("b.*");

Finally, we can:

• inspect the value of a Leaf (value());
• inspect the provenance of a Tree (sourceId());
• inspect that label of an Edge (label());
• move to the target Node of an Edge (target()).

Some further examples:

import static org.gcube.data.trees.data.Nodes.*;
 
Tree tree = attr(t("1",
		e("a",l("2",5)),
		e("b",attr(
				n("3",e("c",4)),
			  a("foo",0))),
		e("c",5)),
           a("x",0));
 
//typed children
String val = doc.child(L,"a").value();
 
//typed descendant
String val2 = tree.descendant(N,"3").child(L,"c").value();
 
for (InnerNode node : tree.children(N))
	for (QName l : node.labels())
		//process label
 
for (Node n : tree.descendants("b","e"))
	for (Edge siblingEdge : n.parent().edges()) 
		if (siblingEdge.target()!=n)
		//process sibling of descendant

XML Bindings

Trees have straightforward XML representations. Nodes become elements and are named after incoming edges, attributes become element attributes. Moreover:

• the root element is arbitrarily named;
• the content of Leaf elements are Leaf values;
• the content of InnerNode elements is the representation of InnerNode's children;
• node identifiers become attributes called http://gcube-system.org/namespaces/data/trees:id;
• source identifiers become attributes called http://gcube-system.org/namespaces/data/trees:sourceId.

Thus one the sample trees discussed above:

attr(t("sourceId","rootId",
		e("a","..."), 
		e(q("http://bar.org","b"),"...")),
        a("x",1),a(q("http://foo.org","y"),"..."));

can be represented in XML as follows:

<t:root xmlns:t="http://gcube-system.org/namespaces/data/trees" 
            xmlns:foo="http://foo.org" 
            t:id="rootId" t:sourceId="sourceId" 
            x="1" foo:y="...">
     <a>...</a>
     <bar:b xmlns:bar="http://bar.org">...</bar:b>
</t:root>

Note that there is no explicit trace in the representation of node or edge concepts. In this sense, it is a "natural" representation, rather than a "serialisation". This means that we can easily parse and manipulate trees with any XML parsing tool.

Patterns