Efficient Manipulation of Bounded Ada Data Structures
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
This disclosure describes a set of related programming methods to support more efficient implementations of bounded versions of reusable Ada components covering a wide variety of data structures.
Efficient Manipulation of Bounded
disclosure describes a set of related programming methods
to support more efficient implementations of bounded versions of
Adacomponents covering a wide variety of data structures.
methods are loosely based on those used by Grady
Booch and described in his book entitled "Software Components with
Ada" (Benjamin/Cummings Publishing Company, 1987).
components for bounded data structures typically
use algorithms that result in excessive movement and/or comparison of
potentially large data areas, thereby significantly reducing their
efficiency. The methods described below for bounded data structures
solve the major performance problems inherent in existing algorithms
a la Booch by eliminating (or greatly reducing) memory-to-memory data
manipulations, thus resulting in significant performance improvement.
bounded data structure algorithms use fixed-length
arrays and maintain associated information about which array element
is currently the last "used" by the structure. To improve
performance, a small amount of additional information about the
contents of the array is maintained in order to be able to process
operations on the data structure much more efficiently. For example,
where Booch moves all of the elements of a queue when the top element
is popped, it is more efficient to keep extra information about which