Swift Collections 1.1.0

This feature release adds a number of new data structure implementations, along with minor changes to existing constructs.

New Data Structures

• 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)

Other Changes

• This version of the package can only be built using Swift 5.7.2 or later.
• New methods: the OrderedSet.isEqualSet family of functions provide a way to test that two containers contain the same members, ignoring the order of elements. (#183, #234)
• New method: OrderedSet.filter implements a version of the standard filter operation that returns an OrderedSet instead of an Array. (#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.)

New Contributors

• @AquaGeek made their first contribution in #61
• @ejmarchant made their first contribution in #82
• @just-gull made their first contribution in #115
• @jPaolantonio made their first contribution in #121
• @MahanazAtiqullah made their first contribution in #83
• @hectormatos2011 made their first contribution in #155
• @ktoso made their first contribution in #159
• @CTMacUser made their first contribution in #116
• @hassila made their first contribution in #297

Many thanks to our contributors for their great work (and patience)!

List of Pull Requests

Full Changelog: 1.0.6...1.1.0

• Add a min-max heap implementation that can be used to back a priority queue by @AquaGeek in #61
• [benchmark] Review and extend Heap benchmarks by @lorentey in #76
• Add reference benchmarks for bit vector implementations by @lorentey in #79
• Fix Markdown link in README by @AquaGeek in #77
• Fix documentation for types conforming to ExpressibleByArrayLiteral o… by @ejmarchant in #82
• [Heap] Performance tweaks by @lorentey in #78
• Fix typos: missing subscript parameters by @ejmarchant in #81
• [Heap] Update implementation details section in docs by @lorentey in #84
• Update CMakeLists.txt by @compnerd in #85
• Stop depending on swift-collections-benchmark by @lorentey in #86
• [OrderedDictionary] modifyValue → updateValue by @lorentey in #91
• Add Benchmarks package to workspace by @lorentey in #93
• [OrderedDictionary] Deprecate subscript(offset:) for now by @lorentey in #92
• Documentation: Remove in-place mutation comments by @ejmarchant in #96
• [main] Freeze some types for consistency with their inlinable initializers by @lorentey in #98
• Follow stdlib's leading underscore rule by @ejmarchant in #95
• [Heap] Disable heap tests in release builds by @lorentey in #100
• [NFC] Merge release/1.0 to main by @lorentey in #105
• Merge release/1.0 into main by @lorentey in #108
• [README] Note that Heap hasn't been tagged yet & list other enhancements in progress by @lorentey in #109
• PriorityQueueModule: remove import Foundation by @compnerd in #118
• [Heap] Remove Heap's ascending and descending views by @lorentey in #119
• [Heap] Enable heap tests in optimized builds (#101) by @just-gull in #115
• Update CMakeLists.txt by @compnerd in #122
• Fix link to package internal documentation by @jPaolantonio in #121
• Merge release/1.0 to main by @lorentey in #130
• BitArray and BitSet data structures by @MahanazAtiqullah in #83
• Sorted collections by @vihanb in #65
• Merge release/1.0 to main by @lorentey in #141
• Remove Swift PM Artifacts to avoid Generated Schemes in Xcode by @hectormatos2011 in #155
• Reinstate custom schemes under Utils/swift-collections.xcworkspace by @lorentey in #156
• +OrderedSet add filter #158 by @ktoso in #159
• [Xcode] Update schemes & file template by @lorentey in #161
• [OrderedCollection] Use standard temp allocation facility, if available by @lorentey in #160
• [OrderedSet] Work around weird name lookup issue in compiler by @lorentey in #162
• =OrderedSet.filter Attempt to optimize filter impl by @ktoso in #163
• Force-inline _modify accessors to work around a performance issue by @lorentey in #165
• Merge release/1.0 branch to main by @lorentey in #172
• Incubate persistent data structures by @msteindorfer in #31
• Persistent collections updates by @lorentey in #174
• Persistent collections updates by @lorentey in #175
• Persistent collections updates (part 3) by @lorentey in #176
• Persistent collections updates (part 4) by @lorentey in #177
• [OrderedDictionary] Tiny documentation fix by @lorentey in #178
• Persistent collections updates (part 5) by @lorentey in #179
• Integrate PriorityQueueModule, BitCollections, PersistentCollections, SortedCollections into release/1.1 by @lorentey in #181
• Persistent collections updates (part 6) by @lorentey in #180
• Persistent collections updates (part 7) by @lorentey in #182
• [BitSet] Fix decoding format on 32 bit architectures by @lorentey in #185
• Persistent collections updates (part 8) by @lorentey in #184
• Persistent collections updates (part 9) by @lorentey in #188
• Add Sendable conformances to all public types by @lorentey in #191
• [test] Check baseline API expectations for set-like types by @lorentey in #192
• Fleshing out PersistentSet by @lorentey in #193
• Rename PriorityQueueModule to HeapModule by @lorentey in #194
• [BitSet] Fix invariant violation in member subscript by @lorentey in #195
• [1.1.0] Bump minimum required Swift toolchain to 5.5 by @lorentey in #196
• Restore support for building with Swift 5.5 by @lorentey in #198
• Merge release/1.0 to release/1.1 by @lorentey in #199
• Update CMake configuration in preparation for 1.1 by @lorentey in #200
• Update CMakeLists.txt ...

Swift Collections 1.0.6

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.

What's Changed

• Fix typos: OrderedSet Documentation by @kati-kms in #322
• [1.0] build: support building in Debug mode on Windows by @compnerd in #337
• build: tweak search path for embedding by @compnerd in #338
• [OrderedDictionary] forward ordered dictionary values equality to values property by @vanvoorden in #335
• [OrderedSet] forward ordered set equality to elements property by @vanvoorden in #340
• [Deque] check deque equality with buffer identity by @vanvoorden in #341
• [OrderedDictionary] Fix usage of deprecated API in index(forKey:) docs by @lorentey in #342
• [1.0] Backport Sendable conformances on all public types by @lorentey in #343
• OrderedSet: Fix sendable conformance on old swifts by @lorentey in #346
• Update CMake configuration by @lorentey in #347

New Contributors

• @kati-kms made their first contribution in #322
• @vanvoorden made their first contribution in #335

Full Changelog: 1.0.5...1.0.6

Thank you to everyone who contributed to this release!

Swift Collections 1.0.5

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.

What's Changed

• build: add ARM64 to the architecture mappings for Windows by @compnerd in #265
• Fix deprecated UnsafeMutablePointer.assign(repeating:count) method by @FelixHerrmann in #268
• [1.0][test] Fix typename shadowing warning in Swift 5.9 by @lorentey in #315
• [1.0][benchmark] Update std::function syntax for current C++ by @lorentey in #314

New Contributors

• @FelixHerrmann made their first contribution in #268

Full Changelog: 1.0.4...1.0.5

Thank you to everyone who contributed to this release!

Swift Collections 1.0.4

This is a documentation update, including the addition of basic DocC documentation bundles. This release has no functional changes.

Changes

• The package now contains documentation bundles, enabling nicer presentation of API documentation in DocC.

Fixes

• #186 [OrderedCollections] Document Sorting as Stable (by @benrimmington)

Pull requests

• #178 [OrderedDictionary] Tiny documentation fix (by @lorentey)
• #187 Fix rethrows position (by @ensan-hcl)
• #189 [OrderedSet] Tiny doc fixes for isSuperset (by @lorentey)
• #201 [OrderedCollections] Update docs to state that the sort algorithm is stable (by @lorentey)
• #214 [OrderedSet] Small doc updates/fixes (by @lorentey)
• #252 [1.0] Add DocC documentation bundles (by @lorentey)

Full Changelog: 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.

Swift Collections 1.0.3

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.

Changes

• [Clutter] When opened in Xcode, the package no longer adds spurious schemes to dependent projects. (#155)

Fixes

• [Build-time issue] Code that is calling OrderedDictionary's uniquing/unique/grouping initializers and merge operations no longer gets flagged as ambiguous in certain cases involving type inference. (#125, #139)
• [Build-time issue] The package no longer fails to build when library evolution is enabled. (#157) (Note: this configuration remains unsupported. This package does not provide any guarantees about ABI stability.)
• [Performance] In-place mutations of collection contents no longer result in unnecessary heap allocations. (#164)
• [Performance] On Swift 5.6 and better, some operations in the OrderedCollections module now make use of the stdlib's temporary allocation facility. (#160)
• [Docs] Documentation was updated to clarify behavior of the filter and merge methods of OrderedDictionary. (#145)

Pull requests

• #140 [OrderedDictionary] Fix type inference issue with OrderedDictionary.init(grouping:by:) (by @lorentey)
• #153 [OrderedDictionary][doc] Update docs for merge/filter operations (by @lorentey)
• #155 Remove Swift PM Artifacts to avoid Generated Schemes in Xcode (by @hectormatos2011)
• #156 Reinstate custom schemes under Utils/swift-collections.xcworkspace (by @lorentey)
• #160 [OrderedCollection] Use standard temp allocation facility, if available (by @lorentey)
• #161 [Xcode] Update schemes & file template (by @lorentey)
• #162 [OrderedSet] Work around weird name lookup issue in compiler (by @lorentey)
• #165 Force-inline _modify accessors to work around a performance issue (by @lorentey)
• #169 [OrderedDictionary] Resolve call-site ambiguities (by @lorentey)
• #170 Update README for 1.0.3 (by @lorentey)

Full Changelog: 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.

Swift Collections 1.0.2

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.

Fixes

• Fixed a value semantic violation in 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)

Pull requests

• #113 [Deque] append(contentsOf:): Use exponential capacity reservation (by @lorentey)
• #123 [OrderedSet] Add missing uniqueness check (by @lorentey)
• #126 [Utils] run-full-tests.sh: Keep going after a failure (by @lorentey)
• #128 [Utils] run-full-tests.sh: Add support for testing on Swift 5.3 without manual editing (by @lorentey)

Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.

Swift Collections 1.0.1

Changes

• 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.

Pull requests

• #111 [CMake] Match lowercase "aarch64" (by @neonichu)
• #112 [OrderedSet][doc] Fix thinko (by @lorentey)

Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.

Swift Collections 1.0.0

This release marks an important milestone for this package -- the advent of source stability!

Changes

• The public API of Swift Collections is now considered source stable. The README defines what we consider public API.
• The three 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.

Pull requests

• #95 Follow stdlib's leading underscore rule (by @ejmarchant)
• #96 Documentation: Remove in-place mutation comments (by @ejmarchant)
• #97 Freeze some types for consistency with their inlinable initializers (by @lorentey)
• #102 1.0 release preparations (by @lorentey)
• #106 [OrderedSet] Make _checkInvariants public and call it in more operations (by @lorentey)
• #107 [OrderedSet] Don't let the unchecked init create large sets with no hash table (by @lorentey)
• #110 [run-full-tests.sh] Fix bashism: == vs = (by @lorentey)

Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.

Swift Collections 0.0.7

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.)

Changes

• 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.

Pull requests

• #81 Fix typos: missing subscript parameters (by @ejmarchant)
• #82 Fix documentation for types conforming to ExpressibleByArrayLiteral or ExpressibleByDictionaryLiteral (by @ejmarchant)
• #86 Stop depending on swift-collections-benchmark (by @lorentey)
• #91 [OrderedDictionary] modifyValue → updateValue (by @lorentey)
• #93 Add Benchmarks package to workspace (by @lorentey)
• #92 [OrderedDictionary] Deprecate 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.

Swift Collections 0.0.5

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.

Pull requests

• #64: Add arm64 support to CMake build (by @neonichu)

Thank you to everyone who contributed to this release! Your bug reports, discussions and pull requests all help improve this package.