// definition
pub trait IntoIterator {
    type Item;                  // type to be iteratored over
    type IntoIter: Iterator;    // type of iterator to turn into
    fn into_iter(self) -> Self::IntoIter;
}

.iter()           // immutable ref
.iter_mut()       // mutable ref
.into_iter()      // owned value

// &str does not have .iter() method
// use `.char()` and `.bytes()` instead

// Other types have methods to create iters
vec.split(f: F);
string.lines();
buf_read.lines();

fn collect_as_string<T>(collection: T) -> Vec<String>
where
    T: IntoIterator<Item=U>,
    U: std::fmt::Debug,
{
    collection
        .into_iter()
        .map(|item| format!("{:?}", item))
        .collect()
}

// create a one-element iter
let a = std::iter::once(5);

// create an endless iter
let for_ever = std::iter::repeat("for_ever");
// use take to take finite numbers
let fours = iter::repeat(4).take(4);

// creates an empty iter
pub const fn empty<T>() -> Empty<T>

// this could have been an iterator over i32, but alas, it's just not.
let mut nope = std::iter::empty::<i32>();
assert_eq!(None, nope.next());

pub fn from_fn<T, F>(f: F) -> FromFn<F>
where
    F: FnMut() -> Option<T>,
{
    FromFn(f)
}
// example
use rand::random;
let lengths: Vec<f64> =
    from_fn(|| Some((random::<f64>() - random::<f64>()).abs()))
    .take(1000)
    .collect();

// each item depends on the one before
pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F>
where
    F: FnMut(&T) -> Option<T>,
{
    // If this function returned `impl Iterator<Item=T>`
    // it could be based on `unfold` and not need a dedicated type.
    // However having a named `Successors<T, F>` type allows it to be `Clone` when `T` and `F` are.
    Successors { next: first, succ }
}
let powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
assert_eq!(powers_of_10.collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);

// creates a draining iter that removes the specified range in the `String`
// and yields the removed `chars`
// the element range is removed even if the iter is not consumed until the end
pub fn drain<R>(&mut self, range: R) -> Drain<'_>
where
    R: RangeBounds<usize>, 


let mut s = String::from("α is alpha, β is beta");
let beta_offset = s.find('β').unwrap_or(s.len());
// Remove the range up until the β from the string
let t: String = s.drain(..beta_offset).collect();
assert_eq!(t, "α is alpha, ");
assert_eq!(s, "β is beta");
// A full range clears the string
s.drain(..);
assert_eq!(s, "");

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item> {}
}

// every for loop is just a shorthand
for element in &v { ... }
let mut i = (&v).into_iter();
while let Some(e) = i.next() { ... }

// An iterator which counts from one to five
struct Counter {
    count: usize,
}
impl Counter {
    fn new() -> Counter {
        Counter { count: 0 }
    }
}
impl Iterator for Counter {
    type Item = usize;
    // next() is the only required method
    fn next(&mut self) -> Option<Self::Item> {
        self.count += 1;
        // Check to see if we've finished counting or not.
        if self.count < 6 {
            Some(self.count)
        } else {
            None
        }
    }
}

pub trait DoubleEndedIterator: Iterator {
    fn next_back(&mut self) -> Option<Self::Item>;

    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { ... }
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> { ... }
    fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    { ... }
    fn rfold<B, F>(self, init: B, f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    { ... }
    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
    where
        P: FnMut(&Self::Item) -> bool,
    { ... }
}

// map
fn map<B, F>(self, f: F) -> impl Iterator<Item=B>
    where Self: Sized, F: FnMut(Self::Item) -> B;
let v2: Vec<_> = v1.iter().map(|x| x + 1).collect();
// map is lazy; this would not execute
(0..5).map(|x| println!("{}", x));

// filter
fn filter<P>(self, predicate: P) -> impl Iterator<Item=Self::Item>
    where Self: Sized, P: FnMut(&Self::Item) -> bool;
// note the `&Self::Item` arg
// either use double deref, or deref in arg
let a = [0, 1, 2];
let mut iter = a.iter().filter(|&x| *x > 1);
assert_eq!(iter.next(), Some(&2));

// filter_map is to make chains of `filter` and `map`
fn filter_map<B, F>(self, f: F) -> impl Iterator<Item=B>
    where Self: Sized, F: FnMut(Self::Item) -> Option<B>;
let a = ["1", "two", "3"];
let mut iter = a.iter().filter_map(|s| s.parse().ok());
// equvalent to
let mut iter = a.iter().map(|s| s.parse()).filter(|s| s.is_ok()).map(|s| s.unwrap());

// take creates an iterator that yields the first n element
fn take(self, n: usize) -> impl Iterator<Item=Self::Item>
    where Self: Sized;
// take_while takes ref
// stops after the first `false` and the rest of the elements are ignored
fn take_while<P>(self, predicate: P) -> impl Iterator<Item=Self::Item>
    where Self: Sized, P: FnMut(&Self::Item) -> bool;
let a = [-1, 0, 1, -2];
let mut iter = a.iter().take_while(|x| **x < 0);
assert_eq!(iter.next(), Some(&-1));
// We have more elements that are less than zero, but since we already
// got a false, take_while() isn't used any more
assert_eq!(iter.next(), None);

// skip and skip_while
fn skip(self, n: usize) -> impl Iterator<Item=Self::Item>
    where Self: Sized;
// skip_while takes ref in FnMut
// skip after the first `false`
fn skip_while<P>(self, predicate: P) -> impl Iterator<Item=Self::Item>
    where Self: Sized, P: FnMut(&Self::Item) -> bool;
let a = [-1, 0, 1, -2];
let mut iter = a.iter().skip_while(|x| **x < 0);
assert_eq!(iter.next(), Some(&1));
// while this would have been false, since we already got a false,
// skip_while() isn't used any more
assert_eq!(iter.next(), Some(&-2));

// creates an iter which uses the `peek` and `peek_mut` method
// without consuming the element
// the underlying iterator is still advanced when call `peek` the first time
// in order to retrieve the next element, call `next`
fn peekable(self) -> std::iter::Peekable<Self>
    where Self: Sized;
let xs = [1, 2, 3];
let mut iter = xs.iter().peekable();
// peek() lets us see into the future
assert_eq!(iter.peek(), Some(&&1));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
// we can peek() multiple times, the iterator won't advance
assert_eq!(iter.peek(), Some(&&3));
assert_eq!(iter.peek(), Some(&&3));

// creates an iter that flattens nested structure
fn flatten(self) -> impl Iterator<Item=Self::Item::Item>
    where Self::Item: IntoIterator;

let data = vec![vec![1, 2, 3, 4], vec![5, 6]];
let flattened = data.into_iter().flatten().collect::<Vec<u8>>();
assert_eq!(flattened, &[1, 2, 3, 4, 5, 6]);

// only one level at a time
let d3 = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]];
let d2 = d3.iter().flatten().collect::<Vec<_>>();
assert_eq!(d2, [&[1, 2], &[3, 4], &[5, 6], &[7, 8]]);
let d1 = d3.iter().flatten().flatten().collect::<Vec<_>>();
assert_eq!(d1, [&1, &2, &3, &4, &5, &6, &7, &8]);

// `Option` impl `IntoIterator` and treats `None` as empty
// `Result` impl `IntoIterator` and treats `Err` as empty
assert_eq!(vec![None, Some("day"), None, Some("one")]
           .into_iter()
           .flatten()
           .collect::<Vec<_>>(),
           vec!["day", "one"]);


// flat_map is flatten and map
fn flat_map<U, F>(self, f: F) -> impl Iterator<Item=U::Item>
    where F: FnMut(Self::Item) -> U, U: IntoIterator;

let words = ["alpha", "beta", "gamma"];
// chars() returns an iterator
let merged: String = words.iter()
                          .flat_map(|s| s.chars())
                          .collect();
assert_eq!(merged, "alphabetagamma");

// zip: combine two iter to one tuple iterator
fn zip<U>(self, other: U) -> Zip<Self, <U as IntoIterator>::IntoIter>ⓘ
where
    U: IntoIterator,

let a1 = [1, 2, 3];
let a2 = [4, 5, 6];
let mut iter = a1.iter().zip(a2.iter());
assert_eq!(iter.next(), Some((&1, &4)));
assert_eq!(iter.next(), Some((&2, &5)));
assert_eq!(iter.next(), Some((&3, &6)));
assert_eq!(iter.next(), None);

// unzip: converts an iter of pairs into a pair of containers
fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB)
where
    Self: Iterator<Item = (A, B)>,
    FromA: Default + Extend<A>,
    FromB: Default + Extend<B>, 

let a = [(1, 2), (3, 4)];
let (left, right): (Vec<_>, Vec<_>) = a.iter().cloned().unzip();
assert_eq!(left, [1, 3]);
assert_eq!(right, [2, 4]);

// fuse creates an iter which ends after the first `None`

// rev
fn rev(self) -> impl Iterator<Item=Self>
    where Self: Sized + DoubleEndedIterator;
let a = [1, 2, 3];
let mut iter = a.iter().rev();


// inspect 
// common to use as a debugging tool
fn inspect<F>(self, f: F) -> Inspect<Self, F>
where
    F: FnMut(&Self::Item), 
// example
let sum = a.iter()
    .cloned()
    // map is lazy
    .inspect(|x| println!("about to filter: {}", x))
    .filter(|x| x % 2 == 0)
    .inspect(|x| println!("made it through filter: {}", x))
    .fold(0, |sum, i| sum + i);

// chain two iter into one
// `once` is more common to adapt a single value into a chain
fn chain<U>(self, other: U) -> impl Iterator<Item=Self::Item>
    where Self: Sized, U: IntoIterator<Item=Self::Item>;
let a1 = [1, 2, 3];
let a2 = [4, 5, 6];
let mut iter = a1.iter().chain(a2.iter());
// can chain directly if a type impl `IntoIterator`
let s1 = &[1, 2, 3];
let s2 = &[4, 5, 6];
let mut iter = s1.iter().chain(s2);


// enumerate
// creates an iterator `(i, val)` where `i` is the current index
// and `val` is the value returned
let a = ['a', 'b', 'c'];
let mut iter = a.iter().enumerate();
assert_eq!(iter.next(), Some((2, &'c')));
assert_eq!(iter.next(), None);
// convert enumerate
let v = a.iter().enumerate().filter(|(x,_)| x % 2 == 0).map(|(_, y)| y).collect();

// `copied` and `cloned`
// Both create an iter that copy/clone all the elements
// useful to convert an `&T` iter to `T`
// `copied` is the same as .map(|&x| x)
fn copied<'a, T>(self) -> Copied<Self>
where
    Self: Iterator<Item = &'a T>,
    T: 'a + Copy, 

fn cloned<'a, T>(self) -> Cloned<Self>
where
    Self: Iterator<Item = &'a T>,
    T: 'a + Clone, 


// cycle
// repeats an iter endlessly
let a = [1, 2, 3];
let mut it = a.iter().cycle();

// step
a.iter().step_by(2);    // takes the first, then every 2 steps

// scan
// similar to `fold`
// takes an initial value which seeds the internal state
// and a closure with two arg, first being a mutable ref to the internal state
// second an iterator element
// return Option
fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>ⓘ
where
    F: FnMut(&mut St, Self::Item) -> Option<B>, 

let a = [1, 2, 3];

let mut iter = a.iter().scan(1, |state, &x| {
    // each iteration, we'll multiply the state by the element
    *state = *state * x;

    // then, we'll yield the negation of the state
    Some(-*state)
});

assert_eq!(iter.next(), Some(-1));
assert_eq!(iter.next(), Some(-2));
assert_eq!(iter.next(), Some(-6));
assert_eq!(iter.next(), None);

.next()     // individual iter may impl differently

// `nth` takes `&mut self` but all proceeding elements will be consumed
fn nth(&mut self, n: usize) -> Option<Self::Item>

// `any` stops at the first true
// an empty iterator returns false
fn any<F>(&mut self, f: F) -> bool
where
    F: FnMut(Self::Item) -> bool, 

let a = [1, 2, 3];
let mut iter = a.iter();
assert!(iter.any(|&x| x != 2));
// we can still use `iter`, as there are more elements.
assert_eq!(iter.next(), Some(&2));

// `all` checks if every element matches
// stops at the first `false`, consumes the tested values
fn all<F>(&mut self, f: F) -> bool
where
    F: FnMut(Self::Item) -> bool, 

let a = [1, 2, 3];
let mut iter = a.iter();
assert!(!iter.all(|&x| x != 2));
// we can still use `iter`, as there are more elements.
assert_eq!(iter.next(), Some(&3));

// by_ref
// Borrows an iterator rather than consuming it
fn by_ref(&mut self) -> &mut Self
let mut words = vec!["hello", "world", "of", "Rust"].into_iter();
// Take the first two words.
let hello_world: Vec<_> = words.by_ref().take(2).collect();
assert_eq!(hello_world, vec!["hello", "world"]);
// Collect the rest of the words.
// We can only do this because we used `by_ref` earlier.
let of_rust: Vec<_> = words.collect();
assert_eq!(of_rust, vec!["of", "Rust"]);

.count()
.sum()
.product()
.max()
.min()
.max_by(F)
.min_by(F)
.max_by_key(F: FnMut)
.min_by_key(f: FnMut)
.is_empty()
.last()

.cmp
.partial_cmp
.eq
.ne
.lt
.ge
.gt

// returning the index of an element
// rposition searches from the right side
// returns Options
// stops at the first true
fn position<P>(&mut self, predicate: P) -> Option<usize>
where
    P: FnMut(Self::Item) -> bool, 

let a = [1, 2, 3, 4];
let mut iter = a.iter();
assert_eq!(iter.position(|&x| x >= 2), Some(1));

// we can still use `iter`, as there are more elements.
assert_eq!(iter.next(), Some(&3));
// The returned index depends on iterator state
assert_eq!(iter.position(|&x| x == 4), Some(0));

// for rposition to work, `Self` needs `DoubleEndedIterator`
fn rposition<P>(&mut self, predicate: P) -> Option<usize>
where
    Self: ExactSizeIterator + DoubleEndedIterator,
    P: FnMut(Self::Item) -> bool, 

// consumes an iter into two collections
// returns (true false) pairs
fn partition<B, F>(self, f: F) -> (B, B)
where
    F: FnMut(&Self::Item) -> bool,
    B: Default + Extend<Self::Item>, 

let a = [1, 2, 3];
let (even, odd): (Vec<i32>, Vec<i32>) = a
    .iter()
    .partition(|&n| n % 2 == 0);
assert_eq!(even, vec![2]);
assert_eq!(odd, vec![1, 3]);

// folds every element into an accumulator by applying an operation (reduce or inject)
// takes: an initial value and a closure
// closure takes: accumulator and an element 
// returns the accumulator
// `rfold` for right-associated version
fn fold<B, F>(self, init: B, f: F) -> B
where
    F: FnMut(B, Self::Item) -> B,

let a = [1, 2, 3];
// the sum of all of the elements of the array
let sum = a.iter().fold(0, |acc, x| acc + x);
assert_eq!(sum, 6);

// reduce is the simple version of fold when
// the initial value is the first element
// and accumu is the same type as element
// returns Option
fn reduce<F>(self, f: F) -> Option<Self::Item>
where
    F: FnMut(Self::Item, Self::Item) -> Self::Item, 

let a = [1, 2, 3];
let sum = a.into_iter().reduce(|acc, x| acc + x);
assert_eq!(sum, Some(6));

//  search for an element; returns Option
// note `&Self` in arg
// stops at the first true
// try_find returns Result<Option, E>
fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
where
    P: FnMut(&Self::Item) -> bool, 
let a = [1, 2, 3];

let mut iter = a.iter();

assert_eq!(iter.find(|&&x| x == 2), Some(&2));

// we can still use `iter`, as there are more elements.
assert_eq!(iter.next(), Some(&3));

// find_map applies fn to the elements and returns the first non-None result
fn find_map<B, F>(&mut self, f: F) -> Option<B>
where
    F: FnMut(Self::Item) -> Option<B>, 

let a = ["lol", "NaN", "2", "5"];
let first_number = a.iter().find_map(|s| s.parse().ok());
assert_eq!(first_number, Some(2));

// call a closure on each element
// equivalent to `for` loop but `break` or `continue` not work
fn for_each<F>(self, f: F)
where
    F: FnMut(Self::Item),

(0..5).flat_map(|x| x * 100 .. x * 110)
      .enumerate()
      .filter(|&(i, x)| (i + x) % 3 == 0)
      .for_each(|(i, x)| println!("{}:{}", i, x));
 
// try_for_each stops at the first error and returning that error
fn try_for_each<F, R>(&mut self, f: F) -> R
where
    F: FnMut(Self::Item) -> R,
    R: Try<Output = ()>, 

// note the generatic type
fn collect<B>(self) -> B
where
    B: FromIterator<Self::Item>,

// turn one collecition to iter, transform, then to anotehr collection
let a = [1, 2, 3];
let doubled: Vec<i32> = a.iter()
                         .map(|&x| x * 2)
                         .collect();
assert_eq!(vec![2, 4, 6], doubled);


// can build any kind of collection
let args: HashSet<String> = std::env::args().collect();
let args: BTreeSet<String> = std::env::args().collect();
let args: LinkedList<String> = std::env::args().collect();

let args = std::env::args().collect::<Vec<String>>();
let args = std::env::args().collect::<HashSet<String>>();

// build a String from char
let chars = ['g', 'd', 'k', 'k', 'n'];
let hello: String = chars.iter()
    .map(|&x| x as u8)
    .map(|x| (x + 1) as char)
    .collect();
assert_eq!("hello", hello);

// collect iter of Result into `Result<Collection<T>, E>`
let results = [Ok(1), Err("nope"), Ok(3), Err("bad")];
let result: Result<Vec<_>, &str> = results.iter().cloned().collect();
// gives us the first error
assert_eq!(Err("nope"), result);
let results = [Ok(1), Ok(3)];
let result: Result<Vec<_>, &str> = results.iter().cloned().collect();
// gives us the list of answers
assert_eq!(Ok(vec![1, 3]), result);

// extend a collection with the contenst of an iter
pub trait Extend<A> {
    fn extend<T>(&mut self, iter: T)
    where
        T: IntoIterator<Item = A>;
}

// You can extend a String with some chars:
let mut message = String::from("The first three letters are: ");
message.extend(&['a', 'b', 'c']);
assert_eq!("abc", &message[29..32]);