use std::cmp::min;
use std::marker::PhantomData;
use std::sync::Arc;
use crate::interval::{Interval, IntervalBounds};
const MIN_CHILDREN: usize = 4;
const MAX_CHILDREN: usize = 8;
pub trait NodeInfo: Clone {
type L: Leaf;
fn accumulate(&mut self, other: &Self);
fn compute_info(_: &Self::L) -> Self;
fn identity() -> Self {
Self::compute_info(&Self::L::default())
}
fn interval(&self, len: usize) -> Interval {
Interval::new(0, len)
}
}
pub trait DefaultMetric: NodeInfo {
type DefaultMetric: Metric<Self>;
}
pub trait Leaf: Sized + Clone + Default {
fn len(&self) -> usize;
fn is_ok_child(&self) -> bool;
fn push_maybe_split(&mut self, other: &Self, iv: Interval) -> Option<Self>;
fn subseq(&self, iv: Interval) -> Self {
let mut result = Self::default();
if result.push_maybe_split(self, iv).is_some() {
panic!("unexpected split");
}
result
}
}
#[derive(Clone)]
pub struct Node<N: NodeInfo>(Arc<NodeBody<N>>);
#[derive(Clone)]
struct NodeBody<N: NodeInfo> {
height: usize,
len: usize,
info: N,
val: NodeVal<N>,
}
#[derive(Clone)]
enum NodeVal<N: NodeInfo> {
Leaf(N::L),
Internal(Vec<Node<N>>),
}
pub trait Metric<N: NodeInfo> {
fn measure(info: &N, len: usize) -> usize;
fn to_base_units(l: &N::L, in_measured_units: usize) -> usize;
fn from_base_units(l: &N::L, in_base_units: usize) -> usize;
fn is_boundary(l: &N::L, offset: usize) -> bool;
fn prev(l: &N::L, offset: usize) -> Option<usize>;
fn next(l: &N::L, offset: usize) -> Option<usize>;
fn can_fragment() -> bool;
}
impl<N: NodeInfo> Node<N> {
pub fn from_leaf(l: N::L) -> Node<N> {
let len = l.len();
let info = N::compute_info(&l);
Node(Arc::new(NodeBody { height: 0, len, info, val: NodeVal::Leaf(l) }))
}
fn from_nodes(nodes: Vec<Node<N>>) -> Node<N> {
let height = nodes[0].0.height + 1;
let mut len = nodes[0].0.len;
let mut info = nodes[0].0.info.clone();
for child in &nodes[1..] {
len += child.0.len;
info.accumulate(&child.0.info);
}
Node(Arc::new(NodeBody { height, len, info, val: NodeVal::Internal(nodes) }))
}
pub fn len(&self) -> usize {
self.0.len
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
fn height(&self) -> usize {
self.0.height
}
fn is_leaf(&self) -> bool {
self.0.height == 0
}
fn interval(&self) -> Interval {
self.0.info.interval(self.0.len)
}
fn get_children(&self) -> &[Node<N>] {
if let NodeVal::Internal(ref v) = self.0.val {
v
} else {
panic!("get_children called on leaf node");
}
}
fn get_leaf(&self) -> &N::L {
if let NodeVal::Leaf(ref l) = self.0.val {
l
} else {
panic!("get_leaf called on internal node");
}
}
fn is_ok_child(&self) -> bool {
match self.0.val {
NodeVal::Leaf(ref l) => l.is_ok_child(),
NodeVal::Internal(ref nodes) => (nodes.len() >= MIN_CHILDREN),
}
}
fn merge_nodes(children1: &[Node<N>], children2: &[Node<N>]) -> Node<N> {
let n_children = children1.len() + children2.len();
if n_children <= MAX_CHILDREN {
Node::from_nodes([children1, children2].concat())
} else {
let splitpoint = min(MAX_CHILDREN, n_children - MIN_CHILDREN);
let mut iter = children1.iter().chain(children2.iter()).cloned();
let left = iter.by_ref().take(splitpoint).collect();
let right = iter.collect();
let parent_nodes = vec![Node::from_nodes(left), Node::from_nodes(right)];
Node::from_nodes(parent_nodes)
}
}
fn merge_leaves(mut rope1: Node<N>, rope2: Node<N>) -> Node<N> {
debug_assert!(rope1.is_leaf() && rope2.is_leaf());
let both_ok = rope1.get_leaf().is_ok_child() && rope2.get_leaf().is_ok_child();
if both_ok {
return Node::from_nodes(vec![rope1, rope2]);
}
match {
let node1 = Arc::make_mut(&mut rope1.0);
let leaf2 = rope2.get_leaf();
if let NodeVal::Leaf(ref mut leaf1) = node1.val {
let leaf2_iv = Interval::new(0, leaf2.len());
let new = leaf1.push_maybe_split(leaf2, leaf2_iv);
node1.len = leaf1.len();
node1.info = N::compute_info(leaf1);
new
} else {
panic!("merge_leaves called on non-leaf");
}
} {
Some(new) => Node::from_nodes(vec![rope1, Node::from_leaf(new)]),
None => rope1,
}
}
pub fn concat(rope1: Node<N>, rope2: Node<N>) -> Node<N> {
use std::cmp::Ordering;
let h1 = rope1.height();
let h2 = rope2.height();
match h1.cmp(&h2) {
Ordering::Less => {
let children2 = rope2.get_children();
if h1 == h2 - 1 && rope1.is_ok_child() {
return Node::merge_nodes(&[rope1], children2);
}
let newrope = Node::concat(rope1, children2[0].clone());
if newrope.height() == h2 - 1 {
Node::merge_nodes(&[newrope], &children2[1..])
} else {
Node::merge_nodes(newrope.get_children(), &children2[1..])
}
}
Ordering::Equal => {
if rope1.is_ok_child() && rope2.is_ok_child() {
return Node::from_nodes(vec![rope1, rope2]);
}
if h1 == 0 {
return Node::merge_leaves(rope1, rope2);
}
Node::merge_nodes(rope1.get_children(), rope2.get_children())
}
Ordering::Greater => {
let children1 = rope1.get_children();
if h2 == h1 - 1 && rope2.is_ok_child() {
return Node::merge_nodes(children1, &[rope2]);
}
let lastix = children1.len() - 1;
let newrope = Node::concat(children1[lastix].clone(), rope2);
if newrope.height() == h1 - 1 {
Node::merge_nodes(&children1[..lastix], &[newrope])
} else {
Node::merge_nodes(&children1[..lastix], newrope.get_children())
}
}
}
}
pub fn measure<M: Metric<N>>(&self) -> usize {
M::measure(&self.0.info, self.0.len)
}
pub(crate) fn push_subseq(&self, b: &mut TreeBuilder<N>, iv: Interval) {
if iv.is_empty() {
return;
}
if iv == self.interval() {
b.push(self.clone());
return;
}
match self.0.val {
NodeVal::Leaf(ref l) => {
b.push_leaf_slice(l, iv);
}
NodeVal::Internal(ref v) => {
let mut offset = 0;
for child in v {
if iv.is_before(offset) {
break;
}
let child_iv = child.interval();
let rec_iv = iv.intersect(child_iv.translate(offset)).translate_neg(offset);
child.push_subseq(b, rec_iv);
offset += child.len();
}
return;
}
}
}
pub fn subseq<T: IntervalBounds>(&self, iv: T) -> Node<N> {
let iv = iv.into_interval(self.len());
let mut b = TreeBuilder::new();
self.push_subseq(&mut b, iv);
b.build()
}
pub fn edit<T, IV>(&mut self, iv: IV, new: T)
where
T: Into<Node<N>>,
IV: IntervalBounds,
{
let mut b = TreeBuilder::new();
let iv = iv.into_interval(self.len());
let self_iv = self.interval();
self.push_subseq(&mut b, self_iv.prefix(iv));
b.push(new.into());
self.push_subseq(&mut b, self_iv.suffix(iv));
*self = b.build();
}
pub fn convert_metrics<M1: Metric<N>, M2: Metric<N>>(&self, mut m1: usize) -> usize {
if m1 == 0 {
return 0;
}
let m1_fudge = if M1::can_fragment() { 1 } else { 0 };
let mut m2 = 0;
let mut node = self;
while node.height() > 0 {
for child in node.get_children() {
let child_m1 = child.measure::<M1>();
if m1 < child_m1 + m1_fudge {
node = child;
break;
}
m2 += child.measure::<M2>();
m1 -= child_m1;
}
}
let l = node.get_leaf();
let base = M1::to_base_units(l, m1);
m2 + M2::from_base_units(l, base)
}
}
impl<N: DefaultMetric> Node<N> {
pub fn count<M: Metric<N>>(&self, offset: usize) -> usize {
self.convert_metrics::<N::DefaultMetric, M>(offset)
}
pub fn count_base_units<M: Metric<N>>(&self, offset: usize) -> usize {
self.convert_metrics::<M, N::DefaultMetric>(offset)
}
}
impl<N: NodeInfo> Default for Node<N> {
fn default() -> Node<N> {
Node::from_leaf(N::L::default())
}
}
pub struct TreeBuilder<N: NodeInfo>(Option<Node<N>>);
impl<N: NodeInfo> TreeBuilder<N> {
pub fn new() -> TreeBuilder<N> {
TreeBuilder(None)
}
pub fn push(&mut self, n: Node<N>) {
match self.0.take() {
None => self.0 = Some(n),
Some(buf) => self.0 = Some(Node::concat(buf, n)),
}
}
pub fn push_leaves(&mut self, leaves: Vec<N::L>) {
let mut stack: Vec<Vec<Node<N>>> = Vec::new();
for leaf in leaves {
let mut new = Node::from_leaf(leaf);
loop {
if stack.last().map_or(true, |r| r[0].height() != new.height()) {
stack.push(Vec::new());
}
stack.last_mut().unwrap().push(new);
if stack.last().unwrap().len() < MAX_CHILDREN {
break;
}
new = Node::from_nodes(stack.pop().unwrap())
}
}
for v in stack {
for r in v {
self.push(r)
}
}
}
pub fn push_leaf(&mut self, l: N::L) {
self.push(Node::from_leaf(l))
}
pub fn push_leaf_slice(&mut self, l: &N::L, iv: Interval) {
self.push(Node::from_leaf(l.subseq(iv)))
}
pub fn build(self) -> Node<N> {
match self.0 {
Some(r) => r,
None => Node::from_leaf(N::L::default()),
}
}
}
const CURSOR_CACHE_SIZE: usize = 4;
pub struct Cursor<'a, N: 'a + NodeInfo> {
root: &'a Node<N>,
position: usize,
cache: [Option<(&'a Node<N>, usize)>; CURSOR_CACHE_SIZE],
leaf: Option<&'a N::L>,
offset_of_leaf: usize,
}
impl<'a, N: NodeInfo> Cursor<'a, N> {
pub fn new(n: &'a Node<N>, position: usize) -> Cursor<'a, N> {
let mut result = Cursor {
root: n,
position,
cache: [None; CURSOR_CACHE_SIZE],
leaf: None,
offset_of_leaf: 0,
};
result.descend();
result
}
pub fn total_len(&self) -> usize {
self.root.len()
}
pub fn root(&self) -> &'a Node<N> {
self.root
}
pub fn get_leaf(&self) -> Option<(&'a N::L, usize)> {
self.leaf.map(|l| (l, self.position - self.offset_of_leaf))
}
pub fn set(&mut self, position: usize) {
self.position = position;
if let Some(l) = self.leaf {
if self.position >= self.offset_of_leaf && self.position < self.offset_of_leaf + l.len()
{
return;
}
}
self.descend();
}
pub fn pos(&self) -> usize {
self.position
}
pub fn is_boundary<M: Metric<N>>(&mut self) -> bool {
if self.leaf.is_none() {
return false;
}
if self.position == self.offset_of_leaf && !M::can_fragment() {
return true;
}
if self.position == 0 || self.position > self.offset_of_leaf {
return M::is_boundary(self.leaf.unwrap(), self.position - self.offset_of_leaf);
}
let l = self.prev_leaf().unwrap().0;
let result = M::is_boundary(l, l.len());
let _ = self.next_leaf();
result
}
pub fn prev<M: Metric<N>>(&mut self) -> Option<(usize)> {
if self.position == 0 || self.leaf.is_none() {
self.leaf = None;
return None;
}
let orig_pos = self.position;
let offset_in_leaf = orig_pos - self.offset_of_leaf;
if offset_in_leaf > 0 {
let l = self.leaf.unwrap();
if let Some(offset_in_leaf) = M::prev(l, offset_in_leaf) {
self.position = self.offset_of_leaf + offset_in_leaf;
return Some(self.position);
}
}
self.prev_leaf()?;
if let Some(offset) = self.last_inside_leaf::<M>(orig_pos) {
return Some(offset);
}
let measure = self.measure_leaf::<M>(self.position);
if measure == 0 {
self.leaf = None;
self.position = 0;
return None;
}
self.descend_metric::<M>(measure);
self.last_inside_leaf::<M>(orig_pos)
}
pub fn next<M: Metric<N>>(&mut self) -> Option<(usize)> {
if self.position >= self.root.len() || self.leaf.is_none() {
self.leaf = None;
return None;
}
if let Some(offset) = self.next_inside_leaf::<M>() {
return Some(offset);
}
self.next_leaf()?;
if let Some(offset) = self.next_inside_leaf::<M>() {
return Some(offset);
}
let measure = self.measure_leaf::<M>(self.position);
self.descend_metric::<M>(measure + 1);
if let Some(offset) = self.next_inside_leaf::<M>() {
return Some(offset);
}
self.position = self.root.len();
self.leaf = None;
None
}
pub fn at_or_next<M: Metric<N>>(&mut self) -> Option<usize> {
if self.is_boundary::<M>() {
Some(self.pos())
} else {
self.next::<M>()
}
}
pub fn at_or_prev<M: Metric<N>>(&mut self) -> Option<usize> {
if self.is_boundary::<M>() {
Some(self.pos())
} else {
self.prev::<M>()
}
}
pub fn iter<'c, M: Metric<N>>(&'c mut self) -> CursorIter<'c, 'a, N, M> {
CursorIter { cursor: self, _metric: PhantomData }
}
#[inline]
fn last_inside_leaf<M: Metric<N>>(&mut self, orig_pos: usize) -> Option<usize> {
let l = self.leaf.expect("inconsistent, shouldn't get here");
let len = l.len();
if self.offset_of_leaf + len < orig_pos && M::is_boundary(l, len) {
let _ = self.next_leaf();
return Some(self.position);
}
let offset_in_leaf = M::prev(l, len)?;
self.position = self.offset_of_leaf + offset_in_leaf;
Some(self.position)
}
#[inline]
fn next_inside_leaf<M: Metric<N>>(&mut self) -> Option<usize> {
let l = self.leaf.expect("inconsistent, shouldn't get here");
let offset_in_leaf = self.position - self.offset_of_leaf;
let offset_in_leaf = M::next(l, offset_in_leaf)?;
if offset_in_leaf == l.len() && self.offset_of_leaf + offset_in_leaf != self.root.len() {
let _ = self.next_leaf();
} else {
self.position = self.offset_of_leaf + offset_in_leaf;
}
Some(self.position)
}
pub fn next_leaf(&mut self) -> Option<(&'a N::L, usize)> {
let leaf = self.leaf?;
self.position = self.offset_of_leaf + leaf.len();
for i in 0..CURSOR_CACHE_SIZE {
if self.cache[i].is_none() {
self.leaf = None;
return None;
}
let (node, j) = self.cache[i].unwrap();
if j + 1 < node.get_children().len() {
self.cache[i] = Some((node, j + 1));
let mut node_down = &node.get_children()[j + 1];
for k in (0..i).rev() {
self.cache[k] = Some((node_down, 0));
node_down = &node_down.get_children()[0];
}
self.leaf = Some(node_down.get_leaf());
self.offset_of_leaf = self.position;
return self.get_leaf();
}
}
if self.offset_of_leaf + self.leaf.unwrap().len() == self.root.len() {
self.leaf = None;
return None;
}
self.descend();
self.get_leaf()
}
pub fn prev_leaf(&mut self) -> Option<(&'a N::L, usize)> {
if self.offset_of_leaf == 0 {
self.leaf = None;
self.position = 0;
return None;
}
for i in 0..CURSOR_CACHE_SIZE {
if self.cache[i].is_none() {
self.leaf = None;
return None;
}
let (node, j) = self.cache[i].unwrap();
if j > 0 {
self.cache[i] = Some((node, j - 1));
let mut node_down = &node.get_children()[j - 1];
for k in (0..i).rev() {
let last_ix = node_down.get_children().len() - 1;
self.cache[k] = Some((node_down, last_ix));
node_down = &node_down.get_children()[last_ix];
}
let leaf = node_down.get_leaf();
self.leaf = Some(leaf);
self.offset_of_leaf -= leaf.len();
self.position = self.offset_of_leaf;
return self.get_leaf();
}
}
self.position = self.offset_of_leaf - 1;
self.descend();
self.position = self.offset_of_leaf;
self.get_leaf()
}
fn descend(&mut self) {
let mut node = self.root;
let mut offset = 0;
while node.height() > 0 {
let children = node.get_children();
let mut i = 0;
loop {
if i + 1 == children.len() {
break;
}
let nextoff = offset + children[i].len();
if nextoff > self.position {
break;
}
offset = nextoff;
i += 1;
}
let cache_ix = node.height() - 1;
if cache_ix < CURSOR_CACHE_SIZE {
self.cache[cache_ix] = Some((node, i));
}
node = &children[i];
}
self.leaf = Some(node.get_leaf());
self.offset_of_leaf = offset;
}
fn measure_leaf<M: Metric<N>>(&self, mut pos: usize) -> usize {
let mut node = self.root;
let mut metric = 0;
while node.height() > 0 {
for child in node.get_children() {
let len = child.len();
if pos < len {
node = child;
break;
}
pos -= len;
metric += child.measure::<M>();
}
}
metric
}
fn descend_metric<M: Metric<N>>(&mut self, mut measure: usize) {
let mut node = self.root;
let mut offset = 0;
while node.height() > 0 {
let children = node.get_children();
let mut i = 0;
loop {
if i + 1 == children.len() {
break;
}
let child = &children[i];
let child_m = child.measure::<M>();
if child_m >= measure {
break;
}
offset += child.len();
measure -= child_m;
i += 1;
}
let cache_ix = node.height() - 1;
if cache_ix < CURSOR_CACHE_SIZE {
self.cache[cache_ix] = Some((node, i));
}
node = &children[i];
}
self.leaf = Some(node.get_leaf());
self.position = offset;
self.offset_of_leaf = offset;
}
}
pub struct CursorIter<'c, 'a: 'c, N: 'a + NodeInfo, M: 'a + Metric<N>> {
cursor: &'c mut Cursor<'a, N>,
_metric: PhantomData<&'a M>,
}
impl<'c, 'a, N: NodeInfo, M: Metric<N>> Iterator for CursorIter<'c, 'a, N, M> {
type Item = usize;
fn next(&mut self) -> Option<usize> {
self.cursor.next::<M>()
}
}
impl<'c, 'a, N: NodeInfo, M: Metric<N>> CursorIter<'c, 'a, N, M> {
pub fn pos(&self) -> usize {
self.cursor.pos()
}
}
#[cfg(test)]
mod test {
use super::*;
use crate::rope::*;
fn build_triangle(n: u32) -> String {
let mut s = String::new();
let mut line = String::new();
for _ in 0..n {
s += &line;
s += "\n";
line += "a";
}
s
}
#[test]
fn eq_rope_with_stack() {
let n = 2_000;
let s = build_triangle(n);
let mut builder_default = TreeBuilder::new();
let mut builder_stacked = TreeBuilder::new();
builder_default.push_str(&s);
builder_stacked.push_str_stacked(&s);
let tree_default = builder_default.build();
let tree_stacked = builder_stacked.build();
assert_eq!(tree_default, tree_stacked);
}
#[test]
fn cursor_next_triangle() {
let n = 2_000;
let text = Rope::from(build_triangle(n));
let mut cursor = Cursor::new(&text, 0);
let mut prev_offset = cursor.pos();
for i in 1..(n + 1) as usize {
let offset = cursor.next::<LinesMetric>().expect("arrived at the end too soon");
assert_eq!(offset - prev_offset, i);
prev_offset = offset;
}
assert_eq!(cursor.next::<LinesMetric>(), None);
}
#[test]
fn node_is_empty() {
let text = Rope::from(String::new());
assert_eq!(text.is_empty(), true);
}
#[test]
fn cursor_next_empty() {
let text = Rope::from(String::new());
let mut cursor = Cursor::new(&text, 0);
assert_eq!(cursor.next::<LinesMetric>(), None);
assert_eq!(cursor.pos(), 0);
}
#[test]
fn cursor_iter() {
let text: Rope = build_triangle(50).into();
let mut cursor = Cursor::new(&text, 0);
let mut manual = Vec::new();
while let Some(nxt) = cursor.next::<LinesMetric>() {
manual.push(nxt);
}
cursor.set(0);
let auto = cursor.iter::<LinesMetric>().collect::<Vec<_>>();
assert_eq!(manual, auto);
}
#[test]
fn cursor_next_misc() {
cursor_next_for("toto");
cursor_next_for("toto\n");
cursor_next_for("toto\ntata");
cursor_next_for("歴史\n科学的");
cursor_next_for("\n歴史\n科学的\n");
cursor_next_for(&build_triangle(100));
}
fn cursor_next_for(s: &str) {
let r = Rope::from(s.to_owned());
for i in 0..r.len() {
let mut c = Cursor::new(&r, i);
let it = c.next::<LinesMetric>();
let pos = c.pos();
assert!(s.as_bytes()[i..pos - 1].iter().all(|c| *c != b'\n'), "missed linebreak");
if pos < s.len() {
assert!(it.is_some(), "must be Some(_)");
assert!(s.as_bytes()[pos - 1] == b'\n', "not a linebreak");
} else {
if s.as_bytes()[s.len() - 1] == b'\n' {
assert!(it.is_some(), "must be Some(_)");
} else {
assert!(it.is_none());
assert!(c.get_leaf().is_none());
}
}
}
}
#[test]
fn cursor_prev_misc() {
cursor_prev_for("toto");
cursor_prev_for("a\na\n");
cursor_prev_for("toto\n");
cursor_prev_for("toto\ntata");
cursor_prev_for("歴史\n科学的");
cursor_prev_for("\n歴史\n科学的\n");
cursor_prev_for(&build_triangle(100));
}
fn cursor_prev_for(s: &str) {
let r = Rope::from(s.to_owned());
for i in 0..r.len() {
let mut c = Cursor::new(&r, i);
let it = c.prev::<LinesMetric>();
let pos = c.pos();
assert!(
s.as_bytes()[pos..i].iter().filter(|c| **c == b'\n').count() <= 1,
"missed linebreak"
);
if i == 0 && s.as_bytes()[i] == b'\n' {
assert_eq!(pos, 0);
}
if pos > 0 {
assert!(it.is_some(), "must be Some(_)");
assert!(s.as_bytes()[pos - 1] == b'\n', "not a linebreak");
}
}
}
#[test]
fn at_or_next() {
let text: Rope = "this\nis\nalil\nstring".into();
let mut cursor = Cursor::new(&text, 0);
assert_eq!(cursor.at_or_next::<LinesMetric>(), Some(5));
assert_eq!(cursor.at_or_next::<LinesMetric>(), Some(5));
cursor.set(1);
assert_eq!(cursor.at_or_next::<LinesMetric>(), Some(5));
assert_eq!(cursor.at_or_prev::<LinesMetric>(), Some(5));
cursor.set(6);
assert_eq!(cursor.at_or_prev::<LinesMetric>(), Some(5));
cursor.set(6);
assert_eq!(cursor.at_or_next::<LinesMetric>(), Some(8));
assert_eq!(cursor.at_or_next::<LinesMetric>(), Some(8));
}
#[test]
fn next_zero_measure_large() {
let mut text = Rope::from("a");
for _ in 0..24 {
text = Node::concat(text.clone(), text);
let mut cursor = Cursor::new(&text, 0);
assert_eq!(cursor.next::<LinesMetric>(), None);
assert_eq!(cursor.get_leaf(), None);
assert_eq!(cursor.pos(), text.len());
cursor.set(text.len());
assert_eq!(cursor.prev::<LinesMetric>(), None);
assert_eq!(cursor.get_leaf(), None);
assert_eq!(cursor.pos(), 0);
}
}
#[test]
fn prev_line_large() {
let s: String = format!("{}{}", "\n", build_triangle(1000));
let rope = Rope::from(s);
let mut expected_pos = rope.len();
let mut cursor = Cursor::new(&rope, rope.len());
for i in (1..1001).rev() {
expected_pos = expected_pos - i;
assert_eq!(expected_pos, cursor.prev::<LinesMetric>().unwrap());
}
assert_eq!(None, cursor.prev::<LinesMetric>());
}
#[test]
fn prev_line_small() {
let empty_rope = Rope::from("\n");
let mut cursor = Cursor::new(&empty_rope, empty_rope.len());
assert_eq!(None, cursor.prev::<LinesMetric>());
let rope = Rope::from("\n\n\n\n\n\n\n\n\n\n");
cursor = Cursor::new(&rope, rope.len());
let mut expected_pos = rope.len();
for _ in (1..10).rev() {
expected_pos -= 1;
assert_eq!(expected_pos, cursor.prev::<LinesMetric>().unwrap());
}
assert_eq!(None, cursor.prev::<LinesMetric>());
}
}