text:
pub use self::MinMaxResult::*;

use clone::Clone;
use cmp;
use cmp::Ord;
use mem;
use num::{ToPrimitive, Int};
use ops::{Add, Deref};
use option::{Option, Some, None};
use uint;

#[deprecated = "renamed to Extend"] pub use self::Extend as Extendable;

/// Conversion from an `Iterator`
#[unstable = "may be replaced by a more general conversion trait"]
pub trait FromIterator<A> {
    /// Build a container with elements from an external iterator.
    fn from_iter<T: Iterator<A>>(iterator: T) -> Self;
}

/// A type growable from an `Iterator` implementation
#[unstable = "just renamed as part of collections reform"]
pub trait Extend<A> {
    /// Extend a container with the elements yielded by an arbitrary iterator
    fn extend<T: Iterator<A>>(&mut self, iterator: T);
}

/// An interface for dealing with "external iterators". These types of iterators
/// can be resumed at any time as all state is stored internally as opposed to
/// being located on the call stack.
///
/// The Iterator protocol states that an iterator yields a (potentially-empty,
/// potentially-infinite) sequence of values, and returns `None` to signal that
/// it's finished. The Iterator protocol does not define behavior after `None`
/// is returned. A concrete Iterator implementation may choose to behave however
/// it wishes, either by returning `None` infinitely, or by doing something
/// else.
#[lang="iterator"]
#[unstable = "just split up for object safety"]
pub trait Iterator<A> {
    /// Advance the iterator and return the next value. Return `None` when the end is reached.
    fn next(&mut self) -> Option<A>;

    /// Returns a lower and upper bound on the remaining length of the iterator.
    ///
    /// An upper bound of `None` means either there is no known upper bound, or the upper bound
    /// does not fit within a `uint`.
    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
}

#[unstable = "new convention for extension traits"]
/// An extension trait providing numerous methods applicable to all iterators.
pub trait IteratorExt<A>: Iterator<A> {
    /// Chain this iterator with another, returning a new iterator which will
    /// finish iterating over the current iterator, and then it will iterate
    /// over the other specified iterator.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [0i];
    /// let b = [1i];
    /// let mut it = a.iter().chain(b.iter());
    /// assert_eq!(it.next().unwrap(), &0);
    /// assert_eq!(it.next().unwrap(), &1);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[stable]
    fn chain<U: Iterator<A>>(self, other: U) -> Chain<Self, U> {
        Chain{a: self, b: other, flag: false}
    }

    /// Creates an iterator which iterates over both this and the specified
    /// iterators simultaneously, yielding the two elements as pairs. When
    /// either iterator returns None, all further invocations of next() will
    /// return None.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [0i];
    /// let b = [1i];
    /// let mut it = a.iter().zip(b.iter());
    /// let (x0, x1) = (0i, 1i);
    /// assert_eq!(it.next().unwrap(), (&x0, &x1));
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[stable]
    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U> {
        Zip{a: self, b: other}
    }

    /// Creates a new iterator which will apply the specified function to each
    /// element returned by the first, yielding the mapped element instead.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2];
    /// let mut it = a.iter().map(|&x| 2 * x);
    /// assert_eq!(it.next().unwrap(), 2);
    /// assert_eq!(it.next().unwrap(), 4);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn map<'r, B>(self, f: |A|: 'r -> B) -> Map<'r, A, B, Self> {
        Map{iter: self, f: f}
    }

    /// Creates an iterator which applies the predicate to each element returned
    /// by this iterator. Only elements which have the predicate evaluate to
    /// `true` will be yielded.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2];
    /// let mut it = a.iter().filter(|&x| *x > 1);
    /// assert_eq!(it.next().unwrap(), &2);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn filter<'r>(self, predicate: |&A|: 'r -> bool) -> Filter<'r, A, Self> {
        Filter{iter: self, predicate: predicate}
    }

    /// Creates an iterator which both filters and maps elements.
    /// If the specified function returns None, the element is skipped.
    /// Otherwise the option is unwrapped and the new value is yielded.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2];
    /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
    /// assert_eq!(it.next().unwrap(), 4);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn filter_map<'r, B>(self, f: |A|: 'r -> Option<B>) -> FilterMap<'r, A, B, Self> {
        FilterMap { iter: self, f: f }
    }

    /// Creates an iterator which yields a pair of the value returned by this
    /// iterator plus the current index of iteration.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [100i, 200];
    /// let mut it = a.iter().enumerate();
    /// let (x100, x200) = (100i, 200i);
    /// assert_eq!(it.next().unwrap(), (0, &x100));
    /// assert_eq!(it.next().unwrap(), (1, &x200));
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[stable]
    fn enumerate(self) -> Enumerate<Self> {
        Enumerate{iter: self, count: 0}
    }

    /// Creates an iterator that has a `.peek()` method
    /// that returns an optional reference to the next element.
    ///
    /// # Example
    ///
    /// ```rust
    /// let xs = [100i, 200, 300];
    /// let mut it = xs.iter().map(|x| *x).peekable();
    /// assert_eq!(*it.peek().unwrap(), 100);
    /// assert_eq!(it.next().unwrap(), 100);
    /// assert_eq!(it.next().unwrap(), 200);
    /// assert_eq!(*it.peek().unwrap(), 300);
    /// assert_eq!(*it.peek().unwrap(), 300);
    /// assert_eq!(it.next().unwrap(), 300);
    /// assert!(it.peek().is_none());
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[stable]
    fn peekable(self) -> Peekable<A, Self> {
        Peekable{iter: self, peeked: None}
    }

    /// Creates an iterator which invokes the predicate on elements until it
    /// returns false. Once the predicate returns false, all further elements are
    /// yielded.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 2, 1];
    /// let mut it = a.iter().skip_while(|&a| *a < 3);
    /// assert_eq!(it.next().unwrap(), &3);
    /// assert_eq!(it.next().unwrap(), &2);
    /// assert_eq!(it.next().unwrap(), &1);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn skip_while<'r>(self, predicate: |&A|: 'r -> bool) -> SkipWhile<'r, A, Self> {
        SkipWhile{iter: self, flag: false, predicate: predicate}
    }

    /// Creates an iterator which yields elements so long as the predicate
    /// returns true. After the predicate returns false for the first time, no
    /// further elements will be yielded.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 2, 1];
    /// let mut it = a.iter().take_while(|&a| *a < 3);
    /// assert_eq!(it.next().unwrap(), &1);
    /// assert_eq!(it.next().unwrap(), &2);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures, may want to require peek"]
    fn take_while<'r>(self, predicate: |&A|: 'r -> bool) -> TakeWhile<'r, A, Self> {
        TakeWhile{iter: self, flag: false, predicate: predicate}
    }

    /// Creates an iterator which skips the first `n` elements of this iterator,
    /// and then it yields all further items.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter().skip(3);
    /// assert_eq!(it.next().unwrap(), &4);
    /// assert_eq!(it.next().unwrap(), &5);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[stable]
    fn skip(self, n: uint) -> Skip<Self> {
        Skip{iter: self, n: n}
    }

    /// Creates an iterator which yields the first `n` elements of this
    /// iterator, and then it will always return None.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter().take(3);
    /// assert_eq!(it.next().unwrap(), &1);
    /// assert_eq!(it.next().unwrap(), &2);
    /// assert_eq!(it.next().unwrap(), &3);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[stable]
    fn take(self, n: uint) -> Take<Self> {
        Take{iter: self, n: n}
    }

    /// Creates a new iterator which behaves in a similar fashion to fold.
    /// There is a state which is passed between each iteration and can be
    /// mutated as necessary. The yielded values from the closure are yielded
    /// from the Scan instance when not None.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter().scan(1, |fac, &x| {
    ///   *fac = *fac * x;
    ///   Some(*fac)
    /// });
    /// assert_eq!(it.next().unwrap(), 1);
    /// assert_eq!(it.next().unwrap(), 2);
    /// assert_eq!(it.next().unwrap(), 6);
    /// assert_eq!(it.next().unwrap(), 24);
    /// assert_eq!(it.next().unwrap(), 120);
    /// assert!(it.next().is_none());
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn scan<'r, St, B>(self, initial_state: St, f: |&mut St, A|: 'r -> Option<B>)
        -> Scan<'r, A, B, Self, St> {
        Scan{iter: self, f: f, state: initial_state}
    }

    /// Creates an iterator that maps each element to an iterator,
    /// and yields the elements of the produced iterators
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::count;
    ///
    /// let xs = [2u, 3];
    /// let ys = [0u, 1, 0, 1, 2];
    /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x));
    /// // Check that `it` has the same elements as `ys`
    /// let mut i = 0;
    /// for x in it {
    ///     assert_eq!(x, ys[i]);
    ///     i += 1;
    /// }
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn flat_map<'r, B, U: Iterator<B>>(self, f: |A|: 'r -> U)
        -> FlatMap<'r, A, Self, U> {
        FlatMap{iter: self, f: f, frontiter: None, backiter: None }
    }

    /// Creates an iterator that yields `None` forever after the underlying
    /// iterator yields `None`. Random-access iterator behavior is not
    /// affected, only single and double-ended iterator behavior.
    ///
    /// # Example
    ///
    /// ```rust
    /// fn process<U: Iterator<int>>(it: U) -> int {
    ///     let mut it = it.fuse();
    ///     let mut sum = 0;
    ///     for x in it {
    ///         if x > 5 {
    ///             break;
    ///         }
    ///         sum += x;
    ///     }
    ///     // did we exhaust the iterator?
    ///     if it.next().is_none() {
    ///         sum += 1000;
    ///     }
    ///     sum
    /// }
    /// let x = vec![1i,2,3,7,8,9];
    /// assert_eq!(process(x.into_iter()), 6);
    /// let x = vec![1i,2,3];
    /// assert_eq!(process(x.into_iter()), 1006);
    /// ```
    #[inline]
    #[stable]
    fn fuse(self) -> Fuse<Self> {
        Fuse{iter: self, done: false}
    }

    /// Creates an iterator that calls a function with a reference to each
    /// element before yielding it. This is often useful for debugging an
    /// iterator pipeline.
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::AdditiveIterator;
    ///
    /// let xs = [1u, 4, 2, 3, 8, 9, 6];
    /// let sum = xs.iter()
    ///             .map(|&x| x)
    ///             .inspect(|&x| println!("filtering {}", x))
    ///             .filter(|&x| x % 2 == 0)
    ///             .inspect(|&x| println!("{} made it through", x))
    ///             .sum();
    /// println!("{}", sum);
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn inspect<'r>(self, f: |&A|: 'r) -> Inspect<'r, A, Self> {
        Inspect{iter: self, f: f}
    }

    /// Creates a wrapper around a mutable reference to the iterator.
    ///
    /// This is useful to allow applying iterator adaptors while still
    /// retaining ownership of the original iterator value.
    ///
    /// # Example
    ///
    /// ```rust
    /// let mut xs = range(0u, 10);
    /// // sum the first five values
    /// let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
    /// assert!(partial_sum == 10);
    /// // xs.next() is now `5`
    /// assert!(xs.next() == Some(5));
    /// ```
    #[stable]
    fn by_ref<'r>(&'r mut self) -> ByRef<'r, Self> {
        ByRef{iter: self}
    }

    /// Loops through the entire iterator, collecting all of the elements into
    /// a container implementing `FromIterator`.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let b: Vec<int> = a.iter().map(|&x| x).collect();
    /// assert!(a.as_slice() == b.as_slice());
    /// ```
    #[inline]
    #[unstable = "waiting for general conversion traits, just changed to take self by value"]
    fn collect<B: FromIterator<A>>(self) -> B {
        FromIterator::from_iter(self)
    }

    /// Loops through `n` iterations, returning the `n`th element of the
    /// iterator.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter();
    /// assert!(it.nth(2).unwrap() == &3);
    /// assert!(it.nth(2) == None);
    /// ```
    #[inline]
    #[stable]
    fn nth(&mut self, mut n: uint) -> Option<A> {
        for x in *self {
            if n == 0 { return Some(x) }
            n -= 1;
        }
        None
    }

    /// Loops through the entire iterator, returning the last element of the
    /// iterator.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// assert!(a.iter().last().unwrap() == &5);
    /// ```
    #[inline]
    #[unstable = "just changed to take self by value"]
    fn last(mut self) -> Option<A> {
        let mut last = None;
        for x in self { last = Some(x); }
        last
    }

    /// Performs a fold operation over the entire iterator, returning the
    /// eventual state at the end of the iteration.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures, just changed to take self by value"]
    fn fold<B>(mut self, init: B, f: |B, A| -> B) -> B {
        let mut accum = init;
        for x in self {
            accum = f(accum, x);
        }
        accum
    }

    /// Counts the number of elements in this iterator.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter();
    /// assert!(it.count() == 5);
    /// ```
    #[inline]
    #[unstable = "just changed to take self by value"]
    fn count(self) -> uint {
        self.fold(0, |cnt, _x| cnt + 1)
    }

    /// Tests whether the predicate holds true for all elements in the iterator.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// assert!(a.iter().all(|x| *x > 0));
    /// assert!(!a.iter().all(|x| *x > 2));
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures, just changed to take self by value"]
    fn all(mut self, f: |A| -> bool) -> bool {
        for x in self { if !f(x) { return false; } }
        true
    }

    /// Tests whether any element of an iterator satisfies the specified
    /// predicate.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter();
    /// assert!(it.any(|x| *x == 3));
    /// assert!(!it.any(|x| *x == 3));
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn any(&mut self, f: |A| -> bool) -> bool {
        for x in *self { if f(x) { return true; } }
        false
    }

    /// Returns the first element satisfying the specified predicate.
    ///
    /// Does not consume the iterator past the first found element.
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn find(&mut self, predicate: |&A| -> bool) -> Option<A> {
        for x in *self {
            if predicate(&x) { return Some(x) }
        }
        None
    }

    /// Return the index of the first element satisfying the specified predicate
    #[inline]
    #[unstable = "waiting for unboxed closures"]
    fn position(&mut self, predicate: |A| -> bool) -> Option<uint> {
        let mut i = 0;
        for x in *self {
            if predicate(x) {
                return Some(i);
            }
            i += 1;
        }
        None
    }

    /// Return the element that gives the maximum value from the
    /// specified function.
    ///
    /// # Example
    ///
    /// ```rust
    /// use core::num::SignedInt;
    ///
    /// let xs = [-3i, 0, 1, 5, -10];
    /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures, just changed to take self by value"]
    fn max_by<B: Ord>(self, f: |&A| -> B) -> Option<A> {
        self.fold(None, |max: Option<(A, B)>, x| {
            let x_val = f(&x);
            match max {
                None             => Some((x, x_val)),
                Some((y, y_val)) => if x_val > y_val {
                    Some((x, x_val))
                } else {
                    Some((y, y_val))
                }
            }
        }).map(|(x, _)| x)
    }

    /// Return the element that gives the minimum value from the
    /// specified function.
    ///
    /// # Example
    ///
    /// ```rust
    /// use core::num::SignedInt;
    ///
    /// let xs = [-3i, 0, 1, 5, -10];
    /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
    /// ```
    #[inline]
    #[unstable = "waiting for unboxed closures, just changed to take self by value"]
    fn min_by<B: Ord>(self, f: |&A| -> B) -> Option<A> {
        self.fold(None, |min: Option<(A, B)>, x| {
            let x_val = f(&x);
            match min {
                None             => Some((x, x_val)),
                Some((y, y_val)) => if x_val < y_val {
                    Some((x, x_val))
                } else {
                    Some((y, y_val))
                }
            }
        }).map(|(x, _)| x)
    }
}

#[unstable = "trait is unstable"]
impl<A, I> IteratorExt<A> for I where I: Iterator<A> {}

/// A range iterator able to yield elements from both ends
///
/// A `DoubleEndedIterator` can be thought of as a deque in that `next()` and `next_back()` exhaust
/// elements from the *same* range, and do not work independently of each other.
#[unstable = "recently split into two traits"]
pub trait DoubleEndedIterator<A>: Iterator<A> {
    /// Yield an element from the end of the range, returning `None` if the range is empty.
    fn next_back(&mut self) -> Option<A>;
}

/// Extension methods for double-ended iterators.
#[unstable = "new extension trait convention"]
pub trait DoubleEndedIteratorExt<A>: DoubleEndedIterator<A> {
    /// Change the direction of the iterator
    ///
    /// The flipped iterator swaps the ends on an iterator that can already
    /// be iterated from the front and from the back.
    ///
    ///
    /// If the iterator also implements RandomAccessIterator, the flipped
    /// iterator is also random access, with the indices starting at the back
    /// of the original iterator.
    ///
    /// Note: Random access with flipped indices still only applies to the first
    /// `uint::MAX` elements of the original iterator.
    #[inline]
    #[stable]
    fn rev(self) -> Rev<Self> {
        Rev{iter: self}
    }
}

#[unstable = "trait is unstable"]
impl<A, I> DoubleEndedIteratorExt<A> for I where I: DoubleEndedIterator<A> {}

/// A double-ended iterator yielding mutable references
#[experimental = "not widely used"]
pub trait MutableDoubleEndedIterator {
    // FIXME: #5898: should be called `reverse`
    /// Use an iterator to reverse a container in-place
    fn reverse_(&mut self);
}

#[experimental = "trait is experimental"]
impl<'a, A:'a, T: DoubleEndedIterator<&'a mut A>> MutableDoubleEndedIterator for T {
    // FIXME: #5898: should be called `reverse`
    /// Use an iterator to reverse a container in-place
    fn reverse_(&mut self) {
        loop {
            match (self.next(), self.next_back()) {
                (Some(x), Some(y)) => mem::swap(x, y),
                _ => break
            }
        }
    }
}

/// An object implementing random access indexing by `uint`
///
/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
/// Calling `next()` or `next_back()` on a `RandomAccessIterator`
/// reduces the indexable range accordingly. That is, `it.idx(1)` will become `it.idx(0)`
/// after `it.next()` is called.
#[experimental = "not widely used, may be better decomposed into Index and ExactSizeIterator"]
pub trait RandomAccessIterator<A>: Iterator<A> {
    /// Return the number of indexable elements. At most `std::uint::MAX`
    /// elements are indexable, even if the iterator represents a longer range.
    fn indexable(&self) -> uint;

    /// Return an element at an index, or `None` if the index is out of bounds
    fn idx(&mut self, index: uint) -> Option<A>;
}

/// An iterator that knows its exact length
///
/// This trait is a helper for iterators like the vector iterator, so that
/// it can support double-ended enumeration.
///
/// `Iterator::size_hint` *must* return the exact size of the iterator.
/// Note that the size must fit in `uint`.
#[unstable = "could move DoubleEndedIterator bound onto rposition with method-level where clauses"]
pub trait ExactSizeIterator<A> : DoubleEndedIterator<A> {
    /// Return the index of the last element satisfying the specified predicate
    ///
    /// If no element matches, None is returned.
    #[inline]
    fn rposition(&mut self, predicate: |A| -> bool) -> Option<uint> {
        let len = self.len();
        for i in range(0, len).rev() {
            if predicate(self.next_back().expect("rposition: incorrect ExactSizeIterator")) {
                return Some(i);
            }
        }
        None
    }

    #[inline]
    /// Return the exact length of the iterator.
    fn len(&self) -> uint {
        let (lower, upper) = self.size_hint();
        // Note: This assertion is overly defensive, but it checks the invariant
        // guaranteed by the trait. If this trait were rust-internal,
        // we could use debug_assert!; assert_eq! will check all Rust user
        // implementations too.
        assert_eq!(upper, Some(lower));
        lower
    }
}

// All adaptors that preserve the size of the wrapped iterator are fine
// Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
#[unstable = "trait is unstable"]
impl<A, T: ExactSizeIterator<A>> ExactSizeIterator<(uint, A)> for Enumerate<T> {}
#[unstable = "trait is unstable"]
impl<'a, A, T: ExactSizeIterator<A>> ExactSizeIterator<A> for Inspect<'a, A, T> {}
#[unstable = "trait is unstable"]
impl<A, T: ExactSizeIterator<A>> ExactSizeIterator<A> for Rev<T> {}
#[unstable = "trait is unstable"]
impl<'a, A, B, T: ExactSizeIterator<A>> ExactSizeIterator<B> for Map<'a, A, B, T> {}
#[unstable = "trait is unstable"]
impl<A, B, T, U> ExactSizeIterator<(A, B)> for Zip<T, U>
    where T: ExactSizeIterator<A>, U: ExactSizeIterator<B> {}

/// An double-ended iterator with the direction inverted
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Rev<T> {
    iter: T
}

#[unstable = "trait is unstable"]
impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Rev<T> {
    #[inline]
    fn next(&mut self) -> Option<A> { self.iter.next_back() }
    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
}

#[unstable = "trait is unstable"]
impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Rev<T> {
    #[inline]
    fn next_back(&mut self) -> Option<A> { self.iter.next() }
}

#[experimental = "trait is experimental"]
impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
    for Rev<T> {
    #[inline]
    fn indexable(&self) -> uint { self.iter.indexable() }
    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        let amt = self.indexable();
        self.iter.idx(amt - index - 1)
    }
}

/// A mutable reference to an iterator
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct ByRef<'a, T:'a> {
    iter: &'a mut T
}

#[unstable = "trait is unstable"]
impl<'a, A, T: Iterator<A>+'a> Iterator<A> for ByRef<'a, T> {
    #[inline]
    fn next(&mut self) -> Option<A> { self.iter.next() }
    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
}

#[unstable = "trait is unstable"]
impl<'a, A, T: DoubleEndedIterator<A>+'a> DoubleEndedIterator<A> for ByRef<'a, T> {
    #[inline]
    fn next_back(&mut self) -> Option<A> { self.iter.next_back() }
}

/// A trait for iterators over elements which can be added together
#[experimental = "needs to be re-evaluated as part of numerics reform"]
pub trait AdditiveIterator<A> {
    /// Iterates over the entire iterator, summing up all the elements
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::AdditiveIterator;
    ///
    /// let a = [1i, 2, 3, 4, 5];
    /// let mut it = a.iter().map(|&x| x);
    /// assert!(it.sum() == 15);
    /// ```
    fn sum(self) -> A;
}

macro_rules! impl_additive {
    ($A:ty, $init:expr) => {
        #[experimental = "trait is experimental"]
        impl<T: Iterator<$A>> AdditiveIterator<$A> for T {
            #[inline]
            fn sum(self) -> $A {
                self.fold($init, |acc, x| acc + x)
            }
        }
    };
}
impl_additive!(i8,   0)
impl_additive!(i16,  0)
impl_additive!(i32,  0)
impl_additive!(i64,  0)
impl_additive!(int,  0)
impl_additive!(u8,   0)
impl_additive!(u16,  0)
impl_additive!(u32,  0)
impl_additive!(u64,  0)
impl_additive!(uint, 0)
impl_additive!(f32,  0.0)
impl_additive!(f64,  0.0)

/// A trait for iterators over elements which can be multiplied together.
#[experimental = "needs to be re-evaluated as part of numerics reform"]
pub trait MultiplicativeIterator<A> {
    /// Iterates over the entire iterator, multiplying all the elements
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::{count, MultiplicativeIterator};
    ///
    /// fn factorial(n: uint) -> uint {
    ///     count(1u, 1).take_while(|&i| i <= n).product()
    /// }
    /// assert!(factorial(0) == 1);
    /// assert!(factorial(1) == 1);
    /// assert!(factorial(5) == 120);
    /// ```
    fn product(self) -> A;
}

macro_rules! impl_multiplicative {
    ($A:ty, $init:expr) => {
        #[experimental = "trait is experimental"]
        impl<T: Iterator<$A>> MultiplicativeIterator<$A> for T {
            #[inline]
            fn product(self) -> $A {
                self.fold($init, |acc, x| acc * x)
            }
        }
    };
}
impl_multiplicative!(i8,   1)
impl_multiplicative!(i16,  1)
impl_multiplicative!(i32,  1)
impl_multiplicative!(i64,  1)
impl_multiplicative!(int,  1)
impl_multiplicative!(u8,   1)
impl_multiplicative!(u16,  1)
impl_multiplicative!(u32,  1)
impl_multiplicative!(u64,  1)
impl_multiplicative!(uint, 1)
impl_multiplicative!(f32,  1.0)
impl_multiplicative!(f64,  1.0)

/// A trait for iterators over elements which can be compared to one another.
#[unstable = "recently renamed for new extension trait conventions"]
pub trait IteratorOrdExt<A> {
    /// Consumes the entire iterator to return the maximum element.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// assert!(a.iter().max().unwrap() == &5);
    /// ```
    fn max(self) -> Option<A>;

    /// Consumes the entire iterator to return the minimum element.
    ///
    /// # Example
    ///
    /// ```rust
    /// let a = [1i, 2, 3, 4, 5];
    /// assert!(a.iter().min().unwrap() == &1);
    /// ```
    fn min(self) -> Option<A>;

    /// `min_max` finds the minimum and maximum elements in the iterator.
    ///
    /// The return type `MinMaxResult` is an enum of three variants:
    ///
    /// - `NoElements` if the iterator is empty.
    /// - `OneElement(x)` if the iterator has exactly one element.
    /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two
    ///    values are equal if and only if there is more than one
    ///    element in the iterator and all elements are equal.
    ///
    /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
    /// and so is faster than calling `min` and `max` separately which does `2 * n` comparisons.
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::{NoElements, OneElement, MinMax};
    ///
    /// let v: [int, ..0] = [];
    /// assert_eq!(v.iter().min_max(), NoElements);
    ///
    /// let v = [1i];
    /// assert!(v.iter().min_max() == OneElement(&1));
    ///
    /// let v = [1i, 2, 3, 4, 5];
    /// assert!(v.iter().min_max() == MinMax(&1, &5));
    ///
    /// let v = [1i, 2, 3, 4, 5, 6];
    /// assert!(v.iter().min_max() == MinMax(&1, &6));
    ///
    /// let v = [1i, 1, 1, 1];
    /// assert!(v.iter().min_max() == MinMax(&1, &1));
    /// ```
    fn min_max(self) -> MinMaxResult<A>;
}

#[unstable = "trait is unstable"]
impl<A: Ord, T: Iterator<A>> IteratorOrdExt<A> for T {
    #[inline]
    fn max(self) -> Option<A> {
        self.fold(None, |max, x| {
            match max {
                None    => Some(x),
                Some(y) => Some(cmp::max(x, y))
            }
        })
    }

    #[inline]
    fn min(self) -> Option<A> {
        self.fold(None, |min, x| {
            match min {
                None    => Some(x),
                Some(y) => Some(cmp::min(x, y))
            }
        })
    }

    fn min_max(mut self) -> MinMaxResult<A> {
        let (mut min, mut max) = match self.next() {
            None => return NoElements,
            Some(x) => {
                match self.next() {
                    None => return OneElement(x),
                    Some(y) => if x < y {(x, y)} else {(y,x)}
                }
            }
        };

        loop {
            // `first` and `second` are the two next elements we want to look at.
            // We first compare `first` and `second` (#1). The smaller one is then compared to
            // current minimum (#2). The larger one is compared to current maximum (#3). This
            // way we do 3 comparisons for 2 elements.
            let first = match self.next() {
                None => break,
                Some(x) => x
            };
            let second = match self.next() {
                None => {
                    if first < min {
                        min = first;
                    } else if first > max {
                        max = first;
                    }
                    break;
                }
                Some(x) => x
            };
            if first < second {
                if first < min {min = first;}
                if max < second {max = second;}
            } else {
                if second < min {min = second;}
                if max < first {max = first;}
            }
        }

        MinMax(min, max)
    }
}

/// `MinMaxResult` is an enum returned by `min_max`. See `IteratorOrdExt::min_max` for more detail.
#[deriving(Clone, PartialEq, Show)]
#[unstable = "waiting on namespaced enum conventions"]
pub enum MinMaxResult<T> {
    /// Empty iterator
    NoElements,

    /// Iterator with one element, so the minimum and maximum are the same
    OneElement(T),

    /// More than one element in the iterator, the first element is not larger than the second
    MinMax(T, T)
}

#[stable]
impl<T: Clone> MinMaxResult<T> {
    /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option` has variant
    /// `None` if and only if the `MinMaxResult` has variant `NoElements`. Otherwise variant
    /// `Some(x,y)` is returned where `x <= y`. If `MinMaxResult` has variant `OneElement(x)`,
    /// performing this operation will make one clone of `x`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::{NoElements, OneElement, MinMax, MinMaxResult};
    ///
    /// let r: MinMaxResult<int> = NoElements;
    /// assert_eq!(r.into_option(), None)
    ///
    /// let r = OneElement(1i);
    /// assert_eq!(r.into_option(), Some((1,1)));
    ///
    /// let r = MinMax(1i,2i);
    /// assert_eq!(r.into_option(), Some((1,2)));
    /// ```
    pub fn into_option(self) -> Option<(T,T)> {
        match self {
            NoElements => None,
            OneElement(x) => Some((x.clone(), x)),
            MinMax(x, y) => Some((x, y))
        }
    }
}

/// A trait for iterators that contain cloneable elements
#[unstable = "recently renamed for extension trait conventions"]
pub trait IteratorCloneExt<A> {
    /// Creates an iterator that clones the elements it yields. Useful for converting an
    /// Iterator<&T> to an Iterator<T>.
    fn cloned(self) -> Cloned<Self>;
}

#[unstable = "trait is unstable"]
impl<A: Clone, D: Deref<A>, I: Iterator<D>> IteratorCloneExt<A> for I {
    fn cloned(self) -> Cloned<I> {
        Cloned { it: self }
    }
}

/// An iterator that clones the elements of an underlying iterator
pub struct Cloned<I> {
    it: I,
}

impl<A: Clone, D: Deref<A>, I: Iterator<D>> Iterator<A> for Cloned<I> {
    fn next(&mut self) -> Option<A> {
        self.it.next().cloned()
    }

    fn size_hint(&self) -> (uint, Option<uint>) {
        self.it.size_hint()
    }
}

impl<A: Clone, D: Deref<A>, I: DoubleEndedIterator<D>>
        DoubleEndedIterator<A> for Cloned<I> {
    fn next_back(&mut self) -> Option<A> {
        self.it.next_back().cloned()
    }
}

#[unstable = "trait is unstable"]
impl<A: Clone, D: Deref<A>, I: ExactSizeIterator<D>> ExactSizeIterator<A> for Cloned<I> {}

#[unstable = "recently renamed for extension trait conventions"]
/// An extension trait for cloneable iterators.
pub trait CloneIteratorExt {
    /// Repeats an iterator endlessly
    ///
    /// # Example
    ///
    /// ```rust
    /// use std::iter::{CloneIteratorExt, count};
    ///
    /// let a = count(1i,1i).take(1);
    /// let mut cy = a.cycle();
    /// assert_eq!(cy.next(), Some(1));
    /// assert_eq!(cy.next(), Some(1));
    /// ```
    #[stable]
    fn cycle(self) -> Cycle<Self>;
}

impl<A, I> CloneIteratorExt for I where I: Iterator<A> + Clone {
    #[inline]
    fn cycle(self) -> Cycle<I> {
        Cycle{orig: self.clone(), iter: self}
    }
}

/// An iterator that repeats endlessly
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Cycle<T> {
    orig: T,
    iter: T,
}

#[unstable = "trait is unstable"]
impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        match self.iter.next() {
            None => { self.iter = self.orig.clone(); self.iter.next() }
            y => y
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // the cycle iterator is either empty or infinite
        match self.orig.size_hint() {
            sz @ (0, Some(0)) => sz,
            (0, _) => (0, None),
            _ => (uint::MAX, None)
        }
    }
}

#[experimental = "trait is experimental"]
impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
    #[inline]
    fn indexable(&self) -> uint {
        if self.orig.indexable() > 0 {
            uint::MAX
        } else {
            0
        }
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        let liter = self.iter.indexable();
        let lorig = self.orig.indexable();
        if lorig == 0 {
            None
        } else if index < liter {
            self.iter.idx(index)
        } else {
            self.orig.idx((index - liter) % lorig)
        }
    }
}

/// An iterator which strings two iterators together
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Chain<T, U> {
    a: T,
    b: U,
    flag: bool,
}

#[unstable = "trait is unstable"]
impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.flag {
            self.b.next()
        } else {
            match self.a.next() {
                Some(x) => return Some(x),
                _ => ()
            }
            self.flag = true;
            self.b.next()
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (a_lower, a_upper) = self.a.size_hint();
        let (b_lower, b_upper) = self.b.size_hint();

        let lower = a_lower.saturating_add(b_lower);

        let upper = match (a_upper, b_upper) {
            (Some(x), Some(y)) => x.checked_add(y),
            _ => None
        };

        (lower, upper)
    }
}

#[unstable = "trait is unstable"]
impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
for Chain<T, U> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        match self.b.next_back() {
            Some(x) => Some(x),
            None => self.a.next_back()
        }
    }
}

#[experimental = "trait is experimental"]
impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
for Chain<T, U> {
    #[inline]
    fn indexable(&self) -> uint {
        let (a, b) = (self.a.indexable(), self.b.indexable());
        a.saturating_add(b)
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        let len = self.a.indexable();
        if index < len {
            self.a.idx(index)
        } else {
            self.b.idx(index - len)
        }
    }
}

/// An iterator which iterates two other iterators simultaneously
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Zip<T, U> {
    a: T,
    b: U
}

#[unstable = "trait is unstable"]
impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> {
    #[inline]
    fn next(&mut self) -> Option<(A, B)> {
        match self.a.next() {
            None => None,
            Some(x) => match self.b.next() {
                None => None,
                Some(y) => Some((x, y))
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (a_lower, a_upper) = self.a.size_hint();
        let (b_lower, b_upper) = self.b.size_hint();

        let lower = cmp::min(a_lower, b_lower);

        let upper = match (a_upper, b_upper) {
            (Some(x), Some(y)) => Some(cmp::min(x,y)),
            (Some(x), None) => Some(x),
            (None, Some(y)) => Some(y),
            (None, None) => None
        };

        (lower, upper)
    }
}

#[unstable = "trait is unstable"]
impl<A, B, T: ExactSizeIterator<A>, U: ExactSizeIterator<B>> DoubleEndedIterator<(A, B)>
for Zip<T, U> {
    #[inline]
    fn next_back(&mut self) -> Option<(A, B)> {
        let a_sz = self.a.len();
        let b_sz = self.b.len();
        if a_sz != b_sz {
            // Adjust a, b to equal length
            if a_sz > b_sz {
                for _ in range(0, a_sz - b_sz) { self.a.next_back(); }
            } else {
                for _ in range(0, b_sz - a_sz) { self.b.next_back(); }
            }
        }
        match (self.a.next_back(), self.b.next_back()) {
            (Some(x), Some(y)) => Some((x, y)),
            (None, None) => None,
            _ => unreachable!(),
        }
    }
}

#[experimental = "trait is experimental"]
impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>>
RandomAccessIterator<(A, B)> for Zip<T, U> {
    #[inline]
    fn indexable(&self) -> uint {
        cmp::min(self.a.indexable(), self.b.indexable())
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<(A, B)> {
        match self.a.idx(index) {
            None => None,
            Some(x) => match self.b.idx(index) {
                None => None,
                Some(y) => Some((x, y))
            }
        }
    }
}

/// An iterator which maps the values of `iter` with `f`
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Map<'a, A, B, T> {
    iter: T,
    f: |A|: 'a -> B
}

impl<'a, A, B, T> Map<'a, A, B, T> {
    #[inline]
    fn do_map(&mut self, elt: Option<A>) -> Option<B> {
        match elt {
            Some(a) => Some((self.f)(a)),
            _ => None
        }
    }
}

#[unstable = "trait is unstable"]
impl<'a, A, B, T: Iterator<A>> Iterator<B> for Map<'a, A, B, T> {
    #[inline]
    fn next(&mut self) -> Option<B> {
        let next = self.iter.next();
        self.do_map(next)
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        self.iter.size_hint()
    }
}

#[unstable = "trait is unstable"]
impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B> for Map<'a, A, B, T> {
    #[inline]
    fn next_back(&mut self) -> Option<B> {
        let next = self.iter.next_back();
        self.do_map(next)
    }
}

#[experimental = "trait is experimental"]
impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> for Map<'a, A, B, T> {
    #[inline]
    fn indexable(&self) -> uint {
        self.iter.indexable()
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<B> {
        let elt = self.iter.idx(index);
        self.do_map(elt)
    }
}

/// An iterator which filters the elements of `iter` with `predicate`
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Filter<'a, A, T> {
    iter: T,
    predicate: |&A|: 'a -> bool
}

#[unstable = "trait is unstable"]
impl<'a, A, T: Iterator<A>> Iterator<A> for Filter<'a, A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        for x in self.iter {
            if (self.predicate)(&x) {
                return Some(x);
            } else {
                continue
            }
        }
        None
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper) // can't know a lower bound, due to the predicate
    }
}

#[unstable = "trait is unstable"]
impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        for x in self.iter.by_ref().rev() {
            if (self.predicate)(&x) {
                return Some(x);
            }
        }
        None
    }
}

/// An iterator which uses `f` to both filter and map elements from `iter`
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct FilterMap<'a, A, B, T> {
    iter: T,
    f: |A|: 'a -> Option<B>
}

#[unstable = "trait is unstable"]
impl<'a, A, B, T: Iterator<A>> Iterator<B> for FilterMap<'a, A, B, T> {
    #[inline]
    fn next(&mut self) -> Option<B> {
        for x in self.iter {
            match (self.f)(x) {
                Some(y) => return Some(y),
                None => ()
            }
        }
        None
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper) // can't know a lower bound, due to the predicate
    }
}

#[unstable = "trait is unstable"]
impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B>
for FilterMap<'a, A, B, T> {
    #[inline]
    fn next_back(&mut self) -> Option<B> {
        for x in self.iter.by_ref().rev() {
            match (self.f)(x) {
                Some(y) => return Some(y),
                None => ()
            }
        }
        None
    }
}

/// An iterator which yields the current count and the element during iteration
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Enumerate<T> {
    iter: T,
    count: uint
}

#[unstable = "trait is unstable"]
impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
    #[inline]
    fn next(&mut self) -> Option<(uint, A)> {
        match self.iter.next() {
            Some(a) => {
                let ret = Some((self.count, a));
                self.count += 1;
                ret
            }
            _ => None
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        self.iter.size_hint()
    }
}

#[unstable = "trait is unstable"]
impl<A, T: ExactSizeIterator<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
    #[inline]
    fn next_back(&mut self) -> Option<(uint, A)> {
        match self.iter.next_back() {
            Some(a) => {
                let len = self.iter.len();
                Some((self.count + len, a))
            }
            _ => None
        }
    }
}

#[experimental = "trait is experimental"]
impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
    #[inline]
    fn indexable(&self) -> uint {
        self.iter.indexable()
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<(uint, A)> {
        match self.iter.idx(index) {
            Some(a) => Some((self.count + index, a)),
            _ => None,
        }
    }
}

/// An iterator with a `peek()` that returns an optional reference to the next element.
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Peekable<A, T> {
    iter: T,
    peeked: Option<A>,
}

#[unstable = "trait is unstable"]
impl<A, T: Iterator<A>> Iterator<A> for Peekable<A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.peeked.is_some() { self.peeked.take() }
        else { self.iter.next() }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (lo, hi) = self.iter.size_hint();
        if self.peeked.is_some() {
            let lo = lo.saturating_add(1);
            let hi = match hi {
                Some(x) => x.checked_add(1),
                None => None
            };
            (lo, hi)
        } else {
            (lo, hi)
        }
    }
}

#[stable]
impl<'a, A, T: Iterator<A>> Peekable<A, T> {
    /// Return a reference to the next element of the iterator with out advancing it,
    /// or None if the iterator is exhausted.
    #[inline]
    pub fn peek(&'a mut self) -> Option<&'a A> {
        if self.peeked.is_none() {
            self.peeked = self.iter.next();
        }
        match self.peeked {
            Some(ref value) => Some(value),
            None => None,
        }
    }

    /// Check whether peekable iterator is empty or not.
    #[inline]
    pub fn is_empty(&mut self) -> bool {
        self.peek().is_none()
    }
}

/// An iterator which rejects elements while `predicate` is true
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct SkipWhile<'a, A, T> {
    iter: T,
    flag: bool,
    predicate: |&A|: 'a -> bool
}

#[unstable = "trait is unstable"]
impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        for x in self.iter {
            if self.flag || !(self.predicate)(&x) {
                self.flag = true;
                return Some(x);
            }
        }
        None
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper) // can't know a lower bound, due to the predicate
    }
}

/// An iterator which only accepts elements while `predicate` is true
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct TakeWhile<'a, A, T> {
    iter: T,
    flag: bool,
    predicate: |&A|: 'a -> bool
}

#[unstable = "trait is unstable"]
impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.flag {
            None
        } else {
            match self.iter.next() {
                Some(x) => {
                    if (self.predicate)(&x) {
                        Some(x)
                    } else {
                        self.flag = true;
                        None
                    }
                }
                None => None
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper) // can't know a lower bound, due to the predicate
    }
}

/// An iterator which skips over `n` elements of `iter`.
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Skip<T> {
    iter: T,
    n: uint
}

#[unstable = "trait is unstable"]
impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        let mut next = self.iter.next();
        if self.n == 0 {
            next
        } else {
            let mut n = self.n;
            while n > 0 {
                n -= 1;
                match next {
                    Some(_) => {
                        next = self.iter.next();
                        continue
                    }
                    None => {
                        self.n = 0;
                        return None
                    }
                }
            }
            self.n = 0;
            next
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (lower, upper) = self.iter.size_hint();

        let lower = lower.saturating_sub(self.n);

        let upper = match upper {
            Some(x) => Some(x.saturating_sub(self.n)),
            None => None
        };

        (lower, upper)
    }
}

#[experimental = "trait is experimental"]
impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
    #[inline]
    fn indexable(&self) -> uint {
        self.iter.indexable().saturating_sub(self.n)
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        if index >= self.indexable() {
            None
        } else {
            self.iter.idx(index + self.n)
        }
    }
}

/// An iterator which only iterates over the first `n` iterations of `iter`.
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Take<T> {
    iter: T,
    n: uint
}

#[unstable = "trait is unstable"]
impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.n != 0 {
            self.n -= 1;
            self.iter.next()
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (lower, upper) = self.iter.size_hint();

        let lower = cmp::min(lower, self.n);

        let upper = match upper {
            Some(x) if x < self.n => Some(x),
            _ => Some(self.n)
        };

        (lower, upper)
    }
}

#[experimental = "trait is experimental"]
impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
    #[inline]
    fn indexable(&self) -> uint {
        cmp::min(self.iter.indexable(), self.n)
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        if index >= self.n {
            None
        } else {
            self.iter.idx(index)
        }
    }
}

/// An iterator to maintain state while iterating another iterator
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[unstable = "waiting for unboxed closures"]
pub struct Scan<'a, A, B, T, St> {
    iter: T,
    f: |&mut St, A|: 'a -> Option<B>,

    /// The current internal state to be passed to the closure next.
    pub state: St,
}

#[unstable = "trait is unstable"]
impl<'a, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'a, A, B, T, St> {
    #[inline]
    fn next(&mut self) -> Option<B> {
        self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper) // can't know a lower bound, due to the scan function
    }
}

/// An iterator that maps each element to an iterator,
/// and yields the elements of the produced iterators
///
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[unstable = "waiting for unboxed closures"]
pub struct FlatMap<'a, A, T, U> {
    iter: T,
    f: |A|: 'a -> U,
    frontiter: Option<U>,
    backiter: Option<U>,
}

#[unstable = "trait is unstable"]
impl<'a, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for FlatMap<'a, A, T, U> {
    #[inline]
    fn next(&mut self) -> Option<B> {
        loop {
            for inner in self.frontiter.iter_mut() {
                for x in *inner {
                    return Some(x)
                }
            }
            match self.iter.next().map(|x| (self.f)(x)) {
                None => return self.backiter.as_mut().and_then(|it| it.next()),
                next => self.frontiter = next,
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
        let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
        let lo = flo.saturating_add(blo);
        match (self.iter.size_hint(), fhi, bhi) {
            ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
            _ => (lo, None)
        }
    }
}

#[unstable = "trait is unstable"]
impl<'a,
     A, T: DoubleEndedIterator<A>,
     B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B>
     for FlatMap<'a, A, T, U> {
    #[inline]
    fn next_back(&mut self) -> Option<B> {
        loop {
            for inner in self.backiter.iter_mut() {
                match inner.next_back() {
                    None => (),
                    y => return y
                }
            }
            match self.iter.next_back().map(|x| (self.f)(x)) {
                None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
                next => self.backiter = next,
            }
        }
    }
}

/// An iterator that yields `None` forever after the underlying iterator
/// yields `None` once.
#[deriving(Clone)]
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[stable]
pub struct Fuse<T> {
    iter: T,
    done: bool
}

#[unstable = "trait is unstable"]
impl<A, T: Iterator<A>> Iterator<A> for Fuse<T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.done {
            None
        } else {
            match self.iter.next() {
                None => {
                    self.done = true;
                    None
                }
                x => x
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        if self.done {
            (0, Some(0))
        } else {
            self.iter.size_hint()
        }
    }
}

#[unstable = "trait is unstable"]
impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Fuse<T> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        if self.done {
            None
        } else {
            match self.iter.next_back() {
                None => {
                    self.done = true;
                    None
                }
                x => x
            }
        }
    }
}

// Allow RandomAccessIterators to be fused without affecting random-access behavior
#[experimental = "trait is experimental"]
impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
    #[inline]
    fn indexable(&self) -> uint {
        self.iter.indexable()
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        self.iter.idx(index)
    }
}

#[experimental = "seems marginal"]
impl<T> Fuse<T> {
    /// Resets the fuse such that the next call to .next() or .next_back() will
    /// call the underlying iterator again even if it previously returned None.
    #[inline]
    pub fn reset_fuse(&mut self) {
        self.done = false
    }
}

/// An iterator that calls a function with a reference to each
/// element before yielding it.
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[unstable = "waiting for unboxed closures"]
pub struct Inspect<'a, A, T> {
    iter: T,
    f: |&A|: 'a
}

impl<'a, A, T> Inspect<'a, A, T> {
    #[inline]
    fn do_inspect(&mut self, elt: Option<A>) -> Option<A> {
        match elt {
            Some(ref a) => (self.f)(a),
            None => ()
        }

        elt
    }
}

#[unstable = "trait is unstable"]
impl<'a, A, T: Iterator<A>> Iterator<A> for Inspect<'a, A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        let next = self.iter.next();
        self.do_inspect(next)
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        self.iter.size_hint()
    }
}

#[unstable = "trait is unstable"]
impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A>
for Inspect<'a, A, T> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        let next = self.iter.next_back();
        self.do_inspect(next)
    }
}

#[experimental = "trait is experimental"]
impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
for Inspect<'a, A, T> {
    #[inline]
    fn indexable(&self) -> uint {
        self.iter.indexable()
    }

    #[inline]
    fn idx(&mut self, index: uint) -> Option<A> {
        let element = self.iter.idx(index);
        self.do_inspect(element)
    }
}

/// An iterator which just modifies the contained state throughout iteration.
#[experimental]
pub struct Unfold<'a, A, St> {
    f: |&mut St|: 'a -> Option<A>,
    /// Internal state that will be yielded on the next iteration
    pub state: St,
}

#[experimental]
impl<'a, A, St> Unfold<'a, A, St> {
    /// Creates a new iterator with the specified closure as the "iterator
    /// function" and an initial state to eventually pass to the iterator
    #[inline]
    pub fn new<'a>(initial_state: St, f: |&mut St|: 'a -> Option<A>)
               -> Unfold<'a, A, St> {
        Unfold {
            f: f,
            state: initial_state
        }
    }
}

#[experimental]
impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        (self.f)(&mut self.state)
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // no possible known bounds at this point
        (0, None)
    }
}

/// An infinite iterator starting at `start` and advancing by `step` with each
/// iteration
#[deriving(Clone)]
#[unstable = "may be renamed"]
pub struct Counter<A> {
    /// The current state the counter is at (next value to be yielded)
    state: A,
    /// The amount that this iterator is stepping by
    step: A,
}

/// Creates a new counter with the specified start/step
#[inline]
#[unstable = "may be renamed"]
pub fn count<A>(start: A, step: A) -> Counter<A> {
    Counter{state: start, step: step}
}

#[unstable = "trait is unstable"]
impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        let result = self.state.clone();
        self.state = self.state + self.step;
        Some(result)
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        (uint::MAX, None) // Too bad we can't specify an infinite lower bound
    }
}

/// An iterator over the range [start, stop)
#[deriving(Clone)]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub struct Range<A> {
    state: A,
    stop: A,
    one: A,
}

/// Returns an iterator over the given range [start, stop) (that is, starting
/// at start (inclusive), and ending at stop (exclusive)).
///
/// # Example
///
/// ```rust
/// let array = [0, 1, 2, 3, 4];
///
/// for i in range(0, 5u) {
///     println!("{}", i);
///     assert_eq!(i,  array[i]);
/// }
/// ```
#[inline]
pub fn range<A: Int>(start: A, stop: A) -> Range<A> {
    Range {
        state: start,
        stop: stop,
        one: Int::one(),
    }
}

// FIXME: #10414: Unfortunate type bound
#[unstable = "trait is unstable"]
impl<A: Int + ToPrimitive> Iterator<A> for Range<A> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.state < self.stop {
            let result = self.state.clone();
            self.state = self.state + self.one;
            Some(result)
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // This first checks if the elements are representable as i64. If they aren't, try u64 (to
        // handle cases like range(huge, huger)). We don't use uint/int because the difference of
        // the i64/u64 might lie within their range.
        let bound = match self.state.to_i64() {
            Some(a) => {
                let sz = self.stop.to_i64().map(|b| b.checked_sub(a));
                match sz {
                    Some(Some(bound)) => bound.to_uint(),
                    _ => None,
                }
            },
            None => match self.state.to_u64() {
                Some(a) => {
                    let sz = self.stop.to_u64().map(|b| b.checked_sub(a));
                    match sz {
                        Some(Some(bound)) => bound.to_uint(),
                        _ => None
                    }
                },
                None => None
            }
        };

        match bound {
            Some(b) => (b, Some(b)),
            // Standard fallback for unbounded/unrepresentable bounds
            None => (0, None)
        }
    }
}

/// `Int` is required to ensure the range will be the same regardless of
/// the direction it is consumed.
#[unstable = "trait is unstable"]
impl<A: Int + ToPrimitive> DoubleEndedIterator<A> for Range<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        if self.stop > self.state {
            self.stop = self.stop - self.one;
            Some(self.stop.clone())
        } else {
            None
        }
    }
}

/// An iterator over the range [start, stop]
#[deriving(Clone)]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub struct RangeInclusive<A> {
    range: Range<A>,
    done: bool,
}

/// Return an iterator over the range [start, stop]
#[inline]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub fn range_inclusive<A: Int>(start: A, stop: A) -> RangeInclusive<A> {
    RangeInclusive {
        range: range(start, stop),
        done: false,
    }
}

#[unstable = "trait is unstable"]
impl<A: Int + ToPrimitive> Iterator<A> for RangeInclusive<A> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        match self.range.next() {
            Some(x) => Some(x),
            None => {
                if !self.done && self.range.state == self.range.stop {
                    self.done = true;
                    Some(self.range.stop.clone())
                } else {
                    None
                }
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        let (lo, hi) = self.range.size_hint();
        if self.done {
            (lo, hi)
        } else {
            let lo = lo.saturating_add(1);
            let hi = match hi {
                Some(x) => x.checked_add(1),
                None => None
            };
            (lo, hi)
        }
    }
}

#[unstable = "trait is unstable"]
impl<A: Int + ToPrimitive> DoubleEndedIterator<A> for RangeInclusive<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        if self.range.stop > self.range.state {
            let result = self.range.stop.clone();
            self.range.stop = self.range.stop - self.range.one;
            Some(result)
        } else if !self.done && self.range.state == self.range.stop {
            self.done = true;
            Some(self.range.stop.clone())
        } else {
            None
        }
    }
}

/// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
#[deriving(Clone)]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub struct RangeStep<A> {
    state: A,
    stop: A,
    step: A,
    rev: bool,
}

/// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
#[inline]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub fn range_step<A: Int>(start: A, stop: A, step: A) -> RangeStep<A> {
    let rev = step < Int::zero();
    RangeStep{state: start, stop: stop, step: step, rev: rev}
}

#[unstable = "trait is unstable"]
impl<A: Int> Iterator<A> for RangeStep<A> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
            let result = self.state;
            match self.state.checked_add(self.step) {
                Some(x) => self.state = x,
                None => self.state = self.stop.clone()
            }
            Some(result)
        } else {
            None
        }
    }
}

/// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
#[deriving(Clone)]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub struct RangeStepInclusive<A> {
    state: A,
    stop: A,
    step: A,
    rev: bool,
    done: bool,
}

/// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
#[inline]
#[unstable = "may be refactored due to numerics reform or ops reform"]
pub fn range_step_inclusive<A: Int>(start: A, stop: A, step: A) -> RangeStepInclusive<A> {
    let rev = step < Int::zero();
    RangeStepInclusive {
        state: start,
        stop: stop,
        step: step,
        rev: rev,
        done: false,
    }
}

#[unstable = "trait is unstable"]
impl<A: Int> Iterator<A> for RangeStepInclusive<A> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        if !self.done && ((self.rev && self.state >= self.stop) ||
                          (!self.rev && self.state <= self.stop)) {
            let result = self.state;
            match self.state.checked_add(self.step) {
                Some(x) => self.state = x,
                None => self.done = true
            }
            Some(result)
        } else {
            None
        }
    }
}

/// An iterator that repeats an element endlessly
#[deriving(Clone)]
#[stable]
pub struct Repeat<A> {
    element: A
}

impl<A: Clone> Repeat<A> {
    /// Create a new `Repeat` that endlessly repeats the element `elt`.
    #[inline]
    #[deprecated = "use iter::repeat instead"]
    pub fn new(elt: A) -> Repeat<A> {
        Repeat{element: elt}
    }
}

#[unstable = "trait is unstable"]
impl<A: Clone> Iterator<A> for Repeat<A> {
    #[inline]
    fn next(&mut self) -> Option<A> { self.idx(0) }
    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) { (uint::MAX, None) }
}

#[unstable = "trait is unstable"]
impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A> { self.idx(0) }
}

#[experimental = "trait is experimental"]
impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
    #[inline]
    fn indexable(&self) -> uint { uint::MAX }
    #[inline]
    fn idx(&mut self, _: uint) -> Option<A> { Some(self.element.clone()) }
}

type IterateState<'a, T> = (|T|: 'a -> T, Option<T>, bool);

/// An iterator that repeatedly applies a given function, starting
/// from a given seed value.
#[experimental]
pub type Iterate<'a, T> = Unfold<'a, T, IterateState<'a, T>>;

/// Create a new iterator that produces an infinite sequence of
/// repeated applications of the given function `f`.
#[experimental]
pub fn iterate<'a, T: Clone>(seed: T, f: |T|: 'a -> T) -> Iterate<'a, T> {
    Unfold::new((f, Some(seed), true), |st| {
        let &(ref mut f, ref mut val, ref mut first) = st;
        if *first {
            *first = false;
        } else {
            match val.take() {
                Some(x) => {
                    *val = Some((*f)(x))
                }
                None => {}
            }
        }
        val.clone()
    })
}

/// Create a new iterator that endlessly repeats the element `elt`.
#[inline]
#[stable]
pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
    Repeat{element: elt}
}

/// Functions for lexicographical ordering of sequences.
///
/// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
/// that the elements implement both `PartialEq` and `PartialOrd`.
///
/// If two sequences are equal up until the point where one ends,
/// the shorter sequence compares less.
#[experimental = "likely to be removed after cmp reform"]
pub mod order {
    use cmp;
    use cmp::{Eq, Ord, PartialOrd, PartialEq};
    use option::{Option, Some, None};
    use super::Iterator;

    /// Compare `a` and `b` for equality using `Eq`
    pub fn equals<A: Eq, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return true,
                (None, _) | (_, None) => return false,
                (Some(x), Some(y)) => if x != y { return false },
            }
        }
    }

    /// Order `a` and `b` lexicographically using `Ord`
    pub fn cmp<A: Ord, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> cmp::Ordering {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return cmp::Equal,
                (None, _   ) => return cmp::Less,
                (_   , None) => return cmp::Greater,
                (Some(x), Some(y)) => match x.cmp(&y) {
                    cmp::Equal => (),
                    non_eq => return non_eq,
                },
            }
        }
    }

    /// Order `a` and `b` lexicographically using `PartialOrd`
    pub fn partial_cmp<A: PartialOrd, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S)
            -> Option<cmp::Ordering> {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return Some(cmp::Equal),
                (None, _   ) => return Some(cmp::Less),
                (_   , None) => return Some(cmp::Greater),
                (Some(x), Some(y)) => match x.partial_cmp(&y) {
                    Some(cmp::Equal) => (),
                    non_eq => return non_eq,
                },
            }
        }
    }

    /// Compare `a` and `b` for equality (Using partial equality, `PartialEq`)
    pub fn eq<A: PartialEq, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return true,
                (None, _) | (_, None) => return false,
                (Some(x), Some(y)) => if !x.eq(&y) { return false },
            }
        }
    }

    /// Compare `a` and `b` for nonequality (Using partial equality, `PartialEq`)
    pub fn ne<A: PartialEq, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return false,
                (None, _) | (_, None) => return true,
                (Some(x), Some(y)) => if x.ne(&y) { return true },
            }
        }
    }

    /// Return `a` < `b` lexicographically (Using partial order, `PartialOrd`)
    pub fn lt<A: PartialOrd, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return false,
                (None, _   ) => return true,
                (_   , None) => return false,
                (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
            }
        }
    }

    /// Return `a` <= `b` lexicographically (Using partial order, `PartialOrd`)
    pub fn le<A: PartialOrd, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return true,
                (None, _   ) => return true,
                (_   , None) => return false,
                (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
            }
        }
    }

    /// Return `a` > `b` lexicographically (Using partial order, `PartialOrd`)
    pub fn gt<A: PartialOrd, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return false,
                (None, _   ) => return false,
                (_   , None) => return true,
                (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
            }
        }
    }

    /// Return `a` >= `b` lexicographically (Using partial order, `PartialOrd`)
    pub fn ge<A: PartialOrd, T: Iterator<A>, S: Iterator<A>>(mut a: T, mut b: S) -> bool {
        loop {
            match (a.next(), b.next()) {
                (None, None) => return true,
                (None, _   ) => return false,
                (_   , None) => return true,
                (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },
            }
        }
    }
}


text:
Reggae Recording Artist OmariBanks11 "Move On" Album Listed #4 on Popular German Riddim Magazine
Created: Sunday, January 03 2016 8:25pm
Reggae recording artist Omari Banks is humbled and grateful to fans and music industry insiders for an amazing year culminating with Omari's "Move On" Album listed #4 on the top ten reggae albums of 2015 of the latest issue of popular prestigious German Riddim Magazine.
"It is humbling and the honor isn't lost of me. Every song has become a part of me, so to recognize my work, is to recognize my soul." stated Omari.
The artist's "Move On" album was also named in Kenya's Juiced Today magazine as Best of 2015 among other notable music piers. "I love Kenya, I can't wait to make my way to Africa. I know that touching and feeling the soil of the motherland will inspire me. Thank you to all my fans that have shown me love via social media, I hope to see you soon".
These honors round off an impressive year for Omari who is still reeling from his European tour as part of Grammy nominated Morgan Heritage "Strictly Roots European Tour", his role an one of Anguilla's ambassador at Toronto Fashion Week in Canada, and the recent cover of True Anguilla magazine. True ANGUILLA is a full-colour, complimentary guide to Anguilla that is freely distributed all over Anguilla and in neighboring St. Maarten/St. Martin. The compact, colourful, attractive and extremely practical magazine has been designed to be an essential guide to the island.
"To keep saying that I am thankful is an understatement, but I have to repeat it. I have lots in store for the new year. New music, more shows and a few surprises. Thank you to everyone who has embarked on this musical journey with me, from the bloggers, to fans, my team to the media, thank you for validating my calling"
Get the album

redpajama_set_name: RedPajamaCommonCrawl


Description: Quality Inn Fort Pierce - Welcome to Quality Inn Fort Pierce FL Hotel located between the Florida Turnpike and Interstate 95.
Description: Confirm your stay at Quality Inn Greensburg PA Hotel near Idlewild Park.
Description: Check out information about Hotel Motel near Mohegan Sun, CT and Hotel near Historic Mystic Groton.
Description: Quality Inn Hillsville Hotel is ideally located in Carroll County surrounding beautiful Blue Ridge Mountains and close to fun filled Labor Day Flea Market and Gun Show.
Description: On Your Stay at Quality Inn Byron Hotel near Robins Air Force Base, enjoy visiting Macon attractions.


text:
Judge Rowan Wilson, Dissenting in Personal Jurisdiction Case, Advocates that Court of Appeals Should Have Dismissed Appeal as Improvidently Granted
In Wilson v Dantas (No. 62), previewed here, the Court of Appeals affirmed an order of the Appellate Division, First Department, holding that it had long-arm jurisdiction over the defendants in a breach of contract and fiduciary duty action, because the appellant expressly abandoned his challenge to the personal jurisdiction ruling on appeal.
Interestingly, however, Judge Rowan Wilson dissented, and argued that the Court should have dismissed the appeal for lack of appellate jurisdiction because the two personal jurisdiction issues on which leave to appeal had been granted were rendered academic by an amendment to the complaint. The issues decided by the majority, Judge Wilson noted, were never argued in seeking leave to appeal, and the Court's precedent typically binds the party seeking leave to appeal to those questions that were the basis of the leave grant. Judge Wilson did not take kindly to the defendants' "switcheroo."
Judge Wilson explained that holding the parties to the issues that the Court, or here the Appellate Division, decided were leaveworthy is fundamentally fair as those were the issues the parties had notice would be argued on appeal. Permitting what defendants did here, in contrast, potentially denied the plaintiff the opportunity to cross-move for leave to appeal seeking review of additional issues. That is not how the Court's review should work, Judge Wilson noted.
Judge Wilson also notes that if a similar situation occurred in an appeal before the United States Supreme Court, that Court has jurisdiction to dismiss the appeal as improvidently granted. Although he recognized that the Court of Appeals does not have that same jurisdiction, he argues that it should, and would have dismissed this appeal if it did.
I can't say that I disagree with Judge Wilson's stance. Where a change in circumstances has left the questions upon which the parties obtained leave to appeal either academic, unreviewable, or no longer leaveworthy, the Court of Appeals should have jurisdiction simply to dismiss the appeal as improvidently granted. As Judge Wilson pointed out, such a result is not only fair, but it would allow the Court more control over its own docket and avoid decisions like this one, where the majority writes a memorandum decision with no analysis of the legal issues it decided at all.
The Court of Appeals' opinion can be found here.
Court of Appeals, Decision Summaries
Court of Appeals Holds New York City's Adult Use Zoning Ordinance Does Not Violate First Amendment
Second Circuit Certifies Questions to Court of Appeals Concerning Damages, Interest in Misappropriation of Trade Secrets Cases
One thought on "Judge Rowan Wilson, Dissenting in Personal Jurisdiction Case, Advocates that Court of Appeals Should Have Dismissed Appeal as Improvidently Granted"
Pingback: Bring Your Lunch to the Court of Appeals: A Conversation with Judge Leslie Stein – New York Appeals


VeroFlex™ is a PolyJet rigid photopolymer material offering a flexibility ideal for rapid prototyping eye-wear. Get prototypes with full-part realism in a wide range of colors, textures and materials from opaque to transparent, unique to the Stratasys J735 and Stratasys J750 3D Printers.
Stratasys has released new 3D printing materials that bring even more power to your creativity. These new PolyJet materials allow you to prototype in such a way that others will ask "Is this the final product?". New materials include Agilus30™ White, VeroFlexVivid™ and VeroCyanV™. It is no surprise that the J735 and J750 continues to evolve with every update.
Antero 800NA is a PEKK-based FDM thermoplastic. It combines FDM's design freedom and ease of use with the excellent strength, toughness and wear-resistant properties of PEKK material. Appropriate applications include aircraft components exposed to jet fuel, oil and hydraulic fluid, spacecraft parts that demand low outgassing and chemical-resistant industrial parts.


This week saw the opening of the long awaited South Devon Highway. Fifty years in the planning and three years in the making, the 5.5km bypass around the village of Kingskerswell opened to the public around 4.30am on 15th December.
Since construction began back in September 2012. Throughout the project CET infrastructure has been providing essential on-site materials testing services to principal contractors Galliford Try / SIAC JV.
CET managed every element of the site laboratory from conception, supply of equipment, system implementation to delivery of test data. Our site labs delivered a combination of soils, aggregate, and cementitious laboratory services, plus other site-related services; including density surveys and LWD stiffness testing.
Since achieving flexible scope accreditation, CET has provided UKAS accredited mobile laboratories to a number of high profile UK infrastructure projects, including Crossrail and DIRFT2.
Offering everything from basic soil classification to running surface testing, our on-site UKAS laboratories are staffed by fully-qualified engineers & technicians and ensure a responsive, high quality service tailored to specific project requirements with technical reporting and on-site support and materials advice.
Use the form below to email us any questions you may have regarding any of our services.


Below are some links to information that will be helpful in finding transition related resources.
My Delicious page: Here you will find several links to information that can be helpful in finding a variety of informative resources and connections to services you may find useful.
My Future Builder: My Future Builder is a website to help parents, students, and teachers work together to develop plans for transitioning. Take some time to explore the site and lets plan for the Future!
Conover Online: The Conover web resource is a tool we use to assess student needs and skill levels in many areas. Students will be given assignments on the Conover website. To access these assignments, Students will be given a user name and password.
Natural Readers and VozMe are both text to speech websites. Both are free. Natural Readers will work online for small amounts of text or has a program you can download. If you create an account, you can choose more natural sounding voices and change the speed to make it easier to understand. If you just need something quick, VozMe will be the job done. Both will help you read web content that you cut and paste into the text window.
Khan Academy: A site with a large variety of video lessons on many topics. The site also now includes practice for skills. A great resource for learning new skills or reviewing skills.
EdHeads: EdHeads is a website with a variety of educational games that can help students learn skills and information.


Chick A: "Kyaaaa! A huge monster came in!"
Sea: "Hey! This is my house! Please don't take over!"
Chick D: "How come I can't fly? This is the destiny of being a chicken, isn't it?"
Chick A: "Let's go for a walk. We don't want to be pecked by huge monsters."
Chick B: "Let's do it. They are scary."
Ehime: "Poor chicks. Then, I can play with them."
Mommy: "I think they will say no thank you."
Kona: "I'm allergic to chickens."
Kona: "I'm not able to eat chicken meat."
Ehime: "...... You sound like the most scary one for them."
For chicks who don't want to be close to Goldens, please click the puppy photo on the right above or a dog picture below to vote for a doggie blog ranking. Thank you!


text:
Ransomware to wreak havoc in 2016, ICIT study says
The Institute for Critical Infrastructure Technology said ransomware is so common that it's becoming its own economy and criminals will be increasingly targeting healthcare entities via social engineering and other tactics....
21 March, 2016 / 0 Comments
Amazon Leans on Government in Its Quest to Be a Delivery Powerhouse
WASHINGTON — Ever since Jeff Bezos started the website Amazon to sell books, he has wrestled with how to deliver its products as quickly and cheaply as possible. Today, Amazon, now a retail giant, remains obsessed with this issue, building its own fleet of drones,...
Apple Encryption Engineers, if Ordered to Unlock iPhone, Might Resist
SAN FRANCISCO — If the F.B.I. wins its court fight to force Apple's help in unlocking an iPhone, the agency may run into yet another roadblock: Apple's engineers. Apple employees are already discussing what they will do if ordered to help law enforcement authorities. Some say...
A beginner's guide to finally buying a virtual reality headset
It's finally happening: After years of promises about virtual reality for the everyday person, this year will actually bring shoppers a variety of options. In truth, there are probably a lot of people who have no interest in these headsets — which is totally understandable with...
Epic to develop Apple Watch app, 'Limerick,' a test results notifier
The app enables doctors to receive alerts via Apple Watch so if they are waiting on test results about one patient, that physician can know immediately. Electronic health record giant Epic is working on an app for Apple's Watch, according to CEO Judy Faulkner. "Limerick on the...
How To Make Your Workplace Culture Collaborative
Open spaces, water cooler talk, and allowing employees to update Facebook are often more effective in creating a collaborative workplace than all the team-building exercises your consultants can dream up. Here's a look at what works in the real world. Pay is only one component in...
EASY IoT Changes Touchless Technology As We Know It
Elliptic Labs has been passionate about gesture-controlled technology since its founding in 2006. While much of their energy has been focused on a touch-free mobile phone experience – enabling hands-free video recording and selfies – they unveiled EASY IoT software at Mobile World Congress, allowing...
Prepare for a cyberattack on the power grid, Wisconsin officials say
A cyberattack taking down the nation's power grid could leave Americans scrambling to survive without electricity, potable water or working sewage systems, the commander of the Wisconsin National Guard warned, unless "gaps and seams" are filled in to mitigate the risk of catastrophe. Maj. Gen....
American Medical Group Association campaign hopes to improve diabetes care, leverage data sharing
More than 100 member organizations have committed to participating in the effort to empower patients and improve care delivery. The AMGA Foundation – the nonprofit arm of the American Medical Group Association – has launched a national campaign aimed at improving care for diabetes patients....
As a Data Deluge Grows, Companies Rethink Storage
MOUNTAIN VIEW, Calif. — John Hayes, cleareyed and wild-haired, stood before his silent creation. Big as a slim refrigerator, it held 16 petabytes of data, roughly equal to 16 billion thick books. "People are going to have to think about things to put into this," he...


There is no better way to simplify and gain control over your financial life than by eliminating high-interest debt. So pay off your credit card and other high-interest loans ASAP. For most of us, this is by far the best investment opportunity we'll ever receive.


text:
NAD Electronics T 778 Reference AV Receiver Review
Posted on 8th September, 2020
Tony O'Brien tunes into an impressive new mid-price Dirac Live-equipped AV receiver…
NAD Electronics
T 778 Reference AV Receiver
SGD $4,200 RRP
Value for money is what makes NAD stand out from the crowd, and that doesn't mean dozens of superfluous functions, gizmos and gadgets. Instead, the company has always offered a measure of useful features allied to fine sound and decent but understated build quality. Typical buyers of this brand are almost reassured by sober looks, devoid of shiny bits of metal and flashing lights.
The new T778 is no different – NAD says it's a cutting edge powerhouse that seeks to repeat its winning formula. At its heart are nine high current digital amplifiers, featuring the company's own Hybrid Digital Amplifier Technology. The T778's UcD102 power module is a self-contained dual-channel, high-performance Class D amplifier which the company says achieves a flat frequency response irrespective of load impedance, with frequency-independent distortion behaviour.
At first glance, its quoted 85W RMS per channel may seem a little modest. However, it's for all channels driven simultaneously at full bandwidth – which is effectively the worst-case scenario for power output measurements. Such blunt honesty is a refreshing departure. In truth, it's pretty much as high as any of its competitors in real terms.
The T778 doesn't boast a double-digit amplifier count but can process up to 11.2 channels with external amplification. This is thanks in part to its Modular Design Construction, which allows both audio and video circuits to be replaced as new formats become available. Not just ballyhoo, NAD's older T758 V3 had three upgrades during its nine-year lifecycle which heralded in everything from Atmos, 4K Ultra HD video and Dirac Live Room Correction – hence the V3 moniker.
Speaking of which, the T778 includes a license for Dirac Live Room Correction with the option of purchasing a Pro License and expanding its abilities accordingly. Oh, and it's capable of decoding the latest in lossless surround formats including Dolby Atmos and DTS X. Notably absent from its list of supported formats is IMAX Enhanced, but this could change with a future firmware update.
BluOS adds wireless multi-room streaming to the T778's feature set, along with all the usual suspects such as Tidal, Spotify, Deezer and Internet Radio. Also present is support for hi-res FLAC and WAV audio playback, and Apple Airplay 2.
Open the carton and you'll find the unit, plus another box with two remotes, the power cord, a microphone for Dirac live calibration, BluOs Kit and rack mount ears. While many are not going to need the latter, it's this attention to detail that sets the T778 apart. The main remote is identical to the remote that shipped with the T758 V3. Rather longish in design, it sits comfortably in hand, with large easy to read buttons, with the press of a button activating the backlight. A second, smaller and far less impressive remote is reserved for controlling the T778 from a separate zone.
At 435x140x430mm, the T778 fits into spaces that larger AVRs will baulk at. Its modest dimensions and minimalistic façade make it both distinctively NAD, yet uniquely different from anything we've seen from the manufacturer before. A large TFT screen dominates the front panel, while controls are kept to a minimum – save for the power button, volume dial, USB and HDMI input, plus a headphone jack. Its curved edges give way to a robust aluminium case, which apart from its top vents is otherwise sealed. Styling and build quality are first class.
At the back are eighteen loudspeaker binding posts mounted in a horizontal configuration, and above this are four replaceable MDC panels that house the inputs and outputs. The first is reserved for future expansion, while the second slot contains five HDMI inputs, two HDMI outs and a USB input, plus an Ethernet port. The remaining MDC panels slots host its pre-outs, in addition to dual analogue, coaxial and TOSLINK inputs. Dual subwoofer outputs are provided, in addition to 3.5mm connectors for IR sensors and 12v triggers.
Both a Panasonic UB9000 4K Blu-ray player and Apple TV were connected directly to the T778 via its HDMI inputs, while the output went to a Sony VPL-VW270ES projector via a Lumagen Radiance Pro, which was projected onto a Severtson 100" Cinegray screen. In our home theatre, Analysis Plus cables provided the link to VAF Signature i91 front, and centre speakers and four VAF i90 rear surround and ceiling mounted Atmos speakers. The T778 has two parallel sub outputs, so it's only possible to create a single delay and trim for both sums. These drove two VAF Veritas 10" custom subs for a 5.2.2 Atmos system.
Upon powering up the unit, you're greeted by a NAD logo during which the T778 completes its power cycle. In addition to revealing the source and volume, the TFT display also grants access and control over its various functions while also acting as an on-screen display. There are no setup wizards, so it's a case of just diving and getting your feet wet. The menus are cleanly and logically laid out, but it's still worth acquainting yourself with the downloadable user manual before getting started.
Dirac Live needs to be downloaded to a PC to complete speaker calibration and room EQ. While not as simple to use as other systems, it adds a level of versatility and customisation that's simply not possible with inbuilt room-correction systems. Since I last dabbled with Dirac, it's had a significant update in the form of version 3.0. The resulting software is both more stable and easier to use than its predecessor. The calibration process was remarkably smooth, with easy to follow instructions and diagrams illustrating where the microphone should be placed for measurements.
While it may have been simplified, I'd strongly encourage you to spend some time familiarising yourself with Dirac if you want to hear all that the T778 has to offer. Likewise, invest in a tripod or mic stand to use with the microphone. In its 'free' form, Dirac will EQ between 20Hz and 500Hz which is fine for most. The Pro license comes at an additional cost of USD $99 and unlocks EQ of the entire frequency range of 20Hz-20kHz and promises improved soundstaging and clarity. Of course, for any tinkerer this is a must.
The T778 is a gutsy AV receiver that's equally at home dishing out the sonic mayhem of action blockbusters, as it is revealing the nuances of subtler fare. Pinpoint location of effects gives the T778 a tightly focused soundstage. For example, Spider-Man: Into the Spider-Verse is not only a highly entertaining watch but also contains a cracking Dolby Atmos soundtrack. The heartbeat in the Marvel intro was not only heard but felt at the primary listening position. With Dirac switched in, overall bass reproduction was excellent but lacking some of the control that I'm accustomed to.
The T778's ability to retrieve detail and precision when placing objects within the sound field brought the ambient sound of Mile's school hall to life, putting myself and my budding nine-year-old reviewer right in the chaos of the school hall. Its precision gives it a polite sonic character that took some time get accustomed to, but it's a sound that grew on me during the review period. It's a characteristic that can lull you into a false sense of security, as the T778 is capable of huge dynamic swings.
As the Imperial Navy steamed its way into our listening room, the T778 was very much at home dishing out the sonic onslaught of Midway's DTS HD soundtrack. Gunfire, explosions and the roar of the Dauntless dive-bombers engines ripping their way through the listening room. Nudging the volume control higher than I'm accustomed to proved this AV receiver's power amp section was up to the task, effortlessly driving the speakers without a hint of strain. I heard great dynamic swings, but all of the aforementioned subtleties and politeness were present and accounted for, bringing a sense of order and cohesion to the explosion-filled mayhem.
All of these traits were present with the Atmos soundtrack of Atomic Blonde. Here the T778 delivered Charlise Theron's fight scenes with conviction, its musical prowess doing the nineteen-eighties soundtrack justice. The Atmos soundtrack on the 4K Blu-ray of John Wick may be equally potent, but it does require a nudge on the volume control to get things ticking. Regardless, the NAD served up the soundtrack with the same sense of enthusiasm I've become accustomed to. My only criticism is that the sound was not quite as muscular as my own Anthem MX720.
Likewise, the soundstage lacked some of the height and the width I'm used to. Rather than a criticism, it's a point of difference as the NAD produced a more focused and tighter soundstage than the Anthem. I have no doubt this was emphasised due to the options that I chose when running Dirac calibration, however, it's a trait I've noticed with other NAD AVRs that have been in our listening room too.
The new NAD T778 distinguishes itself with a refined sonic character, one that's equally at home dishing out the sonic goodies as it is with more subtle fare. It has more than enough dynamics to create an expansive home theatre experience. At the same time, the ability to deliver effects with pinpoint precision ensures the action's delivered not only with a sense of impact but credibility. Coupled with its modest dimensions and downright cool styling, this box brings flagship performance to a range of spaces which may have dictated a compromise in the past. Highly recommended, then.
For more information visit NAD Electronics
Tony O'Brien
As the owner of Adelaide based 'Clarity Audio & Video Calibration', Tony is a certified ISF Calibrator. Tony is an accomplished Audio-Visual reviewer specialising in theatre and visual products.
Posted in:Amplifiers AV Receivers & Processors Applause Awards 2020 Home Theatre
Tags: lenbrook nad


text:
Quay of Sea Voices on iTunes
17th February 2016 28th February 2016 by director
Quay of Sea Voices were involved with other choirs in Portsmouth in making an album for the D-Day Museum last year
The album is called Heroes' Tide and money raised goes towards the D-Day Museum
Follow the link and have a listen to it.
https://itunes.apple.com/gb/album/heroes-tide/id1079244724
Singing Lessons in Portsmouth


text:
Kuehneromyces is a genus of agaric fungi in the family Strophariaceae. The genus was circumscribed by mycologists Rolf Singer and Alexander H. Smith in 1946.

The genus name of Kuehneromyces is in honour of Robert Kühner (1903-1996), who was a French mycologist most notable for reviewing many agaric.

See also

List of Agaricales genera

References

Bolbitiaceae
Agaricales genera
Taxa named by Alexander H. Smith
Taxa named by Rolf Singer
Taxa described in 1946

redpajama_set_name: RedPajamaWikipedia


We think it would be very wise to add this nocturnal beauty to your garden. A small but tough Owl, the Southern Boobook Owl outlived the larger Laughing Owl who died out over 100 years ago. Need a tough friend in your garden? This piece of garden decor is perfect for you.