src/lib/vec.rs

   1 // Interior vector utility functions.
   2
   3 import option::{some, none};
   4 import uint::next_power_of_two;
   5 import ptr::addr_of;
   6
   7 native "rust-intrinsic" mod rusti {
   8     fn vec_len<T>(v: [T]) -> uint;
   9 }
  10
  11 native "rust" mod rustrt {
  12     fn vec_reserve_shared<T>(&v: [mutable? T], n: uint);
  13     fn vec_from_buf_shared<T>(ptr: *T, count: uint) -> [T];
  14 }
  15
  16 /// Reserves space for `n` elements in the given vector.
  17 fn reserve<@T>(&v: [mutable? T], n: uint) {
  18     rustrt::vec_reserve_shared(v, n);
  19 }
  20
  21 fn len<T>(v: [mutable? T]) -> uint { ret rusti::vec_len(v); }
  22
  23 type init_op<T> = fn(uint) -> T;
  24
  25 fn init_fn<@T>(op: init_op<T>, n_elts: uint) -> [T] {
  26     let v = [];
  27     reserve(v, n_elts);
  28     let i: uint = 0u;
  29     while i < n_elts { v += [op(i)]; i += 1u; }
  30     ret v;
  31 }
  32
  33 // TODO: Remove me once we have slots.
  34 fn init_fn_mut<@T>(op: init_op<T>, n_elts: uint) -> [mutable T] {
  35     let v = [mutable];
  36     reserve(v, n_elts);
  37     let i: uint = 0u;
  38     while i < n_elts { v += [mutable op(i)]; i += 1u; }
  39     ret v;
  40 }
  41
  42 fn init_elt<@T>(t: T, n_elts: uint) -> [T] {
  43     let v = [];
  44     reserve(v, n_elts);
  45     let i: uint = 0u;
  46     while i < n_elts { v += [t]; i += 1u; }
  47     ret v;
  48 }
  49
  50 // TODO: Remove me once we have slots.
  51 fn init_elt_mut<@T>(t: T, n_elts: uint) -> [mutable T] {
  52     let v = [mutable];
  53     reserve(v, n_elts);
  54     let i: uint = 0u;
  55     while i < n_elts { v += [mutable t]; i += 1u; }
  56     ret v;
  57 }
  58
  59 // FIXME: Possible typestate postcondition:
  60 // len(result) == len(v) (needs issue #586)
  61 fn to_mut<@T>(v: [T]) -> [mutable T] {
  62     let vres = [mutable];
  63     for t: T in v { vres += [mutable t]; }
  64     ret vres;
  65 }
  66
  67 // Same comment as from_mut
  68 fn from_mut<@T>(v: [mutable T]) -> [T] {
  69     let vres = [];
  70     for t: T in v { vres += [t]; }
  71     ret vres;
  72 }
  73
  74 // Predicates
  75 pure fn is_empty<T>(v: [mutable? T]) -> bool {
  76     // FIXME: This would be easier if we could just call len
  77     for t: T in v { ret false; }
  78     ret true;
  79 }
  80
  81 pure fn is_not_empty<T>(v: [mutable? T]) -> bool { ret !is_empty(v); }
  82
  83 // Accessors
  84
  85 /// Returns the first element of a vector
  86 fn head<@T>(v: [mutable? T]) : is_not_empty(v) -> T { ret v[0]; }
  87
  88 /// Returns all but the first element of a vector
  89 fn tail<@T>(v: [mutable? T]) : is_not_empty(v) -> [mutable? T] {
  90     ret slice(v, 1u, len(v));
  91 }
  92
  93 /// Returns the last element of `v`.
  94 fn last<@T>(v: [mutable? T]) -> option::t<T> {
  95     if len(v) == 0u { ret none; }
  96     ret some(v[len(v) - 1u]);
  97 }
  98
  99 /// Returns the last element of a non-empty vector `v`.
 100 fn last_total<@T>(v: [mutable? T]) : is_not_empty(v) -> T {
 101     ret v[len(v) - 1u];
 102 }
 103
 104 /// Returns a copy of the elements from [`start`..`end`) from `v`.
 105 fn slice<@T>(v: [mutable? T], start: uint, end: uint) -> [T] {
 106     assert (start <= end);
 107     assert (end <= len(v));
 108     let result = [];
 109     reserve(result, end - start);
 110     let i = start;
 111     while i < end { result += [v[i]]; i += 1u; }
 112     ret result;
 113 }
 114
 115 // TODO: Remove me once we have slots.
 116 fn slice_mut<@T>(v: [mutable? T], start: uint, end: uint) -> [mutable T] {
 117     assert (start <= end);
 118     assert (end <= len(v));
 119     let result = [mutable];
 120     reserve(result, end - start);
 121     let i = start;
 122     while i < end { result += [mutable v[i]]; i += 1u; }
 123     ret result;
 124 }
 125
 126
 127 // Mutators
 128
 129 fn shift<@T>(&v: [mutable? T]) -> T {
 130     let ln = len::<T>(v);
 131     assert (ln > 0u);
 132     let e = v[0];
 133     v = slice::<T>(v, 1u, ln);
 134     ret e;
 135 }
 136
 137 // TODO: Write this, unsafely, in a way that's not O(n).
 138 fn pop<@T>(&v: [mutable? T]) -> T {
 139     let ln = len(v);
 140     assert (ln > 0u);
 141     ln -= 1u;
 142     let e = v[ln];
 143     v = slice(v, 0u, ln);
 144     ret e;
 145 }
 146
 147 // TODO: More.
 148
 149
 150 // Appending
 151
 152 /// Expands the given vector in-place by appending `n` copies of `initval`.
 153 fn grow<@T>(&v: [T], n: uint, initval: T) {
 154     reserve(v, next_power_of_two(len(v) + n));
 155     let i: uint = 0u;
 156     while i < n { v += [initval]; i += 1u; }
 157 }
 158
 159 // TODO: Remove me once we have slots.
 160 fn grow_mut<@T>(&v: [mutable T], n: uint, initval: T) {
 161     reserve(v, next_power_of_two(len(v) + n));
 162     let i: uint = 0u;
 163     while i < n { v += [mutable initval]; i += 1u; }
 164 }
 165
 166 /// Calls `f` `n` times and appends the results of these calls to the given
 167 /// vector.
 168 fn grow_fn<@T>(&v: [T], n: uint, init_fn: fn(uint) -> T) {
 169     reserve(v, next_power_of_two(len(v) + n));
 170     let i: uint = 0u;
 171     while i < n { v += [init_fn(i)]; i += 1u; }
 172 }
 173
 174 /// Sets the element at position `index` to `val`. If `index` is past the end
 175 /// of the vector, expands the vector by replicating `initval` to fill the
 176 /// intervening space.
 177 fn grow_set<@T>(&v: [mutable T], index: uint, initval: T, val: T) {
 178     if index >= len(v) { grow_mut(v, index - len(v) + 1u, initval); }
 179     v[index] = val;
 180 }
 181
 182
 183 // Functional utilities
 184
 185 fn map<@T, @U>(f: block(T) -> U, v: [mutable? T]) -> [U] {
 186     let result = [];
 187     reserve(result, len(v));
 188     for elem: T in v {
 189         let elem2 = elem; // satisfies alias checker
 190         result += [f(elem2)];
 191     }
 192     ret result;
 193 }
 194
 195 fn map2<@T, @U, @V>(f: block(T, U) -> V, v0: [T], v1: [U]) -> [V] {
 196     let v0_len = len::<T>(v0);
 197     if v0_len != len::<U>(v1) { fail; }
 198     let u: [V] = [];
 199     let i = 0u;
 200     while i < v0_len { u += [f({ v0[i] }, { v1[i] })]; i += 1u; }
 201     ret u;
 202 }
 203
 204 fn filter_map<@T, @U>(f: block(T) -> option::t<U>, v: [mutable? T]) -> [U] {
 205     let result = [];
 206     for elem: T in v {
 207         let elem2 = elem; // satisfies alias checker
 208         alt f(elem2) {
 209           none. {/* no-op */ }
 210           some(result_elem) { result += [result_elem]; }
 211         }
 212     }
 213     ret result;
 214 }
 215
 216 fn filter<@T>(f: block(T) -> bool, v: [mutable? T]) -> [T] {
 217     let result = [];
 218     for elem: T in v {
 219         let elem2 = elem; // satisfies alias checker
 220         if f(elem2) {
 221             result += [elem2];
 222         }
 223     }
 224     ret result;
 225 }
 226
 227 fn foldl<@T, @U>(p: block(U, T) -> U, z: U, v: [mutable? T]) -> U {
 228     let sz = len(v);
 229     if sz == 0u { ret z; }
 230     let first = v[0];
 231     let rest = slice(v, 1u, sz);
 232     ret p(foldl(p, z, rest), first);
 233 }
 234
 235 fn any<T>(f: block(T) -> bool, v: [T]) -> bool {
 236     for elem: T in v { if f(elem) { ret true; } }
 237     ret false;
 238 }
 239
 240 fn all<T>(f: block(T) -> bool, v: [T]) -> bool {
 241     for elem: T in v { if !f(elem) { ret false; } }
 242     ret true;
 243 }
 244
 245 fn member<T>(x: T, v: [T]) -> bool {
 246     for elt: T in v { if x == elt { ret true; } }
 247     ret false;
 248 }
 249
 250 fn count<T>(x: T, v: [mutable? T]) -> uint {
 251     let cnt = 0u;
 252     for elt: T in v { if x == elt { cnt += 1u; } }
 253     ret cnt;
 254 }
 255
 256 fn find<@T>(f: block(T) -> bool, v: [T]) -> option::t<T> {
 257     for elt: T in v { if f(elt) { ret some(elt); } }
 258     ret none;
 259 }
 260
 261 fn position<@T>(x: T, v: [T]) -> option::t<uint> {
 262     let i: uint = 0u;
 263     while i < len(v) { if x == v[i] { ret some::<uint>(i); } i += 1u; }
 264     ret none;
 265 }
 266
 267 fn position_pred<T>(f: fn(T) -> bool, v: [T]) -> option::t<uint> {
 268     let i: uint = 0u;
 269     while i < len(v) { if f(v[i]) { ret some::<uint>(i); } i += 1u; }
 270     ret none;
 271 }
 272
 273 pure fn same_length<T, U>(xs: [T], ys: [U]) -> bool {
 274     let xlen = unchecked{ vec::len(xs) };
 275     let ylen = unchecked{ vec::len(ys) };
 276     xlen == ylen
 277 }
 278
 279 // FIXME: if issue #586 gets implemented, could have a postcondition
 280 // saying the two result lists have the same length -- or, could
 281 // return a nominal record with a constraint saying that, instead of
 282 // returning a tuple (contingent on issue #869)
 283 fn unzip<@T, @U>(v: [(T, U)]) -> ([T], [U]) {
 284     let as = [], bs = [];
 285     for (a, b) in v { as += [a]; bs += [b]; }
 286     ret (as, bs);
 287 }
 288
 289 fn zip<@T, @U>(v: [T], u: [U]) : same_length(v, u) -> [(T, U)] {
 290     let zipped = [];
 291     let sz = len(v), i = 0u;
 292     assert (sz == len(u));
 293     while i < sz { zipped += [(v[i], u[i])]; i += 1u; }
 294     ret zipped;
 295 }
 296
 297 // Swaps two elements in a vector
 298 fn swap<@T>(v: [mutable T], a: uint, b: uint) {
 299     let t: T = v[a];
 300     v[a] = v[b];
 301     v[b] = t;
 302 }
 303
 304 // In place vector reversal
 305 fn reverse<@T>(v: [mutable T]) {
 306     let i: uint = 0u;
 307     let ln = len::<T>(v);
 308     while i < ln / 2u { swap(v, i, ln - i - 1u); i += 1u; }
 309 }
 310
 311
 312 // Functional vector reversal. Returns a reversed copy of v.
 313 fn reversed<@T>(v: [T]) -> [T] {
 314     let rs: [T] = [];
 315     let i = len::<T>(v);
 316     if i == 0u { ret rs; } else { i -= 1u; }
 317     while i != 0u { rs += [v[i]]; i -= 1u; }
 318     rs += [v[0]];
 319     ret rs;
 320 }
 321
 322 // Generating vecs.
 323 fn enum_chars(start: u8, end: u8) : u8::le(start, end) -> [char] {
 324     let i = start;
 325     let r = [];
 326     while i <= end { r += [i as char]; i += 1u as u8; }
 327     ret r;
 328 }
 329
 330 fn enum_uints(start: uint, end: uint) : uint::le(start, end) -> [uint] {
 331     let i = start;
 332     let r = [];
 333     while i <= end { r += [i]; i += 1u; }
 334     ret r;
 335 }
 336
 337 // Iterate over a list with with the indexes
 338 iter iter2<@T>(v: [T]) -> (uint, T) {
 339     let i = 0u;
 340     for x in v { put (i, x); i += 1u; }
 341 }
 342
 343 mod unsafe {
 344     type vec_repr = {mutable fill: uint, mutable alloc: uint, data: u8};
 345
 346     fn from_buf<T>(ptr: *T, elts: uint) -> [T] {
 347         ret rustrt::vec_from_buf_shared(ptr, elts);
 348     }
 349
 350     fn set_len<T>(&v: [T], new_len: uint) {
 351         let repr: **vec_repr = ::unsafe::reinterpret_cast(addr_of(v));
 352         (**repr).fill = new_len * sys::size_of::<T>();
 353     }
 354
 355     fn to_ptr<T>(v: [T]) -> *T {
 356         let repr: **vec_repr = ::unsafe::reinterpret_cast(addr_of(v));
 357         ret ::unsafe::reinterpret_cast(addr_of((**repr).data));
 358     }
 359 }
 360
 361 fn to_ptr<T>(v: [T]) -> *T { ret unsafe::to_ptr(v); }
 362
 363 // Local Variables:
 364 // mode: rust;
 365 // fill-column: 78;
 366 // indent-tabs-mode: nil
 367 // c-basic-offset: 4
 368 // buffer-file-coding-system: utf-8-unix
 369 // compile-command: "make -k -C $RBUILD 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
 370 // End: