src/test/bench/shootout-k-nucleotide-pipes.rs

   1 // Copyright 2012-2014 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 // ignore-android: FIXME(#10393)
  12 // ignore-pretty very bad with line comments
  13
  14 // multi tasking k-nucleotide
  15
  16 #![feature(slicing_syntax)]
  17
  18 extern crate collections;
  19
  20 use std::ascii::{AsciiExt, OwnedAsciiExt};
  21 use std::cmp::Ordering::{mod, Less, Greater, Equal};
  22 use std::collections::HashMap;
  23 use std::sync::mpsc::{channel, Sender, Receiver};
  24 use std::mem::replace;
  25 use std::num::Float;
  26 use std::option;
  27 use std::os;
  28 use std::string::IntoString;
  29 use std::thread::Thread;
  30
  31 fn f64_cmp(x: f64, y: f64) -> Ordering {
  32     // arbitrarily decide that NaNs are larger than everything.
  33     if y.is_nan() {
  34         Less
  35     } else if x.is_nan() {
  36         Greater
  37     } else if x < y {
  38         Less
  39     } else if x == y {
  40         Equal
  41     } else {
  42         Greater
  43     }
  44 }
  45
  46 // given a map, print a sorted version of it
  47 fn sort_and_fmt(mm: &HashMap<Vec<u8> , uint>, total: uint) -> String {
  48    fn pct(xx: uint, yy: uint) -> f64 {
  49       return (xx as f64) * 100.0 / (yy as f64);
  50    }
  51
  52    // sort by key, then by value
  53    fn sortKV(mut orig: Vec<(Vec<u8> ,f64)> ) -> Vec<(Vec<u8> ,f64)> {
  54         orig.sort_by(|&(ref a, _), &(ref b, _)| a.cmp(b));
  55         orig.sort_by(|&(_, a), &(_, b)| f64_cmp(b, a));
  56         orig
  57    }
  58
  59    let mut pairs = Vec::new();
  60
  61    // map -> [(k,%)]
  62    for (key, &val) in mm.iter() {
  63       pairs.push(((*key).clone(), pct(val, total)));
  64    }
  65
  66    let pairs_sorted = sortKV(pairs);
  67
  68    let mut buffer = String::new();
  69    for &(ref k, v) in pairs_sorted.iter() {
  70        buffer.push_str(format!("{} {:0.3}\n",
  71                                k.to_ascii_uppercase(),
  72                                v).as_slice());
  73    }
  74
  75    return buffer
  76 }
  77
  78 // given a map, search for the frequency of a pattern
  79 fn find(mm: &HashMap<Vec<u8> , uint>, key: String) -> uint {
  80    let key = key.into_ascii_lowercase();
  81    match mm.get(key.as_bytes()) {
  82       option::Option::None      => { return 0u; }
  83       option::Option::Some(&num) => { return num; }
  84    }
  85 }
  86
  87 // given a map, increment the counter for a key
  88 fn update_freq(mm: &mut HashMap<Vec<u8> , uint>, key: &[u8]) {
  89     let key = key.to_vec();
  90     let newval = match mm.pop(&key) {
  91         Some(v) => v + 1,
  92         None => 1
  93     };
  94     mm.insert(key, newval);
  95 }
  96
  97 // given a Vec<u8>, for each window call a function
  98 // i.e., for "hello" and windows of size four,
  99 // run it("hell") and it("ello"), then return "llo"
 100 fn windows_with_carry(bb: &[u8], nn: uint, it: |window: &[u8]|) -> Vec<u8> {
 101    let mut ii = 0u;
 102
 103    let len = bb.len();
 104    while ii < len - (nn - 1u) {
 105       it(bb[ii..ii+nn]);
 106       ii += 1u;
 107    }
 108
 109    return bb[len - (nn - 1u)..len].to_vec();
 110 }
 111
 112 fn make_sequence_processor(sz: uint,
 113                            from_parent: &Receiver<Vec<u8>>,
 114                            to_parent: &Sender<String>) {
 115    let mut freqs: HashMap<Vec<u8>, uint> = HashMap::new();
 116    let mut carry = Vec::new();
 117    let mut total: uint = 0u;
 118
 119    let mut line: Vec<u8>;
 120
 121    loop {
 122
 123        line = from_parent.recv().unwrap();
 124        if line == Vec::new() { break; }
 125
 126        carry.push_all(line.as_slice());
 127        carry = windows_with_carry(carry.as_slice(), sz, |window| {
 128            update_freq(&mut freqs, window);
 129            total += 1u;
 130        });
 131    }
 132
 133    let buffer = match sz {
 134        1u => { sort_and_fmt(&freqs, total) }
 135        2u => { sort_and_fmt(&freqs, total) }
 136        3u => { format!("{}\t{}", find(&freqs, "GGT".to_string()), "GGT") }
 137        4u => { format!("{}\t{}", find(&freqs, "GGTA".to_string()), "GGTA") }
 138        6u => { format!("{}\t{}", find(&freqs, "GGTATT".to_string()), "GGTATT") }
 139       12u => { format!("{}\t{}", find(&freqs, "GGTATTTTAATT".to_string()), "GGTATTTTAATT") }
 140       18u => { format!("{}\t{}", find(&freqs, "GGTATTTTAATTTATAGT".to_string()),
 141                        "GGTATTTTAATTTATAGT") }
 142         _ => { "".to_string() }
 143    };
 144
 145     to_parent.send(buffer);
 146 }
 147
 148 // given a FASTA file on stdin, process sequence THREE
 149 fn main() {
 150     use std::io::{stdio, MemReader, BufferedReader};
 151
 152     let rdr = if os::getenv("RUST_BENCH").is_some() {
 153         let foo = include_bytes!("shootout-k-nucleotide.data");
 154         box MemReader::new(foo.to_vec()) as Box<Reader>
 155     } else {
 156         box stdio::stdin() as Box<Reader>
 157     };
 158     let mut rdr = BufferedReader::new(rdr);
 159
 160     // initialize each sequence sorter
 161     let sizes = vec!(1u,2,3,4,6,12,18);
 162     let mut streams = Vec::from_fn(sizes.len(), |_| Some(channel::<String>()));
 163     let mut from_child = Vec::new();
 164     let to_child  = sizes.iter().zip(streams.iter_mut()).map(|(sz, stream_ref)| {
 165         let sz = *sz;
 166         let stream = replace(stream_ref, None);
 167         let (to_parent_, from_child_) = stream.unwrap();
 168
 169         from_child.push(from_child_);
 170
 171         let (to_child, from_parent) = channel();
 172
 173         Thread::spawn(move|| {
 174             make_sequence_processor(sz, &from_parent, &to_parent_);
 175         }).detach();
 176
 177         to_child
 178     }).collect::<Vec<Sender<Vec<u8> >> >();
 179
 180
 181    // latch stores true after we've started
 182    // reading the sequence of interest
 183    let mut proc_mode = false;
 184
 185    for line in rdr.lines() {
 186        let line = line.unwrap().as_slice().trim().to_string();
 187
 188        if line.len() == 0u { continue; }
 189
 190        match (line.as_bytes()[0] as char, proc_mode) {
 191
 192            // start processing if this is the one
 193            ('>', false) => {
 194                match line.as_slice().slice_from(1).find_str("THREE") {
 195                    option::Option::Some(_) => { proc_mode = true; }
 196                    option::Option::None    => { }
 197                }
 198            }
 199
 200            // break our processing
 201            ('>', true) => { break; }
 202
 203            // process the sequence for k-mers
 204            (_, true) => {
 205                let line_bytes = line.as_bytes();
 206
 207                for (ii, _sz) in sizes.iter().enumerate() {
 208                    let lb = line_bytes.to_vec();
 209                    to_child[ii].send(lb);
 210                }
 211            }
 212
 213            // whatever
 214            _ => { }
 215        }
 216    }
 217
 218    // finish...
 219    for (ii, _sz) in sizes.iter().enumerate() {
 220        to_child[ii].send(Vec::new());
 221    }
 222
 223    // now fetch and print result messages
 224    for (ii, _sz) in sizes.iter().enumerate() {
 225        println!("{}", from_child[ii].recv().unwrap());
 226    }
 227 }