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
|
/*
Module: deque
A deque. Untested as of yet. Likely buggy.
*/
/*
Object: t
*/
type t<T> = obj {
// 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
*/
fn create<copy T>() -> 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<copy T>(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 option::none]; }
i += 1u;
}
ret rv;
}
fn get<T>(elts: [mutable cell<T>], i: uint) -> T {
ret alt elts[i] { option::some(t) { t } _ { fail } };
}
obj deque<copy T>(mutable nelts: uint,
mutable lo: uint,
mutable hi: uint,
mutable elts: [mutable cell<T>]) {
fn size() -> uint { ret nelts; }
fn add_front(t: T) {
let oldlo: uint = lo;
if lo == 0u {
lo = vec::len::<cell<T>>(elts) - 1u;
} else { lo -= 1u; }
if lo == hi {
elts = grow::<T>(nelts, oldlo, elts);
lo = vec::len::<cell<T>>(elts) - 1u;
hi = nelts;
}
elts[lo] = option::some::<T>(t);
nelts += 1u;
}
fn add_back(t: T) {
if lo == hi && nelts != 0u {
elts = grow::<T>(nelts, lo, elts);
lo = 0u;
hi = nelts;
}
elts[hi] = option::some::<T>(t);
hi = (hi + 1u) % vec::len::<cell<T>>(elts);
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::<T>(elts, lo);
elts[lo] = option::none::<T>;
lo = (lo + 1u) % vec::len::<cell<T>>(elts);
nelts -= 1u;
ret t;
}
fn pop_back() -> T {
if hi == 0u {
hi = vec::len::<cell<T>>(elts) - 1u;
} else { hi -= 1u; }
let t: T = get::<T>(elts, hi);
elts[hi] = option::none::<T>;
nelts -= 1u;
ret t;
}
fn peek_front() -> T { ret get::<T>(elts, lo); }
fn peek_back() -> T { ret get::<T>(elts, hi - 1u); }
fn get(i: int) -> T {
let idx: uint = (lo + (i as uint)) % vec::len::<cell<T>>(elts);
ret get::<T>(elts, idx);
}
}
let v: [mutable cell<T>] =
vec::init_elt_mut(option::none, initial_capacity);
ret deque::<T>(0u, 0u, 0u, v);
}
// Local Variables:
// mode: rust;
// fill-column: 78;
// indent-tabs-mode: nil
// c-basic-offset: 4
// buffer-file-coding-system: utf-8-unix
// End:
|
