Navigator pattern

This article publishes a draft of a previously unreleased object-oriented design pattern

See also UML diagrams of the Navigator pattern on the next pages

The Navigator design pattern is a way to apply a separated algorithm to an object graph. That algorithm implements the behavior that otherwise would be implemented in the object graph itself (in an object-oriented design) or that would be implemented in general behavior classes (like services). The Navigator pattern consists of two sides: on one side the navigator, which implements the behavior that shall be applied, and on the other side the navigable, which represents an object graph that shall be traversed by the navigator in order to apply its behavior. The traversal of a navigable by a navigator is called navigation.

It is crucial for the Navigator pattern that the navigator determines the navigation, which means the navigator can control by its own behavior if and how it traverses the object graph, e.g. the navigator might omit individual nodes of that graph, the navigator might navigate the nodes in different orders, etc. To give the navigator the control over the navigation, the navigator gets the next nodes known to the current node (child nodes) from that current node. The navigator can then sort, filter, etc. these nodes before proceeding to the node which then is the next one. Therefore, each navigable node must implement an operation to get its children (or next navigables) to the navigator.

Another crucial ability of the navigator is to enter a navigable before proceeding to its children and after the navigation on these children. That means the navigator enters the (parent) navigable, then navigates its navigable children and then reenters the (parent) navigable. This way the navigator can apply behavior twice for each node in a graph. The first entry into a navigable is typically used to prepare the traversal of the children of that navigable, also by adding new children to that navigable, while the reentry is typically used to evaluate states and to finalize the navigation. By adding new children on the first entry, the navigator extends the object graph with nodes which the same navigator will traverse in the next step. Therefore a navigator can effectively build up and evaluate an object graph within one single run. But in most cases of navigations the complete object graph is already given, typically as a domain model, data transfer object structure or the like.

In the Navigator pattern the client which uses (and typically creates) the navigator invokes the respective "navigate" operation of the navigator by passing the navigable as an argument. That navigable is then considered as the root navigable of the object graph it represents. For instance with a model of a tree with trunk, branches and leafs, the client would pass the trunk to the navigator and the navigator traverses the trunk, all branches and all leafs. Passing the navigable to the navigator and not vice versa, allows for a generalized behavior at that point. The "navigate" operation can be implemented by a navigator generalization and further features can be added.

After the navigator received the root navigable from the client, the navigator will pass itself to that root navigable, just to enable the root navigable to pass itself as well, but with its concrete type, back to the navigator, which implements an overloaded operation for each concrete type of navigables. This realizes a double dispatch, where the behavior that is applied to a certain navigable is choosen by the concrete navigator type and the concrete navigable type.