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