use std::error::Error;
use std::fs::File;
use std::io::{ErrorKind, Read, Write};
use std::path::Path;
use std::rc::Rc;

const MAX_NODE_SIZE: usize = 255;

#[derive(Debug, Clone)]
struct Leaf {
    buf: Rc<[u8]>,
    start: u8,
    end: u8,
}

impl Leaf {
    fn bytes(&self) -> &[u8] {
        return &self.buf[usize::from(self.start)..usize::from(self.end)];
    }
}

#[derive(Debug, Clone)]
struct Branch {
    len: usize,
    // Number of newline characters under this branch.
    lines: usize,
    height: usize,
    child1: Rope,
    child2: Rope,
    child3: Option<Rope>,
}

impl Branch {
    fn children(&self) -> Children {
        return Children { b: self, i: 0 };
    }
}

#[derive(Debug, Clone, Copy)]
struct Children<'a> {
    b: &'a Branch,
    i: u8,
}

impl<'a> Iterator for Children<'a> {
    type Item = Rope;

    fn next(&mut self) -> Option<Self::Item> {
        let c = match self.i {
            0 => self.b.child1.clone(),
            1 => self.b.child2.clone(),
            2 => match &self.b.child3 {
                Some(child3) => child3.clone(),
                None => {
                    return None;
                }
            },
            _ => {
                return None;
            }
        };
        self.i += 1;
        return Some(c);
    }
}

#[derive(Debug, Clone)]
enum Node {
    Leaf(Leaf),
    Branch(Rc<Branch>),
}

#[derive(Debug, Clone)]
pub struct Rope(Node);

fn leaf(buf: Vec<u8>) -> Rope {
    let len = buf.len();
    return Rope(Node::Leaf(Leaf {
        buf: Rc::from(buf),
        start: 0,
        end: u8::try_from(len).expect("buffer too long"),
    }));
}

// The two and three constructors maintain the size of the tree.
fn two(l: &Rope, r: &Rope) -> Rope {
    if l.height() != r.height() {
        panic!("Joining trees of different height");
    }
    return Rope(Node::Branch(Rc::new(Branch {
        len: l.len() + r.len(),
        lines: l.lines() + r.lines(),
        height: l.height() + 1,
        child1: l.clone(),
        child2: r.clone(),
        child3: None,
    })));
}

fn three(a: &Rope, b: &Rope, c: &Rope) -> Rope {
    if a.height() != b.height() || b.height() != c.height() {
        panic!("Joining trees of different height");
    }
    return Rope(Node::Branch(Rc::new(Branch {
        len: a.len() + b.len() + c.len(),
        lines: a.lines() + b.lines() + c.lines(),
        height: a.height() + 1,
        child1: a.clone(),
        child2: b.clone(),
        child3: Some(c.clone()),
    })));
}

#[derive(Debug)]
enum Insert {
    Node(Rope),
    Split(Rope, Rope),
}

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

    pub fn len(&self) -> usize {
        match self {
            Rope(Node::Leaf(l)) => {
                return usize::from(l.end - l.start);
            }
            Rope(Node::Branch(b)) => {
                return b.len;
            }
        }
    }

    pub fn height(&self) -> usize {
        match self {
            Rope(Node::Leaf(_)) => 0,
            Rope(Node::Branch(b)) => b.height,
        }
    }

    pub fn print(&self, out: &mut dyn Write) -> Result<(), std::io::Error> {
        if self.len() == 0 {
            return Ok(());
        }
        // TODO: escape unprintable characters
        match self {
            Rope(Node::Leaf(l)) => {
                out.write_all(l.bytes())?;
                return Ok(());
            }
            Rope(Node::Branch(b)) => {
                for child in b.children() {
                    child.print(out)?;
                }
                return Ok(());
            }
        }
    }

    pub fn line_idx(&self, n: usize) -> usize {
        if n > self.lines() {
            panic!("Index {} out of range 0..{}", n, self.lines() + 1);
        }
        if n == 0 {
            return 0;
        }
        match self {
            Rope(Node::Leaf(l)) => {
                let mut nl_count = 0;
                for (i, &c) in l.bytes().iter().enumerate() {
                    if c != b'\n' {
                        continue;
                    }
                    nl_count += 1;
                    if nl_count == n {
                        return i + 1;
                    }
                }
                panic!("unreachable");
            }
            Rope(Node::Branch(b)) => {
                let mut offset = 0;
                let mut n = n;
                for child in b.children() {
                    let child_lines = child.lines();
                    if n <= child_lines {
                        return offset + child.line_idx(n);
                    }
                    offset += child.len();
                    n -= child_lines;
                }
                panic!("unreachable");
            }
        }
    }

    fn try_concat(&self, other: &Rope) -> Insert {
        if self.len() == 0 {
            return Insert::Node(other.clone());
        }
        if other.len() == 0 {
            return Insert::Node(self.clone());
        }
        if let (Rope(Node::Leaf(l)), Rope(Node::Leaf(r))) = (self, other) {
            if self.len() <= MAX_NODE_SIZE - other.len() {
                let mut buf = Vec::new();
                buf.extend_from_slice(&l.bytes());
                buf.extend_from_slice(&r.bytes());
                return Insert::Node(leaf(buf));
            }
            if self.len() < MAX_NODE_SIZE / 2 || other.len() < MAX_NODE_SIZE / 2 {
                let mut buf = Vec::new();
                buf.extend_from_slice(&l.bytes());
                buf.extend_from_slice(&r.bytes());
                let mut buf1 = Vec::new();
                buf1.extend_from_slice(&buf[..buf.len() / 2]);
                let mut buf2 = Vec::new();
                buf2.extend_from_slice(&buf[buf.len() / 2..]);
                return Insert::Split(leaf(buf1), leaf(buf2));
            }
        }
        if self.height() == other.height() {
            return Insert::Split(self.clone(), other.clone());
        }
        if self.height() > other.height() {
            let Rope(Node::Branch(selfb)) = self else {
                panic!("self should have height at least one, which means it's a branch");
            };
            match &selfb.child3 {
                Some(child3) => match child3.try_concat(other) {
                    Insert::Node(new_child) => {
                        Insert::Node(three(&selfb.child1, &selfb.child2, &new_child))
                    }
                    Insert::Split(child1, child2) => {
                        Insert::Split(two(&selfb.child1, &selfb.child2), two(&child1, &child2))
                    }
                },
                None => match selfb.child2.try_concat(other) {
                    Insert::Node(new_child) => Insert::Node(two(&selfb.child1, &new_child)),
                    Insert::Split(child1, child2) => {
                        Insert::Node(three(&selfb.child1, &child1, &child2))
                    }
                },
            }
        } else {
            let Rope(Node::Branch(otherb)) = other else {
                panic!("other should have height at least one, which means it's a branch");
            };
            match &otherb.child3 {
                Some(child3) => match self.try_concat(&otherb.child1) {
                    Insert::Node(new_child) => {
                        Insert::Node(three(&new_child, &otherb.child2, &child3))
                    }
                    Insert::Split(child1, child2) => {
                        Insert::Split(two(&child1, &child2), two(&otherb.child2, &child3))
                    }
                },
                None => match self.try_concat(&otherb.child1) {
                    Insert::Node(new_child) => Insert::Node(two(&new_child, &otherb.child2)),
                    Insert::Split(child1, child2) => {
                        Insert::Node(three(&child1, &child2, &otherb.child2))
                    }
                },
            }
        }
    }

    pub fn concat(&self, other: &Rope) -> Rope {
        match self.try_concat(other) {
            Insert::Node(r) => r,
            Insert::Split(l, r) => two(&l, &r),
        }
    }

    pub fn insert(&self, pos: usize, c: u8) -> Rope {
        let res = self
            .slice(0, pos)
            .concat(&leaf(vec![c]))
            .concat(&self.slice(pos, self.len()));
        return res;
    }

    pub fn slice(&self, start: usize, end: usize) -> Rope {
        if start > self.len() {
            panic!("Index {} out of range 0..{}", start, self.len() + 1);
        }
        if end > self.len() {
            panic!("Index {} out of range 0..{}", end, self.len());
        }
        if start > end {
            panic!(
                "Slice start index {} is greater than end index {}",
                start, end
            );
        }
        match self {
            Rope(Node::Leaf(l)) => {
                return Rope(Node::Leaf(Leaf {
                    buf: l.buf.clone(),
                    start: l.start + u8::try_from(start).expect("buffer too long"),
                    end: l.start + u8::try_from(end).expect("buffer too long"),
                }));
            }
            Rope(Node::Branch(b)) => {
                let mut start = start;
                let mut end = end;
                let mut slice = leaf(Vec::new());
                for child in b.children() {
                    if start < child.len() {
                        slice = slice.concat(&child.slice(start, std::cmp::min(end, child.len())));
                        if end < child.len() {
                            break;
                        }
                        start = 0;
                    } else {
                        start -= child.len();
                    }
                    end -= child.len();
                }
                return slice;
            }
        }
    }

    pub fn open(path: &Path) -> Result<Rope, Box<dyn Error>> {
        let mut f =
            File::open(path).map_err(|err| format!("open file {}: {}", path.display(), err))?;
        let mut rope = leaf(Vec::new());
        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(Box::from(format!("read file {}: {}", path.display(), err)));
                }
            };
            if n == 0 {
                break;
            }
            buf.truncate(n);
            rope = rope.concat(&leaf(buf));
        }
        return Ok(rope);
    }

    pub fn save(&self, path: &Path) -> Result<(), Box<dyn Error>> {
        let mut f = File::create(path)
            .map_err(|err| format!("save: create file {}: {}", path.display(), err))?;
        self.print(&mut f)
            .map_err(|err| format!("save: write file {}: {}", path.display(), err))?;
        f.sync_all()
            .map_err(|err| format!("save: write file {}: {}", path.display(), err))?;
        return Ok(());
    }

    pub fn line(&self, n: usize) -> Rope {
        if n > self.lines() {
            panic!("Index {} out of range 0..{}", n, self.lines() + 1);
        }
        let start = self.line_idx(n);
        let mut end = self.len();
        if n < self.lines() {
            end = self.line_idx(n + 1) - 1;
        }
        return self.slice(start, end);
    }

    fn is_char_boundary(&self, index: usize) -> bool {
        match self {
            Rope(Node::Leaf(l)) => {
                return l.bytes()[index] & 0xc0 != 0x80;
            }
            Rope(Node::Branch(b)) => {
                let mut index = index;
                for child in b.children() {
                    if index < child.len() {
                        return child.is_char_boundary(index);
                    }
                    index -= child.len();
                }
                return false;
            }
        }
    }

    pub fn floor_char_boundary(&self, index: usize) -> usize {
        for i in (0..index + 1).rev() {
            if self.is_char_boundary(i) {
                return i;
            }
        }
        panic!("I'm not valid UTF-8: {:?}", self);
    }

    pub fn ceil_char_boundary(&self, index: usize) -> usize {
        for i in index..self.len() {
            if self.is_char_boundary(i) {
                return i;
            }
        }
        return self.len();
    }
}