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
|
/*!
* A simple map based on a vector for small integer keys. Space requirements
* are O(highest integer key).
*/
#[forbid(deprecated_mode)];
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>>};
pub enum SmallIntMap<T:Copy> {
SmallIntMap_(@SmallIntMap_<T>)
}
/// Create a smallintmap
pub 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)]
pub 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
*/
pub 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
*/
pub pure fn get<T: Copy>(self: SmallIntMap<T>, key: uint) -> T {
match find(self, key) {
None => {
error!("smallintmap::get(): key not present");
fail;
}
Some(move v) => return v
}
}
/// Returns true if the map contains a value for the specified key
pub 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(ref 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
pub fn as_map<V: Copy>(s: SmallIntMap<V>) -> map::Map<uint, V> {
s as map::Map::<uint, V>
}
|
