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
|
/*!
* A simple map based on a vector for small integer keys. Space requirements
* are O(highest integer key).
*/
import core::option;
import core::option::{some, none};
import dvec::{dvec, extensions};
import 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();
ret smallintmap_(@{v: 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() { ret self.v.get_elt(key); }
ret 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 {
alt find(self, key) {
none { error!{"smallintmap::get(): key not present"}; fail; }
some(v) { ret v; }
}
}
/// Returns true if the map contains a value for the specified key
fn contains_key<T: copy>(self: smallintmap<T>, key: uint) -> bool {
ret !option::is_none(find(self, key));
}
/// Implements the map::map interface for smallintmap
impl <V: copy> of map::map<uint, V> for smallintmap<V> {
fn size() -> uint {
let mut sz = 0u;
for self.v.each |item| {
alt item { some(_) { sz += 1u; } _ {} }
}
sz
}
#[inline(always)]
fn insert(+key: uint, +value: V) -> bool {
let exists = contains_key(self, key);
insert(self, key, value);
ret !exists;
}
fn remove(&&key: uint) -> option<V> {
if key >= self.v.len() { ret none; }
let old = self.v.get_elt(key);
self.v.set_elt(key, none);
old
}
fn clear() {
self.v.set(~[mut]);
}
fn contains_key(&&key: uint) -> bool {
contains_key(self, key)
}
fn get(&&key: uint) -> V { get(self, key) }
fn [](&&key: uint) -> V { get(self, key) }
fn find(&&key: uint) -> option<V> { find(self, key) }
fn rehash() { fail }
fn each(it: fn(&&uint, V) -> bool) {
let mut idx = 0u, l = self.v.len();
while idx < l {
alt self.v.get_elt(idx) {
some(elt) {
if !it(idx, elt) { break; }
}
none { }
}
idx += 1u;
}
}
fn each_key(it: fn(&&uint) -> bool) {
let mut idx = 0u, l = self.v.len();
while idx < l {
if self.v.get_elt(idx) != none && !it(idx) { ret; }
idx += 1u;
}
}
fn each_value(it: fn(V) -> bool) {
self.each(|_i, v| it(v));
}
}
impl extensions<V: copy> of ops::index<uint, V> for smallintmap<V> {
pure fn index(&&key: uint) -> V {
unchecked {
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>
}
|
