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
|
import option::{some, none};
/*
Module: deque
A deque. Untested as of yet. Likely buggy.
*/
/*
Iface: t
*/
iface t<T> {
// Method: size
fn size() -> uint;
// Method: add_front
fn add_front(T);
// Method: add_back
fn add_back(T);
// Method: pop_front
fn pop_front() -> T;
// Method: pop_back
fn pop_back() -> T;
// Method: peek_front
fn peek_front() -> T;
// Method: peek_back
fn peek_back() -> T;
// Method: get
fn get(int) -> T;
}
/*
Section: Functions
*/
/*
Function: create
*/
// FIXME eventually, a proper datatype plus an exported impl would be
// preferrable
fn create<T: copy>() -> t<T> {
type cell<T> = option::t<T>;
let initial_capacity: uint = 32u; // 2^5
/**
* Grow is only called on full elts, so nelts is also len(elts), unlike
* elsewhere.
*/
fn grow<T: copy>(nelts: uint, lo: uint, elts: [mutable cell<T>]) ->
[mutable cell<T>] {
assert (nelts == vec::len(elts));
let rv = [mutable];
let i = 0u;
let nalloc = uint::next_power_of_two(nelts + 1u);
while i < nalloc {
if i < nelts {
rv += [mutable elts[(lo + i) % nelts]];
} else { rv += [mutable none]; }
i += 1u;
}
ret rv;
}
fn get<T: copy>(elts: [mutable cell<T>], i: uint) -> T {
ret alt elts[i] { some(t) { t } _ { fail } };
}
type repr<T> = {mutable nelts: uint,
mutable lo: uint,
mutable hi: uint,
mutable elts: [mutable cell<T>]};
impl <T: copy> of t<T> for repr<T> {
fn size() -> uint { ret self.nelts; }
fn add_front(t: T) {
let oldlo: uint = self.lo;
if self.lo == 0u {
self.lo = vec::len(self.elts) - 1u;
} else { self.lo -= 1u; }
if self.lo == self.hi {
self.elts = grow(self.nelts, oldlo, self.elts);
self.lo = vec::len(self.elts) - 1u;
self.hi = self.nelts;
}
self.elts[self.lo] = some(t);
self.nelts += 1u;
}
fn add_back(t: T) {
if self.lo == self.hi && self.nelts != 0u {
self.elts = grow(self.nelts, self.lo, self.elts);
self.lo = 0u;
self.hi = self.nelts;
}
self.elts[self.hi] = some(t);
self.hi = (self.hi + 1u) % vec::len(self.elts);
self.nelts += 1u;
}
/**
* We actually release (turn to none()) the T we're popping so
* that we don't keep anyone's refcount up unexpectedly.
*/
fn pop_front() -> T {
let t: T = get(self.elts, self.lo);
self.elts[self.lo] = none;
self.lo = (self.lo + 1u) % vec::len(self.elts);
self.nelts -= 1u;
ret t;
}
fn pop_back() -> T {
if self.hi == 0u {
self.hi = vec::len(self.elts) - 1u;
} else { self.hi -= 1u; }
let t: T = get(self.elts, self.hi);
self.elts[self.hi] = none;
self.nelts -= 1u;
ret t;
}
fn peek_front() -> T { ret get(self.elts, self.lo); }
fn peek_back() -> T { ret get(self.elts, self.hi - 1u); }
fn get(i: int) -> T {
let idx = (self.lo + (i as uint)) % vec::len(self.elts);
ret get(self.elts, idx);
}
}
let repr: repr<T> = {
mutable nelts: 0u,
mutable lo: 0u,
mutable hi: 0u,
mutable elts: vec::init_elt_mut(none, initial_capacity)
};
repr as t::<T>
}
|
