-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinaryMap.swift
91 lines (78 loc) · 1.51 KB
/
BinaryMap.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
struct BinaryMap<K: Comparable, V> : CustomStringConvertible {
var keys = [K](),
vals = [V](),
count = 0
func get(_ key: K) -> V? {
if let i = binarySearch(elements: keys, target: key) {
return vals[i]
} else {
return nil
}
}
mutating func set(_ key: K, _ val: V) {
if let i = binarySearch(elements: keys, target: key) {
vals[i] = val
} else {
insert(key, val)
count += 1
}
}
private mutating func insert(_ key: K, _ val: V) {
switch (count) {
case 0:
keys.append(key)
vals.append(val)
return
case 1:
if key > keys[0] {
keys.append(key)
vals.append(val)
} else {
keys.insert(key, at: 0)
vals.insert(val, at: 0)
}
return
// 2+ elements
default:
// Key should be first
if key < keys[0] {
keys.insert(key, at: 0)
vals.insert(val, at: 0)
return
}
// Key should be somewhere in the middle
for i in 1 ..< count {
if key > keys[i-1] && key < keys[i] {
keys.insert(key, at: i)
vals.insert(val, at: i)
return
}
}
// Key should be last
keys.append(key)
vals.append(val)
}
}
mutating func remove(_ key: K) {
if let i = binarySearch(elements: keys, target: key) {
keys.remove(at: i)
vals.remove(at: i)
count -= 1
}
}
subscript(key: K) -> V? {
get {
return self.get(key)
}
set(val) {
self.set(key, val!)
}
}
var description: String {
var desc = "BinaryMap[\n"
for i in 0 ..< count {
desc += " \(keys[i]) : \(vals[i])\n"
}
return desc + "]"
}
}