chiark - git - mdw - wordchain/blob - chain.rs

   1 use std::cell::Cell;
   2 use std::io::{self, BufRead, Write};
   3
   4 use typed_arena;
   5
   6 #[cfg(feature = "btree")]
   7 use std::collections::{btree_map::Entry as MapEntry, BTreeMap as Map};
   8
   9 #[cfg(feature = "hash")]
  10 use std::collections::{hash_map::Entry as MapEntry, HashMap as Map};
  11
  12 #[derive(Debug, Default)]
  13 struct Node<'a> {
  14   word: &'a [u8],
  15   len: Cell<u32>,
  16   down: Cell<Option<&'a Node<'a>>>,
  17   right: Cell<Option<&'a Node<'a>>>,
  18   up: Cell<Option<&'a Node<'a>>>
  19 }
  20
  21 fn print_chain<W: io::Write>(node: &Node, out: &mut W) -> io::Result<()> {
  22   match node.right.get() {
  23     None => {
  24       out.write_all(node.word)?;
  25       if let Some(down) = node.down.get()
  26         { out.write_all(b" ")?; print_chain(down, out)?; }
  27     }
  28     Some(_) => {
  29       out.write_all(b"{ ")?;
  30       let mut node = node;
  31       loop {
  32         out.write_all(node.word)?;
  33         if let Some(down) = node.down.get()
  34           { out.write_all(b" ")?; print_chain(down, out)?; }
  35         if let Some(right) = node.right.get()
  36           { node = right; out.write_all(b" | ")?; }
  37         else
  38           { break; }
  39       }
  40       out.write_all(b" }")?;
  41     }
  42   }
  43   Ok(())
  44 }
  45
  46 fn main() -> io::Result<()> {
  47   let byte_arena = typed_arena::Arena::new();
  48   let node_arena = typed_arena::Arena::new();
  49   let mut buf: Vec<u8> = Vec::with_capacity(64);
  50   let global_stdin  = io::stdin();  let mut stdin  = global_stdin.lock();
  51   let global_stdout = io::stdout(); let mut stdout = global_stdout.lock();
  52   let global_stderr = io::stderr(); let mut stderr = global_stderr.lock();
  53   let mut map = Map::new();
  54
  55   loop {
  56     buf.clear();
  57     let n = stdin.read_until(b'\n', &mut buf)?;
  58     let mut line = &buf[0 .. n];
  59     let n = line.len();
  60     if n == 0 { break; }
  61     if line[n - 1] == b'\n' { line = &line[0 .. n - 1]; }
  62     //stdout.write_all(b";; read `")?;
  63     //stdout.write_all(line)?;
  64     //stdout.write_all(b"'\n")?;
  65     let word: &[u8] = byte_arena.alloc_extend(line.iter().map(|p| *p));
  66     if let MapEntry::Vacant(e) = map.entry(word) {
  67       e.insert(node_arena.alloc(Node { word: word, .. Node::default() }));
  68     } else {
  69       stderr.write_all(b";; duplicate `")?;
  70       stderr.write_all(word)?;
  71       stderr.write_all(b"'\n")?;
  72     }
  73   }
  74
  75   let mut max = 0; let mut winners = Vec::with_capacity(8);
  76   for node in map.values() {
  77     //stdout.write_all(b";; ponder `")?;
  78     //stdout.write_all(node.word)?;
  79     //stdout.write_all(b"'\n")?;
  80     let mut node: &Node = node;
  81     let mut parent;
  82     let n = node.word.len();
  83     if n <= 1 { continue; }
  84     parent = map.get(&node.word[0 .. n - 1]).map(|n| &**n);
  85     if let None = parent { continue; }
  86     node.up.set(parent);
  87     let mut nlen = node.len.get();
  88     loop {
  89       match parent {
  90         None => {
  91           if nlen >= max {
  92             if nlen > max {
  93               max = nlen;
  94               winners.clear();
  95             }
  96             winners.push(node);
  97           }
  98           break;
  99         }
 100         Some(parent_node) => {
 101           let plen = parent_node.len.get(); nlen += 1;
 102           if plen > nlen
 103             { break; }
 104           else if plen == nlen {
 105             node.right.set(parent_node.down.get());
 106             parent_node.down.set(Some(node));
 107             break;
 108           } else {
 109             parent_node.down.set(Some(node));
 110             node.right.set(None);
 111             parent_node.len.set(nlen);
 112             node = parent_node; parent = node.up.get();
 113           }
 114         }
 115       }
 116     }
 117   }
 118
 119   for node in winners
 120     { print_chain(node, &mut stdout)?; stdout.write(b"\n")?; }
 121
 122   Ok(())
 123 }