Hierarchical Collections

Represents a hierarchical collection of data.

Many efficient data structures naturally contain some hierarchy. Examples include B-trees, adjacency lists in graphs, and elements within a hash table (if using bucket chaining). By explicitly encoding the hierarchical nature of a collection into the the static type, more efficient algorithms are possible to express.

For additional details, please see:

• “Segmented Iterators and Hierarchical Algorithms”, Matthew H. Austern, 2000.
• “Hierarchical Data Structures and Related Concepts for the C++ Standard Library”, Reiter & Rivera, 2013.

Note: due to limitations in Swift’s type system, a single type cannot be both a HierarchicalCollection and a Collection.

When conforming to HierarchicalCollection, only forEachWhile and count are required.

See more

public protocol HierarchicalCollection

MutableHierarchicalCollection extends HierarchicalCollections to allow mutation of contents.

While many algorithms simply query the data structure in order to do their work, some algorithms modify the data structure. This protocol abstracts over a set of common mutation operations of hierarchical data structures.

See more

public protocol MutableHierarchicalCollection : HierarchicalCollection

A dynamically-sized double-ended queue that allows pushing and popping at both the front and the back.

See more

public struct Deque<Element>

extension Deque: Queue

extension Deque: HierarchicalCollection

A fixed-size, contiguous collection allowing additions and removals at either end (space permitting).

Beware: unbalanced pushes/pops to either the front or the back will result in the effective working size to be diminished. If you would like this to be managed for you automatically, please use a Deque.

See more

public struct DoubleEndedBuffer<T>

extension DoubleEndedBuffer: Collection

Describes where the initial insertions into a buffer should go.

See more

public enum DoubleEndedAllocationPolicy

A hierarchical collection composed of T hierarchical collections.

See more

public struct HierarchicalArray<T> : HierarchicalCollection where T : HierarchicalCollection

LeafArray wraps an Array to form a HierarchicalCollection.

LeafArray is a “bottom” type within a HierarchicalCollection.

See more

public struct LeafArray<Element> : HierarchicalCollection