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

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