1 use std
::cell
::{Cell, RefCell}
;
4 /// A trait to unify FnMut for GroupBy with the chunk key in IntoChunks
7 fn call_mut(&mut self, arg
: A
) -> Self::Key
;
10 impl<'a
, A
, K
, F
: ?Sized
> KeyFunction
<A
> for F
11 where F
: FnMut(A
) -> K
15 fn call_mut(&mut self, arg
: A
) -> Self::Key
{
21 /// ChunkIndex acts like the grouping key function for IntoChunks
31 fn new(size
: usize) -> Self {
40 impl<'a
, A
> KeyFunction
<A
> for ChunkIndex
{
43 fn call_mut(&mut self, _arg
: A
) -> Self::Key
{
44 if self.index
== self.size
{
54 struct GroupInner
<K
, I
, F
>
59 current_key
: Option
<K
>,
60 current_elt
: Option
<I
::Item
>,
61 /// flag set if iterator is exhausted
63 /// Index of group we are currently buffering or visiting
65 /// Least index for which we still have elements buffered
66 oldest_buffered_group
: usize,
67 /// Group index for `buffer[0]` -- the slots
68 /// bottom_group..oldest_buffered_group are unused and will be erased when
69 /// that range is large enough.
71 /// Buffered groups, from `bottom_group` (index 0) to `top_group`.
72 buffer
: Vec
<vec
::IntoIter
<I
::Item
>>,
73 /// index of last group iter that was dropped, usize::MAX == none
77 impl<K
, I
, F
> GroupInner
<K
, I
, F
>
79 F
: for<'a
> KeyFunction
<&'a I
::Item
, Key
=K
>,
82 /// `client`: Index of group that requests next element
84 fn step(&mut self, client
: usize) -> Option
<I
::Item
> {
86 println!("client={}, bottom_group={}, oldest_buffered_group={}, top_group={}, buffers=[{}]",
87 client, self.bottom_group, self.oldest_buffered_group,
89 self.buffer.iter().map(|elt| elt.len()).format(", "));
91 if client
< self.oldest_buffered_group
{
93 } else if client
< self.top_group
||
94 (client
== self.top_group
&&
95 self.buffer
.len() > self.top_group
- self.bottom_group
)
97 self.lookup_buffer(client
)
100 } else if self.top_group
== client
{
103 self.step_buffering(client
)
108 fn lookup_buffer(&mut self, client
: usize) -> Option
<I
::Item
> {
109 // if `bufidx` doesn't exist in self.buffer, it might be empty
110 let bufidx
= client
- self.bottom_group
;
111 if client
< self.oldest_buffered_group
{
114 let elt
= self.buffer
.get_mut(bufidx
).and_then(|queue
| queue
.next());
115 if elt
.is_none() && client
== self.oldest_buffered_group
{
116 // FIXME: VecDeque is unfortunately not zero allocation when empty,
117 // so we do this job manually.
118 // `bottom_group..oldest_buffered_group` is unused, and if it's large enough, erase it.
119 self.oldest_buffered_group
+= 1;
120 // skip forward further empty queues too
121 while self.buffer
.get(self.oldest_buffered_group
- self.bottom_group
)
122 .map_or(false, |buf
| buf
.len() == 0)
124 self.oldest_buffered_group
+= 1;
127 let nclear
= self.oldest_buffered_group
- self.bottom_group
;
128 if nclear
> 0 && nclear
>= self.buffer
.len() / 2 {
130 self.buffer
.retain(|buf
| {
132 debug_assert
!(buf
.len() == 0 || i
> nclear
);
135 self.bottom_group
= self.oldest_buffered_group
;
141 /// Take the next element from the iterator, and set the done
142 /// flag if exhausted. Must not be called after done.
144 fn next_element(&mut self) -> Option
<I
::Item
> {
145 debug_assert
!(!self.done
);
146 match self.iter
.next() {
147 None
=> { self.done = true; None }
148 otherwise
=> otherwise
,
154 fn step_buffering(&mut self, client
: usize) -> Option
<I
::Item
> {
155 // requested a later group -- walk through the current group up to
156 // the requested group index, and buffer the elements (unless
157 // the group is marked as dropped).
158 // Because the `Groups` iterator is always the first to request
159 // each group index, client is the next index efter top_group.
160 debug_assert
!(self.top_group
+ 1 == client
);
161 let mut group
= Vec
::new();
163 if let Some(elt
) = self.current_elt
.take() {
164 if self.top_group
!= self.dropped_group
{
168 let mut first_elt
= None
; // first element of the next group
170 while let Some(elt
) = self.next_element() {
171 let key
= self.key
.call_mut(&elt
);
172 match self.current_key
.take() {
174 Some(old_key
) => if old_key
!= key
{
175 self.current_key
= Some(key
);
176 first_elt
= Some(elt
);
180 self.current_key
= Some(key
);
181 if self.top_group
!= self.dropped_group
{
186 if self.top_group
!= self.dropped_group
{
187 self.push_next_group(group
);
189 if first_elt
.is_some() {
191 debug_assert
!(self.top_group
== client
);
196 fn push_next_group(&mut self, group
: Vec
<I
::Item
>) {
197 // When we add a new buffered group, fill up slots between oldest_buffered_group and top_group
198 while self.top_group
- self.bottom_group
> self.buffer
.len() {
199 if self.buffer
.is_empty() {
200 self.bottom_group
+= 1;
201 self.oldest_buffered_group
+= 1;
203 self.buffer
.push(Vec
::new().into_iter());
206 self.buffer
.push(group
.into_iter());
207 debug_assert
!(self.top_group
+ 1 - self.bottom_group
== self.buffer
.len());
210 /// This is the immediate case, where we use no buffering
212 fn step_current(&mut self) -> Option
<I
::Item
> {
213 debug_assert
!(!self.done
);
214 if let elt @
Some(..) = self.current_elt
.take() {
217 match self.next_element() {
220 let key
= self.key
.call_mut(&elt
);
221 match self.current_key
.take() {
223 Some(old_key
) => if old_key
!= key
{
224 self.current_key
= Some(key
);
225 self.current_elt
= Some(elt
);
230 self.current_key
= Some(key
);
236 /// Request the just started groups' key.
238 /// `client`: Index of group
240 /// **Panics** if no group key is available.
241 fn group_key(&mut self, client
: usize) -> K
{
242 // This can only be called after we have just returned the first
243 // element of a group.
244 // Perform this by simply buffering one more element, grabbing the
246 debug_assert
!(!self.done
);
247 debug_assert
!(client
== self.top_group
);
248 debug_assert
!(self.current_key
.is_some());
249 debug_assert
!(self.current_elt
.is_none());
250 let old_key
= self.current_key
.take().unwrap();
251 if let Some(elt
) = self.next_element() {
252 let key
= self.key
.call_mut(&elt
);
256 self.current_key
= Some(key
);
257 self.current_elt
= Some(elt
);
263 impl<K
, I
, F
> GroupInner
<K
, I
, F
>
266 /// Called when a group is dropped
267 fn drop_group(&mut self, client
: usize) {
268 // It's only useful to track the maximal index
269 if self.dropped_group
== !0 || client
> self.dropped_group
{
270 self.dropped_group
= client
;
275 /// `GroupBy` is the storage for the lazy grouping operation.
277 /// If the groups are consumed in their original order, or if each
278 /// group is dropped without keeping it around, then `GroupBy` uses
279 /// no allocations. It needs allocations only if several group iterators
280 /// are alive at the same time.
282 /// This type implements `IntoIterator` (it is **not** an iterator
283 /// itself), because the group iterators need to borrow from this
284 /// value. It should be stored in a local variable or temporary and
287 /// See [`.group_by()`](../trait.Itertools.html#method.group_by) for more information.
288 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
289 pub struct GroupBy
<K
, I
, F
>
292 inner
: RefCell
<GroupInner
<K
, I
, F
>>,
293 // the group iterator's current index. Keep this in the main value
294 // so that simultaneous iterators all use the same state.
299 pub fn new
<K
, J
, F
>(iter
: J
, f
: F
) -> GroupBy
<K
, J
::IntoIter
, F
>
300 where J
: IntoIterator
,
301 F
: FnMut(&J
::Item
) -> K
,
304 inner
: RefCell
::new(GroupInner
{
306 iter
: iter
.into_iter(),
311 oldest_buffered_group
: 0,
320 impl<K
, I
, F
> GroupBy
<K
, I
, F
>
323 /// `client`: Index of group that requests next element
324 fn step(&self, client
: usize) -> Option
<I
::Item
>
325 where F
: FnMut(&I
::Item
) -> K
,
328 self.inner
.borrow_mut().step(client
)
331 /// `client`: Index of group
332 fn drop_group(&self, client
: usize) {
333 self.inner
.borrow_mut().drop_group(client
)
337 impl<'a
, K
, I
, F
> IntoIterator
for &'a GroupBy
<K
, I
, F
>
340 F
: FnMut(&I
::Item
) -> K
,
343 type Item
= (K
, Group
<'a
, K
, I
, F
>);
344 type IntoIter
= Groups
<'a
, K
, I
, F
>;
346 fn into_iter(self) -> Self::IntoIter
{
347 Groups { parent: self }
352 /// An iterator that yields the Group iterators.
354 /// Iterator element type is `(K, Group)`:
355 /// the group's key `K` and the group's iterator.
357 /// See [`.group_by()`](../trait.Itertools.html#method.group_by) for more information.
358 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
359 pub struct Groups
<'a
, K
: 'a
, I
: 'a
, F
: 'a
>
363 parent
: &'a GroupBy
<K
, I
, F
>,
366 impl<'a
, K
, I
, F
> Iterator
for Groups
<'a
, K
, I
, F
>
369 F
: FnMut(&I
::Item
) -> K
,
372 type Item
= (K
, Group
<'a
, K
, I
, F
>);
375 fn next(&mut self) -> Option
<Self::Item
> {
376 let index
= self.parent
.index
.get();
377 self.parent
.index
.set(index
+ 1);
378 let inner
= &mut *self.parent
.inner
.borrow_mut();
379 inner
.step(index
).map(|elt
| {
380 let key
= inner
.group_key(index
);
390 /// An iterator for the elements in a single group.
392 /// Iterator element type is `I::Item`.
393 pub struct Group
<'a
, K
: 'a
, I
: 'a
, F
: 'a
>
397 parent
: &'a GroupBy
<K
, I
, F
>,
399 first
: Option
<I
::Item
>,
402 impl<'a
, K
, I
, F
> Drop
for Group
<'a
, K
, I
, F
>
407 self.parent
.drop_group(self.index
);
411 impl<'a
, K
, I
, F
> Iterator
for Group
<'a
, K
, I
, F
>
414 F
: FnMut(&I
::Item
) -> K
,
419 fn next(&mut self) -> Option
<Self::Item
> {
420 if let elt @
Some(..) = self.first
.take() {
423 self.parent
.step(self.index
)
427 ///// IntoChunks /////
430 pub fn new_chunks
<J
>(iter
: J
, size
: usize) -> IntoChunks
<J
::IntoIter
>
431 where J
: IntoIterator
,
434 inner
: RefCell
::new(GroupInner
{
435 key
: ChunkIndex
::new(size
),
436 iter
: iter
.into_iter(),
441 oldest_buffered_group
: 0,
451 /// `ChunkLazy` is the storage for a lazy chunking operation.
453 /// `IntoChunks` behaves just like `GroupBy`: it is iterable, and
454 /// it only buffers if several chunk iterators are alive at the same time.
456 /// This type implements `IntoIterator` (it is **not** an iterator
457 /// itself), because the chunk iterators need to borrow from this
458 /// value. It should be stored in a local variable or temporary and
461 /// Iterator element type is `Chunk`, each chunk's iterator.
463 /// See [`.chunks()`](../trait.Itertools.html#method.chunks) for more information.
464 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
465 pub struct IntoChunks
<I
>
468 inner
: RefCell
<GroupInner
<usize, I
, ChunkIndex
>>,
469 // the chunk iterator's current index. Keep this in the main value
470 // so that simultaneous iterators all use the same state.
475 impl<I
> IntoChunks
<I
>
478 /// `client`: Index of chunk that requests next element
479 fn step(&self, client
: usize) -> Option
<I
::Item
> {
480 self.inner
.borrow_mut().step(client
)
483 /// `client`: Index of chunk
484 fn drop_group(&self, client
: usize) {
485 self.inner
.borrow_mut().drop_group(client
)
489 impl<'a
, I
> IntoIterator
for &'a IntoChunks
<I
>
493 type Item
= Chunk
<'a
, I
>;
494 type IntoIter
= Chunks
<'a
, I
>;
496 fn into_iter(self) -> Self::IntoIter
{
504 /// An iterator that yields the Chunk iterators.
506 /// Iterator element type is `Chunk`.
508 /// See [`.chunks()`](../trait.Itertools.html#method.chunks) for more information.
509 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
510 pub struct Chunks
<'a
, I
: 'a
>
514 parent
: &'a IntoChunks
<I
>,
517 impl<'a
, I
> Iterator
for Chunks
<'a
, I
>
521 type Item
= Chunk
<'a
, I
>;
524 fn next(&mut self) -> Option
<Self::Item
> {
525 let index
= self.parent
.index
.get();
526 self.parent
.index
.set(index
+ 1);
527 let inner
= &mut *self.parent
.inner
.borrow_mut();
528 inner
.step(index
).map(|elt
| {
538 /// An iterator for the elements in a single chunk.
540 /// Iterator element type is `I::Item`.
541 pub struct Chunk
<'a
, I
: 'a
>
545 parent
: &'a IntoChunks
<I
>,
547 first
: Option
<I
::Item
>,
550 impl<'a
, I
> Drop
for Chunk
<'a
, I
>
555 self.parent
.drop_group(self.index
);
559 impl<'a
, I
> Iterator
for Chunk
<'a
, I
>
565 fn next(&mut self) -> Option
<Self::Item
> {
566 if let elt @
Some(..) = self.first
.take() {
569 self.parent
.step(self.index
)