1 /***********************************************************************
2  * Copyright (c) 2013-2025 General Atomics Integrated Intelligence, Inc.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Apache License, Version 2.0
5  * which accompanies this distribution and is available at
6  * https://www.apache.org/licenses/LICENSE-2.0
7  ***********************************************************************/
8 
9 package org.locationtech.geomesa.utils.iterators
10 
11 /**
12  * Can create an iterator over all combinations of items from a list-of-lists.
13  * Because the final list of combinations can be large, we allow for a safe
14  * way to query the list size that is independent of the iterator itself.
15  * (That is, asking for the size does not exhaust any iterator.)
16  *
17  * NB:  The first sequence is the least significant; that is, it will
18  * increment fast while the last sequence is the most significant (will
19  * increment slowly).
20  *
21  * @param seqs the list-of-lists whose items are to be recombined
22  */
23 
24 case class CartesianProductIterable(seqs: Seq[Seq[_]]) extends Iterable[Seq[_]] {
25   lazy val expectedSize: Long = seqs.map(_.size.toLong).product
26 
27   def iterator: Iterator[Seq[_]] = new Iterator[Seq[_]] {
28     private val n: Int = seqs.size
29     private val maxes: Vector[Int] = seqs.map(seq => seq.size).toVector
30     private val indexes = Array.ofDim[Int](seqs.size)
31     private var nextItem: Seq[_] = if (isValid) realize else null
32 
33     def isValid: Boolean = (0 until n).forall(i => indexes(i) < maxes(i))
34 
35     def realize: Seq[_] = (0 until n).map(i => seqs(i)(indexes(i)))
36 
37     def hasNext: Boolean = nextItem != null
38 
39     def next(): Seq[_] = {
40       if (nextItem == null) throw new Exception("Iterator exhausted")
41       val result = nextItem
42 
43       // advance the internal state
44       nextItem = null
45       var j = 0
46       var done = false
47       while (j < n && !done) {
48         indexes(j) = indexes(j) + 1
49         if (indexes(j) >= maxes(j)) {
50           indexes(j) = 0
51           j = j + 1
52         } else {
53           done = true
54         }
55       }
56       if (done || j < n) nextItem = realize
57 
58       result
59     }
60   }
61 }