Rope

Rope acts as if it is a list, but inserting a value at an arbitrary position takes time complexity of amortized \( O(\log{N}) \). However, accessing values also takes amortized \( O(\log{N}) \) time. Building a rope from an iterator takes \( O(N) \).

When accessing to elements, if you use immutable borrow; that is, borrowing through rope.get(idx) or immutably indexing a value like let v = rope[3];, then splaying doesn't happen and in the worst case the accessing could take \(O(N)\). Make sure to use get_mut() for performance.

Example

fn main() {
use rope::Rope;

let mut arr: Rope<i32> = (0..10).collect();
println!("{:?}", arr);

let out = arr.take_range(1..5).unwrap();
arr.merge_right(out);
println!("{:?}", arr);

for i in 11..100000 {
    let n = arr.len() / 2;
    arr.insert(n, i);
}
println!("{}", arr[50000]);

for _ in 0..arr.len() - 10 {
    let n = arr.len() / 2;
    arr.remove(n + 1);
}
println!("{:?}", arr);
}
mod rope {
    use std::{
        cmp::Ordering,
        fmt::{Debug, Display},
        ops::{Bound::*, Index, IndexMut, RangeBounds},
        ptr::{self, NonNull},
        iter::FromIterator,
    };
    pub struct Node<T> {
        data: T,
        subt: usize,
        l: Link<T>,
        r: Link<T>,
        p: Link<T>,
    }
    type Link<T> = Option<NonNull<Node<T>>>;
    impl<T> Node<T> {
        fn new(data: T) -> Self {
            Node {
                data,
                subt: 1,
                l: None,
                r: None,
                p: None,
            }
        }
        fn left_size(&self) -> usize {
            unsafe { self.l.map_or(0, |l| (*l.as_ptr()).subt) }
        }
        fn right_size(&self) -> usize {
            unsafe { self.r.map_or(0, |r| (*r.as_ptr()).subt) }
        }
        fn upd_subtree(&mut self) {
            self.subt = 1 + self.left_size() + self.right_size();
        }
        // Option<(is_left, parent)>
        unsafe fn is_left_child(x: NonNull<Self>) -> Option<(bool, NonNull<Self>)> {
            if let Some(p) = (*x.as_ptr()).p {
                if (*p.as_ptr())
                    .l
                    .map_or(false, |pl| ptr::eq(x.as_ptr(), pl.as_ptr()))
                {
                    Some((true, p))
                } else {
                    Some((false, p))
                }
            } else {
                None
            }
        }
    }
    pub struct Rope<T> {
        root: Link<T>,
        size: usize,
    }
    impl<T> Default for Rope<T> {
        fn default() -> Self {
            Self {
                root: None,
                size: 0,
            }
        }
    }
    impl<T> Rope<T> {
        pub fn new() -> Self {
            Self::default()
        }
        pub fn len(&self) -> usize {
            self.size
        }
        pub fn insert(&mut self, idx: usize, data: T) {
            debug_assert!(idx <= self.size);
            unsafe {
                let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(data))));
                if let Some(r) = self.root {
                    let idx = self.kth_ptr(idx);
                    if let Some(idx) = idx {
                        // idx_node is the node which new_node should replace
                        // "Replace" means the new_node should be placed right before the idx_node
                        if let Some(l) = (*idx.as_ptr()).l {
                            // Attach at the right of rightmost node from l
                            let mut p = l;
                            while let Some(r) = (*p.as_ptr()).r {
                                p = r;
                            }
                            // Attach new_node to the right of p
                            (*new_node.as_ptr()).p = Some(p);
                            (*p.as_ptr()).r = Some(new_node);
                        } else {
                            // Attach it right away
                            let p = idx;
                            (*new_node.as_ptr()).p = Some(p);
                            (*p.as_ptr()).l = Some(new_node);
                        }
                    } else {
                        // idx == self.size
                        // new_node goes to the rightmost of the tree
                        let mut p = r;
                        while let Some(r) = (*p.as_ptr()).r {
                            p = r;
                        }
                        // Attach new_node to the right of p
                        (*new_node.as_ptr()).p = Some(p);
                        (*p.as_ptr()).r = Some(new_node);
                    }
                    let mut c = new_node;
                    while let Some(p) = (*c.as_ptr()).p {
                        c = p;
                        (*c.as_ptr()).upd_subtree();
                    }
                } else {
                    self.root = Some(new_node);
                }
                self.splay(new_node);
                self.size += 1;
            }
        }
        pub fn remove(&mut self, idx: usize) -> Option<T> {
            if idx >= self.size {
                return None;
            }
            let data: T = unsafe {
                if let Some(mut rt) = self.kth_ptr(idx) {
                    rt = self.remove_helper(rt);
                    if let Some(rp) = (*rt.as_ptr()).p {
                        self.splay(rp);
                    }
                    let retr = Box::from_raw(rt.as_ptr());
                    retr.data
                } else {
                    unreachable!()
                }
            };
            self.size -= 1;
            Some(data)
        }
        pub fn push_front(&mut self, data: T) {
            self.insert(0, data);
        }
        pub fn push_back(&mut self, data: T) {
            self.insert(self.size, data);
        }
        pub fn pop_front(&mut self) -> Option<T> {
            self.remove(0)
        }
        pub fn pop_back(&mut self) -> Option<T> {
            self.remove(self.size - 1)
        }
        /// Splits out the rope, leaving self[..at] and returning self[at..].
        /// If the index is invalid, it returns None.
        pub fn take_right(&mut self, right_start: usize) -> Option<Self> {
            let rhs = unsafe {
                if right_start == 0 {
                    let rhs = Self {
                        root: self.root,
                        size: self.size,
                    };
                    self.root = None;
                    self.size = 0;
                    rhs
                } else {
                    let root = self.kth_ptr(right_start - 1)?;
                    self.splay(root);
                    if let Some(r) = (*root.as_ptr()).r {
                        (*root.as_ptr()).r = None;
                        (*r.as_ptr()).p = None;
                        (*root.as_ptr()).upd_subtree();
                        self.size = (*root.as_ptr()).subt;
                        Self {
                            root: Some(r),
                            size: (*r.as_ptr()).subt,
                        }
                    } else {
                        Self {
                            root: None,
                            size: 0,
                        }
                    }
                }
            };
            Some(rhs)
        }
        /// Splits out the rope and returns self[..at] and self[at..].
        /// If the index is invalid, it returns None.
        pub fn split_at(mut self, at: usize) -> Option<(Self, Self)> {
            let rhs = self.take_right(at)?;
            Some((self, rhs))
        }
        /// Takes out the range from the rope.
        /// Returns None if the index is invalid.
        pub fn take_range(&mut self, range: impl RangeBounds<usize>) -> Option<Self> {
            let l = match range.start_bound() {
                Included(&l) => l,
                Excluded(&l) => l + 1,
                Unbounded => 0,
            };
            let r = match range.end_bound() {
                Included(&r) => r + 1,
                Excluded(&r) => r,
                Unbounded => self.size,
            };
            if l > r || l > self.size || r > self.size {
                return None;
            }
            // Now the operations below never ends early
            let c = self.take_right(r)?;
            let b = self.take_right(l)?;
            self.merge_right(c);
            Some(b)
        }
        pub fn merge_right(&mut self, mut rhs: Self) {
            if self.len() == 0 {
                self.root = rhs.root;
                self.size = rhs.size;
            } else {
                unsafe {
                    let rmost = self.kth_ptr(self.size - 1).unwrap();
                    self.splay(rmost);
                    (*rmost.as_ptr()).r = rhs.root;
                    if let Some(rhs_root) = rhs.root {
                        (*rhs_root.as_ptr()).p = Some(rmost);
                    }
                    (*rmost.as_ptr()).upd_subtree();
                    self.size = (*rmost.as_ptr()).subt;
                }
            }
            rhs.root = None;
            rhs.size = 0;
        }
        pub fn merge_left(&mut self, mut lhs: Self) {
            if self.len() == 0 {
                self.root = lhs.root;
                self.size = lhs.size;
            } else {
                unsafe {
                    let lmost = self.kth_ptr(0).unwrap();
                    self.splay(lmost);
                    (*lmost.as_ptr()).l = lhs.root;
                    if let Some(lhs_root) = lhs.root {
                        (*lhs_root.as_ptr()).p = Some(lmost);
                    }
                    (*lmost.as_ptr()).upd_subtree();
                    self.size = (*lmost.as_ptr()).subt;
                }
            }
            lhs.root = None;
            lhs.size = 0;
        }
    }
    impl<T: Debug> Debug for Rope<T> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "[")?;
            let mut cnt: usize = 0;
            unsafe {
                let mut stack: Vec<*mut Node<T>> = Vec::new();
                let mut curr = self.root;
                loop {
                    while let Some(x) = curr {
                        stack.push(x.as_ptr());
                        curr = (*x.as_ptr()).l;
                    }
                    if let Some(x) = stack.pop() {
                        if cnt == 0 {
                            write!(f, "{:?}", (*x).data)?;
                        } else {
                            write!(f, ", {:?}", (*x).data)?;
                        }
                        cnt += 1;
                        curr = (*x).r;
                    } else {
                        break;
                    }
                }
            }
            write!(f, "]")
        }
    }
    impl<T: Display> Display for Rope<T> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            unsafe {
                let mut stack: Vec<*mut Node<T>> = Vec::new();
                let mut curr = self.root;
                loop {
                    while let Some(x) = curr {
                        stack.push(x.as_ptr());
                        curr = (*x.as_ptr()).l;
                    }
                    if let Some(x) = stack.pop() {
                        write!(f, "{}", (*x).data)?;
                        curr = (*x).r;
                    } else {
                        break;
                    }
                }
            }
            Ok(())
        }
    }
    impl<T> Drop for Rope<T> {
        fn drop(&mut self) {
            if let Some(root) = self.root {
                unsafe {
                    let mut st: Vec<*mut Node<T>> = Vec::new();
                    st.push(root.as_ptr());
                    while let Some(t) = st.pop() {
                        let v = Box::from_raw(t);
                        if let Some(l) = v.l {
                            st.push(l.as_ptr());
                        }
                        if let Some(r) = v.r {
                            st.push(r.as_ptr());
                        }
                        // retrieve.drop()
                    }
                }
            }
        }
    }
    impl<T> Index<usize> for Rope<T> {
        type Output = T;
        fn index(&self, idx: usize) -> &Self::Output {
            unsafe {
                let p = self.kth_ptr(idx);
                &(*p.unwrap().as_ptr()).data
            }
        }
    }
    impl<T> IndexMut<usize> for Rope<T> {
        fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
            unsafe {
                let p = self.kth_ptr(idx);
                &mut (*p.unwrap().as_ptr()).data
            }
        }
    }
    impl<T> FromIterator<T> for Rope<T> {
        fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
            let mut arr = Self::new();
            for v in iter {
                unsafe { arr.push_ontop_root(v) };
            }
            arr
        }
    }
    //------------------------
    // Helper implementations
    //------------------------
    impl<T> Rope<T> {
        /// Adds data as a new root of a rope, and putting the original root
        /// as a left child of the root.
        unsafe fn push_ontop_root(&mut self, data: T) {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(data))));
            if let Some(root) = self.root {
                (*root.as_ptr()).p = Some(new_node);
                (*new_node.as_ptr()).l = Some(root);
            }
            self.root = Some(new_node);
            (*new_node.as_ptr()).upd_subtree();
            self.size += 1;
        }
        /// Returns false if x has no parent, and do nothing
        /// Returns true if x has a parent, after performing rotation
        unsafe fn rotate(&mut self, x: NonNull<Node<T>>) -> bool {
            if let Some((is_x_left, p)) = Node::is_left_child(x) {
                // Check if p is root
                if let Some(root) = self.root {
                    if ptr::eq(root.as_ptr(), p.as_ptr()) {
                        self.root = Some(x);
                    }
                }
                // Connect x to xpp. If pp is None, do nothing.
                (*x.as_ptr()).p = (*p.as_ptr()).p;
                if let Some((is_p_left, pp)) = Node::is_left_child(p) {
                    if is_p_left {
                        (*pp.as_ptr()).l = Some(x);
                    } else {
                        (*pp.as_ptr()).r = Some(x);
                    }
                }
                if is_x_left {
                    let b = (*x.as_ptr()).r;
                    (*x.as_ptr()).r = Some(p);
                    (*p.as_ptr()).p = Some(x);
                    (*p.as_ptr()).l = b;
                    if let Some(b) = b {
                        (*b.as_ptr()).p = Some(p);
                    }
                } else {
                    let b = (*x.as_ptr()).l;
                    (*x.as_ptr()).l = Some(p);
                    (*p.as_ptr()).p = Some(x);
                    (*p.as_ptr()).r = b;
                    if let Some(b) = b {
                        (*b.as_ptr()).p = Some(p);
                    }
                }
                (*p.as_ptr()).upd_subtree();
                (*x.as_ptr()).upd_subtree();
                true
            } else {
                false
            }
        }
        fn splay(&mut self, x: NonNull<Node<T>>) {
            unsafe {
                while let Some(root) = self.root {
                    if ptr::eq(x.as_ptr(), root.as_ptr()) {
                        break;
                    }
                    if let Some((is_x_left, p)) = Node::is_left_child(x) {
                        if ptr::eq(root.as_ptr(), p.as_ptr()) {
                            // If p is root, rotate x once
                            self.rotate(x);
                        } else {
                            // Panics if pp doesn't exist, which happens only when p is root
                            let (is_p_left, _pp) = Node::is_left_child(p).unwrap();
                            if is_x_left == is_p_left {
                                self.rotate(p);
                                self.rotate(x);
                            } else {
                                self.rotate(x);
                                self.rotate(x);
                            }
                        }
                    } else {
                        // x has no parent, which should logically never happen
                        unreachable!()
                    }
                }
            }
        }
        unsafe fn kth_ptr(&self, idx: usize) -> Link<T> {
            if self.size <= idx {
                return None;
            }
            if let Some(r) = self.root {
                let mut rem = idx;
                let mut p = r;
                loop {
                    let lsize = (*p.as_ptr()).left_size();
                    match rem.cmp(&lsize) {
                        Ordering::Less => {
                            p = (*p.as_ptr()).l?;
                        }
                        Ordering::Equal => {
                            break;
                        }
                        Ordering::Greater => {
                            rem -= lsize + 1;
                            p = (*p.as_ptr()).r?;
                        }
                    }
                }
                Some(p)
            } else {
                None
            }
        }
        unsafe fn remove_helper(&mut self, x: NonNull<Node<T>>) -> NonNull<Node<T>> {
            // Set remove_target to the actual node to delete
            match ((*x.as_ptr()).l, ((*x.as_ptr()).r)) {
                (None, None) => {
                    // Reset root if the node itself is root
                    if let Some(root) = self.root {
                        if ptr::eq(root.as_ptr(), x.as_ptr()) {
                            self.root = None;
                        }
                    }
                    // Detatch itself from parent
                    if let Some((is_x_left, p)) = Node::is_left_child(x) {
                        if is_x_left {
                            (*p.as_ptr()).l = None;
                        } else {
                            (*p.as_ptr()).r = None;
                        }
                        // Update subtree size
                        let mut p = p;
                        (*p.as_ptr()).upd_subtree();
                        while let Some(pp) = (*p.as_ptr()).p {
                            p = pp;
                            (*p.as_ptr()).upd_subtree();
                        }
                    }
                    x
                }
                (Some(l), None) => {
                    // Reset root if the node itself is a root
                    if let Some(root) = self.root {
                        if ptr::eq(root.as_ptr(), x.as_ptr()) {
                            self.root = Some(l);
                        }
                    }
                    (*l.as_ptr()).p = (*x.as_ptr()).p;
                    if let Some((is_rt_left, p)) = Node::is_left_child(x) {
                        if is_rt_left {
                            (*p.as_ptr()).l = Some(l);
                        } else {
                            (*p.as_ptr()).r = Some(l);
                        }
                    }
                    let mut p = l;
                    while let Some(pp) = (*p.as_ptr()).p {
                        p = pp;
                        (*p.as_ptr()).upd_subtree();
                    }
                    x
                }
                (None, Some(r)) => {
                    // Reset root if the node itself is a root
                    if let Some(root) = self.root {
                        if ptr::eq(root.as_ptr(), x.as_ptr()) {
                            self.root = Some(r);
                        }
                    }
                    (*r.as_ptr()).p = (*x.as_ptr()).p;
                    if let Some((is_rt_left, p)) = Node::is_left_child(x) {
                        if is_rt_left {
                            (*p.as_ptr()).l = Some(r);
                        } else {
                            (*p.as_ptr()).r = Some(r);
                        }
                    }
                    let mut p = r;
                    while let Some(pp) = (*p.as_ptr()).p {
                        p = pp;
                        (*p.as_ptr()).upd_subtree();
                    }
                    x
                }
                (Some(l), Some(_)) => {
                    let mut sw = l;
                    while let Some(sr) = (*sw.as_ptr()).r {
                        sw = sr;
                    }
                    std::mem::swap(&mut (*x.as_ptr()).data, &mut (*sw.as_ptr()).data);
                    sw = self.remove_helper(sw);
                    sw
                }
            }
        }
    }
    //-----------
    // Iterators
    //-----------
    impl<T> Rope<T> {
        pub fn iter(&self) -> Iter<T> {
            Iter::new(self)
        }
        pub fn iter_mut(&mut self) -> IterMut<T> {
            IterMut::new(self)
        }
    }
    pub struct Iter<'a, T> {
        rope: &'a Rope<T>,
        stack: Vec<NonNull<Node<T>>>,
        curr: Link<T>,
    }
    impl<'a, T> Iter<'a, T> {
        fn new(rope: &'a Rope<T>) -> Self {
            let root = rope.root;
            Self {
                rope,
                stack: Vec::new(),
                curr: root,
            }
        }
    }
    impl<'a, T> IntoIterator for &'a Rope<T> {
        type Item = &'a T;
        type IntoIter = Iter<'a, T>;
        fn into_iter(self) -> Self::IntoIter {
            Self::IntoIter::new(self)
        }
    }
    impl<'a, T> Iterator for Iter<'a, T> {
        type Item = &'a T;
        fn next(&mut self) -> Option<Self::Item> {
            unsafe {
                while let Some(x) = self.curr {
                    self.stack.push(x);
                    self.curr = (*x.as_ptr()).l;
                }
                if let Some(x) = self.stack.pop() {
                    self.curr = (*x.as_ptr()).r;
                    Some(&x.as_ref().data)
                } else {
                    None
                }
            }
        }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rope.len(), Some(self.rope.len()))
        }
    }
    pub struct IterMut<'a, T> {
        rope: &'a mut Rope<T>,
        stack: Vec<NonNull<Node<T>>>,
        curr: Link<T>,
    }
    impl<'a, T> IterMut<'a, T> {
        fn new(rope: &'a mut Rope<T>) -> Self {
            let root = rope.root;
            Self {
                rope,
                stack: Vec::new(),
                curr: root,
            }
        }
    }
    impl<'a, T> IntoIterator for &'a mut Rope<T> {
        type Item = &'a mut T;
        type IntoIter = IterMut<'a, T>;
        fn into_iter(self) -> Self::IntoIter {
            Self::IntoIter::new(self)
        }
    }
    impl<'a, T> Iterator for IterMut<'a, T> {
        type Item = &'a mut T;
        fn next(&mut self) -> Option<Self::Item> {
            unsafe {
                while let Some(x) = self.curr {
                    self.stack.push(x);
                    self.curr = (*x.as_ptr()).l;
                }
                if let Some(mut x) = self.stack.pop() {
                    self.curr = (*x.as_ptr()).r;
                    Some(&mut x.as_mut().data)
                } else {
                    None
                }
            }
        }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rope.len(), Some(self.rope.len()))
        }
    }
}

Code

mod rope {
    use std::{
        cmp::Ordering,
        fmt::{Debug, Display},
        ops::{Bound::*, Index, IndexMut, RangeBounds},
        ptr::{self, NonNull},
    };

    pub struct Rope<T> {
        root: Link<T>,
        size: usize,
    }

    impl<T> Default for Rope<T> {
        fn default() -> Self {
            Self {
                root: None,
                size: 0,
            }
        }
    }

    impl<T> Rope<T> {
        pub fn new() -> Self {
            Self::default()
        }

        pub fn len(&self) -> usize {
            self.size
        }

        pub fn clear(&mut self) {
            let drop_tree = Self {
                root: self.root,
                size: self.size,
            };
            drop(drop_tree);
            self.root = None;
            self.size = 0;
        }

        pub fn insert(&mut self, idx: usize, data: T) {
            debug_assert!(idx <= self.size);
            unsafe {
                let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(data))));

                if let Some(r) = self.root {
                    let idx = self.kth_ptr(idx);
                    if let Some(idx) = idx {
                        // idx_node is the node which new_node should replace
                        // "Replace" means the new_node should be placed right before the idx_node
                        if let Some(l) = (*idx.as_ptr()).l {
                            // Attach at the right of rightmost node from l
                            let mut p = l;
                            while let Some(r) = (*p.as_ptr()).r {
                                p = r;
                            }
                            // Attach new_node to the right of p
                            (*new_node.as_ptr()).p = Some(p);
                            (*p.as_ptr()).r = Some(new_node);
                        } else {
                            // Attach it right away
                            let p = idx;
                            (*new_node.as_ptr()).p = Some(p);
                            (*p.as_ptr()).l = Some(new_node);
                        }
                    } else {
                        // idx == self.size
                        // new_node goes to the rightmost of the tree
                        let mut p = r;
                        while let Some(r) = (*p.as_ptr()).r {
                            p = r;
                        }
                        // Attach new_node to the right of p
                        (*new_node.as_ptr()).p = Some(p);
                        (*p.as_ptr()).r = Some(new_node);
                    }

                    let mut c = new_node;
                    while let Some(p) = (*c.as_ptr()).p {
                        c = p;
                        (*c.as_ptr()).upd_subtree();
                    }
                } else {
                    self.root = Some(new_node);
                }

                self.splay(new_node);
                self.size += 1;
            }
        }

        pub fn remove(&mut self, idx: usize) -> Option<T> {
            if idx >= self.size {
                return None;
            }

            let data: T = unsafe {
                if let Some(mut rt) = self.kth_ptr(idx) {
                    rt = self.remove_helper(rt);
                    if let Some(rp) = (*rt.as_ptr()).p {
                        self.splay(rp);
                    }
                    let retr = Box::from_raw(rt.as_ptr());
                    retr.data
                } else {
                    unreachable!()
                }
            };

            self.size -= 1;
            Some(data)
        }

        pub fn push_front(&mut self, data: T) {
            self.insert(0, data);
        }

        pub fn push_back(&mut self, data: T) {
            self.insert(self.size, data);
        }

        pub fn pop_front(&mut self) -> Option<T> {
            self.remove(0)
        }

        pub fn pop_back(&mut self) -> Option<T> {
            self.remove(self.size - 1)
        }

        /// Splits out the rope, leaving self[..at] and returning self[at..].
        /// If the index is invalid, it returns None.
        pub fn take_right(&mut self, right_start: usize) -> Option<Self> {
            let rhs = unsafe {
                if right_start == 0 {
                    let rhs = Self {
                        root: self.root,
                        size: self.size,
                    };
                    self.root = None;
                    self.size = 0;
                    rhs
                } else {
                    let root = self.kth_ptr(right_start - 1)?;
                    self.splay(root);
                    if let Some(r) = (*root.as_ptr()).r {
                        (*root.as_ptr()).r = None;
                        (*r.as_ptr()).p = None;
                        (*root.as_ptr()).upd_subtree();
                        self.size = (*root.as_ptr()).subt;
                        Self {
                            root: Some(r),
                            size: (*r.as_ptr()).subt,
                        }
                    } else {
                        Self {
                            root: None,
                            size: 0,
                        }
                    }
                }
            };
            Some(rhs)
        }

        /// Splits out the rope and returns self[..at] and self[at..].
        /// If the index is invalid, it returns None.
        pub fn split_at(mut self, at: usize) -> Option<(Self, Self)> {
            let rhs = self.take_right(at)?;
            Some((self, rhs))
        }

        /// Takes out the range from the rope.
        /// Returns None if the index is invalid.
        pub fn take_range(&mut self, range: impl RangeBounds<usize>) -> Option<Self> {
            let l = match range.start_bound() {
                Included(&l) => l,
                Excluded(&l) => l + 1,
                Unbounded => 0,
            };
            let r = match range.end_bound() {
                Included(&r) => r + 1,
                Excluded(&r) => r,
                Unbounded => self.size,
            };

            if l > r || l > self.size || r > self.size {
                return None;
            }
            // Now the operations below never ends early
            let c = self.take_right(r)?;
            let b = self.take_right(l)?;
            self.merge_right(c);
            Some(b)
        }

        pub fn merge_right(&mut self, mut rhs: Self) {
            if self.len() == 0 {
                self.root = rhs.root;
                self.size = rhs.size;
            } else {
                unsafe {
                    let rmost = self.kth_ptr(self.size - 1).unwrap();
                    self.splay(rmost);
                    (*rmost.as_ptr()).r = rhs.root;
                    if let Some(rhs_root) = rhs.root {
                        (*rhs_root.as_ptr()).p = Some(rmost);
                    }
                    (*rmost.as_ptr()).upd_subtree();
                    self.size = (*rmost.as_ptr()).subt;
                }
            }
            rhs.root = None;
            rhs.size = 0;
        }

        pub fn merge_left(&mut self, mut lhs: Self) {
            if self.len() == 0 {
                self.root = lhs.root;
                self.size = lhs.size;
            } else {
                unsafe {
                    let lmost = self.kth_ptr(0).unwrap();
                    self.splay(lmost);
                    (*lmost.as_ptr()).l = lhs.root;
                    if let Some(lhs_root) = lhs.root {
                        (*lhs_root.as_ptr()).p = Some(lmost);
                    }
                    (*lmost.as_ptr()).upd_subtree();
                    self.size = (*lmost.as_ptr()).subt;
                }
            }
            lhs.root = None;
            lhs.size = 0;
        }

        /// Inserts rope into self at self.
        /// After the operation, rope[0] becomes self[at].
        /// Returns false if the specified index is invalid, true otherwise.
        pub fn insert_rope(&mut self, rope: Self, at: usize) -> bool {
            let rhs = self.take_right(at);
            if let Some(rhs) = rhs {
                self.merge_right(rope);
                self.merge_right(rhs);
                true
            } else {
                false
            }
        }
    }

    impl<T: Clone> Clone for Rope<T> {
        fn clone(&self) -> Self {
            self.iter().cloned().collect()
        }
    }

    impl<T: Debug> Debug for Rope<T> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "[")?;
            let mut cnt: usize = 0;
            unsafe {
                let mut stack: Vec<*mut Node<T>> = Vec::new();
                let mut curr = self.root;
                loop {
                    while let Some(x) = curr {
                        stack.push(x.as_ptr());
                        curr = (*x.as_ptr()).l;
                    }
                    if let Some(x) = stack.pop() {
                        if cnt == 0 {
                            write!(f, "{:?}", (*x).data)?;
                        } else {
                            write!(f, ", {:?}", (*x).data)?;
                        }
                        cnt += 1;
                        curr = (*x).r;
                    } else {
                        break;
                    }
                }
            }
            write!(f, "]")
        }
    }

    impl<T: Display> Display for Rope<T> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            unsafe {
                let mut stack: Vec<*mut Node<T>> = Vec::new();
                let mut curr = self.root;
                loop {
                    while let Some(x) = curr {
                        stack.push(x.as_ptr());
                        curr = (*x.as_ptr()).l;
                    }
                    if let Some(x) = stack.pop() {
                        write!(f, "{}", (*x).data)?;
                        curr = (*x).r;
                    } else {
                        break;
                    }
                }
            }
            Ok(())
        }
    }

    impl<T> Drop for Rope<T> {
        fn drop(&mut self) {
            if let Some(root) = self.root {
                unsafe {
                    let mut st: Vec<*mut Node<T>> = Vec::new();
                    st.push(root.as_ptr());
                    while let Some(t) = st.pop() {
                        let v = Box::from_raw(t);
                        if let Some(l) = v.l {
                            st.push(l.as_ptr());
                        }
                        if let Some(r) = v.r {
                            st.push(r.as_ptr());
                        }
                        drop(v);
                    }
                }
            }
        }
    }

    impl<T> Index<usize> for Rope<T> {
        type Output = T;
        fn index(&self, idx: usize) -> &Self::Output {
            unsafe {
                let p = self.kth_ptr(idx).unwrap();
                &(*p.as_ptr()).data
            }
        }
    }

    impl<T> IndexMut<usize> for Rope<T> {
        fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
            unsafe {
                let p = self.kth_ptr(idx).unwrap();
                self.splay(p);
                &mut (*p.as_ptr()).data
            }
        }
    }

    impl<T> FromIterator<T> for Rope<T> {
        fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
            let mut arr = Self::new();
            for v in iter {
                unsafe { arr.push_ontop_root(v) };
            }
            arr
        }
    }

    impl<T> Rope<T> {
        pub fn iter(&self) -> Iter<T> {
            Iter::new(self)
        }

        pub fn iter_mut(&mut self) -> IterMut<T> {
            IterMut::new(self)
        }
    }

    pub struct Iter<'a, T> {
        rope: &'a Rope<T>,
        stack: Vec<NonNull<Node<T>>>,
        curr: Link<T>,
    }

    impl<'a, T> Iter<'a, T> {
        fn new(rope: &'a Rope<T>) -> Self {
            let root = rope.root;
            Self {
                rope,
                stack: Vec::new(),
                curr: root,
            }
        }
    }

    impl<'a, T> IntoIterator for &'a Rope<T> {
        type Item = &'a T;
        type IntoIter = Iter<'a, T>;
        fn into_iter(self) -> Self::IntoIter {
            Self::IntoIter::new(self)
        }
    }

    impl<'a, T> Iterator for Iter<'a, T> {
        type Item = &'a T;
        fn next(&mut self) -> Option<Self::Item> {
            unsafe {
                while let Some(x) = self.curr {
                    self.stack.push(x);
                    self.curr = (*x.as_ptr()).l;
                }
                if let Some(x) = self.stack.pop() {
                    self.curr = (*x.as_ptr()).r;
                    Some(&x.as_ref().data)
                } else {
                    None
                }
            }
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rope.len(), Some(self.rope.len()))
        }
    }

    pub struct IterMut<'a, T> {
        rope: &'a mut Rope<T>,
        stack: Vec<NonNull<Node<T>>>,
        curr: Link<T>,
    }

    impl<'a, T> IterMut<'a, T> {
        fn new(rope: &'a mut Rope<T>) -> Self {
            let root = rope.root;
            Self {
                rope,
                stack: Vec::new(),
                curr: root,
            }
        }
    }

    impl<'a, T> IntoIterator for &'a mut Rope<T> {
        type Item = &'a mut T;
        type IntoIter = IterMut<'a, T>;
        fn into_iter(self) -> Self::IntoIter {
            Self::IntoIter::new(self)
        }
    }

    impl<'a, T> Iterator for IterMut<'a, T> {
        type Item = &'a mut T;
        fn next(&mut self) -> Option<Self::Item> {
            unsafe {
                while let Some(x) = self.curr {
                    self.stack.push(x);
                    self.curr = (*x.as_ptr()).l;
                }
                if let Some(mut x) = self.stack.pop() {
                    self.curr = (*x.as_ptr()).r;
                    Some(&mut x.as_mut().data)
                } else {
                    None
                }
            }
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rope.len(), Some(self.rope.len()))
        }
    }

    //------------------------
    // Helper implementations
    //------------------------

    struct Node<T> {
        data: T,
        subt: usize,
        l: Link<T>,
        r: Link<T>,
        p: Link<T>,
    }

    type Link<T> = Option<NonNull<Node<T>>>;

    impl<T> Node<T> {
        fn new(data: T) -> Self {
            Node {
                data,
                subt: 1,
                l: None,
                r: None,
                p: None,
            }
        }
        fn left_size(&self) -> usize {
            unsafe { self.l.map_or(0, |l| (*l.as_ptr()).subt) }
        }
        fn right_size(&self) -> usize {
            unsafe { self.r.map_or(0, |r| (*r.as_ptr()).subt) }
        }
        fn upd_subtree(&mut self) {
            self.subt = 1 + self.left_size() + self.right_size();
        }

        // Option<(is_left, parent)>
        unsafe fn is_left_child(x: NonNull<Self>) -> Option<(bool, NonNull<Self>)> {
            if let Some(p) = (*x.as_ptr()).p {
                if (*p.as_ptr())
                    .l
                    .map_or(false, |pl| ptr::eq(x.as_ptr(), pl.as_ptr()))
                {
                    Some((true, p))
                } else {
                    Some((false, p))
                }
            } else {
                None
            }
        }
    }

    impl<T> Rope<T> {
        /// Adds data as a new root of a rope, and putting the original root
        /// as a left child of the root.
        unsafe fn push_ontop_root(&mut self, data: T) {
            let new_node = NonNull::new_unchecked(Box::into_raw(Box::new(Node::new(data))));
            if let Some(root) = self.root {
                (*root.as_ptr()).p = Some(new_node);
                (*new_node.as_ptr()).l = Some(root);
            }
            self.root = Some(new_node);
            (*new_node.as_ptr()).upd_subtree();
            self.size += 1;
        }

        /// Returns false if x has no parent, and do nothing
        /// Returns true if x has a parent, after performing rotation
        unsafe fn rotate(&mut self, x: NonNull<Node<T>>) -> bool {
            if let Some((is_x_left, p)) = Node::is_left_child(x) {
                // Check if p is root
                if let Some(root) = self.root {
                    if ptr::eq(root.as_ptr(), p.as_ptr()) {
                        self.root = Some(x);
                    }
                }

                // Connect x to xpp. If pp is None, do nothing.
                (*x.as_ptr()).p = (*p.as_ptr()).p;
                if let Some((is_p_left, pp)) = Node::is_left_child(p) {
                    if is_p_left {
                        (*pp.as_ptr()).l = Some(x);
                    } else {
                        (*pp.as_ptr()).r = Some(x);
                    }
                }

                if is_x_left {
                    let b = (*x.as_ptr()).r;
                    (*x.as_ptr()).r = Some(p);
                    (*p.as_ptr()).p = Some(x);
                    (*p.as_ptr()).l = b;
                    if let Some(b) = b {
                        (*b.as_ptr()).p = Some(p);
                    }
                } else {
                    let b = (*x.as_ptr()).l;
                    (*x.as_ptr()).l = Some(p);
                    (*p.as_ptr()).p = Some(x);
                    (*p.as_ptr()).r = b;
                    if let Some(b) = b {
                        (*b.as_ptr()).p = Some(p);
                    }
                }

                (*p.as_ptr()).upd_subtree();
                (*x.as_ptr()).upd_subtree();
                true
            } else {
                false
            }
        }

        fn splay(&mut self, x: NonNull<Node<T>>) {
            unsafe {
                while let Some(root) = self.root {
                    if ptr::eq(x.as_ptr(), root.as_ptr()) {
                        break;
                    }

                    if let Some((is_x_left, p)) = Node::is_left_child(x) {
                        if ptr::eq(root.as_ptr(), p.as_ptr()) {
                            // If p is root, rotate x once
                            self.rotate(x);
                        } else {
                            // Panics if pp doesn't exist, which happens only when p is root
                            let (is_p_left, _pp) = Node::is_left_child(p).unwrap();
                            if is_x_left == is_p_left {
                                self.rotate(p);
                                self.rotate(x);
                            } else {
                                self.rotate(x);
                                self.rotate(x);
                            }
                        }
                    } else {
                        // x has no parent, which should logically never happen
                        unreachable!()
                    }
                }
            }
        }

        unsafe fn kth_ptr(&self, idx: usize) -> Link<T> {
            if self.size <= idx {
                return None;
            }
            if let Some(r) = self.root {
                let mut rem = idx;
                let mut p = r;
                loop {
                    let lsize = (*p.as_ptr()).left_size();
                    match rem.cmp(&lsize) {
                        Ordering::Less => {
                            p = (*p.as_ptr()).l?;
                        }
                        Ordering::Equal => {
                            break;
                        }
                        Ordering::Greater => {
                            rem -= lsize + 1;
                            p = (*p.as_ptr()).r?;
                        }
                    }
                }
                Some(p)
            } else {
                None
            }
        }

        unsafe fn remove_helper(&mut self, x: NonNull<Node<T>>) -> NonNull<Node<T>> {
            // Set remove_target to the actual node to delete
            match ((*x.as_ptr()).l, ((*x.as_ptr()).r)) {
                (None, None) => {
                    // Reset root if the node itself is root
                    if let Some(root) = self.root {
                        if ptr::eq(root.as_ptr(), x.as_ptr()) {
                            self.root = None;
                        }
                    }
                    // Detatch itself from parent
                    if let Some((is_x_left, p)) = Node::is_left_child(x) {
                        if is_x_left {
                            (*p.as_ptr()).l = None;
                        } else {
                            (*p.as_ptr()).r = None;
                        }
                        // Update subtree size
                        let mut p = p;
                        (*p.as_ptr()).upd_subtree();
                        while let Some(pp) = (*p.as_ptr()).p {
                            p = pp;
                            (*p.as_ptr()).upd_subtree();
                        }
                    }
                    x
                }
                (Some(l), None) => {
                    // Reset root if the node itself is a root
                    if let Some(root) = self.root {
                        if ptr::eq(root.as_ptr(), x.as_ptr()) {
                            self.root = Some(l);
                        }
                    }

                    (*l.as_ptr()).p = (*x.as_ptr()).p;
                    if let Some((is_rt_left, p)) = Node::is_left_child(x) {
                        if is_rt_left {
                            (*p.as_ptr()).l = Some(l);
                        } else {
                            (*p.as_ptr()).r = Some(l);
                        }
                    }

                    let mut p = l;
                    while let Some(pp) = (*p.as_ptr()).p {
                        p = pp;
                        (*p.as_ptr()).upd_subtree();
                    }
                    x
                }
                (None, Some(r)) => {
                    // Reset root if the node itself is a root
                    if let Some(root) = self.root {
                        if ptr::eq(root.as_ptr(), x.as_ptr()) {
                            self.root = Some(r);
                        }
                    }

                    (*r.as_ptr()).p = (*x.as_ptr()).p;
                    if let Some((is_rt_left, p)) = Node::is_left_child(x) {
                        if is_rt_left {
                            (*p.as_ptr()).l = Some(r);
                        } else {
                            (*p.as_ptr()).r = Some(r);
                        }
                    }

                    let mut p = r;
                    while let Some(pp) = (*p.as_ptr()).p {
                        p = pp;
                        (*p.as_ptr()).upd_subtree();
                    }
                    x
                }
                (Some(l), Some(_)) => {
                    let mut sw = l;
                    while let Some(sr) = (*sw.as_ptr()).r {
                        sw = sr;
                    }
                    std::mem::swap(&mut (*x.as_ptr()).data, &mut (*sw.as_ptr()).data);
                    sw = self.remove_helper(sw);
                    sw
                }
            }
        }
    }
}