-
Notifications
You must be signed in to change notification settings - Fork 12.5k
/
smallintmap.rs
145 lines (133 loc) · 3.71 KB
/
smallintmap.rs
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*!
* A simple map based on a vector for small integer keys. Space requirements
* are O(highest integer key).
*/
#[forbid(deprecated_mode)];
#[forbid(deprecated_pattern)];
use core::option;
use core::option::{Some, None};
use dvec::DVec;
use map::Map;
// FIXME (#2347): Should not be @; there's a bug somewhere in rustc that
// requires this to be.
type SmallIntMap_<T: Copy> = {v: DVec<Option<T>>};
enum SmallIntMap<T:Copy> {
SmallIntMap_(@SmallIntMap_<T>)
}
/// Create a smallintmap
fn mk<T: Copy>() -> SmallIntMap<T> {
let v = DVec();
return SmallIntMap_(@{v: move v});
}
/**
* Add a value to the map. If the map already contains a value for
* the specified key then the original value is replaced.
*/
#[inline(always)]
fn insert<T: Copy>(self: SmallIntMap<T>, key: uint, +val: T) {
//io::println(fmt!("%?", key));
self.v.grow_set_elt(key, None, Some(val));
}
/**
* Get the value for the specified key. If the key does not exist
* in the map then returns none
*/
pure fn find<T: Copy>(self: SmallIntMap<T>, key: uint) -> Option<T> {
if key < self.v.len() { return self.v.get_elt(key); }
return None::<T>;
}
/**
* Get the value for the specified key
*
* # Failure
*
* If the key does not exist in the map
*/
pure fn get<T: Copy>(self: SmallIntMap<T>, key: uint) -> T {
match find(self, key) {
None => {
error!("smallintmap::get(): key not present");
fail;
}
Some(v) => return v
}
}
/// Returns true if the map contains a value for the specified key
fn contains_key<T: Copy>(self: SmallIntMap<T>, key: uint) -> bool {
return !find(self, key).is_none();
}
/// Implements the map::map interface for smallintmap
impl<V: Copy> SmallIntMap<V>: map::Map<uint, V> {
pure fn size() -> uint {
let mut sz = 0u;
for self.v.each |item| {
match *item {
Some(_) => sz += 1u,
_ => ()
}
}
sz
}
#[inline(always)]
fn insert(+key: uint, +value: V) -> bool {
let exists = contains_key(self, key);
insert(self, key, value);
return !exists;
}
fn remove(+key: uint) -> bool {
if key >= self.v.len() {
return false;
}
let old = self.v.get_elt(key);
self.v.set_elt(key, None);
old.is_some()
}
fn clear() {
self.v.set(~[]);
}
fn contains_key(+key: uint) -> bool {
contains_key(self, key)
}
fn contains_key_ref(key: &uint) -> bool {
contains_key(self, *key)
}
fn get(+key: uint) -> V { get(self, key) }
pure fn find(+key: uint) -> Option<V> { find(self, key) }
fn rehash() { fail }
pure fn each(it: fn(+key: uint, +value: V) -> bool) {
self.each_ref(|k, v| it(*k, *v))
}
pure fn each_key(it: fn(+key: uint) -> bool) {
self.each_ref(|k, _v| it(*k))
}
pure fn each_value(it: fn(+value: V) -> bool) {
self.each_ref(|_k, v| it(*v))
}
pure fn each_ref(it: fn(key: &uint, value: &V) -> bool) {
let mut idx = 0u, l = self.v.len();
while idx < l {
match self.v.get_elt(idx) {
Some(elt) => if !it(&idx, &elt) { break },
None => ()
}
idx += 1u;
}
}
pure fn each_key_ref(blk: fn(key: &uint) -> bool) {
self.each_ref(|k, _v| blk(k))
}
pure fn each_value_ref(blk: fn(value: &V) -> bool) {
self.each_ref(|_k, v| blk(v))
}
}
impl<V: Copy> SmallIntMap<V>: ops::Index<uint, V> {
pure fn index(&&key: uint) -> V {
unsafe {
get(self, key)
}
}
}
/// Cast the given smallintmap to a map::map
fn as_map<V: Copy>(s: SmallIntMap<V>) -> map::Map<uint, V> {
s as map::Map::<uint, V>
}