swift-collections

1.1.0

Commonly used data structures for Swift
apple/swift-collections

What's New

Swift Collections 1.1.0

2024-02-08T00:59:33Z

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

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 by @compnerd in #202
  • [1.1][SortedCollections] Remove for now by @lorentey in #205
  • [Heap] Change value of minimum or maximum element by @CTMacUser in #116
  • [Heap] Prerelease preparations by @lorentey in #210
  • Update README files by @lorentey in #212
  • [manifest] Exclude CMakeLists.txt; remove unnecessary path settings; reindent file by @lorentey in #213
  • Review and finalize (?) set relation predicates for 1.1 by @lorentey in #216
  • Merge.1.0→1.1 by @lorentey in #217
  • Update CMake configuration by @lorentey in #218
  • Cherry pick changes from main to release/1.1 by @lorentey in #219
  • Fix unusual build problems by @lorentey in #221
  • Review & update descriptions throughout the package by @lorentey in #222
  • Review and finalize (?) binary set operations for 1.1 by @lorentey in #223
  • [Xcode] Disable implicit dependencies by @lorentey in #227
  • [OrderedSet] Improve sequence-taking initializer by @lorentey in #226
  • [OrderedSet, BitSet] Fix custom mirror display style by @lorentey in #225
  • Finalize persistent collections API by @lorentey in #224
  • Start working on DocC support by @lorentey in #228
  • Update CMake build configuration by @lorentey in #230
  • [PersistentSet] Iterator.next(): Make inlinable by @lorentey in #233
  • [SetAlgebra types] isEqual(to:) → isEqualSet(to:) by @lorentey in #234
  • [PersistentCollections] Doc & benchmark updates in preparation of API review by @lorentey in #235
  • Apply changes from in-progress review thread by @lorentey in #237
  • [ShareableHashedCollections] API Review: add missing mutating keywords by @lorentey in #238
  • [Benchmarks] Split default huge library up into individual files, one per type by @lorentey in #240
  • [ShareableHashedCollections] Add missing import by @lorentey in #243
  • Unify unsafe bit set implementations by @lorentey in #244
  • Fix warnings in development versions of Swift by @lorentey in #245
  • [HashTreeCollections] Change prefix Shareable to Tree by @lorentey in #242
  • [TreeDictionary] Fix in-place merge operation to properly update the count by @lorentey in #247
  • [cmake] Update CMake configuration by @lorentey in #249
  • Add not so experimental rope implementation by @lorentey in #264
  • Fix off by one error in BitSet by @lorentey in #267
  • Monomodule support by @lorentey in #266
  • Expose a handful of BigString.Index methods by @lorentey in #269
  • BitArray API refinements & additions by @lorentey in #263
  • Make most of Rope inlinable by @lorentey in #270
  • BigString: Fix String.Index._knownScalarAligned by @lorentey in #272
  • Rope: Fix Sendable conformance by @lorentey in #271
  • Require Swift 5.6 by @lorentey in #273
  • [OrderedDictionary] Explicitly mention in documentation that keys/values are ordered by @lorentey in #275
  • [HashCollections] Ensure self doesn’t get destroyed before we’re done working with it by @lorentey in #276
  • Remove obsolete swift(>=5.5)/swift(>=5.6) checks by @lorentey in #277
  • [Xcode] Update Xcode project by @lorentey in #278
  • Minor rope updates by @lorentey in #279
  • [Rope] remove(at:): Fix assertion when removing the last item creates a deficiency by @lorentey in #280
  • Merge changes from release 1.0 to release 1.1 by @lorentey in #283
  • [CollectionUtilities] Silence a warning on 32 bit platforms by @lorentey in #286
  • [BitSet] Fix a thinko in BitSet.isEqualSet by @lorentey in #287
  • Grab bag of fixes for small test issues by @lorentey in #288
  • [Xcode] Set a code sign identity in the Xcode project by @lorentey in #285
  • Rope: Fix trap when replaceSubrange is called on an empty rope by @lorentey in #290
  • Rope.find returns a bogus remainder for the end position by @lorentey in #291
  • Update TreeSet.md by @hassila in #297
  • Fix CustomStringConvertible/CustomDebugStringConvertible conformances by @lorentey in #302
  • [RopeModule] Fix issues in Swift's ABI stable dialect by @lorentey in #318
  • [CMake, Xcode] Update configurations for alternate build systems by @lorentey in #319
  • [RopeModule] Remove unnecessary typealiases by @lorentey in #320
  • [Heap] Improve type-level doc comment by @lorentey in #326
  • [Heap] insert(contentsOf:) Switch to Floyd’s if we’re inserting too many items by @lorentey in #327
  • [1.1] build: support building in Debug mode on Windows by @compnerd in #336
  • Merge release/1.0 to release/1.1 by @lorentey in #348
  • [Heap] Convert min() and max() to properties by @lorentey in #328
  • [BitArray] Disable bitwise operators for now by @lorentey in #353
  • [Heap] Final(?) Heap API adjustments for 1.1 by @lorentey in #354
  • [Benchmarks] Add Collection Equality Benchmarks by @vanvoorden in #351
  • Release preparations for 1.1 by @lorentey in #355
  • [1.1] Fix typos by @lorentey in #357
  • [TreeDictionary][Keys] Add Equatable and Hashable Conformance to TreeDictionary.Keys by @vanvoorden in #352

Swift Collections

Swift Collections is an open-source package of data structure implementations for the Swift programming language.

Read more about the package, and the intent behind it, in the announcement on swift.org.

Contents

The package currently provides the following implementations:

  • BitSet and BitArray, dynamic bit collections.

  • Deque<Element>, a double-ended queue backed by a ring buffer. Deques are range-replaceable, mutable, random-access collections.

  • Heap, a min-max heap backed by an array, suitable for use as a priority queue.

  • OrderedSet<Element>, a variant of the standard Set where the order of items is well-defined and items can be arbitrarily reordered. Uses a ContiguousArray as its backing store, augmented by a separate hash table of bit packed offsets into it.

  • OrderedDictionary<Key, Value>, an ordered variant of the standard Dictionary, providing similar benefits.

  • TreeSet and TreeDictionary, persistent hashed collections implementing Compressed Hash-Array Mapped Prefix Trees (CHAMP). These work similar to the standard Set and Dictionary, but they excel at use cases that mutate shared copies, offering dramatic memory savings and radical time improvements.

The following data structures are currently under development but they aren't ready for inclusion in a tagged release:

Swift Collections uses the same modularization approach as Swift Numerics: it provides a standalone module for each thematic group of data structures it implements. For instance, if you only need a double-ended queue type, you can pull in only that by importing DequeModule. OrderedSet and OrderedDictionary share much of the same underlying implementation, so they are provided by a single module, called OrderedCollections. However, there is also a top-level Collections module that gives you every collection type with a single import statement:

import Collections

var deque: Deque<String> = ["Ted", "Rebecca"]
deque.prepend("Keeley")
deque.append("Nathan")
print(deque) // ["Keeley", "Ted", "Rebecca", "Nathan"]

Project Status

The Swift Collections package is source stable. The version numbers follow Semantic Versioning -- source breaking changes to public API can only land in a new major version.

The public API of version 1.1 of the swift-collections package consists of non-underscored declarations that are marked public in the Collections, BitCollections, DequeModule, HeapModule, OrderedCollections and HashTreeCollections modules.

Interfaces that aren't part of the public API may continue to change in any release, including patch releases. If you have a use case that requires using underscored APIs, please submit a Feature Request describing it! We'd like the public interface to be as useful as possible -- although preferably without compromising safety or limiting future evolution.

By "underscored declarations" we mean declarations that have a leading underscore anywhere in their fully qualified name. For instance, here are some names that wouldn't be considered part of the public API, even if they were technically marked public:

  • FooModule.Bar._someMember(value:) (underscored member)
  • FooModule._Bar.someMember (underscored type)
  • _FooModule.Bar (underscored module)
  • FooModule.Bar.init(_value:) (underscored initializer)

Note that contents of the Tests, Utils and Benchmarks subdirectories aren't public API. We don't make any source compatibility promises about them -- they may change at whim, and code may be removed in any new release. Do not rely on anything about them.

Future minor versions of the package may update these rules as needed.

We'd like this package to quickly embrace Swift language and toolchain improvements that are relevant to its mandate. Accordingly, from time to time, new versions of this package require clients to upgrade to a more recent Swift toolchain release. (This allows the package to make use of new language/stdlib features, build on compiler bug fixes, and adopt new package manager functionality as soon as they are available.) Patch (i.e., bugfix) releases will not increase the required toolchain version, but any minor (i.e., new feature) release may do so.

The following table maps existing package releases to their minimum required Swift toolchain release:

Package version Swift version Xcode release
swift-collections 1.0.x >= Swift 5.3.2 >= Xcode 12.4
swift-collections 1.1.x >= Swift 5.7.2 >= Xcode 14.2

(Note: the package has no minimum deployment target, so while it does require clients to use a recent Swift toolchain to build it, the code itself is able to run on any OS release that supports running Swift code.)

Using Swift Collections in your project

To use this package in a SwiftPM project, you need to set it up as a package dependency:

// swift-tools-version:5.9
import PackageDescription

let package = Package(
  name: "MyPackage",
  dependencies: [
    .package(
      url: "https://github.com/apple/swift-collections.git", 
      .upToNextMinor(from: "1.1.0") // or `.upToNextMajor
    )
  ],
  targets: [
    .target(
      name: "MyTarget",
      dependencies: [
        .product(name: "Collections", package: "swift-collections")
      ]
    )
  ]
)

Contributing to Swift Collections

We have a dedicated Swift Collections Forum where people can ask and answer questions on how to use or work on this package. It's also a great place to discuss its evolution.

If you find something that looks like a bug, please open a Bug Report! Fill out as many details as you can.

Working on the package

We have some basic documentation on package internals that will help you get started.

By submitting a pull request, you represent that you have the right to license your contribution to Apple and the community, and agree by submitting the patch that your contributions are licensed under the Swift License, a copy of which is provided in this repository.

Fixing a bug or making a small improvement

  1. Submit a PR with your change. If there is an existing issue for the bug you're fixing, please include a reference to it.
  2. Make sure to add tests covering whatever changes you are making.

Proposing a small enhancement

  1. Raise a Feature Request. Discuss why it would be important to implement it.
  2. Submit a PR with your implementation, participate in the review discussion.
  3. When there is a consensus that the feature is desirable, and the implementation works well, it is fully tested and documented, then it will be merged.
  4. Rejoice!

Proposing the addition of a new data structure

We intend this package to collect generally useful data structures -- the ones that ought to be within easy reach of every Swift engineer's basic toolbox. The implementations we ship need to be of the highest technical quality, polished to the same shine as anything that gets included in the Swift Standard Library. (The only real differences are that this package isn't under the formal Swift Evolution process, and its code isn't ABI stable.)

Accordingly, adding a new data structure to this package is not an easy or quick process, and not all useful data structures are going to be a good fit.

If you have an idea for a data structure that might make a good addition to this package, please start a topic on the forum, explaining why you believe it would be important to implement it. This way we can figure out if it would be right for the package, discuss implementation strategies, and plan to allocate capacity to help.

Not all data structures will reach a high enough level of usefulness to ship in this package -- those that have a more limited audience might work better as a standalone package. Of course, reasonable people might disagree on the importance of including any particular data structure; but at the end of the day, the decision whether to take an implementation is up to the maintainers of this package.

If maintainers have agreed that your implementation would likely make a good addition, then it's time to start work on it. Submit a PR with your implementation as soon as you have something that's ready to show! We'd love to get involved as early as you like. Historically, the best additions resulted from close work between the contributor and a package maintainer.

Participate in the review discussion, and adapt code accordingly. Sometimes we may need to go through several revisions over multiple months! This is fine -- it makes the end result that much better. When there is a consensus that the feature is ready, and the implementation is fully tested and documented, the PR will be merged by a maintainer. This is good time for a small celebration -- merging is a good indicator that the addition will ship at some point.

Historically, PRs adding a new data structure have typically been merged to a new feature branch rather than directly to a release branch or main, and there was an extended amount of time between the initial merge and the tag that shipped the new feature. Nobody likes to wait, but getting a new data structure implementation from a state that was ready to merge to a state that's ready to ship is actually quite difficult work, and it takes maintainer time and effort that needs to be scheduled in advance. The closer an implementation is to the coding conventions and performance baseline of the Standard Library, the shorter this wait is likely to become, and the fewer changes there will be between merging and shipping.

Code of Conduct

Like all Swift.org projects, we would like the Swift Collections project to foster a diverse and friendly community. We expect contributors to adhere to the Swift.org Code of Conduct. A copy of this document is available in this repository.

Contact information

The current code owner of this package is Karoy Lorentey (@lorentey). You can contact him on the Swift forums, or by writing an email to klorentey at apple dot com. (Please keep it related to this project.)

In case of moderation issues, you can also directly contact a member of the Swift Core Team.

Description

  • Swift Tools 5.7.0
View More Packages from this Author

Dependencies

  • None
Last updated: Fri Apr 12 2024 18:29:54 GMT-0900 (Hawaii-Aleutian Daylight Time)