src/libstd/list.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A standard linked list
  12
  13 #[deriving(Eq)]
  14 pub enum List<T> {
  15     Cons(T, @List<T>),
  16     Nil,
  17 }
  18
  19 #[deriving(Eq)]
  20 pub enum MutList<T> {
  21     MutCons(T, @mut MutList<T>),
  22     MutNil,
  23 }
  24
  25 /// Create a list from a vector
  26 pub fn from_vec<T:Copy>(v: &[T]) -> @List<T> {
  27     vec::foldr(v, @Nil::<T>, |h, t| @Cons(*h, t))
  28 }
  29
  30 /**
  31  * Left fold
  32  *
  33  * Applies `f` to `u` and the first element in the list, then applies `f` to
  34  * the result of the previous call and the second element, and so on,
  35  * returning the accumulated result.
  36  *
  37  * # Arguments
  38  *
  39  * * ls - The list to fold
  40  * * z - The initial value
  41  * * f - The function to apply
  42  */
  43 pub fn foldl<T:Copy,U>(z: T, ls: @List<U>, f: &fn(&T, &U) -> T) -> T {
  44     let mut accum: T = z;
  45     do iter(ls) |elt| { accum = f(&accum, elt);}
  46     accum
  47 }
  48
  49 /**
  50  * Search for an element that matches a given predicate
  51  *
  52  * Apply function `f` to each element of `v`, starting from the first.
  53  * When function `f` returns true then an option containing the element
  54  * is returned. If `f` matches no elements then none is returned.
  55  */
  56 pub fn find<T:Copy>(ls: @List<T>, f: &fn(&T) -> bool) -> Option<T> {
  57     let mut ls = ls;
  58     loop {
  59         ls = match *ls {
  60           Cons(ref hd, tl) => {
  61             if f(hd) { return Some(*hd); }
  62             tl
  63           }
  64           Nil => return None
  65         }
  66     };
  67 }
  68
  69 /// Returns true if a list contains an element with the given value
  70 pub fn has<T:Copy + Eq>(ls: @List<T>, elt: T) -> bool {
  71     for each(ls) |e| {
  72         if *e == elt { return true; }
  73     }
  74     return false;
  75 }
  76
  77 /// Returns true if the list is empty
  78 pub fn is_empty<T:Copy>(ls: @List<T>) -> bool {
  79     match *ls {
  80         Nil => true,
  81         _ => false
  82     }
  83 }
  84
  85 /// Returns the length of a list
  86 pub fn len<T>(ls: @List<T>) -> uint {
  87     let mut count = 0u;
  88     iter(ls, |_e| count += 1u);
  89     count
  90 }
  91
  92 /// Returns all but the first element of a list
  93 pub fn tail<T:Copy>(ls: @List<T>) -> @List<T> {
  94     match *ls {
  95         Cons(_, tl) => return tl,
  96         Nil => fail!(~"list empty")
  97     }
  98 }
  99
 100 /// Returns the first element of a list
 101 pub fn head<T:Copy>(ls: @List<T>) -> T {
 102     match *ls {
 103       Cons(copy hd, _) => hd,
 104       // makes me sad
 105       _ => fail!(~"head invoked on empty list")
 106     }
 107 }
 108
 109 /// Appends one list to another
 110 pub fn append<T:Copy>(l: @List<T>, m: @List<T>) -> @List<T> {
 111     match *l {
 112       Nil => return m,
 113       Cons(copy x, xs) => {
 114         let rest = append(xs, m);
 115         return @Cons(x, rest);
 116       }
 117     }
 118 }
 119
 120 /*
 121 /// Push one element into the front of a list, returning a new list
 122 /// THIS VERSION DOESN'T ACTUALLY WORK
 123 fn push<T:Copy>(ll: &mut @list<T>, vv: T) {
 124     ll = &mut @cons(vv, *ll)
 125 }
 126 */
 127
 128 /// Iterate over a list
 129 pub fn iter<T>(l: @List<T>, f: &fn(&T)) {
 130     let mut cur = l;
 131     loop {
 132         cur = match *cur {
 133           Cons(ref hd, tl) => {
 134             f(hd);
 135             tl
 136           }
 137           Nil => break
 138         }
 139     }
 140 }
 141
 142 /// Iterate over a list
 143 pub fn each<T>(l: @List<T>, f: &fn(&T) -> bool) {
 144     let mut cur = l;
 145     loop {
 146         cur = match *cur {
 147           Cons(ref hd, tl) => {
 148             if !f(hd) { return; }
 149             tl
 150           }
 151           Nil => break
 152         }
 153     }
 154 }
 155
 156 impl<T> MutList<T> {
 157     /// Iterate over a mutable list
 158     pub fn each(@mut self, f: &fn(&mut T) -> bool) {
 159         let mut cur = self;
 160         loop {
 161             let borrowed = &mut *cur;
 162             cur = match *borrowed {
 163                 MutCons(ref mut hd, tl) => {
 164                     if !f(hd) {
 165                         return;
 166                     }
 167                     tl
 168                 }
 169                 MutNil => break
 170             }
 171         }
 172     }
 173 }
 174
 175 #[cfg(test)]
 176 mod tests {
 177     use list::*;
 178     use list;
 179
 180     use core::option;
 181
 182     #[test]
 183     fn test_is_empty() {
 184         let empty : @list::List<int> = from_vec(~[]);
 185         let full1 = from_vec(~[1]);
 186         let full2 = from_vec(~['r', 'u']);
 187
 188         assert!(is_empty(empty));
 189         assert!(!is_empty(full1));
 190         assert!(!is_empty(full2));
 191     }
 192
 193     #[test]
 194     fn test_from_vec() {
 195         let l = from_vec(~[0, 1, 2]);
 196
 197         assert!((head(l) == 0));
 198
 199         let tail_l = tail(l);
 200         assert!((head(tail_l) == 1));
 201
 202         let tail_tail_l = tail(tail_l);
 203         assert!((head(tail_tail_l) == 2));
 204     }
 205
 206     #[test]
 207     fn test_from_vec_empty() {
 208         let empty : @list::List<int> = from_vec(~[]);
 209         assert!((empty == @list::Nil::<int>));
 210     }
 211
 212     #[test]
 213     fn test_foldl() {
 214         fn add(a: &uint, b: &int) -> uint { return *a + (*b as uint); }
 215         let l = from_vec(~[0, 1, 2, 3, 4]);
 216         let empty = @list::Nil::<int>;
 217         assert!((list::foldl(0u, l, add) == 10u));
 218         assert!((list::foldl(0u, empty, add) == 0u));
 219     }
 220
 221     #[test]
 222     fn test_foldl2() {
 223         fn sub(a: &int, b: &int) -> int {
 224             *a - *b
 225         }
 226         let l = from_vec(~[1, 2, 3, 4]);
 227         assert!((list::foldl(0, l, sub) == -10));
 228     }
 229
 230     #[test]
 231     fn test_find_success() {
 232         fn match_(i: &int) -> bool { return *i == 2; }
 233         let l = from_vec(~[0, 1, 2]);
 234         assert!((list::find(l, match_) == option::Some(2)));
 235     }
 236
 237     #[test]
 238     fn test_find_fail() {
 239         fn match_(_i: &int) -> bool { return false; }
 240         let l = from_vec(~[0, 1, 2]);
 241         let empty = @list::Nil::<int>;
 242         assert!((list::find(l, match_) == option::None::<int>));
 243         assert!((list::find(empty, match_) == option::None::<int>));
 244     }
 245
 246     #[test]
 247     fn test_has() {
 248         let l = from_vec(~[5, 8, 6]);
 249         let empty = @list::Nil::<int>;
 250         assert!((list::has(l, 5)));
 251         assert!((!list::has(l, 7)));
 252         assert!((list::has(l, 8)));
 253         assert!((!list::has(empty, 5)));
 254     }
 255
 256     #[test]
 257     fn test_len() {
 258         let l = from_vec(~[0, 1, 2]);
 259         let empty = @list::Nil::<int>;
 260         assert!((list::len(l) == 3u));
 261         assert!((list::len(empty) == 0u));
 262     }
 263
 264     #[test]
 265     fn test_append() {
 266         assert!(from_vec(~[1,2,3,4])
 267             == list::append(list::from_vec(~[1,2]), list::from_vec(~[3,4])));
 268     }
 269 }