//! # An rope.
//!
//! An immutable Rope data structure for storing large text documents. This
//! implementation is a component of the [`an-editor`]
//! project.
//!
//! A rope is an efficient data structure for large strings. It's
//! essentially a binary tree whose leaves are strings.
//!
//! For more information, see the following resources:
//!
//! + http://scienceblogs.com/goodmath/2009/01/26/ropes-twining-together-strings/
//! + https://www.ibm.com/developerworks/library/j-ropes/
//! + http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf
//! [`an-editor`]: https://github.com/an-cabal/an-editor
#![cfg_attr( feature = "unstable"
, feature( const_fn
, box_syntax, box_patterns
, conservative_impl_trait
, collections, collections_range
, inclusive_range_syntax
))]
#![cfg_attr( all( test, feature = "unstable")
, feature( test, insert_str) )]
#![cfg_attr( feature = "clippy", feature(plugin) )]
#![cfg_attr( feature = "clippy", plugin(clippy) )]
#![cfg_attr( feature = "clippy", allow(unused_variables, dead_code))]
#[macro_use] extern crate macro_attr;
#[macro_use] extern crate newtype_derive;
#[cfg(feature = "unstable")] extern crate collections;
#[cfg(feature = "unstable")] use collections::range::RangeArgument;
extern crate unicode_segmentation;
use std::cmp;
use std::ops;
use std::convert;
use std::fmt;
use std::string;
use std::iter;
macro_rules! or_zero {
($a: expr, $b: expr) => { if $a > $b { $a - $b } else { 0 } }
}
#[cfg(feature = "tendril")] extern crate tendril;
#[cfg(test)] #[macro_use] extern crate quickcheck;
#[cfg(test)] mod test;
#[cfg(all( test, feature = "unstable"))] mod bench;
mod unicode;
pub mod metric;
use metric::{Measured, Metric};
use self::internals::{Node, NodeLink};
pub use self::slice::{ RopeSlice
//, RopeSliceMut
};
impl<T> convert::From<T> for Rope
where T: convert::Into<NodeLink> {
#[inline] fn from(that: T) -> Self {
Rope { root: that.into().rebalance() }
}
}
/// A Rope
///
/// This Rope implementation aims to eventually function as a superset of
/// [`String`](https://doc.rust-lang.org/1.3.0/std/string/struct.String.html),
/// providing the same API plus additional methods. Therefore, code which uses
/// `String` can easily be ported to use `Rope`.
///
/// `Rope` provides two APIs for editing a `Rope`: a destructive,
/// append-in-place API whose methods match those of `String`, and a
/// non-destructive, persistant API. The persistant API's methods have names
/// prefixed with ``, such as `push()` and `append()`.
///
#[derive(Clone, Default)]
pub struct Rope {
// can we get away with having these be of &str or will they need
// to be string?
root: NodeLink
}
pub trait Split: Sized {
fn split<M>(&self, index: M) -> (Self,Self)
where M: Metric
, Self: Measured<M>;
}
impl<M> Measured<M> for Rope
where M: Metric
, NodeLink: Measured<M>
, String: Measured<M>
{
#[inline] fn to_byte_index(&self, index: M) -> Option<usize> {
self.root.to_byte_index(index)
}
#[inline] fn measure(&self) -> M { self.root.measure() }
#[inline] fn measure_weight(&self) -> M { self.root.measure_weight() }
}
impl fmt::Debug for Rope {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Rope[\"{}\"] {:?}", self.root, self.root)
}
}
impl fmt::Display for Rope {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.root)
}
}
#[cfg(feature = "unstable")]
macro_rules! unstable_iters {
( $($(#[$attr:meta])*
pub fn $name:ident$(<$lf:tt>)*(&'a $sel:ident) -> $ty:ty {
$body:expr
})+ ) => { $(
$(#[$attr])*
#[cfg_attr(feature = "clippy", allow(needless_lifetimes))]
pub fn $name$(<$lf>)*(&'a $sel) -> $ty {
$body
}
)+ };
( $($(#[$attr:meta])*
pub fn $name:ident$(<$lf:tt>)*(&'a mut $sel:ident) -> $ty:ty {
$body:expr
})+ ) => { $(
$(#[$attr])*
#[cfg(feature = "unstable")]
#[cfg_attr(feature = "clippy", allow(needless_lifetimes))]
pub fn $name$(<$lf>)*(&'a mut $sel) -> $ty {
$body
}
)+ };
}
#[cfg(not(feature = "unstable"))]
macro_rules! unstable_iters {
( $($(#[$attr:meta])*
pub fn $name:ident$(<$lf:tt>)*(&'a $sel:ident) -> impl Iterator<Item=$ty:ty> + 'a {
$body:expr
})+ ) => ($(
$(#[$attr])*
#[cfg(not(feature = "unstable"))]
#[cfg_attr(feature = "clippy", allow(needless_lifetimes))]
pub fn $name$(<$lf>)*(&'a $sel) -> Box<Iterator<Item=$ty> + 'a> {
Box::new($body)
}
)+);
( $( $(#[$attr:meta])*
pub fn $name:ident$(<$lf:tt>)*(&'a mut $sel:ident) - impl Iterator<Item=$ty:ty> + 'a {
$body:expr
})+ ) => { $({
$(#[$attr])*
#[cfg(not(feature = "unstable"))]
#[cfg_attr(feature = "clippy", allow(needless_lifetimes))]
pub fn $name$(<$lf>)*(&'a mut $sel) -> Box<Iterator<Item=$ty> + 'a> {
Box::new($body)
}
})+
};
}
macro_rules! str_iters {
( $($(#[$attr:meta])* impl $name: ident<$ty: ty> for Node {})+ ) => { $(
unstable_iters! {
$(#[$attr])*
pub fn $name<'a>(&'a self) -> impl Iterator<Item=$ty> + 'a{
self.strings().flat_map(str::$name)
}
}
)+ };
( $($(#[$attr:meta])* impl $name: ident<$ty: ty> for Rope {})+ )=> { $(
unstable_iters! {
$(#[$attr])*
pub fn $name<'a>(&'a self) -> impl Iterator<Item=$ty> + 'a{
self.root.$name()
}
}
)+ }
}
macro_rules! unicode_seg_iters {
( $($(#[$attr:meta])* impl $name: ident for Node { extend })+ ) => { $(
unstable_iters! {
$(#[$attr])*
pub fn $name<'a>(&'a self) -> impl Iterator<Item=&'a str> + 'a {
{ // this block is required so that the macro will bind the
// `use` statement
use unicode_segmentation::UnicodeSegmentation;
self.strings()
.flat_map(|s| UnicodeSegmentation::$name(s, true))
}
}
}
)+ };
( $($(#[$attr:meta])* impl $name: ident for Node {} )+ ) => { $(
unstable_iters!{
$(#[$attr])*
pub fn $name<'a>(&'a self) -> impl Iterator<Item=&'a str> + 'a {
{ // this block is required so that the macro will bind the
// `use` statement
use unicode_segmentation::UnicodeSegmentation;
self.strings().flat_map(UnicodeSegmentation::$name)
}
}
}
)+ };
( $($(#[$attr:meta])* impl $name: ident<$ty: ty> for Rope {})+ )=> { $(
unstable_iters! {
$(#[$attr])*
pub fn $name<'a>(&'a self) -> impl Iterator<Item=$ty> + 'a {
self.root.$name()
}
}
)+ }
}
mod internals;
mod slice;
impl Rope {
/// Converts a vector of bytes to a `Rope`.
///
/// If you are sure that the byte slice is valid UTF-8, and you don't want
/// to incur the overhead of the validity check, there is an unsafe version
/// of this function, `from_utf8_unchecked(),`` which has the same behavior
/// but skips the check.
///
/// This method will take care to not copy the vector, for efficiency's
/// sake.
///
/// # Errors
///
/// Returns `Err` if the slice is not UTF-8 with a description as to why the
/// provided bytes are not UTF-8. The vector you moved in is also included.
///
/// # Examples
///
/// Basic usage:
///
/// ```
/// use an_rope::Rope;
///
/// // some bytes, in a vector
/// let sparkle_heart = vec![240, 159, 146, 150];
///
/// // We know these bytes are valid, so we'll use `unwrap()`.
/// let sparkle_heart = Rope::from_utf8(sparkle_heart).unwrap();
///
/// assert_eq!(&sparkle_heart, "💖");
/// ```
///
/// Incorrect bytes:
///
/// ```
/// use an_rope::Rope;
///
/// // some invalid bytes, in a vector
/// let sparkle_heart = vec![0, 159, 146, 150];
///
/// assert!(Rope::from_utf8(sparkle_heart).is_err());
/// ```
///
#[inline]
pub fn from_utf8(vec: Vec<u8>) -> Result<Rope, string::FromUtf8Error> {
String::from_utf8(vec).map(Rope::from)
}
/// Decode a UTF-16 encoded vector `v` into a `Rope`,
/// returning `Err` if `v` contains any invalid data.
#[inline]
pub fn from_utf16(v: &[u16]) -> Result<Rope, string::FromUtf16Error> {
String::from_utf16(v).map(Rope::from)
}
/// Converts a vector of bytes to a `Rope` without checking that the
/// vector contains valid UTF-8.
///
/// See the safe version, [`from_utf8()`], for more details.
///
/// [`from_utf8()`]: struct.Rope.html#method.from_utf8
///
/// # Safety
///
/// This function is unsafe because it does not check that the bytes passed
/// to it are valid UTF-8. If this constraint is violated, it may cause
/// memory unsafety issues with future users of the `Rope`, as the rest of
/// the standard library assumes that `Rope`s are valid UTF-8.
///
/// # Examples
///
/// Basic usage:
///
/// ```
/// use an_rope::Rope;
///
/// // some bytes, in a vector
/// let sparkle_heart = vec![240, 159, 146, 150];
///
/// let sparkle_heart = unsafe {
/// Rope::from_utf8_unchecked(sparkle_heart)
/// };
///
/// assert_eq!(&sparkle_heart, "💖");
/// ```
#[inline]
pub unsafe fn from_utf8_unchecked(bytes: Vec<u8>) -> Rope {
Rope::from(String::from_utf8_unchecked(bytes))
}
/// Returns a new empty Rope
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let mut an_rope = Rope::new();
/// assert_eq!(an_rope.len(), 0);
/// ```
#[inline] pub fn new() -> Rope { Rope::from(Node::empty()) }
/// Returns the length of this Rope
///
/// # Examples
///
/// An empty `Rope` should have length 0.
///
/// ```
/// use an_rope::Rope;
/// let mut an_empty_rope = Rope::new();
/// assert_eq!(an_empty_rope.len(), 0);
/// ```
///
/// ```
/// use an_rope::Rope;
/// let mut an_empty_rope = Rope::from(String::from(""));
/// assert_eq!(an_empty_rope.len(), 0);
/// ```
///
/// A `Rope` with text should have length equal to the number of
/// characters in the `Rope`.
///
/// ```
/// use an_rope::Rope;
/// let mut an_rope = Rope::from(String::from("a string"));
/// assert_eq!(an_rope.len(), "a string".len());
/// ```
pub fn len(&self) -> usize { self.root.len() }
/// Returns `true` if this `Rope` is empty.
///
/// # Examples
///
/// A `Rope` with no characters should be empty:
///
/// ```
/// use an_rope::Rope;
/// let an_empty_rope = Rope::new();
/// assert!(an_empty_rope.is_empty());
/// ```
///
/// ```
/// use an_rope::Rope;
/// let an_empty_rope = Rope::from(String::from(""));
/// assert!(an_empty_rope.is_empty());
/// ```
///
/// A `Rope` with characters should not be empty:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("a string");
/// assert!(!an_rope.is_empty());
/// ```
#[inline] pub fn is_empty(&self) -> bool { self.len() == 0 }
/// Insert `ch` into `index` in this `Rope`, returning a new `Rope`.
///
///
/// # Returns
/// * A new `Rope` with `ch` inserted at `index`
///
/// # Time Complexity
/// O(log _n_)
///
/// # Panics
/// * If `index` is greater than the length of this `Rope`
///
/// # Examples
///
/// Inserting at index 0 prepends `rope` to this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("bcd");
/// let new_rope = an_rope.insert(0, 'a');
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("bcd"));
/// ```
///
/// Inserting at index `len` prepends `char` to this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("abc");
/// let new_rope = an_rope.insert(an_rope.len(), 'd');
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("abc"));
/// ```
///
/// Inserting at an index in the middle inserts `char` at that index:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("acd");
/// let new_rope = an_rope.insert(1, 'b');
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("acd"));
/// ```
#[inline]
#[inline]
pub fn insert<M>(&self, index: M, ch: char) -> Rope
where M: Metric
, Self: Measured<M>
, NodeLink: Measured<M>
, String: Measured<M>
, str: Measured<M>
{
assert!( index <= self.measure()
, "Rope::insert: index {:?} was > length {:?}"
, index, self.measure());
// TODO: this is gross...
let mut s = String::new();
s.push(ch);
self.insert_rope(index, &Rope::from(s))
}
/// Delete the range `range` from this `Rope`,
///
/// # Panics
/// * If the start or end of `range` are indices outside of the `Rope`
/// * If the end index of `range` is greater than the start index
///
/// # Time Complexity
/// O(log _n_)
///
/// # Examples
///
/// Deleting "not" from this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("this is not fine".to_string());
/// let an_rope = an_rope.delete((8..12));
/// assert_eq!(&an_rope, "this is fine");
/// ```
#[inline]
#[cfg(feature = "unstable")]
pub fn delete<R, M>(&self, range: R) -> Rope
where R: RangeArgument<M>
, M: Metric
, Rope: Measured<M>
, NodeLink: Measured<M>
, String: Measured<M>
, str: Measured<M>
{
let start = range.start().map(|s| *s)
.unwrap_or_else(|| { M::default() });
let end = range.end().map(|e| *e)
.unwrap_or_else(|| { self.measure() });
assert!( start <= end
, "invalid index! start {:?} > end {:?}", end, start);
let (l, r) = self.root.split(start);
let (_, r) = r.split(end - start);
Rope::from(Node::new_branch(l, r))
}
#[inline]
#[cfg(not(feature = "unstable"))]
pub fn delete<M: Metric>(&self, range: ops::Range<M>) -> Rope
where NodeLink: Measured<M>
, String: Measured<M>
, str: Measured<M>
{
let (l, r) = self.root.split(range.start);
let (_, r) = r.split(range.end - range.start);
Rope::from(Node::new_branch(l, r))
}
/// Insert `rope` into `index` in this `Rope`, returning a new `Rope`.
///
/// # Returns
/// * A new `Rope` with `rope` inserted at `index`
///
/// # Time Complexity
/// O(log _n_)
///
/// # Panics
/// * If `index` is greater than the length of this `Rope`
///
/// # Examples
///
/// Inserting at index 0 prepends `rope` to this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("cd");
/// let new_rope = an_rope.insert_rope(0, &Rope::from("ab"));
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("cd"));
/// ```
///
/// Inserting at index `len` prepends `rope` to this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("ab");
/// let new_rope = an_rope.insert_rope(an_rope.len(), &Rope::from("cd"));
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("ab"));
/// ```
///
/// Inserting at an index in the middle inserts `rope` at that index:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("ad");
/// let new_rope = an_rope.insert_rope(1, &Rope::from("bc"));
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("ad"))
/// ```
#[inline]
pub fn insert_rope<M>(&self, index: M, rope: &Rope) -> Rope
where M: Metric
, Self: Measured<M>
, NodeLink: Measured<M>
, String: Measured<M>
, str: Measured<M>
{
if !rope.is_empty() {
let len = self.measure();
if index.into() == 0 {
// if the rope is being inserted at index 0, just prepend it
self.prepend(rope)
} else if index == len {
// if the rope is being inserted at index len, append it
self.append(rope)
} else {
// split the rope at the given index
let (left, right) = self.root.split(index);
// construct the new root node with `Rope` inserted
// rebalance the new rope
Rope::from(&left + &rope.root + right)
}
} else {
self.clone()
}
}
/// Insert `s` into `index` in this `Rope`, returning a new `Rope`.
///
/// # Returns
/// * A new `Rope` with `s` inserted at `index`
///
/// # Panics
/// * If `index` is greater than the length of this `Rope`
///
/// # Time Complexity
/// O(log _n_)
///
/// # Examples
///
/// Inserting at index 0 prepends `s` to this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("cd");
/// let an_rope = an_rope.insert_str(0, "ab");
/// assert_eq!(an_rope, Rope::from("abcd"));
/// ```
///
/// Inserting at index `len` prepends `s` to this `Rope`:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("ab");
/// let new_rope = an_rope.insert_str(an_rope.len(), "cd");
/// assert_eq!(new_rope, Rope::from("abcd"));
/// assert_eq!(an_rope, Rope::from("ab"));
/// ```
///
/// Inserting at an index in the middle inserts `s` at that index:
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("ad");
/// let new_rope = an_rope.insert_str(1, "bc");
/// assert_eq!(an_rope, Rope::from("ad"));
/// assert_eq!(new_rope, Rope::from("abcd"));
/// ```
#[inline]
pub fn insert_str<M>(&self, index: M, s: &str) -> Rope
where M: Metric
, Self: Measured<M>
, NodeLink: Measured<M>
, String: Measured<M>
, str: Measured<M>
{
assert!( index <= self.measure()
, "Rope::insert_str: index {:?} was > length {:?}"
, index, self.measure());
self.insert_rope(index, &s.into())
}
/// Appends a `Rope` to the end of this `Rope`, returning a new `Rope`
///
/// Note that this is equivalent to using the `+` operator.
///
/// # Examples
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("abcd");
/// let another_rope = an_rope.append(&Rope::from("efgh"));
/// assert_eq!(&another_rope, "abcdefgh");
/// assert_eq!(&an_rope, "abcd");
/// ```
pub fn append(&self, other: &Rope) -> Rope {
if !other.is_empty() {
Rope::from(&self.root + &other.root)
} else {
self.clone()
}
}
/// Prepends a `Rope` to the end of this `Rope`, returning a new `Rope`
///
/// # Examples
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("efgh");
/// let another_rope = an_rope.prepend(&Rope::from("abcd"));
/// assert_eq!(&an_rope, "efgh");
/// assert_eq!(&another_rope, "abcdefgh");
/// ```
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("");
/// let another_rope = an_rope.prepend(&Rope::from("abcd"));
/// assert_eq!(&an_rope, "");
/// assert_eq!(&another_rope, "abcd");
/// ```
///
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from("abcd");
/// let another_rope = an_rope.prepend(&Rope::from(""));
/// assert_eq!(&an_rope, "abcd");
/// assert_eq!(&another_rope, &an_rope);
/// assert_eq!(&another_rope, "abcd");
/// ```
pub fn prepend(&self, other: &Rope) -> Rope {
if !other.is_empty() {
Rope::from(&other.root + &self.root)
} else {
self.clone()
}
}
/// Splits the rope into two ropes at the given index.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from(String::from("abcd"));
/// let (ab, cd) = an_rope.split(2);
/// assert_eq!(ab, Rope::from(String::from("ab")));
/// assert_eq!(cd, Rope::from(String::from("cd")));
/// ```
pub fn split<M: Metric>(&self, index: M) -> (Rope, Rope)
where Self: Measured<M>
, NodeLink: Measured<M>
, String: Measured<M>
, str: Measured<M>
{
assert!(index <= self.measure());
let (l, r) = self.root.split(index);
(Rope::from(l), Rope::from(r))
}
/// Rebalances this entire `Rope`, returning a balanced `Rope`.
#[inline]
#[cfg(any(test, feature = "rebalance"))]
fn rebalance(&mut self) {
if self.is_balanced() {
// the rope is already balanced, do nothing
} else {
// rebalance the rope
// self.root = self.root.rebalance();
}
}
/// Returns true if this `Rope` is balanced.
///
/// Balancing invariant:
/// the rope length needs to be less than _F_(rope_length) where F is fibonacci
#[inline]
#[cfg(any(test, feature = "rebalance"))]
fn is_balanced(&self) -> bool {
self.root.is_balanced()
}
unstable_iters! {
#[doc="Returns an iterator over all the strings in this `Rope`"]
#[inline]
pub fn strings<'a>(&'a self) -> impl Iterator<Item=&'a str> + 'a {
self.root.strings()
}
#[doc="Returns an iterator over all the lines of text in this `Rope`."]
pub fn lines<'a>(&'a self) -> impl Iterator<Item=RopeSlice<'a>> +'a {
{ // create a new block here so the macro will bind the `use` stmt
use internals::IsLineEnding;
let last_idx = self.len() - 1;
Box::new(self.char_indices()
.filter_map(move |(i, c)|
if c.is_line_ending() { Some(i) }
// special case: slice to the end of the rope
// even if it doesn't end in a newline character
else if i == last_idx { Some(i + 1) }
else { None })
.scan(0, move |mut l, i| {
let last = *l;
*l = i + 1;
Some(self.slice(last..i))
}))
}
}
}
//
//
// /// Returns a move iterator over all the strings in this `Rope`
// ///
// /// Consumes `self`.
// #[cfg(feature = "unstable")]
// #[inline]
// pub fn into_strings<'a>(self) -> impl Iterator<Item=String> + 'a {
// self.root.into_strings()
// }
//
// /// Returns a move iterator over all the strings in this `Rope`
// ///
// /// Consumes `self`.
// #[cfg(not(feature = "unstable"))]
// #[inline]
// pub fn into_strings<'a>(self) -> Box<Iterator<Item=String> + 'a> {
// self.root.into_strings()
// }
str_iters! {
#[doc="Returns an iterator over all the bytes in this `Rope`.\n\
\nAs a Rope consists of a sequence of bytes, we can iterate \
through a rope by byte. This method returns such an iterator."]
#[inline]
impl bytes<u8> for Rope {}
#[doc="Returns an iterator over all the characters in this `Rope`.\n\
\nAs a `Rope` consists of valid UTF-8, we can iterate through a \
`Rope` by `char`. This method returns such an iterator. \n\
\nIt's important to remember that `char` represents a Unicode \
Scalar Value, and may not match your idea of what a \
'character' is. Iteration over grapheme clusters may be what \
you actually want."]
#[inline]
impl chars<char> for Rope {}
#[inline]
impl char_indices<(usize, char)> for Rope {}
#[inline]
impl split_whitespace<&'a str> for Rope {}
// #[inline]
// impl lines<&'a str> for Rope {}
}
unicode_seg_iters! {
#[doc=
"Returns an iterator over the [grapheme clusters][graphemes] of \
`self`.\n\
[graphemes]: \
http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries\
\n\
The iterator is over the *extended grapheme clusters*; as \
[UAX#29]\
(http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries)\
recommends extended grapheme cluster boundaries for general \
processing."]
#[inline]
impl graphemes<&'a str> for Rope {}
#[doc=
"Returns an iterator over the words of `self`, separated on \
[UAX#29 word boundaries]\
(http://www.unicode.org/reports/tr29/#Word_Boundaries).\n\n\
Here, \"words\" are just those substrings which, after splitting on\
UAX#29 word boundaries, contain any alphanumeric characters. That \
is, the substring must contain at least one character with the \
[Alphabetic](http://unicode.org/reports/tr44/#Alphabetic) \
property, or with [General_Category=Number]\
(http://unicode.org/reports/tr44/#General_Category_Values)."]
#[inline]
impl unicode_words<&'a str> for Rope {}
#[doc=
"Returns an iterator over substrings of `self` separated on \
[UAX#29 word boundaries]\
(http://www.unicode.org/reports/tr29/#Word_Boundaries). \n\n\
The concatenation of the substrings returned by this function is \
just the original string."]
#[inline]
impl split_word_bounds<&'a str> for Rope {}
// #[inline]
// impl grapheme_indices<(usize, &'a str)> for Rope {}
// #[inline]
// impl split_word_bound_indices<(usize, &'a str)> for Rope {}
}
/// Returns an iterator over the grapheme clusters of `self` and their
/// byte offsets. See `graphemes()` for more information.
///
/// # Examples
///
/// ```
/// # use an_rope::Rope;
/// let rope = Rope::from("a̐éö̲\r\n");
/// let gr_inds = rope.grapheme_indices()
/// .collect::<Vec<(usize, &str)>>();
/// let b: &[_] = &[(0, "a̐"), (3, "é"), (6, "ö̲"), (11, "\r\n")];
///
/// assert_eq!(&gr_inds[..], b);
/// ```
#[inline]
pub fn grapheme_indices(&self) -> internals::GraphemeIndices {
self.root.grapheme_indices()
}
/// Returns an iterator over substrings of `self`, split on UAX#29 word
/// boundaries, and their offsets. See `split_word_bounds()` for more
/// information.
///
/// # Example
///
/// ```
/// # use an_rope::Rope;
/// let rope = Rope::from("Brr, it's 29.3°F!");
/// let swi1 = rope.split_word_bound_indices()
/// .collect::<Vec<(usize, &str)>>();
/// let b: &[_] = &[ (0, "Brr"), (3, ","), (4, " "), (5, "it's")
/// , (9, " "), (10, "29.3"), (14, "°"), (16, "F")
/// , (17, "!")];
///
/// assert_eq!(&swi1[..], b);
/// ```
#[inline]
pub fn split_word_bound_indices(&self) -> internals::UWordBoundIndices {
self.root.split_word_bound_indices()
}
/// Returns true if the bytes in `self` equal the bytes in `other`
#[inline]
fn bytes_eq<I>(&self, other: I) -> bool
where I: Iterator<Item=u8> {
self.bytes().zip(other).all(|(a, b)| a == b)
}
/// Returns an immutable slice of this `Rope` between the given indices.
///
/// # Arguments
/// + `range`: A [`RangeArgument`](https://doc.rust-lang.org/nightly/collections/range/trait.RangeArgument.html)
/// specifying the range to slice. This can be produced by range syntax
/// like `..`, `a..`, `..b` or `c..d`.
///
/// # Panics
/// If the start or end indices of the range to slice exceed the length of
/// this `Rope`.
///
/// # Examples
/// ```ignore
// this doctest fails to link on my macbook for Secret Reasons.
// i'd really like to know why...
// - eliza, 12/23/2016
/// #![feature(collections)]
/// #![feature(collections_range)]
///
/// extern crate collections;
/// extern crate an_rope;
/// # fn main() {
/// use collections::range::RangeArgument;
/// use an_rope::Rope;
///
/// let rope = Rope::from("this is an example string");
/// assert_eq!(&rope.slice(4..6), "is");
/// # }
/// ```
#[inline]
#[cfg(feature = "unstable")]
pub fn slice<R>(&self, range: R) -> RopeSlice
where R: RangeArgument<usize> {
RopeSlice::new(&self.root, range)
}
#[cfg(not(feature = "unstable"))]
pub fn slice(&self, range: ops::Range<usize>) -> RopeSlice {
RopeSlice::new(&self.root, range)
}
}
impl convert::Into<Vec<u8>> for Rope {
fn into(self) -> Vec<u8> {
unimplemented!()
}
}
//-- comparisons ----------------------------------------------------
impl cmp::Eq for Rope {}
impl cmp::PartialEq for Rope {
/// A rope equals another rope if all the bytes in both are equal.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// assert!(Rope::from("abcd") == Rope::from("abcd"));
/// ```
/// ```
/// use an_rope::Rope;
/// assert!(Rope::from("abcd") != Rope::from("ab"));
/// ```
/// ```
/// use an_rope::Rope;
/// assert!(Rope::from("abcd") != Rope::from("dcab"))
/// ```
#[inline]
fn eq(&self, other: &Rope) -> bool {
if self.len() == other.len() {
self.bytes_eq(other.bytes())
} else {
false
}
}
}
impl cmp::PartialEq<str> for Rope {
/// A rope equals a string if all the bytes in the string equal the rope's.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// assert!(&Rope::from("abcd") == "abcd");
/// ```
/// ```
/// use an_rope::Rope;
/// assert!(&Rope::from("abcd") != "ab");
/// ```
/// ```
/// use an_rope::Rope;
/// assert!(&Rope::from("abcd") != "dcab");
/// ```
#[inline]
fn eq(&self, other: &str) -> bool {
if self.len() == other.len() {
self.bytes_eq(other.bytes())
} else {
false
}
}
}
impl cmp::PartialEq<String> for Rope {
/// A rope equals a string if all the bytes in the string equal the rope's.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// assert!(Rope::from("abcd") == String::from("abcd"));
/// ```
/// ```
/// use an_rope::Rope;
/// assert!(Rope::from("abcd") != String::from("ab"));
/// ```
/// ```
/// use an_rope::Rope;
/// assert!(Rope::from("abcd") != String::from("dcab"));
/// ```
#[inline]
fn eq(&self, other: &String) -> bool {
if self.len() == other.len() {
self.bytes_eq(other.bytes())
} else {
false
}
}
}
//-- concatenation --------------------------------------------------
impl<'a> ops::Add for &'a Rope {
type Output = Rope;
/// Non-destructively concatenate two `Rope`s, returning a new `Rope`.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let rope = Rope::from(String::from("ab"));
/// assert_eq!( &rope + &Rope::from(String::from("cd"))
/// , Rope::from(String::from("abcd")) );
/// ```
#[inline] fn add(self, other: Self) -> Rope { self.append(other) }
}
impl ops::Add for Rope {
type Output = Rope;
/// Non-destructively concatenate two `Rope`s, returning a new `Rope`.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let rope = Rope::from(String::from("ab"));
/// assert_eq!( rope + Rope::from(String::from("cd"))
/// , Rope::from(String::from("abcd")) );
/// ```
#[inline] fn add(self, other: Self) -> Rope { self.append(&other) }
}
impl ops::Add<String> for Rope {
type Output = Rope;
/// Non-destructively concatenate a `Rope` and a `String`.
///
/// Returns a new `Rope`
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let rope = Rope::from(String::from("ab"));
/// assert_eq!( rope + String::from("cd")
/// , Rope::from(String::from("abcd")));
/// ```
#[inline] fn add(self, other: String) -> Rope {
self.append(&Rope::from(other))
}
}
impl<'a, 'b> ops::Add<&'b str> for &'a Rope {
type Output = Rope;
/// Non-destructively concatenate a `Rope` and an `&str`.
///
/// Returns a new `Rope`
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let rope = Rope::from(String::from("ab"));
/// assert_eq!( &rope + "cd"
/// , Rope::from(String::from("abcd")));
/// ```
#[inline] fn add(self, other: &'b str) -> Rope {
self.append(&Rope::from(other.to_owned()))
}
}
impl<'a> ops::Add<&'a str> for Rope {
type Output = Rope;
/// Non-destructively concatenate a `Rope` and an `&str`.
///
/// Returns a new `Rope`
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let rope = Rope::from(String::from("ab"));
/// assert_eq!( rope + "cd"
/// , Rope::from(String::from("abcd")));
/// ```
#[inline] fn add(self, other: &'a str) -> Rope {
self.append(&Rope::from(other.to_owned()))
}
}
impl ops::Index<usize> for Rope {
type Output = str;
/// Recursively index the Rope to return the `i` th character.
///
/// # Examples
/// ```
/// use an_rope::Rope;
/// let an_rope = Rope::from(String::from("abcd"));
/// assert_eq!(&an_rope[0], "a");
/// assert_eq!(&an_rope[1], "b");
/// assert_eq!(&an_rope[2], "c");
/// assert_eq!(&an_rope[3], "d");
/// ```
///
/// # Time complexity
/// _O_(log _n_)
///
#[inline]
fn index(&self, i: usize) -> &str {
&self.root[i]
}
}
//-- slicing operators ----------------------------------------------
impl ops::Index<ops::Range<usize>> for Rope {
type Output = str;
// Index a substring
fn index(&self, _i: ops::Range<usize>) -> &str {
unimplemented!()
}
}
impl ops::Index<ops::RangeTo<usize>> for Rope {
type Output = str;
fn index(&self, _i: ops::RangeTo<usize>) -> &str {
unimplemented!()
}
}
impl ops::Index<ops::RangeFrom<usize>> for Rope {
type Output = str;
fn index(&self, _i: ops::RangeFrom<usize>) -> &str {
unimplemented!()
}
}
impl ops::IndexMut<ops::Range<usize>> for Rope {
fn index_mut(&mut self, _i: ops::Range<usize>) -> &mut str {
unimplemented!()
}
}
impl ops::IndexMut<ops::RangeTo<usize>> for Rope {
fn index_mut(&mut self, _i: ops::RangeTo<usize>) -> &mut str {
unimplemented!()
}
}
impl ops::IndexMut<ops::RangeFrom<usize>> for Rope {
fn index_mut(&mut self, _i: ops::RangeFrom<usize>) -> &mut str {
unimplemented!()
}
}
// impl<'a> Borrow<RopeSlice<'a>> for &'a Rope {
// fn borrow(&self) -> &RopeSlice<'a> {
// unimplemented!()
// }
// }
// impl<A> iter::Extend<A> for Rope
// where Rope: iter::FromIterator<A>{
//
// fn extend<B>(&mut self, iter: B)
// where B: IntoIterator<Item=A> {
//
// self.append(&(iter.into_iter().collect()));
//
// }
//
// }
impl iter::FromIterator<char> for Rope {
fn from_iter<I>(iter: I) -> Rope
where I: IntoIterator<Item=char> {
let s: String = iter.into_iter().collect();
Rope::from(s)
}
}
impl iter::FromIterator<String> for Rope {
fn from_iter<I>(iter: I) -> Rope
where I: IntoIterator<Item=String> {
iter.into_iter().fold(Rope::new(), |acc, x| acc + x)
}
}
impl iter::FromIterator<Rope> for Rope {
fn from_iter<I>(iter: I) -> Rope
where I: IntoIterator<Item=Rope> {
iter.into_iter().fold(Rope::new(), |acc, x| acc + x)
}
}
impl<'a> iter::FromIterator<&'a char> for Rope {
fn from_iter<I>(iter: I) -> Rope
where I: IntoIterator<Item=&'a char> {
let s: String = iter.into_iter().fold(String::new(), |mut acc, x| {acc.push(*x); acc});
Rope::from(s)
}
}
impl<'a> iter::FromIterator<&'a str> for Rope {
fn from_iter<I>(iter: I) -> Rope
where I: IntoIterator<Item=&'a str> {
iter.into_iter().fold(Rope::new(), |acc, x| acc + x)
}
}