Commonly used data structures for Swift
This feature release adds a number of new data structure implementations, along with minor changes to existing constructs.
Heap implements a min-max heap, backed by a native array. (Contributed by @AquaGeek)BitSet and BitArray are two alternate representations of a bitmap type, backed by dynamically allocated storage. (Contributed by @MahanazAtiqullah)TreeSet and TreeDictionary are hashed collections implementing Compressed Hash-Array Mapped Prefix Trees (CHAMP). They provide similar API as Set/Dictionary in the Standard Library, but as persistent data structures, supporting incremental mutations of shared instances and efficient structural diffing. (Contributed by @msteindorfer)OrderedSet.isEqualSet family of functions provide a way to test that two containers contain the same members, ignoring the order of elements. (https://github.com/apple/swift-collections/issues/183, https://github.com/apple/swift-collections/pull/234)OrderedSet.filter implements a version of the standard filter operation that returns an OrderedSet instead of an Array. (https://github.com/apple/swift-collections/pull/159)debugDescription implementations have been updated to follow Swift best practice. (These are called by container types like Array to print their elements, so they work best when they're succinct variants of description that are suitable for embedding in structured output: specifically, they must not produce unpaired delimiter characters ([/], (/), {/}, </> etc), raw top level commas, semicolons, colons, unquoted strings etc. debugDescription should not needlessly print type names etc.)Many thanks to our contributors for their great work (and patience)!
Full Changelog: https://github.com/apple/swift-collections/compare/1.0.6...1.1.0
subscript(offset:) for now by @lorentey in https://github.com/apple/swift-collections/pull/92
release/1.0 into main by @lorentey in https://github.com/apple/swift-collections/pull/108
Heap hasn't been tagged yet & list other enhancements in progress by @lorentey in https://github.com/apple/swift-collections/pull/109
import Foundation by @compnerd in https://github.com/apple/swift-collections/pull/118
ascending and descending views by @lorentey in https://github.com/apple/swift-collections/pull/119
release/1.0 to main by @lorentey in https://github.com/apple/swift-collections/pull/141
PersistentSet by @lorentey in https://github.com/apple/swift-collections/pull/193
PriorityQueueModule to HeapModule by @lorentey in https://github.com/apple/swift-collections/pull/194
mutating keywords by @lorentey in https://github.com/apple/swift-collections/pull/238
Shareable to Tree by @lorentey in https://github.com/apple/swift-collections/pull/242
Sendable conformance by @lorentey in https://github.com/apple/swift-collections/pull/271
self doesn’t get destroyed before we’re done working with it by @lorentey in https://github.com/apple/swift-collections/pull/276
Rope.find returns a bogus remainder for the end position by @lorentey in https://github.com/apple/swift-collections/pull/291
This bugfix release adds Sendable conformances to all public types (fixing compatibility with Swift's strict concurrency checking), and speeds up equality checks (==) of identical collection values.
Full Changelog: https://github.com/apple/swift-collections/compare/1.0.5...1.0.6
Thank you to everyone who contributed to this release!
This bugfix release improves compatibility with recent Swift versions, eliminating several compiler warnings on Swift 5.8 and 5.9. It contains no API-level changes.
Full Changelog: https://github.com/apple/swift-collections/compare/1.0.4...1.0.5
Thank you to everyone who contributed to this release!
This is a documentation update, including the addition of basic DocC documentation bundles. This release has no functional changes.
rethrows position (by @ensan-hcl)Full Changelog: https://github.com/apple/swift-collections/compare/1.0.3...1.0.4
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release resolves issues uncovered since 1.0.2 was tagged. The fixes improve performance of some operations, resolve compile-time issues and update documentation. This release contains no observable behavioral changes.
OrderedDictionary's uniquing/unique/grouping initializers and merge operations no longer gets flagged as ambiguous in certain cases involving type inference. (#125, #139)OrderedCollections module now make use of the stdlib's temporary allocation facility. (#160)filter and merge methods of OrderedDictionary. (#145)Full Changelog: https://github.com/apple/swift-collections/compare/1.0.2...1.0.3
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release resolves issues uncovered since 1.0.1 was tagged, including a high severity crash in OrderedSet and OrderedDictionary. Upgrading is recommended for all clients.
OrderedSet and OrderedDictionary that could result in some mutation methods corrupting shared copies of the same value, leading to subsequent crashes. (Issue #104)Deque.append(contentsOf:) now uses an exponential storage resizing strategy, as expected. Calling it in a loop no longer results in O(n) reallocations. (Issue #113)Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
The CMake configuration now supports building the package for AArch64 Linux distributions, unblocking adoption in SPM.
(Note that the CMake configuration is intended only to support the use of this package from within Swift toolchain builds. It is provided as is, with no source compatibility guarantees.)
Minor documentation updates.
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release marks an important milestone for this package -- the advent of source stability!
OrderedDictionary methods that were deprecated in 0.0.7 are now marked unavailable.OrderedDictionary.init(uncheckedUniqueElements:) no longer creates large dictionary instances without an associated hash table.Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release prepares for source stability by deprecating some OrderedDictionary APIs that we'd like to remove in version 1.0 of the package. (All deprecated names have reasonable replacements.)
The two OrderedDictionary.modifyValue methods were renamed updateValue, to better align with the standard updateValue function (#90)
/* Old: */ d.modifyValue(forKey: key, default: []) { $0.append(newValue) }
/* New: */ d.updateValue(forKey: key, default: []) { $0.append(newValue) }
/* Old: */ d.modifyValue(forKey: key, insertingDefault: [], at: 0) { $0.append(newValue) }
/* New: */ d.updateValue(forKey: key, insertingDefault: [], at: 0) { $0.append(newValue) }
OrderedDictionary.subscript(offset:) was removed; it used inconsistent terminology. To access a key-value pair at a given position, you can continue using the unlabeled subscript on the elements view.
/* Deprecated: */ d[offset: 42]
/* Replacement: */ d.element[42]
The collections benchmarks were moved to a standalone nested package in a subdirectory of the repository, allowing the top-level package manifest to stop declaring a dependency on swift-collections-benchmark. This will make it easier to add Swift Collections as a dependency, especially in projects such as the Package Manager (or the benchmarking tool itself).
The old names for removed/renamed APIs are still available as deprecated members -- these will be removed in the 1.0 release.
subscript(offset:) for now (by @lorentey)Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.
This release consists of an update to the CMake config that is used during non-bootstrapped builds of the Swift toolchain. It contains no changes for package-based projects.
Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.