Array helpers for Rust's Vector and String types

Daniel P. Clark

Last update: Dec 9, 2022

Related tags

Data structures rust string vector iterator crates wordwrap grapheme justify

Overview

array_tool

Array helpers for Rust. Some of the most common methods you would use on Arrays made available on Vectors. Polymorphic implementations for handling most of your use cases.

Installation

Add the following to your Cargo.toml file

[dependencies]
array_tool = "~1.0.3"

And in your rust files where you plan to use it put this at the top

extern crate array_tool;

And if you plan to use all of the Vector helper methods available you may do

use array_tool::vec::*;

This crate has helpful methods for strings as well.

Iterator Usage

use array_tool::iter::ZipOpt;
fn zip_option<U: Iterator>(self, other: U) -> ZipOption<Self, U>
  where Self: Sized, U: IntoIterator;
  //  let a = vec![1];
  //  let b = vec![];
  //  a.zip_option(b).next()      // input
  //  Some((Some(1), None))       // return value

Vector Usage

pub fn uniques<T: PartialEq + Clone>(a: Vec<T>, b: Vec<T>) -> Vec<Vec<T>>
  //  array_tool::uniques(vec![1,2,3,4,5], vec![2,5,6,7,8]) // input
  //  vec![vec![1,3,4], vec![6,7,8]]                        // return value

use array_tool::vec::Uniq;
fn uniq(&self, other: Vec<T>) -> Vec<T>;
  //  vec![1,2,3,4,5,6].uniq( vec![1,2,5,7,9] ) // input
  //  vec![3,4,6]                               // return value
fn uniq_via<F: Fn(&T, &T) -> bool>(&self, other: Self, f: F) -> Self;
  //  vec![1,2,3,4,5,6].uniq_via( vec![1,2,5,7,9], |&l, r| l == r + 2 ) // input 
  //  vec![1,2,4,6]                                                     // return value
fn unique(&self) -> Vec<T>;
  //  vec![1,2,1,3,2,3,4,5,6].unique()          // input
  //  vec![1,2,3,4,5,6]                         // return value
fn unique_via<F: Fn(&T, &T) -> bool>(&self, f: F) -> Self;
  //  vec![1.0,2.0,1.4,3.3,2.1,3.5,4.6,5.2,6.2].
  //  unique_via( |l: &f64, r: &f64| l.floor() == r.floor() ) // input
  //  vec![1.0,2.0,3.3,4.6,5.2,6.2]                           // return value
fn is_unique(&self) -> bool;
  //  vec![1,2,1,3,4,3,4,5,6].is_unique()       // input
  //  false                                     // return value
  //  vec![1,2,3,4,5,6].is_unique()             // input
  //  true                                      // return value

use array_tool::vec::Shift;
fn unshift(&mut self, other: T);    // no return value, modifies &mut self directly
  //  let mut x = vec![1,2,3];
  //  x.unshift(0);
  //  assert_eq!(x, vec![0,1,2,3]);
fn shift(&mut self) -> Option<T>;
  //  let mut x = vec![0,1,2,3];
  //  assert_eq!(x.shift(), Some(0));
  //  assert_eq!(x, vec![1,2,3]);

use array_tool::vec::Intersect;
fn intersect(&self, other: Vec<T>) -> Vec<T>;
  //  vec![1,1,3,5].intersect(vec![1,2,3]) // input
  //  vec![1,3]                            // return value
fn intersect_if<F: Fn(&T, &T) -> bool>(&self, other: Vec<T>, validator: F) -> Vec<T>;
  //  vec!['a','a','c','e'].intersect_if(vec!['A','B','C'], |l, r| l.eq_ignore_ascii_case(r)) // input
  //  vec!['a','c']                                                                           // return value

use array_tool::vec::Join;
fn join(&self, joiner: &'static str) -> String;
  //  vec![1,2,3].join(",")                // input
  //  "1,2,3"                              // return value

use array_tool::vec::Times;
fn times(&self, qty: i32) -> Vec<T>;
  //  vec![1,2,3].times(3)                 // input
  //  vec![1,2,3,1,2,3,1,2,3]              // return value

use array_tool::vec::Union;
fn union(&self, other: Vec<T>) -> Vec<T>;
  //  vec!["a","b","c"].union(vec!["c","d","a"])   // input
  //  vec![ "a", "b", "c", "d" ]                   // return value

String Usage

use array_tool::string::ToGraphemeBytesIter;
fn grapheme_bytes_iter(&'a self) -> GraphemeBytesIter<'a>;
  //  let string = "a s—d féZ";
  //  let mut graphemes = string.grapheme_bytes_iter()
  //  graphemes.skip(3).next();            // input
  //  [226, 128, 148]                      // return value for emdash `—`

use array_tool::string::Squeeze;
fn squeeze(&self, targets: &'static str) -> String;
  //  "yellow moon".squeeze("")            // input
  //  "yelow mon"                          // return value
  //  "  now   is  the".squeeze(" ")       // input
  //  " now is the"                        // return value

use array_tool::string::Justify;
fn justify_line(&self, width: usize) -> String;
  //  "asd as df asd".justify_line(16)     // input
  //  "asd  as  df  asd"                   // return value
  //  "asd as df asd".justify_line(18)     // input
  //  "asd   as   df  asd"                 // return value

use array_tool::string::SubstMarks;
fn subst_marks(&self, marks: Vec<usize>, chr: &'static str) -> String;
  //  "asdf asdf asdf".subst_marks(vec![0,5,8], "Z") // input
  //  "Zsdf ZsdZ asdf"                               // return value

use array_tool::string::WordWrap;
fn word_wrap(&self, width: usize) -> String;
  //  "01234 67 9 BC EFG IJ".word_wrap(6)  // input
  //  "01234\n67 9\nBC\nEFG IJ"            // return value

use array_tool::string::AfterWhitespace;
fn seek_end_of_whitespace(&self, offset: usize) -> Option<usize>;
  //  "asdf           asdf asdf".seek_end_of_whitespace(6) // input
  //  Some(9)                                              // return value
  //  "asdf".seek_end_of_whitespace(3)                     // input
  //  Some(0)                                              // return value
  //  "asdf           ".seek_end_of_whitespace(6)          // input
  //  None                                                 // return_value

Future plans

Expect methods to become more polymorphic over time (same method implemented for similar & compatible types). I plan to implement many of the methods available for Arrays in higher languages; such as Ruby. Expect regular updates.

License

Licensed under either of

Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (MIT-LICENSE or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments

String library functions do not work with UTF8

I added a test to test/string.rs: assert_eq!("ééé".subst_marks(vec![1], "Z"), "éZé");

and 'cargo test' crashes on:

---- it_substitutes_character_at_each_indexed_point stdout ---- thread 'it_substitutes_character_at_each_indexed_point' panicked at 'byte index 1 is not a char boundary; it is inside 'é' (bytes 0..2) of ééé', C:\bot\slave\stable-dist- rustc-win-gnu-64\build\src\libcore\str/mod.rs:1771 note: Run with RUST_BACKTRACE=1 for a backtrace.
bug

opened by VladimirMarkelov 5

Special functions for sorted arrays

As mentioned in the title, would be awesome to see some of these functions (intersect cough cough) be able to process pre-sorted arrays faster. I got a significant speedup by avoiding the n^2 runtime with this:

pub trait IntersectSorted<T> {
    /// Intersect two sorted sequences
    fn intersect(&mut self, other: &Self);
}

impl<T: PartialEq + PartialOrd> IntersectSorted<T> for Vec<T> {
   fn intersect(&mut self, other: &Self) {
        let (mut i, mut j, mut cursor) = (0, 0, 0);
        while cursor + i < self.len() && j < other.len() {
            if self[cursor + i] == other[j] {
                self[cursor] = self[cursor + i];
                cursor += 1;
                j += 1;
                continue;
            }
            if self[cursor + i] > other[j] {
                j += 1;
            } else {
                i += 1;
            }
        }
        self.resize(cursor, self[0]);
    }
}

Potentially out-of-scope, understandable, but some specific functions that cater to sorted sequences would be awesome

EDIT :: updated code to work. Sorry, being lazy with my hw assignment...

opened by mfigurski80 4

Issue#20
This PR implements a series of similar traits with new assumptions for sorted vectors (both ascending and descending -- these are important as they lead to significant runtime improvements. Resolves #20 .

This PR so far includes:

Cargo Warning + Error fixes

Cargo Formatting

Doc + Doctest fixes

A new sorted_vec module which defines and implements...

SortedUniq trait: takes advantage of sortedness assumption to improve runtime. Implements some slightly different methods, as the basic uniq_via needs not only a custom equality comparator, but a custom ordering comparator (in line with the new traits required of T: PartialEq + PartialOrd). This is implemented for a standard Vec<T>

SortedIntersect trait: also takes advantage of sortedness assumption. Lots of same assumptions as above

Tests for both

Benchmarks for both: seems like an order-of-magnitude improvement

@danielpclark Hey! This is actually my first real open source contribution -- I'm a pro at neither this nor Rust itself, but this is a pretty cool experience so far. Feel like some of the decisions made in the package code are pretty nonstandard (methods are cloning and returning instead of just mutating) for Rust, but I did my best to follow the patterns established thus far. Would also be cool to do more things here.

I'm still actually somewhat unhappy with this: was hoping to be able to define a different type (type alias for Vec perhaps) and implement all the old traits for it, but it seems like I'd lose a lot of Vec methods (https://stackoverflow.com/questions/35568871/is-it-possible-to-implement-methods-on-type-aliases). I mentioned implementing this for the SortedVec package structs, but it seems like those are more meant to build sortedness rather than maintain and allow efficient mutation. Would love to hear input and potentially make a cleaner interface here.
opened by mfigurski80 1

word_wrap doesn't account for groups of characters that are longer than width

word_wrap exits at the first instance of a word being longer that the word wrap length.

assert_eq!(
  "0123456789ABC EFG IJ".word_wrap(6),
  "0123456789ABC\nEFG IJ"
);

outputs

failures:

---- it_word_wraps_for_string stdout ----
    thread 'it_word_wraps_for_string' panicked at 'assertion failed: `(left == right)` (left: `"0123456789ABC EFG IJ"`, right: `"0123456789ABC\nEFG IJ"`)', tests/string.rs:33

bug

opened by danielpclark 1

word_wrap doesn't account for existing new line characters
Word wrap will create wrapped text but doesn't account for new line characters that may already exist within the string. This may result in odd short lines.

The fix should be easy enough. If the new line character exists in the current segment then shift the offset and continue. In the None block do a seek-next and set a marker and offset there; continue.

assert_eq!( "----\n ---- ---- ----".word_wrap(10), "----\n ---- ----\n----" );

outputs:

failures: ---- it_word_wraps_for_string stdout ---- thread 'it_word_wraps_for_string' panicked at 'assertion failed: `(left == right)` (left: `"----\n\n---- ----\n----"`, right: `"----\n ---- ----\n----"`)', tests/string.rs:38
bug
opened by danielpclark 1

vector::times panics on empty vector

  let vv1: Vec<i32> = Vec::new();
  let vv2: Vec<i32> = Vec::new();
  assert_eq!(vv1.times(4), vv2);

thread 'it_multiplies' panicked at 'index out of bounds: the len is 0 but the index is 0', src\libcollections\vec.rs:1422

opened by VladimirMarkelov 0

Introduce Clippy

Solves Issue #16.

Hey @danielpclark. I don't know exactly what your CI looks like since it seems private, but I added a command that would reject builds if Clippy generates any warnings. Additionally, I fixed some of the issues it highlighted.

In doing this, I wanted to rewrite some of the functions to utilize iter more because Clippy dislikes creating variables just to index things, but these tend to hurt performance. All except for one: intersect_if went from a bench of [802 ns/iter (+/- 26)] to [674 ns/iter (+/- 10)] with a few iterators. It's cool to have those benchmarks btw :+1:

Let me know If this fits your config or if it's entirely useless for you

opened by mfigurski80 0
Add clippy

Clippy will help good coding practices be enforced. It's a bit finicky with requiring Rust nightly and both will need to be set to a specific versions for the C.I. tests.
enhancement

opened by danielpclark 0