--- /dev/null
+use std::cell::{Cell, RefCell};
+use std::vec;
+
+/// A trait to unify FnMut for GroupBy with the chunk key in IntoChunks
+trait KeyFunction<A> {
+ type Key;
+ fn call_mut(&mut self, arg: A) -> Self::Key;
+}
+
+impl<'a, A, K, F: ?Sized> KeyFunction<A> for F
+ where F: FnMut(A) -> K
+{
+ type Key = K;
+ #[inline]
+ fn call_mut(&mut self, arg: A) -> Self::Key {
+ (*self)(arg)
+ }
+}
+
+
+/// ChunkIndex acts like the grouping key function for IntoChunks
+#[derive(Debug)]
+struct ChunkIndex {
+ size: usize,
+ index: usize,
+ key: usize,
+}
+
+impl ChunkIndex {
+ #[inline(always)]
+ fn new(size: usize) -> Self {
+ ChunkIndex {
+ size: size,
+ index: 0,
+ key: 0,
+ }
+ }
+}
+
+impl<'a, A> KeyFunction<A> for ChunkIndex {
+ type Key = usize;
+ #[inline(always)]
+ fn call_mut(&mut self, _arg: A) -> Self::Key {
+ if self.index == self.size {
+ self.key += 1;
+ self.index = 0;
+ }
+ self.index += 1;
+ self.key
+ }
+}
+
+
+struct GroupInner<K, I, F>
+ where I: Iterator
+{
+ key: F,
+ iter: I,
+ current_key: Option<K>,
+ current_elt: Option<I::Item>,
+ /// flag set if iterator is exhausted
+ done: bool,
+ /// Index of group we are currently buffering or visiting
+ top_group: usize,
+ /// Least index for which we still have elements buffered
+ oldest_buffered_group: usize,
+ /// Group index for `buffer[0]` -- the slots
+ /// bottom_group..oldest_buffered_group are unused and will be erased when
+ /// that range is large enough.
+ bottom_group: usize,
+ /// Buffered groups, from `bottom_group` (index 0) to `top_group`.
+ buffer: Vec<vec::IntoIter<I::Item>>,
+ /// index of last group iter that was dropped, usize::MAX == none
+ dropped_group: usize,
+}
+
+impl<K, I, F> GroupInner<K, I, F>
+ where I: Iterator,
+ F: for<'a> KeyFunction<&'a I::Item, Key=K>,
+ K: PartialEq,
+{
+ /// `client`: Index of group that requests next element
+ #[inline(always)]
+ fn step(&mut self, client: usize) -> Option<I::Item> {
+ /*
+ println!("client={}, bottom_group={}, oldest_buffered_group={}, top_group={}, buffers=[{}]",
+ client, self.bottom_group, self.oldest_buffered_group,
+ self.top_group,
+ self.buffer.iter().map(|elt| elt.len()).format(", "));
+ */
+ if client < self.oldest_buffered_group {
+ None
+ } else if client < self.top_group ||
+ (client == self.top_group &&
+ self.buffer.len() > self.top_group - self.bottom_group)
+ {
+ self.lookup_buffer(client)
+ } else if self.done {
+ None
+ } else if self.top_group == client {
+ self.step_current()
+ } else {
+ self.step_buffering(client)
+ }
+ }
+
+ #[inline(never)]
+ fn lookup_buffer(&mut self, client: usize) -> Option<I::Item> {
+ // if `bufidx` doesn't exist in self.buffer, it might be empty
+ let bufidx = client - self.bottom_group;
+ if client < self.oldest_buffered_group {
+ return None;
+ }
+ let elt = self.buffer.get_mut(bufidx).and_then(|queue| queue.next());
+ if elt.is_none() && client == self.oldest_buffered_group {
+ // FIXME: VecDeque is unfortunately not zero allocation when empty,
+ // so we do this job manually.
+ // `bottom_group..oldest_buffered_group` is unused, and if it's large enough, erase it.
+ self.oldest_buffered_group += 1;
+ // skip forward further empty queues too
+ while self.buffer.get(self.oldest_buffered_group - self.bottom_group)
+ .map_or(false, |buf| buf.len() == 0)
+ {
+ self.oldest_buffered_group += 1;
+ }
+
+ let nclear = self.oldest_buffered_group - self.bottom_group;
+ if nclear > 0 && nclear >= self.buffer.len() / 2 {
+ let mut i = 0;
+ self.buffer.retain(|buf| {
+ i += 1;
+ debug_assert!(buf.len() == 0 || i > nclear);
+ i > nclear
+ });
+ self.bottom_group = self.oldest_buffered_group;
+ }
+ }
+ elt
+ }
+
+ /// Take the next element from the iterator, and set the done
+ /// flag if exhausted. Must not be called after done.
+ #[inline(always)]
+ fn next_element(&mut self) -> Option<I::Item> {
+ debug_assert!(!self.done);
+ match self.iter.next() {
+ None => { self.done = true; None }
+ otherwise => otherwise,
+ }
+ }
+
+
+ #[inline(never)]
+ fn step_buffering(&mut self, client: usize) -> Option<I::Item> {
+ // requested a later group -- walk through the current group up to
+ // the requested group index, and buffer the elements (unless
+ // the group is marked as dropped).
+ // Because the `Groups` iterator is always the first to request
+ // each group index, client is the next index efter top_group.
+ debug_assert!(self.top_group + 1 == client);
+ let mut group = Vec::new();
+
+ if let Some(elt) = self.current_elt.take() {
+ if self.top_group != self.dropped_group {
+ group.push(elt);
+ }
+ }
+ let mut first_elt = None; // first element of the next group
+
+ while let Some(elt) = self.next_element() {
+ let key = self.key.call_mut(&elt);
+ match self.current_key.take() {
+ None => {}
+ Some(old_key) => if old_key != key {
+ self.current_key = Some(key);
+ first_elt = Some(elt);
+ break;
+ },
+ }
+ self.current_key = Some(key);
+ if self.top_group != self.dropped_group {
+ group.push(elt);
+ }
+ }
+
+ if self.top_group != self.dropped_group {
+ self.push_next_group(group);
+ }
+ if first_elt.is_some() {
+ self.top_group += 1;
+ debug_assert!(self.top_group == client);
+ }
+ first_elt
+ }
+
+ fn push_next_group(&mut self, group: Vec<I::Item>) {
+ // When we add a new buffered group, fill up slots between oldest_buffered_group and top_group
+ while self.top_group - self.bottom_group > self.buffer.len() {
+ if self.buffer.is_empty() {
+ self.bottom_group += 1;
+ self.oldest_buffered_group += 1;
+ } else {
+ self.buffer.push(Vec::new().into_iter());
+ }
+ }
+ self.buffer.push(group.into_iter());
+ debug_assert!(self.top_group + 1 - self.bottom_group == self.buffer.len());
+ }
+
+ /// This is the immediate case, where we use no buffering
+ #[inline]
+ fn step_current(&mut self) -> Option<I::Item> {
+ debug_assert!(!self.done);
+ if let elt @ Some(..) = self.current_elt.take() {
+ return elt;
+ }
+ match self.next_element() {
+ None => None,
+ Some(elt) => {
+ let key = self.key.call_mut(&elt);
+ match self.current_key.take() {
+ None => {}
+ Some(old_key) => if old_key != key {
+ self.current_key = Some(key);
+ self.current_elt = Some(elt);
+ self.top_group += 1;
+ return None;
+ },
+ }
+ self.current_key = Some(key);
+ Some(elt)
+ }
+ }
+ }
+
+ /// Request the just started groups' key.
+ ///
+ /// `client`: Index of group
+ ///
+ /// **Panics** if no group key is available.
+ fn group_key(&mut self, client: usize) -> K {
+ // This can only be called after we have just returned the first
+ // element of a group.
+ // Perform this by simply buffering one more element, grabbing the
+ // next key.
+ debug_assert!(!self.done);
+ debug_assert!(client == self.top_group);
+ debug_assert!(self.current_key.is_some());
+ debug_assert!(self.current_elt.is_none());
+ let old_key = self.current_key.take().unwrap();
+ if let Some(elt) = self.next_element() {
+ let key = self.key.call_mut(&elt);
+ if old_key != key {
+ self.top_group += 1;
+ }
+ self.current_key = Some(key);
+ self.current_elt = Some(elt);
+ }
+ old_key
+ }
+}
+
+impl<K, I, F> GroupInner<K, I, F>
+ where I: Iterator,
+{
+ /// Called when a group is dropped
+ fn drop_group(&mut self, client: usize) {
+ // It's only useful to track the maximal index
+ if self.dropped_group == !0 || client > self.dropped_group {
+ self.dropped_group = client;
+ }
+ }
+}
+
+/// `GroupBy` is the storage for the lazy grouping operation.
+///
+/// If the groups are consumed in their original order, or if each
+/// group is dropped without keeping it around, then `GroupBy` uses
+/// no allocations. It needs allocations only if several group iterators
+/// are alive at the same time.
+///
+/// This type implements `IntoIterator` (it is **not** an iterator
+/// itself), because the group iterators need to borrow from this
+/// value. It should be stored in a local variable or temporary and
+/// iterated.
+///
+/// See [`.group_by()`](../trait.Itertools.html#method.group_by) for more information.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+pub struct GroupBy<K, I, F>
+ where I: Iterator,
+{
+ inner: RefCell<GroupInner<K, I, F>>,
+ // the group iterator's current index. Keep this in the main value
+ // so that simultaneous iterators all use the same state.
+ index: Cell<usize>,
+}
+
+/// Create a new
+pub fn new<K, J, F>(iter: J, f: F) -> GroupBy<K, J::IntoIter, F>
+ where J: IntoIterator,
+ F: FnMut(&J::Item) -> K,
+{
+ GroupBy {
+ inner: RefCell::new(GroupInner {
+ key: f,
+ iter: iter.into_iter(),
+ current_key: None,
+ current_elt: None,
+ done: false,
+ top_group: 0,
+ oldest_buffered_group: 0,
+ bottom_group: 0,
+ buffer: Vec::new(),
+ dropped_group: !0,
+ }),
+ index: Cell::new(0),
+ }
+}
+
+impl<K, I, F> GroupBy<K, I, F>
+ where I: Iterator,
+{
+ /// `client`: Index of group that requests next element
+ fn step(&self, client: usize) -> Option<I::Item>
+ where F: FnMut(&I::Item) -> K,
+ K: PartialEq,
+ {
+ self.inner.borrow_mut().step(client)
+ }
+
+ /// `client`: Index of group
+ fn drop_group(&self, client: usize) {
+ self.inner.borrow_mut().drop_group(client)
+ }
+}
+
+impl<'a, K, I, F> IntoIterator for &'a GroupBy<K, I, F>
+ where I: Iterator,
+ I::Item: 'a,
+ F: FnMut(&I::Item) -> K,
+ K: PartialEq
+{
+ type Item = (K, Group<'a, K, I, F>);
+ type IntoIter = Groups<'a, K, I, F>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ Groups { parent: self }
+ }
+}
+
+
+/// An iterator that yields the Group iterators.
+///
+/// Iterator element type is `(K, Group)`:
+/// the group's key `K` and the group's iterator.
+///
+/// See [`.group_by()`](../trait.Itertools.html#method.group_by) for more information.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+pub struct Groups<'a, K: 'a, I: 'a, F: 'a>
+ where I: Iterator,
+ I::Item: 'a
+{
+ parent: &'a GroupBy<K, I, F>,
+}
+
+impl<'a, K, I, F> Iterator for Groups<'a, K, I, F>
+ where I: Iterator,
+ I::Item: 'a,
+ F: FnMut(&I::Item) -> K,
+ K: PartialEq
+{
+ type Item = (K, Group<'a, K, I, F>);
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ let index = self.parent.index.get();
+ self.parent.index.set(index + 1);
+ let inner = &mut *self.parent.inner.borrow_mut();
+ inner.step(index).map(|elt| {
+ let key = inner.group_key(index);
+ (key, Group {
+ parent: self.parent,
+ index: index,
+ first: Some(elt),
+ })
+ })
+ }
+}
+
+/// An iterator for the elements in a single group.
+///
+/// Iterator element type is `I::Item`.
+pub struct Group<'a, K: 'a, I: 'a, F: 'a>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ parent: &'a GroupBy<K, I, F>,
+ index: usize,
+ first: Option<I::Item>,
+}
+
+impl<'a, K, I, F> Drop for Group<'a, K, I, F>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ fn drop(&mut self) {
+ self.parent.drop_group(self.index);
+ }
+}
+
+impl<'a, K, I, F> Iterator for Group<'a, K, I, F>
+ where I: Iterator,
+ I::Item: 'a,
+ F: FnMut(&I::Item) -> K,
+ K: PartialEq,
+{
+ type Item = I::Item;
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ if let elt @ Some(..) = self.first.take() {
+ return elt;
+ }
+ self.parent.step(self.index)
+ }
+}
+
+///// IntoChunks /////
+
+/// Create a new
+pub fn new_chunks<J>(iter: J, size: usize) -> IntoChunks<J::IntoIter>
+ where J: IntoIterator,
+{
+ IntoChunks {
+ inner: RefCell::new(GroupInner {
+ key: ChunkIndex::new(size),
+ iter: iter.into_iter(),
+ current_key: None,
+ current_elt: None,
+ done: false,
+ top_group: 0,
+ oldest_buffered_group: 0,
+ bottom_group: 0,
+ buffer: Vec::new(),
+ dropped_group: !0,
+ }),
+ index: Cell::new(0),
+ }
+}
+
+
+/// `ChunkLazy` is the storage for a lazy chunking operation.
+///
+/// `IntoChunks` behaves just like `GroupBy`: it is iterable, and
+/// it only buffers if several chunk iterators are alive at the same time.
+///
+/// This type implements `IntoIterator` (it is **not** an iterator
+/// itself), because the chunk iterators need to borrow from this
+/// value. It should be stored in a local variable or temporary and
+/// iterated.
+///
+/// Iterator element type is `Chunk`, each chunk's iterator.
+///
+/// See [`.chunks()`](../trait.Itertools.html#method.chunks) for more information.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+pub struct IntoChunks<I>
+ where I: Iterator,
+{
+ inner: RefCell<GroupInner<usize, I, ChunkIndex>>,
+ // the chunk iterator's current index. Keep this in the main value
+ // so that simultaneous iterators all use the same state.
+ index: Cell<usize>,
+}
+
+
+impl<I> IntoChunks<I>
+ where I: Iterator,
+{
+ /// `client`: Index of chunk that requests next element
+ fn step(&self, client: usize) -> Option<I::Item> {
+ self.inner.borrow_mut().step(client)
+ }
+
+ /// `client`: Index of chunk
+ fn drop_group(&self, client: usize) {
+ self.inner.borrow_mut().drop_group(client)
+ }
+}
+
+impl<'a, I> IntoIterator for &'a IntoChunks<I>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ type Item = Chunk<'a, I>;
+ type IntoIter = Chunks<'a, I>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ Chunks {
+ parent: self,
+ }
+ }
+}
+
+
+/// An iterator that yields the Chunk iterators.
+///
+/// Iterator element type is `Chunk`.
+///
+/// See [`.chunks()`](../trait.Itertools.html#method.chunks) for more information.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+pub struct Chunks<'a, I: 'a>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ parent: &'a IntoChunks<I>,
+}
+
+impl<'a, I> Iterator for Chunks<'a, I>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ type Item = Chunk<'a, I>;
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ let index = self.parent.index.get();
+ self.parent.index.set(index + 1);
+ let inner = &mut *self.parent.inner.borrow_mut();
+ inner.step(index).map(|elt| {
+ Chunk {
+ parent: self.parent,
+ index: index,
+ first: Some(elt),
+ }
+ })
+ }
+}
+
+/// An iterator for the elements in a single chunk.
+///
+/// Iterator element type is `I::Item`.
+pub struct Chunk<'a, I: 'a>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ parent: &'a IntoChunks<I>,
+ index: usize,
+ first: Option<I::Item>,
+}
+
+impl<'a, I> Drop for Chunk<'a, I>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ fn drop(&mut self) {
+ self.parent.drop_group(self.index);
+ }
+}
+
+impl<'a, I> Iterator for Chunk<'a, I>
+ where I: Iterator,
+ I::Item: 'a,
+{
+ type Item = I::Item;
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ if let elt @ Some(..) = self.first.take() {
+ return elt;
+ }
+ self.parent.step(self.index)
+ }
+}
projects / rustc.git / blobdiff