Operation - sellout/data-structure-zoo GitHub Wiki
The operations for ADTs frequently have many names. Not all the names here may match up with the ones you are used to, but Iβve tried to make them clear and consistent, while distinguishing persistent and mutable versions where necessary. If an operation is labeled βpureβ, that means it returns a new instance of the data structure with the requested change, and also that a mutating version of the operation exists as well (particular data structures may offer only pure or mutating operations, while others may offer both, potentially with different time complexity). If an operation is labeled βmutatingβ, that operation does not have a pure version. Operations labeled βidempotentβ are non-mutating in both pure and mutating data structures.
Sometimes, a pure data structure may provide βunsafeβ operations that mutate the data structure, but in such a way that the original data structure is corrupted and no longer usable. These operations allow for performance improvements in critical sections, when it is known that no one else is holding a reference to the original data structure (or any sub-part of it). These are distinct from the normal mutating operations in that they must return a new data structure as a result and the structure passed as a parameter can not be used instead. These operations arenβt listed here, but are mentioned when a data structure provides them.
fundamental operations
Fundamental operations are operations that are necessary for the data structure to be complete.
[bind](/sellout/data-structure-zoo/wiki/bind) key value containerβ pure[chop](/sellout/data-structure-zoo/wiki/chop) containerβ pure[chop back](/sellout/data-structure-zoo/wiki/chop-back) containerβ pure[chop front](/sellout/data-structure-zoo/wiki/chop-front) containerβ pure[chop optimum](/sellout/data-structure-zoo/wiki/chop-optimum) containerβ pure[empty?](/sellout/data-structure-zoo/wiki/empty?) containerβ idempotent[insert](/sellout/data-structure-zoo/wiki/insert) value position containerβ pure[index](/sellout/data-structure-zoo/wiki/index) position containerβ idempotent[lookup](/sellout/data-structure-zoo/wiki/lookup) key containerβ idempotent[member?](/sellout/data-structure-zoo/wiki/member?) value containerβ idempotent[peek](/sellout/data-structure-zoo/wiki/peek) containerβ idempotent[peek back](/sellout/data-structure-zoo/wiki/peek-back) containerβ idempotent[peek front](/sellout/data-structure-zoo/wiki/peek-front) containerβ idempotent[peek optimum](/sellout/data-structure-zoo/wiki/peek-optimum) containerβ idempotent[pop!](/sellout/data-structure-zoo/wiki/pop!) containerβ mutating[pop back!](/sellout/data-structure-zoo/wiki/pop-back!) containerβ mutating[pop front!](/sellout/data-structure-zoo/wiki/pop-front!) containerβ mutating[pop optimum!](/sellout/data-structure-zoo/wiki/pop-optimum!) containerβ mutating[push](/sellout/data-structure-zoo/wiki/push) value containerβ pure[push back](/sellout/data-structure-zoo/wiki/push-back) value containerβ pure[push front](/sellout/data-structure-zoo/wiki/push-front) value containerβ pure[rebind](/sellout/data-structure-zoo/wiki/rebind) key value containerβ pure[remove](/sellout/data-structure-zoo/wiki/remove) position containerβ pure[unbind](/sellout/data-structure-zoo/wiki/unbind) key containerβ pure
secondary operations
Secondary operations don't need to be implemented as part of the data structure β they can be implemented in the ADT via existing fundamental operations β however, an implementation on the underlying data structure may improve performance. EG, [merge](/sellout/data-structure-zoo/wiki/merge) on the heap ADT can be implemented by [push](/sellout/data-structure-zoo/wiki/push)ing all the values from the existing heaps onto a new empty heap, which is O(n) at best, but when both heapss are Brodal queues, merge can be implemented in O(1).
[concantenate](/sellout/data-structure-zoo/wiki/concantenate) first secondβ pure[merge](/sellout/data-structure-zoo/wiki/merge) a bβ pure