|
|
|
|
|
|
Categories of Abstract Data Type Operations |
|
|
|
|
|
|
|
|
|
In general, the basic operations that are performed on an abstract data type fall into three categories: constructors, transformers, and observers. |
|
|
|
|
|
|
|
|
|
Constructor An operation that creates a new instance (variable) of an ADT |
|
|
|
|
|
|
|
|
|
Transformer An operation that builds a new value of the ADT, given one or more previous values of the type. |
|
|
|
|
|
|
|
|
|
An operation that creates a new instance of an ADT (such as a list) is a constructor. Operations that insert an item into a list and delete an item from a list are transformers. An operation that takes one list and appends it to the end of a second list is also a transformer. |
|
|
|
|
|
|
|
|
|
Observer An operation that allows us to observe the state of an instance of an ADT without changing it. |
|
|
|
|
|
|
|
|
|
A Boolean function that returns TRUE if a list is empty and FALSE if it contains any components is an example of an observer. A Boolean function that tests to see if a certain value is in the list is another observer. |
|
|
|
|
|
|
|
|
|
Some operations are combinations of observers and constructors. An operation that takes two lists and merges them into a (new) third list is both an observer (of the two existing lists) and a constructor (of the third list). |
|
|
|
|
|
|
|
|
|
In addition to the three basic categories of ADT operations, there is a fourth category that is less common: iterators. |
|
|
|
|
|
|
|
|
|
Iterator An operation that allows us to process-one at a time-all the components in an instance of an ADT. |
|
|
|
|
|
|
|
|
|
An operation that returns the first item in a list when it is called initially and returns the next one with each successive call is an iterator. |
|
|
|
|