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

   1 // xfail-test
   2
   3 extern mod extra;
   4
   5 use std::cast::transmute;
   6 use std::i32::range;
   7 use std::libc::{STDIN_FILENO, c_int, fdopen, fgets, fileno, fopen, fstat};
   8 use std::libc::{stat, strlen};
   9 use std::ptr::null;
  10 use std::unstable::intrinsics::init;
  11 use std::vec::{reverse};
  12 use extra::sort::quick_sort3;
  13
  14 static LINE_LEN: uint = 80;
  15 static TABLE: [u8, ..4] = [ 'A' as u8, 'C' as u8, 'G' as u8, 'T' as u8 ];
  16 static TABLE_SIZE: uint = 2 << 16;
  17
  18 static OCCURRENCES: [&'static str, ..5] = [
  19     "GGT",
  20     "GGTA",
  21     "GGTATT",
  22     "GGTATTTTAATT",
  23     "GGTATTTTAATTTATAGT",
  24 ];
  25
  26 // Code implementation
  27
  28 #[deriving(Eq, Ord)]
  29 struct Code(u64);
  30
  31 impl Code {
  32     fn hash(&self) -> u64 {
  33         **self
  34     }
  35
  36     #[inline(always)]
  37     fn push_char(&self, c: u8) -> Code {
  38         Code((**self << 2) + (pack_symbol(c) as u64))
  39     }
  40
  41     fn rotate(&self, c: u8, frame: i32) -> Code {
  42         Code(*self.push_char(c) & ((1u64 << (2 * (frame as u64))) - 1))
  43     }
  44
  45     fn pack(string: &str) -> Code {
  46         let mut code = Code(0u64);
  47         for i in range(0u, string.len()) {
  48             code = code.push_char(string[i]);
  49         }
  50         code
  51     }
  52
  53     // XXX: Inefficient.
  54     fn unpack(&self, frame: i32) -> ~str {
  55         let mut key = **self;
  56         let mut result = ~[];
  57         do (frame as uint).times {
  58             result.push(unpack_symbol((key as u8) & 3));
  59             key >>= 2;
  60         }
  61
  62         reverse(result);
  63         str::from_bytes(result)
  64     }
  65 }
  66
  67 // Hash table implementation
  68
  69 trait TableCallback {
  70     fn f(&self, entry: &mut Entry);
  71 }
  72
  73 struct BumpCallback;
  74
  75 impl TableCallback for BumpCallback {
  76     fn f(&self, entry: &mut Entry) {
  77         entry.count += 1;
  78     }
  79 }
  80
  81 struct PrintCallback(&'static str);
  82
  83 impl TableCallback for PrintCallback {
  84     fn f(&self, entry: &mut Entry) {
  85         printfln!("%d\t%s", entry.count as int, **self);
  86     }
  87 }
  88
  89 struct Entry {
  90     code: Code,
  91     count: i32,
  92     next: Option<~Entry>,
  93 }
  94
  95 struct Table {
  96     count: i32,
  97     items: [Option<~Entry>, ..TABLE_SIZE]
  98 }
  99
 100 impl Table {
 101     fn new() -> Table {
 102         Table {
 103             count: 0,
 104             items: [ None, ..TABLE_SIZE ],
 105         }
 106     }
 107
 108     fn search_remainder<C:TableCallback>(item: &mut Entry, key: Code, c: C) {
 109         match item.next {
 110             None => {
 111                 let mut entry = ~Entry {
 112                     code: key,
 113                     count: 0,
 114                     next: None,
 115                 };
 116                 c.f(entry);
 117                 item.next = Some(entry);
 118             }
 119             Some(ref mut entry) => {
 120                 if entry.code == key {
 121                     c.f(*entry);
 122                     return;
 123                 }
 124
 125                 Table::search_remainder(*entry, key, c)
 126             }
 127         }
 128     }
 129
 130     fn lookup<C:TableCallback>(&mut self, key: Code, c: C) {
 131         let index = *key % (TABLE_SIZE as u64);
 132
 133         {
 134             if self.items[index].is_none() {
 135                 let mut entry = ~Entry {
 136                     code: key,
 137                     count: 0,
 138                     next: None,
 139                 };
 140                 c.f(entry);
 141                 self.items[index] = Some(entry);
 142                 return;
 143             }
 144         }
 145
 146         {
 147             let mut entry = &mut *self.items[index].get_mut_ref();
 148             if entry.code == key {
 149                 c.f(*entry);
 150                 return;
 151             }
 152
 153             Table::search_remainder(*entry, key, c)
 154         }
 155     }
 156
 157     fn each(&self, f: &fn(entry: &Entry) -> bool) {
 158         for self.items.each |item| {
 159             match *item {
 160                 None => {}
 161                 Some(ref item) => {
 162                     let mut item: &Entry = *item;
 163                     loop {
 164                         if !f(item) {
 165                             return;
 166                         }
 167
 168                         match item.next {
 169                             None => break,
 170                             Some(ref next_item) => item = &**next_item,
 171                         }
 172                     }
 173                 }
 174             };
 175         }
 176     }
 177 }
 178
 179 // Main program
 180
 181 fn pack_symbol(c: u8) -> u8 {
 182     match c {
 183         'a' as u8 | 'A' as u8 => 0,
 184         'c' as u8 | 'C' as u8 => 1,
 185         'g' as u8 | 'G' as u8 => 2,
 186         't' as u8 | 'T' as u8 => 3,
 187         _ => fail!(c.to_str())
 188     }
 189 }
 190
 191 fn unpack_symbol(c: u8) -> u8 {
 192     TABLE[c]
 193 }
 194
 195 fn next_char<'a>(mut buf: &'a [u8]) -> &'a [u8] {
 196     loop {
 197         buf = buf.slice(1, buf.len());
 198         if buf.len() == 0 {
 199             break;
 200         }
 201         if buf[0] != (' ' as u8) && buf[0] != ('\t' as u8) &&
 202                 buf[0] != ('\n' as u8) && buf[0] != 0 {
 203             break;
 204         }
 205     }
 206     buf
 207 }
 208
 209 #[inline(never)]
 210 fn read_stdin() -> ~[u8] {
 211     unsafe {
 212         let mode = "r";
 213         //let stdin = fdopen(STDIN_FILENO as c_int, transmute(&mode[0]));
 214         let path = "knucleotide-input.txt";
 215         let stdin = fopen(transmute(&path[0]), transmute(&mode[0]));
 216
 217         let mut st: stat = init();
 218         fstat(fileno(stdin), &mut st);
 219         let mut buf = vec::from_elem(st.st_size as uint, 0);
 220
 221         let header = ">THREE".as_bytes();
 222
 223         {
 224             let mut window: &mut [u8] = buf;
 225             loop {
 226                 fgets(transmute(&mut window[0]), LINE_LEN as c_int, stdin);
 227
 228                 {
 229                     if window.slice(0, 6) == header {
 230                         break;
 231                     }
 232                 }
 233             }
 234
 235             while fgets(transmute(&mut window[0]),
 236                         LINE_LEN as c_int,
 237                         stdin) != null() {
 238                 window = window.mut_slice(strlen(transmute(&window[0])) as uint, window.len());
 239             }
 240         }
 241
 242         buf
 243     }
 244 }
 245
 246 #[inline(never)]
 247 #[fixed_stack_segment]
 248 fn generate_frequencies(frequencies: &mut Table,
 249                         mut input: &[u8],
 250                         frame: i32) {
 251     let mut code = Code(0);
 252
 253     // Pull first frame.
 254     do (frame as uint).times {
 255         code = code.push_char(input[0]);
 256         input = next_char(input);
 257     }
 258     frequencies.lookup(code, BumpCallback);
 259
 260     while input.len() != 0 && input[0] != ('>' as u8) {
 261         code = code.rotate(input[0], frame);
 262         frequencies.lookup(code, BumpCallback);
 263         input = next_char(input);
 264     }
 265 }
 266
 267 #[inline(never)]
 268 #[fixed_stack_segment]
 269 fn print_frequencies(frequencies: &Table, frame: i32) {
 270     let mut vector = ~[];
 271     for frequencies.each |entry| {
 272         vector.push((entry.code, entry.count));
 273     }
 274     quick_sort3(vector);
 275
 276     let mut total_count = 0;
 277     for vector.each |&(_, count)| {
 278         total_count += count;
 279     }
 280
 281     for vector.each |&(key, count)| {
 282         printfln!("%s %.3f",
 283                   key.unpack(frame),
 284                   (count as float * 100.0) / (total_count as float));
 285     }
 286 }
 287
 288 fn print_occurrences(frequencies: &mut Table, occurrence: &'static str) {
 289     frequencies.lookup(Code::pack(occurrence), PrintCallback(occurrence))
 290 }
 291
 292 #[fixed_stack_segment]
 293 fn main() {
 294     let input = read_stdin();
 295
 296     let mut frequencies = ~Table::new();
 297     generate_frequencies(frequencies, input, 1);
 298     print_frequencies(frequencies, 1);
 299
 300     *frequencies = Table::new();
 301     generate_frequencies(frequencies, input, 2);
 302     print_frequencies(frequencies, 2);
 303
 304     for range(0, 5) |i| {
 305         let occurrence = OCCURRENCES[i];
 306         *frequencies = Table::new();
 307         generate_frequencies(frequencies,
 308                              input,
 309                              occurrence.len() as i32);
 310         print_occurrences(frequencies, occurrence);
 311     }
 312 }