42 Commits
Author SHA1 Message Date
Manish Ram c2886d53ee Fix broken links in README and Container-design.md 2026-11-01 15:03:15 -08:00
Sixtos 42446a969f Document standalone macOS backdeployment requirements 2026-10-22 23:41:01 -06:00
Karoy Lorentey a1f0f1411c Update README 2026-09-25 16:01:45 -07:00
apple-ospo[bot] bb7c1a33d4 Replace repo-level CODE_OF_CONDUCT file with the inherited org-wide Code of Conduct in .github repo. 2026-09-25 17:41:17 +00:00
Karoy Lorentey 021a54b8cc Update docs 2026-09-22 18:56:47 -07:00
Karoy Lorentey 78bb4bf6b9 Update README 2026-09-21 13:33:58 -07:00
Karoy Lorentey 9d0f2adb6b Update README 2026-06-05 18:50:16 -07:00
Karoy Lorentey e5236d4e8e Update README 2026-05-07 15:46:33 -07:00
Karoy Lorentey 16d6b8e1fe [ContainersPreview] Inout ⟹ MutableRef 2026-05-06 18:28:07 -07:00
Karoy Lorentey a6fd64697a [ContainersPreview] Borrow ⟹ Ref
Also update the type’s public API surface to reflect SE-0519, leaving deprecated aliases for the old names.
2026-05-06 18:00:13 -07:00
Karoy Lorentey 146056a641 [ContainersPreview] Box ⟹ UniqueBox
Also update the type’s public API surface to reflect SE-0517, leaving deprecated aliases for the old names.
2026-05-05 17:31:05 -07:00
Karoy Lorentey f652543a50 [ContainersPreview] Producer.ProducerError ⟹ Producer.Failure
Reserving a unique name for Producer’s failure type seems unwise, especially if we end up Producer refining a throwing BorrowingSequence protocol.
2026-04-30 13:31:28 -07:00
Karoy Lorentey 5e70e6e846 Update README 2026-03-17 16:55:38 -07:00
Karoy Lorentey ccf872ae97 Add some decorative badges in the README 2026-03-06 18:15:42 -08:00
Karoy Lorentey 03fea65678 Update README 2026-03-05 14:27:32 -08:00
Karoy Lorentey 5b05a1b42b Update README in preparation of the 1.4.0 release 2026-02-09 17:40:18 -08:00
Karoy Lorentey ccb6059969 Update docs
Final documentation pass
2025-09-29 09:23:00 -07:00
Karoy Lorentey 5cc7f613d6 Update README 2025-09-26 22:38:18 -07:00
Alejandro Alonso 377d2a55a8 Fix landing page of collections documentation 2025-09-24 23:21:02 -07:00
Alex Azarov 2d5ed365ff Fix API documentation links in README.md 2025-06-28 17:36:05 +02:00
Karoy Lorentey a09d7cdf45 Drop support for the Swift 5.9.* toolchains 2025-05-16 13:05:36 -07:00
Karoy Lorentey 5a60599749 Update README 2024-09-24 18:29:53 -07:00
Karoy Lorentey e424b48761 [README] Describe branching strategy 2024-02-12 11:07:48 -08:00
Karoy Lorentey 20dd1fc504 [README] Update doc links 2024-02-12 11:07:34 -08:00
Karoy Lorentey 41b95865a2 Update README 2024-02-02 16:27:21 -08:00
Karoy Lorentey e21c18c05c Update Swift version references in docs 2024-02-02 16:20:22 -08:00
Karoy Lorentey 4b6978bf8b Require Swift 5.6
Swift 5.8 is out now, so let’s bump the minimum required toolchain to Swift 5.6. (The package wants to support three major language releases, and now that 5.8 is out, supporting 5.5 would bump that to four.)
2023-04-10 17:08:50 -07:00
Karoy Lorentey b8ef14f0c0 ShareableHashedCollections → HashTreeCollections 2022-11-28 21:35:37 -08:00
Karoy Lorentey e8fc3ee4cd [PersistentCollections] Rename to SharableHashedCollections
`PersistentSet` → `ShareableSet`
`PersistentDictionary` → `ShareableDictionary`
`PersistentCollections` → `ShareableHashedCollections`
2022-11-07 18:10:16 -08:00
Karoy Lorentey 39bdcca7c9 Update README files
- Fix issues reported by @benrimmington (thanks!)
- Update wording on evolving Swift toolchain requirements
- Update contributor guide on adding a new data structure to better reflect reality
- Add an extra sentence on combinatorial tests
2022-10-16 17:06:32 -07:00
Karoy Lorentey cd493b04c8 Update README in preparation to tagging 1.1.0 2022-10-09 17:11:03 -07:00
Karoy Lorentey 9a9d7d87d8 Merge branch 'release/1.0'
# Conflicts:
#	.swiftpm/xcode/xcshareddata/xcschemes/swift-collections-Package.xcscheme
#	Utils/swift-collections.xcworkspace/xcshareddata/xcschemes/Collections.xcscheme
#	Utils/swift-collections.xcworkspace/xcshareddata/xcschemes/OrderedCollections.xcscheme
#	Utils/swift-collections.xcworkspace/xcshareddata/xcschemes/swift-collections-Package.xcscheme
2022-09-02 15:30:31 -07:00
Karoy Lorentey f504716c27 Update README for 1.0.3 2022-09-01 17:32:57 -07:00
James Paolantonio 276ddee5df Fix link to package internal documentation 2021-10-22 15:47:11 -04:00
Karoy Lorentey c46c77f7f8 Note that Heap hasn't been tagged yet & list other enhancements in progress 2021-09-10 12:59:43 -07:00
Karoy Lorentey 5f255a887e Merge branch 'release/1.0' 2021-09-10 11:58:12 -07:00
Karoy Lorentey 4520853f49 Update README for 1.0 2021-09-03 19:11:29 -07:00
Tyler Stromberg 0d73c74c9f Fix Markdown link in README (#77) 2021-08-13 18:31:33 -07:00
940c963bc4 Add a min-max heap implementation that can be used to back a priority queue (#61)
* Add PriorityQueue implementation built on top of a MinMaxHeap

* Merge MinMaxHeap into PriorityQueue

* Add `unordered` read-only view into underlying heap

* Start filling in PriorityQueue benchmarks

* Implement our own swapAt()

storage.swapAt exhibits excessive allocations

* Rename _delete(at:) to _remove(at:)

* Rename removeMin/removeMax -> popMin/popMax

* Use magic values 1, 2 to refer to the items in the first max level

Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>

* Specify logarithmic complexities as "O(log `count`) / 2" instead of "O(log n)"

Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>

* Clarify logic in popMax

* Simplify logic in _remove(at:)

* Move the bounds checking into the various index computation methods

They will all now return `nil` for invalid indices.

* Floyd's heap construction algorithm should start from count/2 - 1

* Add ObjC wrapper around CFBinaryHeap to benchmarks

* Fix benchmarks that broke because of renames

* Add removeMin/removeMax

* Make _minMaxHeapIsMinLevel an instance method

* Split _indexOfChildOrGrandchild(of:sortedUsing:) into two separate functions

There is a large performance cost with passing a predicate function.

* Defer comparing children when determining largest/smallest descendant

If the given index has 4 grandchildren, we can skip comparing the children.

* Added an iterator of the min and max views to the priority queue

* seperated iterator implementation into a new file

* Use renamed popMin/Max in Iterator instead of removeMin/Max

* Fix code formatting

Indentation of 2 spaces and 80 char column width

* Add sequence initializer

* Fix code formatting in benchmarks

* Fix benchmark names

* Remove init from Collection

This should already be handled by the init from Sequence

* Add conformance to ExpressibleByArrayLiteral

* Move ExpressibleByArrayLiteral conformance to separate file

* Update PriorityQueue's CMakeLists.txt

* Make ascending and descending iterators public

* Inline ALL THE THINGS!

* Iterative instead of recursive implementation, @inline(__always) a couple more critical functions.

* Address PR feedback, thanks!

* Check invariants on insertion and deletion

* Minor code formatting cleanup

* Add copyright header to test file

* Fix missing empty line

* Add naïve implementation of insert(contentsOf:)

* Add documentation on complexity of init<S:Sequence>(_:)

* Cite source paper in documentation

* Rename PriorityQueue -> MinMaxHeap

We'll be reintroducing the PriorityQueue type as a wrapper.

* Mark insert(contentsOf:) as inlinable

This results in ~10x speedup in my initial tests.

* Rename argument label "startingAt" -> "elementAt"

These functions used to be recursive, so "startingAt" made sense.
Now that they're iterative, we should fix the label.

* Remove coefficients from complexity docs

* Make `_minMaxHeapIsMinLevel` take an index instead of a count

* Rename MinMaxHeap -> Heap

* Add documentation for Heap

* Make Heap.Iterator init and direction internal

* Fix reference to queue in documentation

Co-authored-by: Dante Broggi <34220985+Dante-Broggi@users.noreply.github.com>

* Don't wrap integers in CFBinaryHeap benchmark in NSNumber

* Avoid heap allocation altogether

* Add table with performance of operations

* Add heap performance graph

* Apply suggestions from code review

Co-authored-by: Karoy Lorentey <klorentey@apple.com>

* Make _checkInvariants comments a doc comment

* Split Heap.Iterator into two separate views

Adapted from Daryle Walker's (github.com/CTMacUser) suggestions

* Prefix heap storage variable with an underscore

* Update benchmark image

* Fix Sources/PriorityQueueModule/CMakeLists.txt

Heap+Iterator.swift was renamed to Heap+OrderedViews.swift

Co-authored-by: Karoy Lorentey <klorentey@apple.com>

* CFBinaryHeap is only available on Darwin

* CFBinaryHeap is only available on Darwin

* CFBinaryHeap is only available on Darwin

Co-authored-by: Tim Vermeulen <tvermeulen@apple.com>
Co-authored-by: Amanuel Ephem <amanuelephrem776@gmail.com>
Co-authored-by: Joakim Hassila <joj@mac.com>
Co-authored-by: Dante Broggi <34220985+Dante-Broggi@users.noreply.github.com>
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2021-08-06 22:21:23 -07:00
Todd Pressley 62c3a3a18e Correct typo for address sanitizer 2021-04-09 02:35:27 -07:00
James Power acdb003117 Fixes link to combinatorics. 2021-04-08 22:56:22 -07:00
Karoy Lorentey a2bcac435f Initial import.
Introduce OrderedCollections module
2021-04-05 09:41:00 -07:00