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.
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>
- 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
- Use a persistent DOI-based link rather than linking to ephemeral course material.
- Replace the example heap (borrowed from Wikipedia) with a better one.
* 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>