HierarchicalCollection

public protocol HierarchicalCollection

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.

Show on GitHub

  • The type of element contained within this hierarchical collection.

    Declaration

    Swift

    associatedtype Element
    Show on GitHub

  • A cursor represents a location within the collection.

    Beware: mutations to the collection may invalidate the Cursor.

    Declaration

    Swift

    associatedtype Cursor : Comparable
    Show on GitHub

  • The total number of elements within this collection.

    Beware: this might be O(n) in some collections!

    Declaration

    Swift

    var count: Int { get }
    Show on GitHub

  • Call fn for each element in the collection until fn returns false.

    Declaration

    Swift

    @discardableResult
func forEachWhile(startingAt start: Cursor?, _ fn: (Element) throws -> Bool) rethrows -> Cursor?

    Parameters

    start

    Start iterating at elements corresponding to this index. If nil, starts at the beginning of the collection.

    Return Value

    a cursor into the data structure corresponding to the first element that returns false.

    Show on GitHub
  • forEach(_:) Default implementation

    Call fn for each element in the collection.

    Note: this is identical to Sequence.forEach, however we cannot re-use the name.

    Default Implementation

    Declaration

    Swift

    func forEach(_ fn: (Element) throws -> Void) rethrows
    Show on GitHub
  • firstIndex(where:) Default implementation

    Finds the first index where predicate is true, and returns a cursor that points to that location. If predicate never returns true, nil is returned.

    Default Implementation

    Declaration

    Swift

    func firstIndex(where predicate: (Element) throws -> Bool) rethrows -> Cursor?
    Show on GitHub
  • flatten() Default implementation

    Copies all elements in this hierarchical data structure into a flat array.

    Default Implementation

    Declaration

    Swift

    func flatten() -> [Element]
    Show on GitHub
  • flatten(into:) Default implementation

    Copies all elements in this hierarchical data structure into the end of a collection.

    Default Implementation

    Declaration

    Swift

    func flatten<T>(into collection: inout T) where T : RangeReplaceableCollection, Self.Element == T.Element
    Show on GitHub
  • mapAndFlatten(_:) Default implementation

    Applies fn on each element in the collection, and concatenates the results.

    Default Implementation

    Declaration

    Swift

    func mapAndFlatten<T>(_ fn: (Element) throws -> T) rethrows -> [T]
    Show on GitHub
  • compactMapAndFlatten(_:) Default implementation

    Applies fn on each element in the collection, and concatenates the non-nil results.

    Default Implementation

    Declaration

    Swift

    func compactMapAndFlatten<T>(_ fn: (Element) throws -> T?) rethrows -> [T]
    Show on GitHub