]> git.lizzy.rs Git - rust.git/blob - src/libcore/iter/traits.rs
4cbabe3f5edafc1036216b05470c7cd7d5478169
[rust.git] / src / libcore / iter / traits.rs
1 // Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 use option::Option::{self, Some};
12 use marker::Sized;
13
14 use super::Iterator;
15
16 /// Conversion from an `Iterator`.
17 ///
18 /// By implementing `FromIterator` for a type, you define how it will be
19 /// created from an iterator. This is common for types which describe a
20 /// collection of some kind.
21 ///
22 /// `FromIterator`'s [`from_iter()`] is rarely called explicitly, and is instead
23 /// used through [`Iterator`]'s [`collect()`] method. See [`collect()`]'s
24 /// documentation for more examples.
25 ///
26 /// [`from_iter()`]: #tymethod.from_iter
27 /// [`Iterator`]: trait.Iterator.html
28 /// [`collect()`]: trait.Iterator.html#method.collect
29 ///
30 /// See also: [`IntoIterator`].
31 ///
32 /// [`IntoIterator`]: trait.IntoIterator.html
33 ///
34 /// # Examples
35 ///
36 /// Basic usage:
37 ///
38 /// ```
39 /// use std::iter::FromIterator;
40 ///
41 /// let five_fives = std::iter::repeat(5).take(5);
42 ///
43 /// let v = Vec::from_iter(five_fives);
44 ///
45 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
46 /// ```
47 ///
48 /// Using [`collect()`] to implicitly use `FromIterator`:
49 ///
50 /// ```
51 /// let five_fives = std::iter::repeat(5).take(5);
52 ///
53 /// let v: Vec<i32> = five_fives.collect();
54 ///
55 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
56 /// ```
57 ///
58 /// Implementing `FromIterator` for your type:
59 ///
60 /// ```
61 /// use std::iter::FromIterator;
62 ///
63 /// // A sample collection, that's just a wrapper over Vec<T>
64 /// #[derive(Debug)]
65 /// struct MyCollection(Vec<i32>);
66 ///
67 /// // Let's give it some methods so we can create one and add things
68 /// // to it.
69 /// impl MyCollection {
70 ///     fn new() -> MyCollection {
71 ///         MyCollection(Vec::new())
72 ///     }
73 ///
74 ///     fn add(&mut self, elem: i32) {
75 ///         self.0.push(elem);
76 ///     }
77 /// }
78 ///
79 /// // and we'll implement FromIterator
80 /// impl FromIterator<i32> for MyCollection {
81 ///     fn from_iter<I: IntoIterator<Item=i32>>(iter: I) -> Self {
82 ///         let mut c = MyCollection::new();
83 ///
84 ///         for i in iter {
85 ///             c.add(i);
86 ///         }
87 ///
88 ///         c
89 ///     }
90 /// }
91 ///
92 /// // Now we can make a new iterator...
93 /// let iter = (0..5).into_iter();
94 ///
95 /// // ... and make a MyCollection out of it
96 /// let c = MyCollection::from_iter(iter);
97 ///
98 /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
99 ///
100 /// // collect works too!
101 ///
102 /// let iter = (0..5).into_iter();
103 /// let c: MyCollection = iter.collect();
104 ///
105 /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
106 /// ```
107 #[stable(feature = "rust1", since = "1.0.0")]
108 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
109                           built from an iterator over elements of type `{A}`"]
110 pub trait FromIterator<A>: Sized {
111     /// Creates a value from an iterator.
112     ///
113     /// See the [module-level documentation] for more.
114     ///
115     /// [module-level documentation]: trait.FromIterator.html
116     ///
117     /// # Examples
118     ///
119     /// Basic usage:
120     ///
121     /// ```
122     /// use std::iter::FromIterator;
123     ///
124     /// let five_fives = std::iter::repeat(5).take(5);
125     ///
126     /// let v = Vec::from_iter(five_fives);
127     ///
128     /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
129     /// ```
130     #[stable(feature = "rust1", since = "1.0.0")]
131     fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self;
132 }
133
134 /// Conversion into an `Iterator`.
135 ///
136 /// By implementing `IntoIterator` for a type, you define how it will be
137 /// converted to an iterator. This is common for types which describe a
138 /// collection of some kind.
139 ///
140 /// One benefit of implementing `IntoIterator` is that your type will [work
141 /// with Rust's `for` loop syntax](index.html#for-loops-and-intoiterator).
142 ///
143 /// See also: [`FromIterator`].
144 ///
145 /// [`FromIterator`]: trait.FromIterator.html
146 ///
147 /// # Examples
148 ///
149 /// Basic usage:
150 ///
151 /// ```
152 /// let v = vec![1, 2, 3];
153 ///
154 /// let mut iter = v.into_iter();
155 ///
156 /// let n = iter.next();
157 /// assert_eq!(Some(1), n);
158 ///
159 /// let n = iter.next();
160 /// assert_eq!(Some(2), n);
161 ///
162 /// let n = iter.next();
163 /// assert_eq!(Some(3), n);
164 ///
165 /// let n = iter.next();
166 /// assert_eq!(None, n);
167 /// ```
168 ///
169 /// Implementing `IntoIterator` for your type:
170 ///
171 /// ```
172 /// // A sample collection, that's just a wrapper over Vec<T>
173 /// #[derive(Debug)]
174 /// struct MyCollection(Vec<i32>);
175 ///
176 /// // Let's give it some methods so we can create one and add things
177 /// // to it.
178 /// impl MyCollection {
179 ///     fn new() -> MyCollection {
180 ///         MyCollection(Vec::new())
181 ///     }
182 ///
183 ///     fn add(&mut self, elem: i32) {
184 ///         self.0.push(elem);
185 ///     }
186 /// }
187 ///
188 /// // and we'll implement IntoIterator
189 /// impl IntoIterator for MyCollection {
190 ///     type Item = i32;
191 ///     type IntoIter = ::std::vec::IntoIter<i32>;
192 ///
193 ///     fn into_iter(self) -> Self::IntoIter {
194 ///         self.0.into_iter()
195 ///     }
196 /// }
197 ///
198 /// // Now we can make a new collection...
199 /// let mut c = MyCollection::new();
200 ///
201 /// // ... add some stuff to it ...
202 /// c.add(0);
203 /// c.add(1);
204 /// c.add(2);
205 ///
206 /// // ... and then turn it into an Iterator:
207 /// for (i, n) in c.into_iter().enumerate() {
208 ///     assert_eq!(i as i32, n);
209 /// }
210 /// ```
211 #[stable(feature = "rust1", since = "1.0.0")]
212 pub trait IntoIterator {
213     /// The type of the elements being iterated over.
214     #[stable(feature = "rust1", since = "1.0.0")]
215     type Item;
216
217     /// Which kind of iterator are we turning this into?
218     #[stable(feature = "rust1", since = "1.0.0")]
219     type IntoIter: Iterator<Item=Self::Item>;
220
221     /// Creates an iterator from a value.
222     ///
223     /// See the [module-level documentation] for more.
224     ///
225     /// [module-level documentation]: trait.IntoIterator.html
226     ///
227     /// # Examples
228     ///
229     /// Basic usage:
230     ///
231     /// ```
232     /// let v = vec![1, 2, 3];
233     ///
234     /// let mut iter = v.into_iter();
235     ///
236     /// let n = iter.next();
237     /// assert_eq!(Some(1), n);
238     ///
239     /// let n = iter.next();
240     /// assert_eq!(Some(2), n);
241     ///
242     /// let n = iter.next();
243     /// assert_eq!(Some(3), n);
244     ///
245     /// let n = iter.next();
246     /// assert_eq!(None, n);
247     /// ```
248     #[stable(feature = "rust1", since = "1.0.0")]
249     fn into_iter(self) -> Self::IntoIter;
250 }
251
252 #[stable(feature = "rust1", since = "1.0.0")]
253 impl<I: Iterator> IntoIterator for I {
254     type Item = I::Item;
255     type IntoIter = I;
256
257     fn into_iter(self) -> I {
258         self
259     }
260 }
261
262 /// Extend a collection with the contents of an iterator.
263 ///
264 /// Iterators produce a series of values, and collections can also be thought
265 /// of as a series of values. The `Extend` trait bridges this gap, allowing you
266 /// to extend a collection by including the contents of that iterator.
267 ///
268 /// # Examples
269 ///
270 /// Basic usage:
271 ///
272 /// ```
273 /// // You can extend a String with some chars:
274 /// let mut message = String::from("The first three letters are: ");
275 ///
276 /// message.extend(&['a', 'b', 'c']);
277 ///
278 /// assert_eq!("abc", &message[29..32]);
279 /// ```
280 ///
281 /// Implementing `Extend`:
282 ///
283 /// ```
284 /// // A sample collection, that's just a wrapper over Vec<T>
285 /// #[derive(Debug)]
286 /// struct MyCollection(Vec<i32>);
287 ///
288 /// // Let's give it some methods so we can create one and add things
289 /// // to it.
290 /// impl MyCollection {
291 ///     fn new() -> MyCollection {
292 ///         MyCollection(Vec::new())
293 ///     }
294 ///
295 ///     fn add(&mut self, elem: i32) {
296 ///         self.0.push(elem);
297 ///     }
298 /// }
299 ///
300 /// // since MyCollection has a list of i32s, we implement Extend for i32
301 /// impl Extend<i32> for MyCollection {
302 ///
303 ///     // This is a bit simpler with the concrete type signature: we can call
304 ///     // extend on anything which can be turned into an Iterator which gives
305 ///     // us i32s. Because we need i32s to put into MyCollection.
306 ///     fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) {
307 ///
308 ///         // The implementation is very straightforward: loop through the
309 ///         // iterator, and add() each element to ourselves.
310 ///         for elem in iter {
311 ///             self.add(elem);
312 ///         }
313 ///     }
314 /// }
315 ///
316 /// let mut c = MyCollection::new();
317 ///
318 /// c.add(5);
319 /// c.add(6);
320 /// c.add(7);
321 ///
322 /// // let's extend our collection with three more numbers
323 /// c.extend(vec![1, 2, 3]);
324 ///
325 /// // we've added these elements onto the end
326 /// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{:?}", c));
327 /// ```
328 #[stable(feature = "rust1", since = "1.0.0")]
329 pub trait Extend<A> {
330     /// Extends a collection with the contents of an iterator.
331     ///
332     /// As this is the only method for this trait, the [trait-level] docs
333     /// contain more details.
334     ///
335     /// [trait-level]: trait.Extend.html
336     ///
337     /// # Examples
338     ///
339     /// Basic usage:
340     ///
341     /// ```
342     /// // You can extend a String with some chars:
343     /// let mut message = String::from("abc");
344     ///
345     /// message.extend(['d', 'e', 'f'].iter());
346     ///
347     /// assert_eq!("abcdef", &message);
348     /// ```
349     #[stable(feature = "rust1", since = "1.0.0")]
350     fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T);
351 }
352
353 /// An iterator able to yield elements from both ends.
354 ///
355 /// Something that implements `DoubleEndedIterator` has one extra capability
356 /// over something that implements [`Iterator`]: the ability to also take
357 /// `Item`s from the back, as well as the front.
358 ///
359 /// It is important to note that both back and forth work on the same range,
360 /// and do not cross: iteration is over when they meet in the middle.
361 ///
362 /// In a similar fashion to the [`Iterator`] protocol, once a
363 /// `DoubleEndedIterator` returns `None` from a `next_back()`, calling it again
364 /// may or may not ever return `Some` again. `next()` and `next_back()` are
365 /// interchangable for this purpose.
366 ///
367 /// [`Iterator`]: trait.Iterator.html
368 ///
369 /// # Examples
370 ///
371 /// Basic usage:
372 ///
373 /// ```
374 /// let numbers = vec![1, 2, 3, 4, 5, 6];
375 ///
376 /// let mut iter = numbers.iter();
377 ///
378 /// assert_eq!(Some(&1), iter.next());
379 /// assert_eq!(Some(&6), iter.next_back());
380 /// assert_eq!(Some(&5), iter.next_back());
381 /// assert_eq!(Some(&2), iter.next());
382 /// assert_eq!(Some(&3), iter.next());
383 /// assert_eq!(Some(&4), iter.next());
384 /// assert_eq!(None, iter.next());
385 /// assert_eq!(None, iter.next_back());
386 /// ```
387 #[stable(feature = "rust1", since = "1.0.0")]
388 pub trait DoubleEndedIterator: Iterator {
389     /// Removes and returns an element from the end of the iterator.
390     ///
391     /// Returns `None` when there are no more elements.
392     ///
393     /// The [trait-level] docs contain more details.
394     ///
395     /// [trait-level]: trait.DoubleEndedIterator.html
396     ///
397     /// # Examples
398     ///
399     /// Basic usage:
400     ///
401     /// ```
402     /// let numbers = vec![1, 2, 3, 4, 5, 6];
403     ///
404     /// let mut iter = numbers.iter();
405     ///
406     /// assert_eq!(Some(&1), iter.next());
407     /// assert_eq!(Some(&6), iter.next_back());
408     /// assert_eq!(Some(&5), iter.next_back());
409     /// assert_eq!(Some(&2), iter.next());
410     /// assert_eq!(Some(&3), iter.next());
411     /// assert_eq!(Some(&4), iter.next());
412     /// assert_eq!(None, iter.next());
413     /// assert_eq!(None, iter.next_back());
414     /// ```
415     #[stable(feature = "rust1", since = "1.0.0")]
416     fn next_back(&mut self) -> Option<Self::Item>;
417 }
418
419 #[stable(feature = "rust1", since = "1.0.0")]
420 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
421     fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() }
422 }
423
424 /// An iterator that knows its exact length.
425 ///
426 /// Many [`Iterator`]s don't know how many times they will iterate, but some do.
427 /// If an iterator knows how many times it can iterate, providing access to
428 /// that information can be useful. For example, if you want to iterate
429 /// backwards, a good start is to know where the end is.
430 ///
431 /// When implementing an `ExactSizeIterator`, You must also implement
432 /// [`Iterator`]. When doing so, the implementation of [`size_hint()`] *must*
433 /// return the exact size of the iterator.
434 ///
435 /// [`Iterator`]: trait.Iterator.html
436 /// [`size_hint()`]: trait.Iterator.html#method.size_hint
437 ///
438 /// The [`len()`] method has a default implementation, so you usually shouldn't
439 /// implement it. However, you may be able to provide a more performant
440 /// implementation than the default, so overriding it in this case makes sense.
441 ///
442 /// [`len()`]: #method.len
443 ///
444 /// # Examples
445 ///
446 /// Basic usage:
447 ///
448 /// ```
449 /// // a finite range knows exactly how many times it will iterate
450 /// let five = 0..5;
451 ///
452 /// assert_eq!(5, five.len());
453 /// ```
454 ///
455 /// In the [module level docs][moddocs], we implemented an [`Iterator`],
456 /// `Counter`. Let's implement `ExactSizeIterator` for it as well:
457 ///
458 /// [moddocs]: index.html
459 ///
460 /// ```
461 /// # struct Counter {
462 /// #     count: usize,
463 /// # }
464 /// # impl Counter {
465 /// #     fn new() -> Counter {
466 /// #         Counter { count: 0 }
467 /// #     }
468 /// # }
469 /// # impl Iterator for Counter {
470 /// #     type Item = usize;
471 /// #     fn next(&mut self) -> Option<usize> {
472 /// #         self.count += 1;
473 /// #         if self.count < 6 {
474 /// #             Some(self.count)
475 /// #         } else {
476 /// #             None
477 /// #         }
478 /// #     }
479 /// # }
480 /// impl ExactSizeIterator for Counter {
481 ///     // We already have the number of iterations, so we can use it directly.
482 ///     fn len(&self) -> usize {
483 ///         self.count
484 ///     }
485 /// }
486 ///
487 /// // And now we can use it!
488 ///
489 /// let counter = Counter::new();
490 ///
491 /// assert_eq!(0, counter.len());
492 /// ```
493 #[stable(feature = "rust1", since = "1.0.0")]
494 pub trait ExactSizeIterator: Iterator {
495     /// Returns the exact number of times the iterator will iterate.
496     ///
497     /// This method has a default implementation, so you usually should not
498     /// implement it directly. However, if you can provide a more efficient
499     /// implementation, you can do so. See the [trait-level] docs for an
500     /// example.
501     ///
502     /// This function has the same safety guarantees as the [`size_hint()`]
503     /// function.
504     ///
505     /// [trait-level]: trait.ExactSizeIterator.html
506     /// [`size_hint()`]: trait.Iterator.html#method.size_hint
507     ///
508     /// # Examples
509     ///
510     /// Basic usage:
511     ///
512     /// ```
513     /// // a finite range knows exactly how many times it will iterate
514     /// let five = 0..5;
515     ///
516     /// assert_eq!(5, five.len());
517     /// ```
518     #[inline]
519     #[stable(feature = "rust1", since = "1.0.0")]
520     fn len(&self) -> usize {
521         let (lower, upper) = self.size_hint();
522         // Note: This assertion is overly defensive, but it checks the invariant
523         // guaranteed by the trait. If this trait were rust-internal,
524         // we could use debug_assert!; assert_eq! will check all Rust user
525         // implementations too.
526         assert_eq!(upper, Some(lower));
527         lower
528     }
529
530     /// Returns whether the iterator is empty.
531     ///
532     /// This method has a default implementation using `self.len()`, so you
533     /// don't need to implement it yourself.
534     ///
535     /// # Examples
536     ///
537     /// Basic usage:
538     ///
539     /// ```
540     /// #![feature(exact_size_is_empty)]
541     ///
542     /// let mut one_element = 0..1;
543     /// assert!(!one_element.is_empty());
544     ///
545     /// assert_eq!(one_element.next(), Some(0));
546     /// assert!(one_element.is_empty());
547     ///
548     /// assert_eq!(one_element.next(), None);
549     /// ```
550     #[inline]
551     #[unstable(feature = "exact_size_is_empty", issue = "35428")]
552     fn is_empty(&self) -> bool {
553         self.len() == 0
554     }
555 }
556
557 #[stable(feature = "rust1", since = "1.0.0")]
558 impl<'a, I: ExactSizeIterator + ?Sized> ExactSizeIterator for &'a mut I {}
559
560 /// Trait to represent types that can be created by summing up an iterator.
561 ///
562 /// This trait is used to implement the `sum` method on iterators. Types which
563 /// implement the trait can be generated by the `sum` method. Like
564 /// `FromIterator` this trait should rarely be called directly and instead
565 /// interacted with through `Iterator::sum`.
566 #[unstable(feature = "iter_arith_traits", issue = "34529")]
567 pub trait Sum<A = Self>: Sized {
568     /// Method which takes an iterator and generates `Self` from the elements by
569     /// "summing up" the items.
570     fn sum<I: Iterator<Item=A>>(iter: I) -> Self;
571 }
572
573 /// Trait to represent types that can be created by multiplying elements of an
574 /// iterator.
575 ///
576 /// This trait is used to implement the `product` method on iterators. Types
577 /// which implement the trait can be generated by the `product` method. Like
578 /// `FromIterator` this trait should rarely be called directly and instead
579 /// interacted with through `Iterator::product`.
580 #[unstable(feature = "iter_arith_traits", issue = "34529")]
581 pub trait Product<A = Self>: Sized {
582     /// Method which takes an iterator and generates `Self` from the elements by
583     /// multiplying the items.
584     fn product<I: Iterator<Item=A>>(iter: I) -> Self;
585 }
586
587 macro_rules! integer_sum_product {
588     ($($a:ident)*) => ($(
589         #[unstable(feature = "iter_arith_traits", issue = "34529")]
590         impl Sum for $a {
591             fn sum<I: Iterator<Item=$a>>(iter: I) -> $a {
592                 iter.fold(0, |a, b| {
593                     a.checked_add(b).expect("overflow in sum")
594                 })
595             }
596         }
597
598         #[unstable(feature = "iter_arith_traits", issue = "34529")]
599         impl Product for $a {
600             fn product<I: Iterator<Item=$a>>(iter: I) -> $a {
601                 iter.fold(1, |a, b| {
602                     a.checked_mul(b).expect("overflow in product")
603                 })
604             }
605         }
606
607         #[unstable(feature = "iter_arith_traits", issue = "34529")]
608         impl<'a> Sum<&'a $a> for $a {
609             fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
610                 iter.fold(0, |a, b| {
611                     a.checked_add(*b).expect("overflow in sum")
612                 })
613             }
614         }
615
616         #[unstable(feature = "iter_arith_traits", issue = "34529")]
617         impl<'a> Product<&'a $a> for $a {
618             fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
619                 iter.fold(1, |a, b| {
620                     a.checked_mul(*b).expect("overflow in product")
621                 })
622             }
623         }
624     )*)
625 }
626
627 macro_rules! float_sum_product {
628     ($($a:ident)*) => ($(
629         #[unstable(feature = "iter_arith_traits", issue = "34529")]
630         impl Sum for $a {
631             fn sum<I: Iterator<Item=$a>>(iter: I) -> $a {
632                 iter.fold(0.0, |a, b| a + b)
633             }
634         }
635
636         #[unstable(feature = "iter_arith_traits", issue = "34529")]
637         impl Product for $a {
638             fn product<I: Iterator<Item=$a>>(iter: I) -> $a {
639                 iter.fold(1.0, |a, b| a * b)
640             }
641         }
642
643         #[unstable(feature = "iter_arith_traits", issue = "34529")]
644         impl<'a> Sum<&'a $a> for $a {
645             fn sum<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
646                 iter.fold(0.0, |a, b| a + *b)
647             }
648         }
649
650         #[unstable(feature = "iter_arith_traits", issue = "34529")]
651         impl<'a> Product<&'a $a> for $a {
652             fn product<I: Iterator<Item=&'a $a>>(iter: I) -> $a {
653                 iter.fold(1.0, |a, b| a * *b)
654             }
655         }
656     )*)
657 }
658
659 integer_sum_product! { i8 i16 i32 i64 isize u8 u16 u32 u64 usize }
660 float_sum_product! { f32 f64 }