Traversing multi-layer data structures using generic functions and indirect recursion.
Original Publication Date: 2004-Dec-02
Included in the Prior Art Database: 2004-Dec-02
The invention provides an algorithm for traversing multi-layered data structures with highly reusable code. Generic data structures exist that provide well defined traversing mechanisms. Upon using these data structures in a multi-layered fashion, there exist few simple traversing mechanisms for the buried structures. And as such, the routines coded for the traversing of buried structures are very specific and can rarely be used in other similar applications. This invention provides to the programmer flexible reusable code. Which results in increased productivity, reduced testing, and less code written.
Traversing multi-layer data structures using generic functions and indirect recursion .
The invention removes the knowledge of how the multi-layered structure is defined from the Traversing Algorithm into an Application Specific Function. Traversing Algorithm: These algorithms are defined simply to traverse (sequential, binary, etc.) a set of items. The Traversing Algorithm uses the Application Specific Function to determine when to stop and how to proceed. Application Specific Function: Though not recursive functions, these functions are written in accordance with recursive theory. These functions make decisions by case about when to stop (base case) and how the traversal will continue by calling or returning to the Traversing Algorithm based on a Tag (distinguishing characteristic).
For simplicity, further discussion of the Traversing Algorithm will be a sequential search type algorithm (figure 2) of the multi-layered linked lists in figure 1. The example Application Specific Function (figure 3) is defined to locate a C type item from the given multi-layered linked list. Where: Val is the distinguishing characteristic (Tag) of the item being searched for.
Fun is the Application Specific Function that determines if a match is found.
Curr is the current type of list being searched.
Want is the type of list a match will be found.
Figure 1 - Multi-Layered Linked Lists
Figure 2 - Sequential Search (Traversing Algorithm)
Figure 3 - Application Specific Function to find a C type item
-Since all the information about the data structure is in the Application Specific Function, the Traversing Algorithm is generic and reusable for data structures other than the example given. -The Application Specific Function example can locate a C type item from an A type list, B type list or C type list. Thus, the Application Specific Function is also reusable under different circumstances. -Other Application Specific Functions can be written to locate A or B type items without modifying the Traversing Algorithm. -Application Specific Functions can be written to call other Traversing Algorithms