alex-plekhanov commented on a change in pull request #9234:
URL: https://github.com/apache/ignite/pull/9234#discussion_r673033919
##########
File path:
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
##########
@@ -113,49 +104,65 @@ else if (ectx.rowHandler().get(firstCol, lower) != null
&& ectx.rowHandler().get
}
/**
- *
+ * Cursor to navigate through a sorted list with duplicates.
*/
private class Cursor implements GridCursor<Row> {
- /** Sub map iterator. */
- private final Iterator<Map.Entry<Row, List<Row>>> mapIt;
+ /** List of rows. */
+ private final List<Row> rows;
- /** Iterator over rows with equal index keys. */
- private Iterator<Row> listIt;
+ /** Upper bound. */
+ private final Row upper;
- /** */
+ /** Current row. */
private Row row;
- /** */
- Cursor(SortedMap<Row, List<Row>> subMap) {
- mapIt = subMap.entrySet().iterator();
- listIt = null;
- }
+ /** Current index of list element. */
+ private int idx;
- /** {@inheritDoc} */
- @Override public boolean next() throws IgniteCheckedException {
- if (!hasNext())
- return false;
-
- next0();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound (inclusive).
+ * @param upper Upper bound (inclusive).
+ */
+ Cursor(List<Row> rows, @Nullable Row lower, @Nullable Row upper) {
+ this.rows = rows;
+ this.upper = upper;
- return true;
+ idx = computeStartIdx(rows, lower) - 1;
}
- /** */
- private boolean hasNext() {
- return listIt != null && listIt.hasNext() || mapIt.hasNext();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound.
+ * @return Lower bound position in the list.
+ */
+ private int computeStartIdx(List<Row> rows, @Nullable Row lower) {
+ int fromIdx = lower == null ? -1 : Collections.binarySearch(rows,
lower, comp);
+
+ if (fromIdx < 0)
+ fromIdx = -fromIdx - 1;
+ else {
+ // Skip duplcates.
+ while (fromIdx > 0 && comp.compare(rows.get(fromIdx - 1),
rows.get(fromIdx)) == 0)
Review comment:
What if there is only one distinct value? In this case algorithm
downgrade to O(n) instead of O(ln(n))
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
