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>,
    len: usize,
    // 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 len(&self) -> usize {
        match self {
            Node::Leaf(v) => {
                return v.len();
            }
            Node::Branch(b) => {
                return b.len;
            }
        }
    }

    fn print(&self, out: &mut dyn Write, start: usize, end: usize) -> Result<(), std::io::Error> {
        // TODO: escape unprintable characters
        match self {
            Node::Leaf(v) => {
                if let Err(err) = out.write(&v[start..end]) {
                    return Err(err);
                }
                return Ok(());
            }
            Node::Branch(b) => {
                let left_len = b.left.len();
                if start < left_len {
                    if let Err(err) = b.left.print(out, start, std::cmp::min(left_len, end)) {
                        return Err(err);
                    }
                }
                if end > left_len {
                    let mut right_start = 0;
                    if start > left_len {
                        right_start = start - left_len;
                    }
                    if let Err(err) = b.right.print(out, right_start, end - left_len) {
                        return Err(err);
                    }
                }
                return Ok(());
            }
        }
    }

    fn line_idx(&self, n: usize) -> Option<usize> {
        if n == 0 {
            return Some(0);
        }
        match self {
            Node::Leaf(v) => {
                let mut nl_count = 0;
                for (i, &c) in v.iter().enumerate() {
                    if c != b'\n' {
                        continue;
                    }
                    nl_count += 1;
                    if nl_count == n {
                        return Some(i + 1);
                    }
                }
                return None;
            }
            Node::Branch(b) => {
                let left_lines = b.left.lines();
                if n <= left_lines {
                    return b.left.line_idx(n);
                }
                match b.right.line_idx(n - left_lines) {
                    Some(i) => {
                        return Some(b.left.len() + i);
                    }
                    None => {
                        return None;
                    }
                }
            }
        }
    }

    fn insert(&self, pos: usize, c: u8) -> Node {
        match self {
            Node::Leaf(v) => {
                if v.len() < MAX_NODE_SIZE {
                    let mut new_buf = vec![0; v.len() + 1];
                    new_buf[..pos].copy_from_slice(&v[..pos]);
                    new_buf[pos] = c;
                    new_buf[pos + 1..].copy_from_slice(&v[pos..]);
                    return Node::Leaf(new_buf);
                }
                let mut buf_left = vec![0; pos + 1];
                buf_left[..pos].copy_from_slice(&v[..pos]);
                buf_left[pos] = c;
                let mut buf_right = Vec::new();
                buf_right.extend_from_slice(&v[pos..]);
                let mut lines = self.lines();
                if c == b'\n' {
                    lines += 1;
                }
                return Node::Branch(Branch {
                    left: Rc::new(Node::Leaf(buf_left)),
                    right: Rc::new(Node::Leaf(buf_right)),
                    len: v.len() + 1,
                    lines: lines,
                });
            }
            Node::Branch(b) => {
                let mut lines = self.lines();
                if c == b'\n' {
                    lines += 1;
                }
                if pos < b.left.len() {
                    return Node::Branch(Branch {
                        left: Rc::new(b.left.insert(pos, c)),
                        right: b.right.clone(),
                        len: b.len + 1,
                        lines: lines,
                    });
                }
                return Node::Branch(Branch {
                    left: b.left.clone(),
                    right: Rc::new(b.right.insert(pos - b.left.len(), c)),
                    len: b.len + 1,
                    lines: lines,
                });
            }
        }
    }
}

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));
    }
}

#[derive(Clone)]
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 len = me.len() + other.len();
        let lines = me.lines() + other.lines();
        return Rope(Rc::new(Node::Branch(Branch {
            left: me,
            right: other,
            len: len,
            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 len(&self) -> usize {
        let Rope(me) = self;
        return me.len();
    }

    pub fn lines(&self) -> usize {
        let Rope(me) = self;
        return me.lines();
    }

    pub fn line(&self, n: usize) -> Option<Slice> {
        let Rope(me) = self;
        let start = match me.line_idx(n) {
            Some(start) => start,
            None => {
                return None;
            }
        };
        match me.line_idx(n + 1) {
            Some(end) => {
                return Some(Slice {
                    start: start,
                    end: end - 1,
                    buf: self.clone(),
                });
            }
            None => {
                return Some(Slice {
                    start: start,
                    end: self.len(),
                    buf: self.clone(),
                });
            }
        }
    }
}

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

pub struct Slice {
    start: usize,
    end: usize,
    buf: Rope,
}

impl Slice {
    pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> {
        let Rope(buf) = &self.buf;
        return buf.print(out, self.start, self.end);
    }

    pub fn len(&self) -> usize {
        return self.end - self.start;
    }

    pub fn insert(&self, pos: usize, c: u8) -> Rope {
        let Rope(buf) = &self.buf;
        return Rope(Rc::new(buf.insert(self.start + pos, c)));
    }
}