use std::fmt::{Display, Formatter};
use std::fs::File;
use std::io::{ErrorKind, Read, Write};
use std::path::Path;
use std::rc::Rc;

// Set to a small value to help identify bugs in the implementation.
const MAX_NODE_SIZE: usize = 4;

struct Branch {
    left: Rc<Node>,
    right: Rc<Node>,
    // Number of newline characters under this branch.
    lines: usize,
}

enum Node {
    Leaf(Vec<u8>),
    Branch(Branch),
}

impl Node {
    fn write(&self, out: &mut Vec<u8>) {
        match self {
            Node::Leaf(v) => {
                out.extend(v);
            }
            Node::Branch(b) => {
                b.left.write(out);
                b.right.write(out);
            }
        }
    }

    fn empty(&self) -> bool {
        return match self {
            Node::Leaf(v) => v.len() == 0,
            _ => false,
        };
    }

    fn lines(&self) -> usize {
        match self {
            Node::Leaf(v) => {
                let mut count = 0;
                for &c in v {
                    if c == b'\n' {
                        count += 1;
                    }
                }
                return count;
            }
            Node::Branch(b) => {
                return b.lines;
            }
        }
    }

    fn print_line(&self, out: &mut dyn Write, n: usize) -> Result<(), std::io::Error> {
        // TODO: escape unprintable characters
        match self {
            Node::Leaf(v) => {
                let mut nl_count = 0;
                let mut start_pos = 0;
                let mut end_pos = v.len();
                for (i, &c) in v.iter().enumerate() {
                    if c != b'\n' {
                        continue;
                    }
                    nl_count += 1;
                    if nl_count == n {
                        start_pos = i + 1;
                    }
                    if nl_count == n + 1 {
                        end_pos = i;
                        break;
                    }
                }
                if let Err(err) = out.write(&v[start_pos..end_pos]) {
                    return Err(err);
                }
                return Ok(());
            }
            Node::Branch(b) => {
                let left_lines = b.left.lines();
                if n <= left_lines {
                    if let Err(err) = b.left.print_line(out, n) {
                        return Err(err);
                    }
                }
                if n >= left_lines {
                    if let Err(err) = b.right.print_line(out, n - left_lines) {
                        return Err(err);
                    }
                }
                return Ok(());
            }
        }
    }
}

impl Display for Node {
    fn fmt(&self, f: &mut Formatter) -> Result<(), std::fmt::Error> {
        let mut buf = Vec::new();
        self.write(&mut buf);
        return write!(f, "{}", String::from_utf8_lossy(&buf));
    }
}

pub struct Rope(Rc<Node>);

impl Rope {
    fn concat(self, Rope(other): Rope) -> Rope {
        let Rope(me) = self;
        if me.empty() {
            return Rope(other);
        }
        if other.empty() {
            return Rope(me);
        }
        let lines = me.lines() + other.lines();
        return Rope(Rc::new(Node::Branch(Branch {
            left: me,
            right: other,
            lines: lines,
        })));
    }

    pub fn open(path: &Path) -> Result<Rope, String> {
        let mut f = match File::open(path) {
            Ok(f) => f,
            Err(err) => {
                return Err(format!("open: {}", err));
            }
        };
        let mut rope = Rope(Rc::new(Node::Leaf(vec![])));
        loop {
            let mut buf = vec![0; MAX_NODE_SIZE];
            let n = match f.read(&mut buf) {
                Ok(n) => n,
                Err(err) => {
                    if err.kind() == ErrorKind::Interrupted {
                        continue;
                    }
                    return Err(format!("read: {}", err));
                }
            };
            if n == 0 {
                break;
            }
            rope = rope.concat(Rope(Rc::new(Node::Leaf(buf))));
        }
        // TODO: rebalance
        return Ok(rope);
    }

    pub fn print_line(&self, out: &mut dyn Write, n: usize) -> Result<(), std::io::Error> {
        let Rope(me) = self;
        return me.print_line(out, n);
    }
}

impl Display for Rope {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
        let Rope(n) = self;
        return write!(f, "{}", n);
    }
}