Tree Component Alternatives to the Composite Design Pattern

Files
TR Number
Date
2008-12-03
Journal Title
Journal ISSN
Volume Title
Publisher
Virginia Tech
Abstract

The Composite design pattern is commonly employed in object-oriented languages to design a system of objects that form a part-whole hierarchical structure with composite objects formed out of primitive objects. The client does not differentiate between a composite object and a primitive object. The composite hierarchy effectively forms a tree-like hierarchical grouping of objects. From a software engineering perspective, there are at least two problems with the Composite pattern. First, it does not maintain a separation of concerns between the structure of the objects in a system and the objects themselves. The objects that comprise the system contain information about their relationship to other objects. This limits the ability of programmers to reuse the system's structural information. Secondly, there is no mechanism for encapsulating the system as a whole. This makes it difficult to specify and reason about global system properties. This thesis presents two tree components that can be used as alternatives to the Composite design pattern in systems that are traditionally implemented with the pattern. Both components are data structures that can contain arbitrary objects and maintain the structure of those objects as an ordered-tree. Since the components encapsulate only the tree structure, they only need to be specified and verified once, and they are available for black-box reuse. The first component is a traversable tree that maintains a conceptual "cursor" position. Methods are provided for inserting and removing objects at the cursor position, and for moving the cursor throughout the tree. The second component extends the traversable tree. A formal specification for each tree component is presented in the Tako language — a Java-like language with alias avoidance that is designed to facilitate specification and verification. A case study is presented that shows how the indexed tree can be used and reasoned about in an application — a text-based adventure game. Finally, a similar application is developed in Java, once using the composite pattern and once using the indexed tree data structure, and object-oriented metrics are given for both systems.

Description
Keywords
Formal Reasoning, Tako, Java, Design Patterns, Tree, Indexed Tree, Composite Pattern
Citation
Collections