Comments (3)
(Beware,
SortedSet
isn't ready for production use yet. These reports are very much appreciated, though!)
Yup, I saw the Readme notice but I needed a SortedSet
in my app and thought I'll give Swift Collections a try :)
In the future, if time allows, I'll try to contribute fixes on my own. But in the meantime, I hope these bug reports will be helpful :)
from swift-collections.
After spending some time I figured out:
- The bug is across the SortedCollections module i.e in
SortedSet
,SortedDictionary
and_BTree
(root cause of the bug lies in here).
- Observed in SortedSet
func test_indexOf() {
var set = SortedSet<Int>()
for i in 0..<50 {
set.insert(i)
}
for (item, index) in zip(set, set.indices) {
let i = set.index(of: item)!
if i != index {
print("Some issue with index(of:)")
break
}
}
}
Output:
Some issue with index(of:)
- Observed in SortedDictionary
func test_indexForKey() {
var sortedDict: SortedDictionary<Int, String> = [:]
for i in 0..<50 {
sortedDict[i] = "\(i)"
}
for (index, item) in zip(sortedDict.indices, sortedDict) {
let i = sortedDict.index(forKey: item.key)!
if i != index {
print("Some issue with index(forKey:)")
break
}
}
}
Output:
Some issue with index(forKey:)
SortedSet.index(of:)
andSortedDictionary.index(forKey:)
are basically a call to_BTrees
'sfindAnyIndex(forKey key: Key) -> Index?
function. So let's test if_BTree.findAnyIndex(forKey:)
is correct. I used this test case.
func test_findAnyIndex() {
var tree = _BTree<Int, String>()
for (key, value) in (0..<50).map({ ($0, "\($0)") }) {
tree.updateAnyValue(value, forKey: key)
}
for (index, item) in zip(tree.indices, tree) {
let i = tree.findAnyIndex(forKey: item.key)
if i != index {
print("Problems with findAnyIndex")
break
}
}
}
Output:
Problems with findAnyIndex
- I then wrote my own
findAnyIndex
as such (O(log n)
implementation):
extension _BTree {
@inlinable
internal func findAnyIndex(forKey key: Key) -> Index? {
var (lo, hi) = (startIndex, endIndex)
while lo < hi {
let mid = index(lo, offsetBy: distance(from: lo, to: hi)/2)
if self[mid].key < key {
lo = index(after: mid)
} else {
hi = mid
}
}
return lo < endIndex && self[lo].key == key ? lo : nil
}
}
and all the bugs vanished.
The test case in the issue gives the following output now.
0 --> 0
Current `index` equals `startIndex`.
set[index] = 0. set[startIndex] = 0
1 --> 1
2 --> 2
3 --> 3
4 --> 4
5 --> 5
6 --> 6
7 --> 7
8 --> 8
9 --> 9
10 --> 10
11 --> 11
12 --> 12
13 --> 13
14 --> 14
15 --> 15
16 --> 16
17 --> 17
18 --> 18
19 --> 19
20 --> 20
21 --> 21
22 --> 22
23 --> 23
24 --> 24
25 --> 25
26 --> 26
27 --> 27
28 --> 28
29 --> 29
30 --> 30
31 --> 31
32 --> 32
33 --> 33
34 --> 34
35 --> 35
36 --> 36
37 --> 37
38 --> 38
39 --> 39
40 --> 40
41 --> 41
42 --> 42
43 --> 43
44 --> 44
45 --> 45
46 --> 46
47 --> 47
48 --> 48
49 --> 49
And also the test cases I made are all working just fine now.
Hope this helps!🤝
from swift-collections.
Yep, this is definitely a bug!
(Beware, SortedSet
isn't ready for production use yet. These reports are very much appreciated, though!)
from swift-collections.
Related Issues (20)
- Update `OrderedCollection` package to use iOS 11 HOT 1
- API-NUMPY-METADATA HOT 2
- `Deque` lacks `capacity` HOT 2
- Support fixed-size `Deque` HOT 2
- OrderedDictionary decoding. HOT 1
- OrderedDictionary insert(at:) HOT 1
- OrderedDictionary `updateValue` autoclosure for insertion index
- Failed to resolve dependencies Dependencies could not be resolved because no versions HOT 1
- Ship Sendable annotations in 1.0.6 HOT 1
- `Heap` documentation does not explain what a heap is
- `Heap.insert(contentsOf:)` is quasilinear instead of linear complexity
- OrderedSet `append(contentsOf:)` with insertion check result/results
- OrderedDictionary.values and OrderedSet Performance Problems when SwiftUI.List is paired with SwiftUI.NavigationStack HOT 6
- Ship release 1.0.6 HOT 11
- Ship release 1.1.0 HOT 19
- BitArray's bitwise operations should allow operating on slices HOT 2
- Version 1.1.0 fails to compile HOT 11
- Add Privacy Manifest HOT 7
- The bundle at path Payload/MyApp.app/Frameworks/_CollectionsUtilities.framework has an invalid CFBundleIdentifier '_CollectionsUtilities' HOT 12
- Mar 3, 2024 Debit MONOKAI, AMSTERDAM, 00000 1% Cash Back -$13.56. Why is VS Code requesting a purchase HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from swift-collections.