8000 Merge pull request scala/scala#11029 from som-snytt/wip/indexed-sliding · scala/scala3@6735bbe · GitHub
[go: up one dir, main page]
Skip to content

Commit 6735bbe

Browse files
som-snyttsom-snytt
authored
Merge pull request scala/scala#11029 from som-snytt/wip/indexed-sliding
A fast sliding iterator for IndexedSeqs
2 parents 62d069e + 6755b3e commit 6735bbe

File tree

3 files changed

+39
-12
lines changed

3 files changed

+39
-12
lines changed

‎library/src/scala/collection/IndexedSeq.scala

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -91,6 +91,11 @@ trait IndexedSeqOps[+A, +CC[_], +C] extends Any with SeqOps[A, CC, C] { self =>
9191

9292
override def slice(from: Int, until: Int): C = fromSpecific(new IndexedSeqView.Slice(this, from, until))
9393

94+
override def sliding(size: Int, step: Int): Iterator[C] = {
95+
require(size >= 1 && step >= 1, f"size=$size%d and step=$step%d, but both must be positive")
96+
new IndexedSeqSlidingIterator[A, CC, C](this, size, step)
97+
}
98+
9499
override def head: A =
95100
if (!isEmpty) apply(0)
96101
else throw new NoSuchElementException(s"head of empty ${
@@ -145,3 +150,26 @@ trait IndexedSeqOps[+A, +CC[_], +C] extends Any with SeqOps[A, CC, C] { self =>
145150
}
146151
}
147152
}
153+
154+
/** A fast sliding iterator for IndexedSeqs which uses the underlying `slice` operation. */
 10000
155+
private final class IndexedSeqSlidingIterator[A, CC[_], C](s: IndexedSeqOps[A, CC, C], size: Int, step: Int)
156+
extends AbstractIterator[C] {
157+
158+
private[this] val len = s.length
159+
private[this] var pos = 0
160+
private def chklen: Boolean = len == s.length || {
161+
throw new java.util.ConcurrentModificationException("collection size changed during iteration")
162+
false
163+
}
164+
165+
def hasNext: Boolean = chklen && pos < len
166+
167+
def next(): C = if (!chklen || !hasNext) Iterator.empty.next() else {
168+
val end = { val x = pos + size; if (x < 0 || x > len) len else x } // (pos.toLong + size).min(len).toInt
169+
val slice = s.slice(pos, end)
170+
pos =
171+
if (end >= len) len
172+
else { val x = pos + step; if (x < 0 || x > len) len else x } // (pos.toLong + step).min(len).toInt
173+
slice
174+
}
175+
}

‎library/src/scala/collection/mutable/ArrayBuffer.scala

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -269,9 +269,16 @@ class ArrayBuffer[A] private (initialElements: Array[AnyRef], initialSize: Int)
269269

270270
override def foldRight[B](z: B)(op: (A, B) => B): B = foldr(0, length, z, op)
271271

272-
override def reduceLeft[B >: A](op: (B, A) => B): B = if (length > 0) foldl(1, length, array(0).asInstanceOf[B], op) else super.reduceLeft(op)
272+
override def reduceLeft[B >: A](op: (B, A) => B): B =
273+
if (length > 0) foldl(1, length, array(0).asInstanceOf[B], op)
274+
else super.reduceLeft(op)
273275

274-
override def reduceRight[B >: A](op: (A, B) => B): B = if (length > 0) foldr(0, length - 1, array(length - 1).asInstanceOf[B], op) else super.reduceRight(op)
276+
override def reduceRight[B >: A](op: (A, B) => B): B =
277+
if (length > 0) foldr(0, length - 1, array(length - 1).asInstanceOf[B], op)
278+
else super.reduceRight(op)
279+
280+
override def sliding(size: Int, step: Int): Iterator[ArrayBuffer[A]] =
281+
new MutationTracker.CheckedIterator(super.sliding(size = size, step = step), mutationCount)
275282
}
276283

277284
/**

‎library/src/scala/collection/mutable/ArrayDeque.scala

Lines changed: 2 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -633,16 +633,8 @@ trait ArrayDequeOps[A, +CC[_], +C <: AnyRef] extends StrictOptimizedSeqOps[A, CC
633633
}
634634
}
635635

636-
override def sliding(window: Int, step: Int): Iterator[C] = {
637-
require(window > 0 && step > 0, s"window=$window and step=$step, but both must be positive")
638-
length match {
639-
case 0 => Iterator.empty
640-
case n if n <= window => Iterator.single(slice(0, length))
641-
case n =>
642-
val lag = if (window > step) window - step else 0
643-
Iterator.range(start = 0, end = n - lag, step = step).map(i => slice(i, i + window))
644-
}
645-
}
636+
override def sliding(@deprecatedName("window") size: Int, step: Int): Iterator[C] =
637+
super.sliding(size = size, step = step)
646638

647639
override def grouped(n: Int): Iterator[C] = sliding(n, n)
648640
}

0 commit comments

Comments
 (0)
0