3.5.3.1 Hierarchies

The data structures have to fulfill the following criteria:

• The hierarchies have to be mapped properly preserving the order of the items.
• Movement in the hierarchy must be possible and has to be implemented efficiently.
• Given its full name, an item has to be found quickly.

For each item its name, its location in the hierarchy, and its properties like the expression in variables or the inheritance scheme for sections have to be stored. To store the inheritance a simple reference to the base-section is necessary. The management of hierarchies requires a hierarchical data structure. For the Input Deck database a special kind of tree has been chosen. The nodes of the tree are formed by the database entries: a node can either be a variable or a section. An example of such a tree is given in Fig. 3.9(a) for the hierarchy

First
{  a = 1;
   Empty
   {
   }
}
Second
{  More
   {  r = 2;
      s = 3;
   }
   x = 4;
   y = 5;
}

Figure 3.9: Hierarchies in the Input Deck database.

(a)  Hierarchy.

(b) Linked items in the Input Deck tree.

The tree shown is not a binary tree since a node may have one ore two successors. A successor which has the same level in the hierarchy is termed sibling. Variables only have a sibling which is the next item in order. Sections have two successor which are the next item in order (the sibling) and the first item inside the section termed child.

To be able to find both the previous and the next sibling in order of a certain item the edges between siblings are implemented as dual linked lists [117]. Moreover, to quickly find the predecessor of a certain item each item stores a reference to its predecessor. The resulting tree is shown in Fig. 3.9(b).

Due to this approach an efficient movement inside the tree is guaranteed. To find all items inside a section or to explore the hierarchy of trees, iterators can be used.