What "distance" between indexes mean in `SortedSet`?

Related Projects Collections
,
1

I'd expect that SortedSet.distance(from:to:) would return the same result as Array.distance(from:to).
I've noticed however that "distance" means something different in SortedSet. I don't fully understand the underlying implementation but I guess it represents something meaningful in a B-Tree structure.

var set = SortedSet<Int>()

for i in 0..<50 {
   set.insert(i)
}
        
set.forEach {
   let d = set.distance(from: set.startIndex, to: set.index(of: $0)!)
   print(d) 
}

Output:

...
34 --> 34
35 --> 3
36 --> 36
...

However, since SortedSet is all about sorting, I'd want to get an "absolute" index (Int) of the particular element.
Is that possible with SortedSet?

2

Can you clarify your output here? set.distance(from:to:) returns an Int, which you then print, but your proposed output has arrows and other fun stuff in it. I assume the second column is the Index? Can you provide the full output?

3

More broadly, distance should absolutely return the number of calls to index(after:) required to get from start to end. If it doesn't, that's a bug.

1 Like
4

@lukasa Oh gosh, sorry, I pasted output after modifying a code a little.
Here's a code:

var set = SortedSet<Int>()
        
for i in 0..<50 {
   set.insert(i)
}
        
set.forEach {
   let i = set.index(of: $0)!
   let v = set[i]
   let d = set.distance(from: set.startIndex, to: i)
   print("\(v) --> \(d)")

   if i == set.startIndex {
      print("Current `index` equals `startIndex`.")
      print("set[index] = \(set[i]). set[startIndex] = \(set[set.startIndex])")
   }
}

And full output:

0 --> 0
Current index equals startIndex.
set[index] = 0. set[startIndex] = 0
1 --> 1
2 --> 0
Current index equals startIndex.
set[index] = 2. set[startIndex] = 0
3 --> 3
4 --> 4
5 --> 1
6 --> 6
7 --> 7
8 --> 0
Current index equals startIndex.
set[index] = 8. set[startIndex] = 0
9 --> 9
10 --> 10
11 --> 9
12 --> 12
13 --> 13
14 --> 10
15 --> 15
16 --> 16
17 --> 1
18 --> 18
19 --> 19
20 --> 18
21 --> 21
22 --> 22
23 --> 19
24 --> 24
25 --> 25
26 --> 2
27 --> 27
28 --> 28
29 --> 27
30 --> 30
31 --> 31
32 --> 28
33 --> 33
34 --> 34
35 --> 3
36 --> 36
37 --> 37
38 --> 36
39 --> 39
40 --> 40
41 --> 37
42 --> 42
43 --> 43
44 --> 38
45 --> 45
46 --> 46
47 --> 47
48 --> 48
49 --> 49

The issue is easiest to notice when index equals to startIndex but getting values for those indexes returns different results.
It definitely looks like a bug. I'll report on Github.

1 Like