43 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
Karoy Lorentey 021a54b8cc Update docs 2026-09-22 18:56:47 -07:00
Karoy Lorentey 5d0faff6c7 Update container design document 2026-09-21 13:07:04 -07:00
Elior Pommier cabf7390ce Fix typos in documentation and comments
Corrects 25 misspellings across DocC articles, design documentation and doc
comments. Prose only: no identifiers, no public API, no behaviour change.

| Typo | Correction | Count |
|---|---|---|
| `offseting` | `offsetting` | 7 |
| `valud` | `value` | 4 |
| `necessarilly` | `necessarily` | 3 |
| `recommmend` | `recommend` | 2 |
| `Mutablility` | `Mutability` | 1 |
| `childs` | `child's` | 1 |
| `constaints` | `constraints` | 1 |
| `destintion` | `destination` | 1 |
| `explan` | `explain` | 1 |
| `forcuses` | `focuses` | 1 |
| `ot` | `or` | 1 |
| `succcess` | `success` | 1 |
| `unqiue` | `unique` | 1 |

Two of these are worth a second look, since they are not pure spelling:

- `_HTable+Removal.swift:18` reads "without marking it as unoccupied ot
  restoring the hash table's other invariants". Read as `or`, matching the
  sentence, and deliberately not as a prefix of `other` later on the line.
- `_Node.UnsafeHandle+Deletion.swift:369` reads "reuse the left childs node".
  Corrected to the possessive `child's` rather than `children`, which is what
  a plain spellchecker suggests but does not fit the sentence.

`valud` is corrected to `value` to match the wording of the equivalent
parameter documentation on `swapAt(_:_:)`.

One change is outside documentation: `CheckContainer.swift:476` fixes
`succcess` inside a test assertion message. It is a human-readable string, not
an expected value, so no test behaviour changes.

Deliberately left alone:

- `isDisjoint(with:)-54iy6` in `OrderedSet.md` is a DocC disambiguation hash,
  not a misspelling.
- `Peristent` in the 2022 ShareableHashedCollections review document, which is
  an archived record of a past review rather than living documentation.

Found with `typos-cli`, then reviewed by hand; the tool's raw output also
flagged identifiers and symbol hashes, which are not included here.
2026-09-18 14:31:47 +02:00
Karoy Lorentey f607b99695 Update design docs 2026-08-25 14:10:06 -07:00
Karoy Lorentey 01f13a1d0f Update docs 2026-07-28 19:43:06 -07:00
Karoy Lorentey 0afc8e0e16 Merge pull request #694 from lorentey/container-updates 2026-07-23 09:59:36 -07:00
Karoy Lorentey 1e5be56021 Merge pull request #691 from ZayanKhan-12/fix-internals-doc-links
Fix stale paths in internals documentation
2026-07-22 19:24:36 -07:00
Karoy Lorentey e12620f050 Update container design document 2026-07-22 19:07:54 -07:00
ZayanKhan-12andClaude Fable 5 6321c6cc34 Fix stale paths in internals documentation
The test support library moved from Sources/_CollectionsTestSupport
to Tests/_CollectionsTestSupport; update the 23 links (and the one
label) in Documentation/Internals/README.md accordingly. The same
README's Benchmarks link and ReleaseChecklist's Utils script links
were written relative to the repo root rather than
Documentation/Internals/.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
2026-07-22 14:46:57 -04:00
Karoy Lorentey 978e8a54a5 Additional fixes 2026-07-21 19:21:09 -07:00
Karoy Lorentey e7c2b34991 Fix typos and do some basic copy editing 2026-07-21 18:36:29 -07:00
Karoy Lorentey 376f4dc087 Document the container design [draft] 2026-07-21 16:32:03 -07:00
Karoy Lorentey 11443c0531 Enforce uniform license headers 2026-03-07 10:26:28 -08:00
Karoy Lorentey d9b09ecde8 Update copyright dates 2026-03-05 19:39:20 -08:00
Karoy Lorentey e004cd36fa Merge branch 'release/1.1' into merge.1.1→main
# Conflicts:
#	CMakeLists.txt
#	README.md
2024-02-07 17:35:40 -08:00
Karoy Lorentey ffa4a58bc1 Update remaining copyright notices 2024-02-02 16:20:22 -08:00
Karoy Lorentey cd03e5b471 Merge branch 'release/1.1'
# Conflicts:
#	Sources/BitCollections/CMakeLists.txt
#	Sources/HashTreeCollections/CMakeLists.txt
2023-11-27 12:02:32 -08:00
Karoy Lorentey 53831b3a22 [Heap] Update docs 2023-11-14 19:10:35 -08:00
Karoy Lorentey 33e2e610f5 Merge branch 'release/1.0' into release/1.1
# Conflicts:
#	Tests/_CollectionsTestSupport/MinimalTypes/MinimalDecoder.swift
2023-11-14 18:06:24 -08:00
kati-kms 5193e405bd Fix typos: OrderedSet.md Documentation 2023-11-10 15:38:16 +09:00
Karoy Lorentey 90b67c44ea Update ReleaseChecklist.md 2023-11-07 17:56:09 -08:00
Karoy Lorentey 339f167745 [ShareableHashedCollections] API Review: add missing mutating keywords 2022-11-07 18:53:07 -08:00
Karoy Lorentey 98d519ec12 [ShareableHashedCollections] Update link in API review document 2022-11-07 18:26:38 -08:00
Karoy Lorentey bab7b7a373 [ShareableHashedCollections] Update API review document 2022-11-07 18:10:16 -08:00
Karoy Lorentey 1098c52654 Add API review proposal for PersistentCollections 2022-11-07 18:10:15 -08:00
Karoy Lorentey 03832459ac Update README files, harder this time 2022-10-18 21:28:26 -07: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 8b06c61c7e Merge branch 'release/1.0' into release/1.1 2022-10-11 11:24:28 -07:00
ensan 0f92943ba3 Fix rethrows position
Minor typo fix.
2022-10-03 11:57:28 +09:00
Karoy Lorentey 286fedb1e8 Merge branch 'release/1.0' 2021-11-15 17:01:49 -08:00
Karoy Lorentey f41f2cae69 [Heap] Update docs 2021-10-11 14:54:59 -07:00
Karoy Lorentey 7f57a0ed1c [OrderedSet][doc] Fix thinko 2021-09-14 11:50:31 -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
Karoy Lorentey 9adbe3e87b [docs] Add a release checklist 2021-09-03 19:11:29 -07:00
Karoy Lorentey 1e68069c98 [OrderedDictionary] modifyValue → updateValue (#91)
* [OrderedDictionary] modifyValue → updateValue

* Update CMakeLists.txt
2021-08-19 19:26:41 -07:00
Karoy Lorentey 53a870dd0b [OrderedDictionary] modifyValue → updateValue (#91)
* [OrderedDictionary] modifyValue → updateValue

* Update CMakeLists.txt
2021-08-19 15:42:17 -07:00
Karoy Lorentey 1eea663318 [Heap] Update implementation details section in docs (#84)
- Use a persistent DOI-based link rather than linking to ephemeral course material.
- Replace the example heap (borrowed from Wikipedia) with a better one.
2021-08-17 13:46:10 -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
Saleem Abdulrasool b91621e0fc Documentation: remove invalid file characters (#34)
`:` is not supported on Windows as a valid file name character.  Replace
the `:` with `-`.
2021-05-10 10:46:22 -07:00
Karoy Lorentey bd924007a2 Add the benchmarking config used in the announcement post on swift.org 2021-04-05 09:41:00 -07:00
Karoy Lorentey a2bcac435f Initial import.
Introduce OrderedCollections module
2021-04-05 09:41:00 -07:00