### Combinatorial Testing Example Source: https://github.com/apple/swift-collections/blob/main/Documentation/Internals/README.md An example of using `withEveryDeque`, `withEvery`, and `withLifetimeTracking` for exhaustive combinatorial testing of collection operations, including variations like shared storage. ```swift func test_popFirst() { withEveryDeque("deque", ofCapacities: [0, 1, 2, 3, 5, 10]) { layout in withEvery("isShared", in: [false, true]) { isShared in withLifetimeTracking { tracker in var (deque, contents) = tracker.deque(with: layout) withHiddenCopies(if: isShared, of: &deque) { deque in let expected = contents[...].popFirst() let actual = deque.popFirst() expectEqual(actual, expected) expectEqualElements(deque, contents) } } } } } ``` -------------------------------- ### Swift Set Mutation and Diffing Example Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md This example demonstrates a scenario where a set is mutated iteratively, and differences are calculated against a previous state. It highlights potential performance issues with standard Set operations. ```swift typealias Model = Set var _state: Model // Private func updateState( with model: Model ) -> (insertions: Set, removals: Set) { let insertions = model.subtracting(_state) let removals = _state.subtracting(model) _state = model return (insertions, removals) } let c = 1_000_000 var model: Model = [] for i in 0 ..< c { model.insert(i) let r = updateState(with: model) precondition(r.insertions.count == 1 && r.removals.count == 0) } ``` -------------------------------- ### Configure Swift Collections CMake Source: https://github.com/apple/swift-collections/blob/main/cmake/modules/CMakeLists.txt Configures the SwiftCollectionsConfig.cmake file. This is typically part of the build system setup. ```cmake set(SWIFT_COLLECTIONS_EXPORTS_FILE ${CMAKE_CURRENT_BINARY_DIR}/SwiftCollectionsExports.cmake) configure_file(SwiftCollectionsConfig.cmake.in ${CMAKE_CURRENT_BINARY_DIR}/SwiftCollectionsConfig.cmake) ``` -------------------------------- ### Array Performance Issue Example Source: https://github.com/apple/swift-collections/blob/main/Sources/BasicContainers/BasicContainers.docc/BasicContainers.md Demonstrates a performance pitfall in standard Array where repeated subscript mutations within a loop can lead to costly full array copies due to copy-on-write semantics. ```swift var items = Array(100 ..< 200) for i in items.indices { let old = items items[i] *= 2 // 🐌 precondition(old[i] != items[i]) } ``` -------------------------------- ### Add Swift Collections as a Package Dependency Source: https://github.com/apple/swift-collections/blob/main/README.md Integrate the Swift Collections package into your SwiftPM project by specifying its URL and version. This example shows how to add it as a dependency and link the 'Collections' product to your target. ```swift // swift-tools-version:6.3 import PackageDescription let package = Package( name: "MyPackage", dependencies: [ .package( url: "https://github.com/apple/swift-collections.git", .upToNextMinor(from: "1.5.0") // or `.upToNextMajor` ) ], targets: [ .target( name: "MyTarget", dependencies: [ .product(name: "Collections", package: "swift-collections") ] ) ] ) ``` -------------------------------- ### RigidArray Capacity Overflow Example Source: https://github.com/apple/swift-collections/blob/main/Sources/BasicContainers/BasicContainers.docc/BasicContainers.md Shows how RigidArray enforces a fixed capacity, leading to a runtime error when attempting to append elements beyond its initial or reallocated size. ```swift var items = RigidArray(capacity: 5, copying: 1 ..< 4) // 1, 2, 3 items.append(4) // OK items.append(5) // OK items.append(6) // runtime error: RigidArray capacity overflow ``` -------------------------------- ### Get Min and Max Elements Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Retrieves the smallest and largest elements from the Heap in constant time. Assumes the heap is not empty. ```swift var heap = Heap(1 ... 20) let min = heap.min // 1 let max = heap.max // 20 ``` -------------------------------- ### OrderedSet Keys View Example Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedDictionary.md The `keys` property returns an `OrderedSet` containing all keys in insertion order. This view is read-only. ```swift let d: OrderedDictionary = [2: "two", 1: "one", 0: "zero"] d.keys // [2, 1, 0] as OrderedSet ``` -------------------------------- ### UniqueArray Indices Source: https://github.com/apple/swift-collections/blob/main/Sources/BasicContainers/BasicContainers.docc/Extensions/UniqueArray.md Understand how to work with indices for accessing elements within a UniqueArray, including start, end, and general indices. ```APIDOC ## UniqueArray Indices ### Description Types and properties related to indexing elements in a `UniqueArray`. ### Types - ``Index`` ### Properties - ``startIndex`` - ``endIndex`` - ``indices`` ``` -------------------------------- ### BitSet Initialization Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitSet.md Methods for creating new instances of BitSet. ```APIDOC ## Initializers for BitSet ### Description Methods for creating new instances of BitSet. ### Topics - ``init()`` - ``init(reservingCapacity:)`` - ``init(_:)-(Sequence)`` - ``init(_:)-(Range)`` - ``init(_:)-(BitArray)`` - ``init(_:)-(BitSet.Counted)`` - ``init(bitPattern:)`` - ``init(words:)`` - ``random(upTo:)`` - ``random(upTo:using:)`` ``` -------------------------------- ### BitSet Initializers Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitSet.Counted.md Provides various ways to initialize a BitSet, from default empty sets to sets created from existing collections, bit patterns, or ranges. ```APIDOC ## Creating a Set ### Initializers - `init()`: Creates an empty BitSet. - `init(reservingCapacity:)`: Creates an empty BitSet with a specified capacity. - `init(_:)-(BitSet)`: Creates a BitSet from another BitSet. - `init(_:)-(BitArray)`: Creates a BitSet from a BitArray. - `init(_:)-(Range)`: Creates a BitSet from a range of integers. - `init(_:)-(Sequence)`: Creates a BitSet from a sequence of integers. - `init(bitPattern:)`: Creates a BitSet from a bit pattern. - `init(words:)`: Creates a BitSet from an array of words. ``` -------------------------------- ### Initialize Heap from Sequence Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Initializes a Heap from an existing sequence in linear time. Useful for bulk loading initial data. ```swift var heap = Heap((1...).prefix(20)) ``` -------------------------------- ### Initialize an Empty Heap Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Creates an empty Heap instance. Use this when you need to populate the heap incrementally. ```swift var heap = Heap() ``` -------------------------------- ### BitArray Initialization Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitArray.md Methods for creating and initializing a BitArray. ```APIDOC ## Creating a Bit Array ### Description Methods for creating and initializing a BitArray. ### Initializers - ``init()``: Creates an empty BitArray. - ``init(minimumCapacity:)``: Creates an empty BitArray with a specified minimum capacity. - ``init(_:)-(Sequence)``: Creates a BitArray from a sequence of booleans. - ``init(repeating:count:)``: Creates a BitArray with a specified value repeated a certain number of times. - ``init(_:)-(BitArray)``: Creates a BitArray by copying another BitArray. - ``init(_:)-(BitArray.SubSequence)``: Creates a BitArray from a subsequence of another BitArray. - ``init(_:)-(BitSet)``: Creates a BitArray from a BitSet. - ``init(bitPattern:)``: Creates a BitArray from a bit pattern. - ``randomBits(count:)``: Creates a BitArray with random bits of a specified count. - ``randomBits(count:using:)``: Creates a BitArray with random bits of a specified count using a given random number generator. ``` -------------------------------- ### OrderedSet Unordered View for SetAlgebra Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedSet.md Access the `unordered` property to get a SetAlgebra-conforming view of the OrderedSet, which ignores element order for equality and operations. ```swift var a: OrderedSet = [0, 1, 2, 3] let b: OrderedSet = [3, 2, 1, 0] a == b // false a.unordered == b.unordered // true func frobnicate(_ set: S) { ... } frobnicate(a) // error: `OrderedSet` does not conform to `SetAlgebra` frobnicate(a.unordered) // OK ``` -------------------------------- ### Mutable Values View Example Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedDictionary.md The `values` property provides a mutable random-access collection of the dictionary's values. Modifications to this view affect the original dictionary. ```swift d.values // "two", "one", "zero" d.values[2] = "nada" // `d` is now [2: "two", 1: "one", 0: "nada"] d.values.sort() // `d` is now [2: "nada", 1: "one", 0: "two"] ``` -------------------------------- ### Creating a Dictionary Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedDictionary.md Initializers for creating a new ordered dictionary, with options for capacity and handling duplicate keys. ```APIDOC ## Initializers ### `init()` Creates an empty ordered dictionary. ### `init(minimumCapacity:persistent:)` Creates an empty ordered dictionary with a specified minimum capacity. ### `init(uniqueKeysWithValues:)` Creates a new ordered dictionary from a sequence of key-value pairs, assuming all keys are unique. ### `init(uncheckedUniqueKeysWithValues:)` Creates a new ordered dictionary from a sequence of key-value pairs, without checking for duplicate keys. ### `init(uniqueKeys:values:)` Creates a new ordered dictionary from separate sequences of keys and values, assuming they have the same count and unique keys. ### `init(uncheckedUniqueKeys:values:)` Creates a new ordered dictionary from separate sequences of keys and values, without checking for duplicate keys or equal counts. ### `init(_:uniquingKeysWith:)` Creates a new ordered dictionary from a sequence of key-value pairs, resolving duplicate keys using a provided closure. ### `init(grouping:by:)` Creates a new ordered dictionary by grouping elements from a sequence based on a provided key-generating closure. ``` -------------------------------- ### Creating a Dictionary Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Initializers for creating new ShareableDictionary instances from various sources, including empty dictionaries, other dictionaries, sets of key-value pairs, and grouped elements. ```APIDOC ## Creating a Dictionary ### Initializers - `init()` - `init(ShareableDictionary)` - `init(Dictionary)` - `init(uniqueKeysWithValues: S)` where S conforms to `Sequence` and `S.Element` is `(Key, Value)`. - `init(S, uniquingKeysWith: (Value, Value) throws -> Value)` where S conforms to `Sequence` and `S.Element` is `(Key, Value)`. - `init(grouping: S, by: (S.Element) throws -> Key)` where S conforms to `Sequence`. - `init(keys: ShareableSet, valueGenerator: (Key) throws -> Value)` ``` -------------------------------- ### UniqueArray Ownership Example Source: https://github.com/apple/swift-collections/blob/main/Sources/BasicContainers/BasicContainers.docc/BasicContainers.md Illustrates how UniqueArray prevents the performance issue seen with standard Array by disallowing shared references, ensuring subscript mutations always have constant complexity. ```swift var items = UniqueArray(copying: 100 ..< 200) // `- error: 'items' used after consume for i in items.indices { let old = items // `- note: consumed here items[i] *= 2 // `- note: used here precondition(old[i] != items[i]) } ``` -------------------------------- ### Creating a ShareableDictionary Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Initializers for creating a new ShareableDictionary from existing collections or by providing unique keys. ```swift init() init(ShareableDictionary) init(Dictionary) init(uniqueKeysWithValues: S) init(S, uniquingKeysWith: (Value, Value) throws -> Value) rethrows init(grouping: S, by: (S.Element) throws -> Key) rethrows init(keys: ShareableSet, valueGenerator: (Key) throws -> Value) rethrows ``` -------------------------------- ### RigidArray Initialization Source: https://github.com/apple/swift-collections/blob/main/Sources/BasicContainers/BasicContainers.docc/Extensions/RigidArray.md Methods for creating new instances of RigidArray. ```APIDOC ## RigidArray Initialization ### Description Methods for creating new instances of RigidArray. ### Initializers - ``init()`` - ``init(capacity:)`` - ``init(capacity:initializingWith:)`` - ``init(repeating:count:)`` - ``init(consuming:)`` - ``init(capacity:copying:)-(_,Sequence)`` - ``init(capacity:copying:)-(_,Collection)`` ``` -------------------------------- ### Creating an OrderedSet Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.md Initializers for creating new OrderedSet instances, including empty sets, sets from sequences, and sets with specific capacities. ```APIDOC ## Creating an OrderedSet ### Initializers - `init()`: Creates an empty ordered set. - `init(_: S)`: Creates an ordered set from a sequence `S`. - `init(uncheckedUniqueElements: UnsafeBufferPointer)`: Creates an ordered set from a buffer of unique elements without performing checks. - `init(minimumCapacity:persistent:)`: Creates an ordered set with a specified minimum capacity and persistence setting. ``` -------------------------------- ### UniqueArray Initialization Source: https://github.com/apple/swift-collections/blob/main/Sources/BasicContainers/BasicContainers.docc/Extensions/UniqueArray.md Learn how to create instances of UniqueArray using different initializers, including those with capacity, repeating elements, and consuming existing collections. ```APIDOC ## UniqueArray Initialization ### Description Initializers for creating a `UniqueArray` instance. ### Methods - ``init()`` - ``init(capacity:)`` - ``init(capacity:initializingWith:)`` - ``init(repeating:count:)`` - ``init(consuming:)`` - ``init(capacity:copying:)-(_,Sequence)`` - ``init(capacity:copying:)-(_,Collection)`` ``` -------------------------------- ### Min-Max Heap Tree and Array Representation Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Illustrates the structure of a min-max heap using a tree diagram and its corresponding array representation. This helps visualize the data organization. ```plaintext // Min-max heap: level 0 (min): ┌────── A ──────┐ level 1 (max): ┌── J ──┐ ┌── G ──┐ level 2 (min): ┌ D ┐ ┌ B F C level 3 (max): I E H // Array representation: ["A", "J", "G", "D", "B", "F", "C", "I", "E", "H"] ``` -------------------------------- ### ShareableSet Initializers Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Provides methods for creating new ShareableSet instances. ```APIDOC ## Initializers ### Description Methods for creating new `ShareableSet` instances. ### Creating a Set ```swift init() init(S) init(`Self`) init(ShareableDictionary.Keys) ``` ``` -------------------------------- ### Initialize Heap from Array Literal Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Initializes a Heap directly from an array literal, providing a concise way to set up initial heap contents. ```swift var heap: Heap = [0.1, 0.6, 1.0, 0.15, 0.42] ``` -------------------------------- ### Create a TrailingPadding instance Source: https://github.com/apple/swift-collections/blob/main/Sources/TrailingElementsModule/TrailingElementsModule.docc/TrailingElementsModule.md Create a `TrailingPadding` instance by providing a header and the total desired allocation size. This primitive manages memory with a header but without predefined trailing data. ```swift var padded = TrailingPadding(header: SomeType(), totalSize: getSizeOfSomeTypeWithPadding()) ``` -------------------------------- ### ShareableSet Initializers Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Provides various ways to initialize a `ShareableSet`, including default initialization, initialization from a sequence, self, and the keys of a `ShareableDictionary`. ```swift init() init(S) init(`Self`) init(ShareableDictionary.Keys) ``` -------------------------------- ### TreeDictionary Initializers Source: https://github.com/apple/swift-collections/blob/main/Sources/HashTreeCollections/HashTreeCollections.docc/Extensions/TreeDictionary.md Methods for creating new TreeDictionary instances. ```APIDOC ## TreeDictionary Initializers ### Description Various initializers are available to create `TreeDictionary` instances from different sources. ### Initializers - ``init()``: Creates an empty `TreeDictionary`. - ``init(_:)-(TreeDictionary)``: Creates a `TreeDictionary` by copying another `TreeDictionary`. - ``init(_:)-([Key:Value])``: Creates a `TreeDictionary` from a standard Swift dictionary. - ``init(uniqueKeysWithValues:)-(Sequence)``: Creates a `TreeDictionary` from a sequence of key-value pairs, assuming unique keys. - ``init(uniqueKeysWithValues:)-(Sequence<(Key,Value)>)``: Creates a `TreeDictionary` from a sequence of tuples, assuming unique keys. - ``init(_:uniquingKeysWith:)-(Sequence,_)``: Creates a `TreeDictionary` from a sequence, resolving duplicate keys using a provided closure. - ``init(_:uniquingKeysWith:)-(Sequence<(Key,Value)>,_)``: Creates a `TreeDictionary` from a sequence of tuples, resolving duplicate keys using a provided closure. - ``init(grouping:by:)-a4ma``: Creates a `TreeDictionary` by grouping elements of a sequence based on a key. - ``init(grouping:by:)-4he86``: Creates a `TreeDictionary` by grouping elements of a sequence based on a key. - ``init(keys:valueGenerator:)``: Creates a `TreeDictionary` with specified keys and a generator for their values. ``` -------------------------------- ### Define ContainersPreview Module Source: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/CMakeLists.txt Configures the build to create a library named 'ContainersPreview' when not building a single module. It adds all specified Swift source files to this library and links it with internal utilities. ```cmake set(module_name ContainersPreview) add_library(ContainersPreview ${COLLECTIONS_CONTAINERS_SOURCES}) target_link_libraries(ContainersPreview PRIVATE InternalCollectionsUtilities) set_target_properties(ContainersPreview PROPERTIES INTERFACE_INCLUDE_DIRECTORIES ${CMAKE_Swift_MODULE_DIRECTORY}) _install_target(ContainersPreview) set_property(GLOBAL APPEND PROPERTY SWIFT_COLLECTIONS_EXPORTS ContainersPreview) ``` -------------------------------- ### Create an OrderedDictionary Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedDictionary.md Initialize an OrderedDictionary using a dictionary literal. The order of elements is preserved. ```swift let responses: OrderedDictionary = [ 200: "OK", 403: "Access forbidden", 404: "File not found", 500: "Internal server error", ] ``` -------------------------------- ### Target Sources for Module Source: https://github.com/apple/swift-collections/blob/main/Sources/ContainersPreview/CMakeLists.txt Specifies the source files to be included in the target module, whether it's a single module or the ContainersPreview library. This ensures all necessary Swift files are compiled as part of the target. ```cmake target_sources(${module_name} PRIVATE "Extensions/OutputSpan+Extras.swift" "Extensions/TemporaryAllocation.swift" "Protocols/Container/BidirectionalContainer.swift" "Protocols/Container/Container.swift" "Protocols/Container/Container+Filter.swift" "Protocols/Container/Container+SpanwiseZip.swift" "Protocols/Container/ContainerIterator.swift" "Protocols/Container/DynamicContainer.swift" "Protocols/Container/MutableContainer.swift" "Protocols/Container/PermutableContainer.swift" "Protocols/Container/RandomAccessContainer.swift" "Protocols/Container/RangeExpression2.swift" "Protocols/Container/RangeReplaceableContainer.swift" "Protocols/Container/Strideable+Limits.swift" "Protocols/BorrowingIteratorProtocol.swift" "Protocols/BorrowingIteratorProtocol+Copy.swift" "Protocols/BorrowingIteratorProtocol+ElementsEqual.swift" "Protocols/BorrowingIteratorProtocol+Filter.swift" "Protocols/BorrowingIteratorProtocol+Map.swift" "Protocols/BorrowingIteratorProtocol+Reduce.swift" "Protocols/BorrowingIteratorProtocol+SpanwiseZip.swift" "Protocols/BorrowingSequence.swift" "Protocols/BorrowingSequence+StandardConformances.swift" "Protocols/BorrowingSequence+Utilities.swift" "Protocols/Drain.swift" "Protocols/Drain+Map.swift" "Protocols/Drain+Reduce.swift" "Protocols/Drain.swift" "Protocols/Producer.swift" "Protocols/Producer+Collect.swift" "Protocols/Producer+Filter.swift" "Protocols/Producer+Map.swift" "Protocols/Producer+Reduce.swift" "Types/InputSpan.swift" "Types/MutableRef.swift" "Types/Ref.swift" "Types/Shared.swift" "Types/UniqueBox.swift") ``` -------------------------------- ### Insert Sequence of Elements into Heap Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Inserts all elements from a sequence into the Heap. This is efficient for adding multiple items at once. ```swift var heap = Heap(0 ..< 10) heap.insert(contentsOf: (20 ... 100).shuffled()) heap.insert(contentsOf: [-5, -6, -8, -12, -3]) ``` -------------------------------- ### Accessing Keys and Values Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Methods and subscript for retrieving values associated with keys, providing options for default values and finding element indices. ```APIDOC ## Accessing Keys and Values ### Subscripts - `subscript(Key) -> Value?` - Returns the value associated with the given key, or `nil` if the key is not present. - `subscript(Key, default _: () -> Value) -> Value` - Returns the value for the given key, or a default value if the key is not present. ### Methods - `func index(forKey: Key) -> Index?` - Returns the index of the element with the specified key, or `nil` if the key is not found. ``` -------------------------------- ### Creating and Applying Differences Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.md Methods for calculating and applying differences between ordered sets. ```APIDOC ## Creating and Applying Differences - `difference(from:)-30bkk`: Returns a new ordered set containing elements in this set but not in another. - `applying(_:)`: Applies a difference or intersection to the set. ``` -------------------------------- ### Accessing OrderedSet Elements by Index Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedSet.md Demonstrates accessing elements of an OrderedSet using integer indices and finding the index of a specific element. Also shows iterating through the set using its count. ```swift let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"] buildingMaterials[1] // "sticks" buildingMaterials.firstIndex(of: "bricks") // 2 for i in 0 ..< buildingMaterials.count { print("Little piggie #\(i) built a house of \(buildingMaterials[i])") } // Little piggie #0 built a house of straw // Little piggie #1 built a house of sticks // Little piggie #2 built a house of bricks ``` -------------------------------- ### Configure Heap Module Name and Sources Source: https://github.com/apple/swift-collections/blob/main/Sources/HeapModule/CMakeLists.txt Sets the module name and adds source files to the Heap module target. This is used when not building as a single module. ```cmake if(COLLECTIONS_SINGLE_MODULE) set(module_name ${COLLECTIONS_MODULE_NAME}) else() set(module_name HeapModule) add_library(HeapModule ${COLLECTIONS_HEAP_SOURCES}) target_link_libraries(HeapModule PRIVATE InternalCollectionsUtilities) set_target_properties(HeapModule PROPERTIES INTERFACE_INCLUDE_DIRECTORIES ${CMAKE_Swift_MODULE_DIRECTORY}) _install_target(HeapModule) set_property(GLOBAL APPEND PROPERTY SWIFT_COLLECTIONS_EXPORTS HeapModule) endif() target_sources (${module_name} PRIVATE "_HeapNode.swift" "Heap.swift" "Heap+Descriptions.swift" "Heap+ExpressibleByArrayLiteral.swift" "Heap+Invariants.swift" "Heap+UnsafeHandle.swift") ``` -------------------------------- ### Declare OrderedDictionary Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedDictionary.md Import the OrderedCollections library to use OrderedDictionary. It requires keys to conform to the Hashable protocol. ```swift import OrderedCollections @frozen struct OrderedDictionary ``` -------------------------------- ### Comparing BitSets Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitSet.md Methods for comparing BitSets for equality, subset, superset, and disjointness. ```APIDOC ## Comparing BitSets ### Description Methods for comparing BitSets for equality, subset, superset, and disjointness. ### Topics - ``==(_:_:)`` - ``isEqualSet(to:)-(BitSet)`` - ``isEqualSet(to:)-(Range)`` - ``isEqualSet(to:)-(BitSet.Counted)`` - ``isEqualSet(to:)-(Sequence)`` - ``isSubset(of:)-(BitSet)`` - ``isSubset(of:)-(Range)`` - ``isSubset(of:)-(BitSet.Counted)`` - ``isSubset(of:)-(Sequence)`` - ``isSuperset(of:)-(Self)`` - ``isSuperset(of:)-(Range)`` - ``isSuperset(of:)-(BitSet.Counted)`` - ``isSuperset(of:)-(Sequence)`` - ``isStrictSubset(of:)-(Self)`` - ``isStrictSubset(of:)-(Range)`` - ``isStrictSubset(of:)-(BitSet.Counted)`` - ``isStrictSubset(of:)-(Sequence)`` - ``isStrictSuperset(of:)-(Self)`` - ``isStrictSuperset(of:)-(Range)`` - ``isStrictSuperset(of:)-(BitSet.Counted)`` - ``isStrictSuperset(of:)-(Sequence)`` - ``isDisjoint(with:)-(Self)`` - ``isDisjoint(with:)-(Range)`` - ``isDisjoint(with:)-(BitSet.Counted)`` - ``isDisjoint(with:)-(Sequence)`` ``` -------------------------------- ### Create an OrderedSet Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedSet.md Initialize an OrderedSet with a collection of elements. The order is preserved, and duplicates are automatically removed. ```swift let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"] ``` -------------------------------- ### Comparing Sets Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.md Methods for comparing ordered sets for equality, subset, superset, and disjointness. ```APIDOC ## Comparing Sets - `==(_:_:)`: Checks if two ordered sets are equal. - `isEqualSet(to:)-6zqj7`: Checks if this set is equal to another set. - `isEqualSet(to:)-34yz0`: Checks if this set is equal to another set. - `isEqualSet(to:)-2bhxr`: Checks if this set is equal to another set. - `isSubset(of:)-ptij`: Checks if this set is a subset of another set. - `isSubset(of:)-3mw6r`: Checks if this set is a subset of another set. - `isSubset(of:)-8yb29`: Checks if this set is a subset of another set. - `isSubset(of:)-9hxl4`: Checks if this set is a subset of another set. - `isSuperset(of:)-4rrsh`: Checks if this set is a superset of another set. - `isSuperset(of:)-2bbv8`: Checks if this set is a superset of another set. - `isSuperset(of:)-7xvog`: Checks if this set is a superset of another set. - `isSuperset(of:)-7oow7`: Checks if this set is a superset of another set. - `isStrictSubset(of:)-8m21h`: Checks if this set is a strict subset of another set. - `isStrictSubset(of:)-9lv3x`: Checks if this set is a strict subset of another set. - `isStrictSubset(of:)-4efhn`: Checks if this set is a strict subset of another set. - `isStrictSubset(of:)-10abw`: Checks if this set is a strict subset of another set. - `isStrictSuperset(of:)-7u97x`: Checks if this set is a strict superset of another set. - `isStrictSuperset(of:)-3kfwa`: Checks if this set is a strict superset of another set. - `isStrictSuperset(of:)-98d9s`: Checks if this set is a strict superset of another set. - `isStrictSuperset(of:)-5e6d5`: Checks if this set is a strict superset of another set. - `isDisjoint(with:)-6vmoh`: Checks if this set is disjoint with another set. - `isDisjoint(with:)-4tsmx`: Checks if this set is disjoint with another set. - `isDisjoint(with:)-54iy6`: Checks if this set is disjoint with another set. - `isDisjoint(with:)-7nqur`: Checks if this set is disjoint with another set. ``` -------------------------------- ### Initialize Deque Source: https://github.com/apple/swift-collections/blob/main/Documentation/Deque.md Initialize a Deque with an array literal. ```swift var colors: Deque = ["red", "yellow", "blue"] ``` -------------------------------- ### TreeSet Structure Visualization Source: https://github.com/apple/swift-collections/blob/main/Sources/HashTreeCollections/HashTreeCollections.docc/Extensions/TreeSet.md Visual representation of how elements with specific hash values are organized within a two-level prefix tree. This illustrates the concept of nodes having slots for members or child nodes based on hash chunks. ```text ┌0┬1┬2───────┬3┬4┬5┬6┬7┬8┬9┬A──┬B┬C┬D┬E┬F┐ │ │ │ Maximo │ │ │ │ │ │ │ │ • │ │ │ │ │ │ └─┴─┴────────┴─┴─┴─┴─┴─┴─┴─┴─┼─┴─┴─┴─┴─┴─┘ ╎ ╎ ┌0┬1┬2┬3┬4┬5┬6───┴──┬7┬8┬9┬A┬B┬C┬D──────────┬E┬F┐ │ │ │ │ │ │ │ Julia │ │ │ │ │ │ │ Don Pablo │ │ │ └─┴─┴─┴─┴─┴─┴───────┴─┴─┴─┴─┴─┴─┴───────────┴─┴─┘ ``` -------------------------------- ### Finding Elements Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.md Methods for checking the presence of elements and finding their indices within the ordered set. ```APIDOC ## Finding Elements - `contains(_:)`: Returns `true` if the set contains the specified element. - `firstIndex(of:)`: Returns the index of the first occurrence of the specified element, or `nil` if not found. - `lastIndex(of:)`: Returns the index of the last occurrence of the specified element, or `nil` if not found. ``` -------------------------------- ### Set Comparison Operations Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Details on comparing sets for equality, subset, superset, and disjointness, including generalized equality checks. ```APIDOC ## Set Comparison Operations ### Description `ShareableSet` supports all standard set comparisons (subset tests, superset tests, disjunctness test), including the customary overloads established by `Set`. As an additional extension, the `isEqualSet` family of member functions generalize the standard `==` operation to support checking whether a `ShareableSet` consists of exactly the same members as an arbitrary sequence. Like `==`, the `isEqualSet` functions ignore element ordering and duplicates (if any). ### Equality #### `==` - `static func == (Self, Self) -> Bool` #### `isEqualSet` - `func isEqualSet(to: Self) -> Bool` - `func isEqualSet(to: ShareableDictionary.Keys) -> Bool` - `func isEqualSet(to: S) -> Bool` ### Subset and Superset Tests #### `isSubset` - `func isSubset(of: Self) -> Bool` - `func isSubset(of: ShareableDictionary.Keys) -> Bool` - `func isSubset(of: S) -> Bool` #### `isSuperset` - `func isSuperset(of: Self) -> Bool` - `func isSuperset(of: ShareableDictionary.Keys) -> Bool` - `func isSuperset(of: S) -> Bool` #### `isStrictSubset` - `func isStrictSubset(of: Self) -> Bool` - `func isStrictSubset(of: ShareableDictionary.Keys) -> Bool` - `func isStrictSubset(of: S) -> Bool` #### `isStrictSuperset` - `func isStrictSuperset(of: Self) -> Bool` - `func isStrictSuperset(of: ShareableDictionary.Keys) -> Bool` - `func isStrictSuperset(of: S) -> Bool` ### Disjointness Test #### `isDisjoint` - `func isDisjoint(with: Self) -> Bool` - `func isDisjoint(with: ShareableDictionary.Keys) -> Bool` - `func isDisjoint(with: S) -> Bool` ``` -------------------------------- ### BitSet Collection Views Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitSet.md Accessing different views of the BitSet collection. ```APIDOC ## BitSet Collection Views ### Description Accessing different views of the BitSet collection. ### Topics - ``Counted`` - ``counted`` ``` -------------------------------- ### BitSet Binary Set Predicates Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitSet.Counted.md Predicates for comparing BitSets and checking set relationships like equality, subset, superset, and disjointness. ```APIDOC ## Binary Set Predicates ### Equality - `==(_:_:)`: Checks if two BitSets are equal. - `isEqualSet(to:)-(BitSet.Counted)`: Checks if the BitSet is equal to another Counted BitSet. - `isEqualSet(to:)-(BitSet)`: Checks if the BitSet is equal to another BitSet. - `isEqualSet(to:)-(Range)`: Checks if the BitSet is equal to a range. - `isEqualSet(to:)-(Sequence)`: Checks if the BitSet is equal to a sequence. ### Subset - `isSubset(of:)-(BitSet.Counted)`: Checks if the BitSet is a subset of another Counted BitSet. - `isSubset(of:)-(BitSet)`: Checks if the BitSet is a subset of another BitSet. - `isSubset(of:)-(Range)`: Checks if the BitSet is a subset of a range. - `isSubset(of:)-(Sequence)`: Checks if the BitSet is a subset of a sequence. ### Superset - `isSuperset(of:)-(BitSet.Counted)`: Checks if the BitSet is a superset of another Counted BitSet. - `isSuperset(of:)-(BitSet)`: Checks if the BitSet is a superset of another BitSet. - `isSuperset(of:)-(Range)`: Checks if the BitSet is a superset of a range. - `isSuperset(of:)-(Sequence)`: Checks if the BitSet is a superset of a sequence. ### Strict Subset - `isStrictSubset(of:)-(BitSet.Counted)`: Checks if the BitSet is a strict subset of another Counted BitSet. - `isStrictSubset(of:)-(BitSet)`: Checks if the BitSet is a strict subset of another BitSet. - `isStrictSubset(of:)-(Range)`: Checks if the BitSet is a strict subset of a range. - `isStrictSubset(of:)-(Sequence)`: Checks if the BitSet is a strict subset of a sequence. ### Strict Superset - `isStrictSuperset(of:)-(BitSet.Counted)`: Checks if the BitSet is a strict superset of another Counted BitSet. - `isStrictSuperset(of:)-(BitSet)`: Checks if the BitSet is a strict superset of another BitSet. - `isStrictSuperset(of:)-(Range)`: Checks if the BitSet is a strict superset of a range. - `isStrictSuperset(of:)-(Sequence)`: Checks if the BitSet is a strict superset of a sequence. ### Disjoint - `isDisjoint(with:)-(BitSet.Counted)`: Checks if the BitSet is disjoint with another Counted BitSet. - `isDisjoint(with:)-(BitSet)`: Checks if the BitSet is disjoint with another BitSet. - `isDisjoint(with:)-(Range)`: Checks if the BitSet is disjoint with a range. - `isDisjoint(with:)-(Sequence)`: Checks if the BitSet is disjoint with a sequence. ``` -------------------------------- ### Create a TrailingArray on the heap Source: https://github.com/apple/swift-collections/blob/main/Sources/TrailingElementsModule/TrailingElementsModule.docc/TrailingElementsModule.md Create an instance of `TrailingArray` by providing a header and appending trailing elements. The buffer is deallocated when the `TrailingArray` value is no longer used. ```swift var coords = TrailingArray(header: Coordinates(numPoints: 3)) { outputSpan in outputSpan.append(Point(x: 1, y: 2)) outputSpan.append(Point(x: 2, y: 3)) outputSpan.append(Point(x: 3, y: 4)) } ``` -------------------------------- ### Reordering Elements Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedDictionary.Values.md Explains how to reorder the elements within the Values collection. ```APIDOC ## Reordering Elements ### Description Methods for reordering elements within the `Values` collection. ### Topics - `swapAt(_:_:)-77eiy`: Swaps two elements at the specified indices. - `partition(by:)-9x0i5`: Partitions the collection based on a predicate. - `sort()`: Sorts the collection in place using its default sorting order. - `sort(by:)`: Sorts the collection in place using a custom comparison closure. - `shuffle()`: Shuffles the collection in place using a default random number generator. - `shuffle(using:)`: Shuffles the collection in place using a provided random number generator. ``` -------------------------------- ### Deque Queue Operations Source: https://github.com/apple/swift-collections/blob/main/Documentation/Deque.md Shows common queue operations like appending, prepending, removing from the last or first element, and prepending a sequence of elements. ```swift colors.append("green") colors.prepend("orange") // colors: ["orange", "red", "blue", "yellow", "green"] colors.popLast() // "green" colors.popFirst() // "orange" // colors: ["red", "blue", "yellow"] colors.prepend(contentsOf: ["purple", "teal"]) // colors: ["purple", "teal", "red", "blue", "yellow"] ``` -------------------------------- ### Adding and Updating Elements in BitSet Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitSet.md Methods for inserting new elements or updating existing ones in a BitSet. ```APIDOC ## Adding and Updating Elements in BitSet ### Description Methods for inserting new elements or updating existing ones in a BitSet. ### Topics - ``insert(_:)`` - ``update(with:)`` ``` -------------------------------- ### Declare OrderedSet Source: https://github.com/apple/swift-collections/blob/main/Documentation/OrderedSet.md Import the OrderedCollections library to use OrderedSet. Elements must conform to the Hashable protocol. ```swift import OrderedCollections @frozen struct OrderedSet ``` -------------------------------- ### Accessing Keys and Values in ShareableDictionary Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Retrieve values by key, with optional default values, or find the index for a given key. ```swift subscript(Key) -> Value? subscript(Key, default _: () -> Value) -> Value func index(forKey: Key) -> Index? ``` -------------------------------- ### Accessing Elements Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedDictionary.Values.md Details on how to access individual elements within the Values collection. ```APIDOC ## Accessing Elements ### Description Methods for accessing elements within the `Values` collection. ### Topics - `subscript(_:)-25vfz`: Accesses an element at a specific index. - `elements`: Returns a collection of the dictionary's values. - `withUnsafeBufferPointer(_:)`: Provides access to the collection's elements via an unsafe buffer pointer. - `withUnsafeMutableBufferPointer(_:)`: Provides mutable access to the collection's elements via an unsafe mutable buffer pointer. ``` -------------------------------- ### Adding and Updating Elements Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedSet.md Functions for adding new elements, appending collections, and updating existing elements in the ordered set. ```APIDOC ## Adding and Updating Elements - `append(_:)`: Appends a new element to the end of the set. - `append(contentsOf:)`: Appends the elements of a sequence to the end of the set. - `insert(_:at:)`: Inserts an element at the specified position. - `updateOrAppend(_:)`: Updates an existing element if present, otherwise appends it. - `updateOrInsert(_:at:)`: Updates an existing element if present, otherwise inserts it at the specified position. - `update(_:at:)`: Updates the element at the specified position. ``` -------------------------------- ### BitArray Adding Elements Source: https://github.com/apple/swift-collections/blob/main/Sources/BitCollections/BitCollections.docc/Extensions/BitArray.md Methods for adding elements to a BitArray. ```APIDOC ## Adding Elements ### Description Methods for adding elements to a BitArray. ### Mutators - ``append(_:)``: Appends a boolean value to the end of the BitArray. - ``append(contentsOf:)-(BitArray)``: Appends the contents of another BitArray to the end. - ``append(contentsOf:)-(BitArray.SubSequence)``: Appends the contents of a BitArray subsequence to the end. - ``append(contentsOf:)-(Sequence)``: Appends the contents of a boolean sequence to the end. - ``append(repeating:count:)``: Appends a specified value repeated a certain number of times. - ``insert(_:at:)``: Inserts a boolean value at a specific index. - ``insert(contentsOf:at:)-(Collection,_)``: Inserts the contents of a boolean collection at a specific index. - ``insert(contentsOf:at:)-(BitArray,_)``: Inserts the contents of another BitArray at a specific index. - ``insert(contentsOf:at:)-(BitArray.SubSequence,_)``: Inserts the contents of a BitArray subsequence at a specific index. - ``insert(repeating:count:at:)``: Inserts a specified value repeated a certain number of times at a specific index. - ``truncateOrExtend(toCount:with:)``: Truncates or extends the BitArray to a specified count, filling new elements with a given value. ``` -------------------------------- ### Target Sources Configuration in CMake Source: https://github.com/apple/swift-collections/blob/main/Sources/InternalCollectionsUtilities/CMakeLists.txt Specifies the source files to be included in the main module target. These files cover various utility and data structure implementations. ```cmake target_sources (${module_name} PRIVATE "IntegerTricks/FixedWidthInteger+roundUpToPowerOfTwo.swift" "IntegerTricks/Integer rank.swift" "IntegerTricks/UInt+first and last set bit.swift" "IntegerTricks/UInt+reversed.swift" "UnsafeBitSet/_UnsafeBitSet+Index.swift" "UnsafeBitSet/_UnsafeBitSet+_Word.swift" "UnsafeBitSet/_UnsafeBitSet.swift" "_SortedCollection.swift" "_UniqueCollection.swift" "Debugging.swift" "Descriptions.swift" "LifetimeOverride.swift" "RandomAccessCollection+Offsets.swift" "Span+Extras.swift" "String+Padding.swift" "UnsafeBufferPointer+Extras.swift" "UnsafeMutableBufferPointer+Extras.swift" "UnsafeMutableRawBufferPointer+Extras.swift" "UnsafeRawBufferPointer+Extras.swift" ) ``` -------------------------------- ### Access Unordered Heap Elements Source: https://github.com/apple/swift-collections/blob/main/Documentation/Heap.md Provides a read-only view of the backing array for the Heap. Elements are not guaranteed to be in a specific order beyond heap properties. ```swift let heap = Heap((1...100).shuffled()) for val in heap.unordered { ... ``` -------------------------------- ### Inspecting a Dictionary Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Properties to check the state of the dictionary, such as whether it is empty or its current number of elements. ```APIDOC ## Inspecting a Dictionary ### Properties - `isEmpty`: `Bool` - Returns `true` if the dictionary contains no elements. - `count`: `Int` - The number of elements in the dictionary. ``` -------------------------------- ### Set Comparison Operations Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Includes standard set comparisons like subset, superset, and disjunctness tests. Also provides `isEqualSet` for comparing a set with arbitrary sequences, ignoring order and duplicates. ```swift static func == (`Self`, `Self`) -> Bool func isEqualSet(to: `Self`) -> Bool func isEqualSet(to: ShareableDictionary.Keys) -> Bool func isEqualSet(to: S) -> Bool func isSubset(of: `Self`) -> Bool func isSubset(of: ShareableDictionary.Keys) -> Bool func isSubset(of: S) -> Bool func isSuperset(of: `Self`) -> Bool func isSuperset(of: ShareableDictionary.Keys) -> Bool func isSuperset(of: S) -> Bool func isStrictSubset(of: `Self`) -> Bool func isStrictSubset(of: ShareableDictionary.Keys) -> Bool func isStrictSubset(of: S) -> Bool func isStrictSuperset(of: `Self`) -> Bool func isStrictSuperset(of: ShareableDictionary.Keys) -> Bool func isStrictSuperset(of: S) -> Bool func isDisjoint(with: `Self`) -> Bool func isDisjoint(with: ShareableDictionary.Keys) -> Bool func isDisjoint(with: S) -> Bool ``` -------------------------------- ### Access and Modify Deque Elements Source: https://github.com/apple/swift-collections/blob/main/Documentation/Deque.md Demonstrates accessing elements by index and inserting/removing elements at specific positions. Note that accessing an index out of bounds will result in a runtime error. ```swift print(colors[1]) // "yellow" print(colors[3]) // Runtime error: Index out of range colors.insert("green", at: 1) // ["red", "green", "yellow", "blue"] colors.remove(at: 2) // "yellow" // ["red", "green", "blue"] ``` -------------------------------- ### Collection Views Source: https://github.com/apple/swift-collections/blob/main/Sources/OrderedCollections/OrderedCollections.docc/Extensions/OrderedDictionary.md Provides views of the dictionary's keys, values, and elements. ```APIDOC ## Collection Views ### `keys` A collection containing the keys of the dictionary in their insertion order. ### `values` A collection containing the values of the dictionary in their insertion order. ### `elements` A collection containing the key-value pairs of the dictionary in their insertion order. ``` -------------------------------- ### Using ShareableSet for Performance Improvement Source: https://github.com/apple/swift-collections/blob/main/Documentation/Reviews/2022-10-31.ShareableHashedCollections/ShareableHashedCollections.md Replacing `Set` with `ShareableSet` can lead to significant performance gains, especially for large datasets. This alias demonstrates a simple type change for potential algorithmic improvement. ```swift typealias Model = ShareableSet ... // Same code as before ```