use std::error::Error;
use std::io::{ErrorKind, Read, Write};
use std::rc::Rc;

const MAX_NODE_SIZE: usize = 1024;
const MAX_CHILDREN: usize = 5;

fn read(r: &mut dyn Read, buf: &mut [u8]) -> Result<usize, std::io::Error> {
    loop {
        match r.read(buf) {
            Ok(n) => return Ok(n),
            Err(err) => {
                if err.kind() == ErrorKind::Interrupted {
                    continue;
                }
                return Err(err);
            }
        }
    }
}

enum Insert {
    Node(Rope),
    Split(Rope, Rope),
}

#[derive(Debug, Clone)]
struct Leaf {
    unsafe_buf: Option<Rc<str>>,
    start: u16,
    end: u16,
    lines: u16,
}

impl Leaf {
    fn buf(&self) -> &str {
        match &self.unsafe_buf {
            None => "",
            Some(buf) => &buf[usize::from(self.start)..usize::from(self.end)],
        }
    }
}

#[derive(Debug, Clone)]
struct Branch {
    children: Rc<[Rope]>,
    len: usize,
    lines: usize,
}

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

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

impl Rope {
    pub fn len(&self) -> usize {
        match self {
            Rope(Node::Leaf(l)) => l.buf().len(),
            Rope(Node::Branch(b)) => b.len,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn lines(&self) -> usize {
        match self {
            Rope(Node::Leaf(l)) => usize::from(l.lines),
            Rope(Node::Branch(b)) => b.lines,
        }
    }

    const EMPTY: Rope = Rope(Node::Leaf(Leaf {
        unsafe_buf: None,
        start: 0,
        end: 0,
        lines: 0,
    }));

    fn leaf(buf: &str) -> Rope {
        if buf.len() > MAX_NODE_SIZE {
            panic!("buffer too long");
        }
        let mut lines = 0;
        for &b in buf.as_bytes().iter() {
            if b == b'\n' {
                lines += 1;
            }
        }
        Rope(Node::Leaf(Leaf {
            unsafe_buf: Some(Rc::from(buf)),
            start: 0,
            end: u16::try_from(buf.len()).expect("buffer too long"),
            lines,
        }))
    }

    fn branch(children: impl Iterator<Item = Rope>) -> Rope {
        let children = Rc::from_iter(children);
        let mut len = 0;
        let mut lines = 0;
        for c in children.iter() {
            len += c.len();
            lines += c.lines();
        }
        Rope(Node::Branch(Branch {
            children,
            len,
            lines,
        }))
    }

    fn concat_height(&self, self_height: usize, other: &Rope, other_height: usize) -> Insert {
        if let (Rope(Node::Leaf(l)), Rope(Node::Leaf(r))) = (self, other) {
            if self.len() + other.len() <= MAX_NODE_SIZE {
                let mut buf = String::with_capacity(self.len() + other.len());
                buf.push_str(l.buf());
                buf.push_str(r.buf());
                return Insert::Node(Rope::leaf(&buf));
            }
            if self.len() < MAX_NODE_SIZE / 2 || other.len() < MAX_NODE_SIZE / 2 {
                let mut buf = String::with_capacity(self.len() + other.len());
                buf.push_str(l.buf());
                buf.push_str(r.buf());
                let mut half = buf.len() / 2;
                while !buf.is_char_boundary(half) {
                    half -= 1;
                }
                return Insert::Split(Rope::leaf(&buf[..half]), Rope::leaf(&buf[half..]));
            }
            return Insert::Split(self.clone(), other.clone());
        }
        if self_height == other_height {
            return Insert::Split(self.clone(), other.clone());
        }
        if self_height > other_height {
            let Rope(Node::Branch(b)) = self else {
                panic!("self_height is at least 1, so it's a branch");
            };
            match b.children[b.children.len() - 1].concat_height(
                self_height - 1,
                other,
                other_height,
            ) {
                Insert::Node(new_child) => {
                    return Insert::Node(Rope::branch(
                        b.children[..b.children.len() - 1]
                            .iter()
                            .cloned()
                            .chain(std::iter::once(new_child)),
                    ));
                }
                Insert::Split(child1, child2) => {
                    if b.children.len() == MAX_CHILDREN {
                        return Insert::Split(
                            Rope::branch(b.children[..(MAX_CHILDREN + 1) / 2].iter().cloned()),
                            Rope::branch(
                                b.children[(MAX_CHILDREN + 1) / 2..MAX_CHILDREN - 1]
                                    .iter()
                                    .cloned()
                                    .chain([child1, child2].into_iter()),
                            ),
                        );
                    }
                    return Insert::Node(Rope::branch(
                        b.children[..b.children.len() - 1]
                            .iter()
                            .cloned()
                            .chain([child1, child2].into_iter()),
                    ));
                }
            }
        }
        let Rope(Node::Branch(b)) = other else {
            panic!("other_height is at least 1, so it's a branch");
        };
        match self.concat_height(self_height, &b.children[0], other_height - 1) {
            Insert::Node(new_child) => Insert::Node(Rope::branch(
                std::iter::once(new_child).chain(b.children[1..].iter().cloned()),
            )),
            Insert::Split(child1, child2) => {
                if b.children.len() == MAX_CHILDREN {
                    return Insert::Split(
                        Rope::branch(
                            [child1, child2]
                                .into_iter()
                                .chain(b.children[1..MAX_CHILDREN / 2].iter().cloned()),
                        ),
                        Rope::branch(b.children[MAX_CHILDREN / 2..].iter().cloned()),
                    );
                }
                Insert::Node(Rope::branch(
                    [child1, child2]
                        .into_iter()
                        .chain(b.children[1..].iter().cloned()),
                ))
            }
        }
    }

    fn height(&self) -> usize {
        match self {
            Rope(Node::Leaf(_)) => 0,
            Rope(Node::Branch(b)) => 1 + b.children[0].height(),
        }
    }

    pub fn concat(&self, other: &Rope) -> Rope {
        if self.is_empty() {
            return other.clone();
        }
        if other.is_empty() {
            return self.clone();
        }
        match self.concat_height(self.height(), other, other.height()) {
            Insert::Node(r) => r,
            Insert::Split(l, r) => Rope::branch([l, r].into_iter()),
        }
    }

    pub fn read(r: &mut dyn Read) -> Result<Rope, Box<dyn Error>> {
        let mut buf = vec![0; MAX_NODE_SIZE];
        let mut rope = Rope::EMPTY;
        let mut offset = 0;
        loop {
            let mut n = read(r, &mut buf[offset..])?;
            n += offset;
            if n == 0 {
                break;
            }
            let s = match std::str::from_utf8(&buf[..n]) {
                Ok(s) => s,
                Err(err) => {
                    let v = err.valid_up_to();
                    if v == 0 {
                        return Err(Box::new(err));
                    }
                    rope = rope.concat(&Rope::leaf(
                        std::str::from_utf8(&buf[..v]).expect("buf should be valid up to v"),
                    ));
                    offset = n - v;
                    for i in 0..offset {
                        buf[i] = buf[v + i];
                    }
                    continue;
                }
            };
            rope = rope.concat(&Rope::leaf(s));
            offset = 0;
        }
        Ok(rope)
    }

    pub fn new(buf: &str) -> Rope {
        if buf.is_empty() {
            return Rope::EMPTY;
        }
        if buf.len() <= MAX_NODE_SIZE {
            return Rope::leaf(buf);
        }
        Rope::read(&mut buf.as_bytes()).expect("reading from a slice should never fail")
    }

    fn is_char_boundary(&self, i: usize) -> bool {
        match self {
            Rope(Node::Leaf(l)) => l.buf().is_char_boundary(i),
            Rope(Node::Branch(b)) => {
                let mut i = i;
                for c in b.children.iter() {
                    if i < c.len() {
                        return c.is_char_boundary(i);
                    }
                    i -= c.len();
                }
                i == 0
            }
        }
    }

    pub fn floor_char_boundary(&self, i: usize) -> usize {
        for i in (0..i + 1).rev() {
            if self.is_char_boundary(i) {
                return i;
            }
        }
        0
    }

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

    fn line_end(&self, n: usize) -> usize {
        match self {
            Rope(Node::Leaf(l)) => {
                let mut count = 0;
                for (i, &c) in l.buf().as_bytes().iter().enumerate() {
                    if c != b'\n' {
                        continue;
                    }
                    if count == n {
                        return i;
                    }
                    count += 1;
                }
            }
            Rope(Node::Branch(b)) => {
                let mut n = n;
                let mut offset = 0;
                for c in b.children.iter() {
                    if n < c.lines() {
                        return offset + c.line_end(n);
                    }
                    n -= c.lines();
                    offset += c.len();
                }
            }
        }
        self.len()
    }

    pub fn line_start(&self, n: usize) -> usize {
        if n == 0 {
            return 0;
        }
        self.line_end(n - 1) + 1
    }

    pub fn line(&self, n: usize) -> Rope {
        if n > self.lines() {
            panic!("Line index {} out of range 0..={}", n, self.lines());
        }
        self.slice(self.line_start(n), self.line_end(n))
    }

    pub fn print(&self, w: &mut dyn Write) -> Result<(), std::io::Error> {
        match self {
            Rope(Node::Leaf(l)) => {
                for c in l.buf().chars() {
                    if c < ' ' || c == '\x7f' {
                        let b = u8::try_from(c).expect("c should be less than \\x7f");
                        write!(w, "\x1b[36m^{}\x1b[m", char::from(b ^ 0x40))?;
                    } else if '\u{80}' <= c && c <= '\u{9f}' {
                        write!(w, "\x1b[36m<{:x}>\x1b[m", u32::from(c))?;
                    } else {
                        write!(w, "{}", c)?;
                    }
                }
                Ok(())
            }
            Rope(Node::Branch(b)) => {
                for c in b.children.iter() {
                    c.print(w)?;
                }
                Ok(())
            }
        }
    }

    pub fn write(&self, w: &mut dyn Write) -> Result<(), std::io::Error> {
        match self {
            Rope(Node::Leaf(l)) => {
                w.write_all(l.buf().as_bytes())?;
            }
            Rope(Node::Branch(b)) => {
                for c in b.children.iter() {
                    c.write(w)?;
                }
            }
        }
        Ok(())
    }

    pub fn slice(&self, start: usize, end: usize) -> Rope {
        if start > self.len() {
            panic!(
                "Slice start index {} out of range 0..={}",
                start,
                self.len()
            );
        }
        if end > self.len() {
            panic!("Slice end index {} out of range 0..={}", end, self.len());
        }
        if start > end {
            panic!("Slice start index {} greater than end index {}", start, end);
        }
        if start == 0 && end == self.len() {
            return self.clone();
        }
        match self {
            Rope(Node::Leaf(l)) => {
                let mut lines = 0;
                for &b in l.buf()[start..end].as_bytes().iter() {
                    if b == b'\n' {
                        lines += 1;
                    }
                }
                Rope(Node::Leaf(Leaf {
                    unsafe_buf: l.unsafe_buf.clone(),
                    start: l.start + u16::try_from(start).expect("start <= self.len()"),
                    end: l.start + u16::try_from(end).expect("end <= self.len()"),
                    lines,
                }))
            }
            Rope(Node::Branch(b)) => {
                let mut s = Rope::EMPTY;
                let mut start = start;
                let mut end = end;
                for c in b.children.iter() {
                    if start >= c.len() {
                        start -= c.len();
                        end -= c.len();
                        continue;
                    }
                    s = s.concat(&c.slice(start, std::cmp::min(end, c.len())));
                    if end <= c.len() {
                        break;
                    }
                    start = 0;
                    end -= c.len();
                }
                s
            }
        }
    }

    pub fn byte(&self, i: usize) -> u8 {
        if i >= self.len() {
            panic!("Index {} out of range 0..{}", i, self.len());
        }
        match self {
            Rope(Node::Leaf(l)) => l.buf().as_bytes()[i],
            Rope(Node::Branch(b)) => {
                let mut i = i;
                for c in b.children.iter() {
                    if i < c.len() {
                        return c.byte(i);
                    }
                    i -= c.len();
                }
                panic!("unreachable");
            }
        }
    }
}