Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Tree Traversal Techniques to Implement Enhanced Searches in Tree View

IP.com Disclosure Number: IPCOM000114887D
Original Publication Date: 1995-Feb-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 185K

Publishing Venue

IBM

Related People

Johnson, DK: AUTHOR [+2]

Abstract

Disclosed is a description of how an application can manually implement the forward and backward traversal techniques necessary to provide multi-character search support for tree view containers.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 31% of the total text.

Tree Traversal Techniques to Implement Enhanced Searches in Tree View

      Disclosed is a description of how an application can manually
implement the forward and backward traversal techniques necessary to
provide multi-character search support for tree view containers.

      Objects in a container in an OS/2* Presentation Manager* (PM)
application can be presented in several different views.  One of
these views is tree view, applicable when the objects have
interrelationships among each other of parent, child and sibling.
Each object can be represented as a node in the tree.

      Each node which has children can be displayed either expanded,
with its children visible in a branch below it, or unexpanded, with
its children hidden from view.  A node with no children is considered
a terminal node, and terminal nodes can exist at any level of the
tree.

      One of the capabilities that users of an application require is
the means to search through the visible nodes of a tree based on the
text associated with each node.  PM supplies a rudimentary search
capability based on the first character of the text.  The search
capability provided by PM has no provision for searching on more than
one character, and has no capability for searching backwards through
the tree.  For users that have a large number of nodes in the tree,
both of these capabilities are essential.

      To provide the enhanced search capability demanded by users, an
application must implement the search itself rather than relying on
that provided by PM.  Only records that are shown, that is, their
ancestor nodes are all expanded, are acceptable results of the
search.  PM does this correctly in their single character search, but
manual implementation of the required tree traversal in the most
efficient manner is quite complex.

      PM provides the CM_SEARCHSTRING message that when sent to a
container with a pointer to a given record will return the next
record in the tree whose text starts with the text also passed in the
message.  This message traverses the tree correctly.  However, its
most serious shortcoming is that it returns the next match regardless
of whether the node is visible and therefore an acceptable result of
the search.  It also has no provision for searching backwards through
the tree.

      There is no way to ask PM if a given node is currently visible
in the tree; no message to send, and no flag to check.  There is a
flag that will tell you if a node that has a branch is expanded, but
not whether that node is currently visible.  The branch will show as
expanded even if a node above it is not expanded and thus the
expanded branch is not visible.

      The application could query up the parent chain of the found
node using the CM_QUERYRECORD message with the CMA_PARENT parameter,
checking at each branch node to see if that branch was expanded, and
repeating this up each level until the expanded root is reached. ...