XAAL Documentation - Data Structures

Data Structures

XAAL supports the usage of data structures to specify the animations lowering the effort needed to produce them. The set of structures is basically the same as, for example, in JAWAA: array, graph, list, and tree. As with the graphical primitives, these also include some extensions of other structures. For example, a tree is a special case of a graph, but has been included in the language to ease the use.

Common Content

All the data structures in XAAL have some common content, and this subsection describes the common elements. First of all, all structures can include a description of the element using the narrative element. This element can contain text and XHTML elements. The structure can also contain a coordinate specification to position the structure, as well as a style definition.

The structure-property element represents a name-value pair. This can be used to provide the application with some extra information about the structure. This can be, for example in case of MatrixPro, information about the layout to use for the structure or the actual data structure to use (for example, AVL-tree).

Structures have also several common attributes. These attributes are described in Table 1.

Table 1: Common attributes of structures.
Name Description
id ID of the structure. This must be unique throughout the instance document.
ref Reference to an existing structure that this makes a new visualization for. If this is used, the referencing visualization should change when the referenced visualization is modified.
style The style used with this structure.

To support the different approaches of existing algorithm animation languages, all structures support an optional graphical presentation of the structure indicating how the structure should be visualized. This information can be included using the graphical element. This element can contain all the graphical primitives and transformations on them.

Common Building Blocks

The actual content of the structures is contained in nodes (or, for arrays, in indices) and keys. The next few paragraphs describe these common building blocks.

Node

Node is the basic building block used in all the structures, except for the array. A node can contain any of the structures, which again can contain nodes. This way, the language allows arbitrarily complex structure hierarchies. In addition to the common attributes, the node element can have an attribute label to attach a textual description to the node. The listing below gives two examples of simple node specifications.

<node id="node1" label="node">
  <narrative xmlns:xhtml="http://www.w3.org/1999/xhtml">
     description of the <xhtml:em>node</xhtml:em>
  </narrative>
  <key value="K"/>
</node>
<node id="node2">
  <array>
    ...
  </array>
</node>

Index

The element index is used to describe the contents of an array. Basically, an index is like a node. It has, however, an additional attribute also called index that can be used to set the position of the element in the enclosing array. The label attribute is used when painting indexed arrays. Listing below gives an example that specifies an index with label C and position 3.

<index id="iC" index="3" label="C">...</index>

Key

Keys are the elements in XAAL that are used to store the primitive data that has no internal structure. The data is stored as an attribute value.

Edge

The element edge is used to represent a binary connection between two nodes. Edge can exist only between two nodes (which can be the same) specified using the from and to attributes. Whether or not the edge is directed can be controlled with the directed attribute. Following listing gives an example of an edge between the two nodes specified in the node example earlier. The edge in the example includes also the graphical representation.

<edge from="node1" to="node2" directed="true">
  <graphical>
    <line>
      <coordinate x="20" y="20"/>
      <coordinate x="70" y="55"/>
      <style><arrow forward="true"/></style>
    </line>
  </graphical>
</edge>

Array

An array is represented in XAAL using element array. Array consists of index elements containing the data. It has also attributes to specify the indexing, orientation, and size of the array. Following XML code fragment gives an example of an array of size 7 with three index elements.

Array example<array indexed="false" size="7" orientation="horizontal">
  <index index="0"><key value="A"/></index>
  <index index="1"><key value="B"/></index>
  <index index="4"><key value="C"/></index>
</array>

Graph

Graph is a structure consisting of a set of nodes connected by edges. In XAAL, a graph is represented using element graph. The content of the graph is included using node and edge tags. Example below shows a specification of a graph in XAAL.

Graph example<graph>
  <node id="n1"><key value="D"/></node>
  <node id="n2"><key value="E"/></node>
  <node id="n3"><key value="M"/></node>
  <node id="n4"><key value="O"/></node>
  <edge from="n1" to="n2" directed="true"/>
  <edge from="n2" to="n3" directed="true"/>
  <edge from="n3" to="n4" directed="true"/>
  <edge from="n4" to="n1" directed="true"/>
</graph>

List

A list is a data structure consisting of a set of nodes and edges connecting the nodes. In XAAL, we do not set any restrictions on the list (such as, can it be doubly linked). Thus, a list is as a graph, included only to provide a more natural way to describe lists with an element list. Element list has also an attribute to specify the orientation. This is the same as the orientation attribute for array.

Tree

Tree is an important and often used data structure and is available in some of the existing AA languages. A tree consists of a set of nodes connected by edges. Tree is headed by a single root node. In a legal tree, only one path exists between any two nodes in the tree.

In XAAL, a tree is represented using an element tree. The content of the tree consists of node and edge elements. The root of the tree is specified using root attribute.