Implementing sparse_range: From a Python Discuss Idea to a Sieve Stress Test
I found an interesting thread over on the Python Discuss forum titled "Possibility to exclude ranges from range". The initial discussion revolved around a common (?), developer need of : how to cleanly skip specific blocks of ints in a range of ints without writing clunky, nested if/continue logic, and without doing something memory-heavy like casting everything into a massive set.
The consensus was that Python's native range is beautiful because it’s a lightweight, memory-efficient arithmetic engine. It doesn't store numbers in RAM; it just calculates them on the fly. But the moment you need to punch holes in it—say, "give me all numbers from 1 to 1000, except for multiples of 5, and except for the block from 200 to 300"—you lose that structural elegance.
This inspired me to build a clean, production-grade abstraction to solve this kind of thng: sparse_range.
The Architectural Concept
The core idea began with a simple mathematical definition: a Sparse range instance is created by a set of (python) ranges S_in that hold possible output values and a set of ranges S_ex that exclude possible output values. A Sparse_range instance can be called with a start, stop, and step argument that generate trial output candidates that are checked against S_in and S_ex to see if they are allowed/filtered. An item is eligible for the final output if its value is present in at least one of our permitted baseline ranges S_in, unless that value happens to be intercepted by one of our forbidden exclusion ranges S_ex. On top of that structure, the outer sparse_range wrapper behaves like a native Python range—it accepts its own outer start, stop, and step constraints, matching the target window requested by the user.
To make the evaluation stateless and fast(?), the engine must evaluate values on the fly. However, native Python range objects are immutable and opaque; they don't natively maintain operational iteration states, nor do they know how to coordinate with one another.
To bridge this gap, the engine internally upgrades every raw Python range passed to collections S_in and S_ex into custom RangePointers.
Why We Need RangePointer and Direction Alignment
When the outer loop steps through values, the internal component ranges must follow along. If the outer loop is counting upwards (step > 0), all internal evaluation cursors must track upwards. If the outer loop reverses direction and counts downwards (step < 0), every single internal range must generate the same values, but in the reverse order, and without using up extra memory for storing values.
If they don't match directions, the leapfrogging logic breaks. A forward-running pointer cannot efficiently tell a backward-running outer loop where the next valid alignment boundary is without wasting CPU cycles scanning dead space or whatever.
Therefore, when a sparse_range instance is invoked, the engine inspects the outer step direction and enforces a unified traversal direction across every single internal S_in and S_ex sequence. If an internal range's native direction opposes the outer loop, it must be completely mathematically inverted.
The Range Reversal Formula
Reversing an arithmetic progression isn't as simple as swapping the start and stop boundaries. Because Python ranges stop before reaching the termination boundary, reversing a range requires recalculating its new alignment based on its exact step constraints.
To reverse a range mathematically, the engine computes:
New Step: The step sign is flipped (-step).
New Start: The final valid item generated by the original range becomes the new starting point. This is computed using the remainder of the length of the sequence:
new_start = start + (length - 1) × step
New Stop: The original start boundary shifts out by one step inverted to act as the non-inclusive terminal wall:
By normalizing all RangePointer instances to track in the exact same direction as the outer loop, the engine can efficiently step through candidate numbers, skipping blocks of excluded data in O(1) or O(K) time (where K is the number of active ranges), keeping the memory footprint at absolute zero.
The code
sparse_range.py
#!/bin/env python3
# Author: Donald "Paddy" McCarthy. paddy3118@gmail.com
# 27/06/2026
#%%
"""
sparse_range - Reusable Sparse Integer Generators
===================================================
This module provides a configured factory class `sparse_range`. You define your
global permitted (`s_in`) and forbidden (`s_ex`) integer lists once, and the
resulting object can be called repeatedly with customized window configurations
exactly like Python's built-in `range()` function.
Usage
-----
>>> from sparse_range import sparse_range
>>> # Configure the template rules
>>> my_filter = sparse_range(s_in=[range(0, 100, 2)], s_ex=[range(10, 20, 3)])
>>>
>>> # Call it like the built-in range function
>>> sequence = my_filter(0, 30, 3)
>>> list(sequence)
[0, 6, 24]
Command Line Interface
----------------------
Run this script directly to run differential limits tests or inspect help files:
python sparse_range.py
"""
import sys
from typing import List, Optional, Iterator, Set, Dict
# Explicitly define module exports
__all__ = ['sparse_range']
class RangePointer:
"""
Manages a single sub-range's mathematical cursor.
Dynamically aligns itself relative to the iteration direction of the caller.
"""
def __init__(self, r: range) -> None:
"""Initializes structural constraints of a single tracking range cursor."""
self.start: int = r.start
self.stop: int = r.stop
self.step: int = r.step
self.length: int = len(r)
# Calculate the actual last element generated by this range
if self.length > 0:
self.last: Optional[int] = r.start + (self.length - 1) * r.step
else:
self.last = None
def align_to_or_past(self, target: int, direction: int) -> Optional[int]:
"""
Leapfrogs the cursor instantly to the closest valid element
aligned with the runtime's traversal direction.
"""
if self.length == 0 or self.last is None:
return None
# 1. Check if the target is entirely out of bounds for this sub-range
low, high = min(self.start, self.last), max(self.start, self.last)
if target < low:
return self.start if direction > 0 else None
if target > high:
return None if direction > 0 else self.last
# 2. Project target onto the arithmetic sequence of this range
distance = target - self.start
if self.step > 0:
k = (distance + self.step - 1) // self.step if distance > 0 else distance // self.step
else:
k = distance // self.step if distance > 0 else (distance + self.step + 1) // self.step
candidate = self.start + k * self.step
# 3. Sweep forward/backward based on global runtime direction
if direction > 0:
while candidate < target:
candidate += self.step
if low <= candidate <= high:
return candidate
else:
while candidate > target:
candidate -= self.step
if low <= candidate <= high:
return candidate
return None
class SparseRangeIterable:
"""The execution runner returned when a configured sparse_range is called."""
def __init__(self, start: int, stop: int, step: int, s_in: List[range], s_ex: List[range]) -> None:
"""Prepares runtime matrices for specific window iterations."""
if step == 0:
raise ValueError("sparse_range loop step argument must not be zero")
self.start: int = start
self.stop: int = stop
self.step: int = step
self.direction: int = 1 if step > 0 else -1
self.in_ranges: List[RangePointer] = [RangePointer(r) for r in s_in if len(r) > 0]
self.ex_ranges: List[RangePointer] = [RangePointer(r) for r in s_ex if len(r) > 0]
def __iter__(self) -> Iterator[int]:
"""Iterates through matching sparse elements using double-pointer acceleration."""
target = self.start
stop = self.stop
step = self.step
dir_mask = self.direction
while (dir_mask > 0 and target < stop) or (dir_mask < 0 and target > stop):
# Align all input sub-ranges and collect their active values
active_in: Dict[RangePointer, int] = {}
for p in self.in_ranges:
val = p.align_to_or_past(target, dir_mask)
if val is not None:
active_in[p] = val
if not active_in:
break
# Align all exclusion sub-ranges
active_ex: Dict[RangePointer, int] = {}
for p in self.ex_ranges:
val = p.align_to_or_past(target, dir_mask)
if val is not None:
active_ex[p] = val
# Dynamic Execution Strategy Optimization Lookup
is_included = False
if len(active_in) <= len(active_ex):
if any(val == target for val in active_in.values()):
if not any(val == target for val in active_ex.values()):
is_included = True
else:
if not any(val == target for val in active_ex.values()):
if any(val == target for val in active_in.values()):
is_included = True
if is_included:
yield target
target += step
class sparse_range:
"""
A factory pattern configuration setup that caches structural filter limits.
Instances can be directly invoked exactly like the standard range() construct.
"""
def __init__(self, s_in: Optional[List[range]] = None, s_ex: Optional[List[range]] = None) -> None:
"""Instantiates the filtering template for subsequent executions."""
self._s_in_raw: List[range] = s_in or []
self._s_ex_raw: List[range] = s_ex or []
def __repr__(self) -> str:
"""Returns structural serialization details for troubleshooting."""
return f"sparse_range(s_in={self._s_in_raw}, s_ex={self._s_ex_raw})"
def __call__(self, start: int, stop: Optional[int] = None, step: int = 1) -> SparseRangeIterable:
"""Mimics the signature properties of Python's default range() function."""
if stop is None:
stop = start
start = 0
return SparseRangeIterable(start, stop, step, self._s_in_raw, self._s_ex_raw)
def _expensive_sparse_range(start: int, stop: int, step: int, s_in: List[range], s_ex: List[range]) -> List[int]:
"""Reference high-memory execution harness to generate baseline validation benchmarks."""
allowed: Set[int] = set()
for r in (s_in or []):
allowed.update(r)
for r in (s_ex or []):
allowed.difference_update(r)
target = start
direction = 1 if step > 0 else -1
result: List[int] = []
while (direction > 0 and target < stop) or (direction < 0 and target > stop):
if target in allowed:
result.append(target)
target += step
return result
def run_tests() -> None:
"""Runs structural verification configurations spanning cross-boundary constraints."""
print("Running Factory Pattern Limits Verification Suite (-1000 to +1000)...\n")
# 1. Main dynamic test setup
filter_config = sparse_range(
s_in=[range(-500, 500, 3)],
s_ex=[range(-50, 50, 2), range(200, 300, 5)]
)
test_windows = [
("Standard positive crawl", (0, 200, 2)),
("Negative direction crawl", (400, -400, -5)),
("Large step slice jump", (-1000, 1000, 25)),
("Completely out of bounds window", (600, 900, 1))
]
# 2. Explicit Empty Input Edge Case Verification Setup
empty_filter_config = sparse_range(s_in=[range(0, 0), range(10, 5)], s_ex=[range(0, 100)])
test_windows.append(("Empty S_in Edge Case", (0, 50, 1)))
passed = 0
for name, args in test_windows:
start, stop, step = args
# Check which config to evaluate against
cfg = empty_filter_config if "Empty" in name else filter_config
actual_output = list(cfg(start, stop, step))
expected_output = _expensive_sparse_range(start, stop, step, cfg._s_in_raw, cfg._s_ex_raw)
if actual_output == expected_output:
print(f"✅ PASS: {name:<35} -> args: ({start}, {stop}, {step})")
passed += 1
else:
print(f"❌ FAIL: {name:<35}")
print(f" Expected: {expected_output}")
print(f" Got: {actual_output}")
print(f"\nTest Summary: {passed}/{len(test_windows)} passed successfully.")
if __name__ == "__main__":
args = sys.argv[1:]
if not args or "--test" in args:
run_tests()
elif "--help" in args or "-h" in args:
print("""sparse_range Factory Engine\n---------------------------""")
elif "--doc" in args:
print(__doc__.strip())
A run of included tests
Running Factory Pattern Limits Verification Suite (-1000 to +1000)...
✅ PASS: Standard positive crawl -> args: (0, 200, 2)
✅ PASS: Negative direction crawl -> args: (400, -400, -5)
✅ PASS: Large step slice jump -> args: (-1000, 1000, 25)
✅ PASS: Completely out of bounds window -> args: (600, 900, 1)
✅ PASS: Empty S_in Edge Case -> args: (0, 50, 1)
Test Summary: 5/5 passed successfully.
The Ultimate Stress Test: A Declarative Sieve
It's easy to write a basic range filter that skips a static block of numbers. But to prove that this RangePointer inversion and alignment math is completely airtight across dozens of concurrent boundaries, I decided to implement a completely declarative Sieve of Eratosthenes.
Instead of allocating a large mutable array of booleans in memory and procedurally striking out composites, we can use pure sequence logic:
The Permitted Range S_in: Our baseline pool of candidate of ints starting at 2: [range(2, limit + 1)].
The Exclusion ranges S_ex: A list of independent arithmetic progression ranges tracking the composites for every factor m up to √(limit).
Each exclusion range/stream starts at m × m (instead of m × 2). Any composite smaller than m × m has a prime factor smaller than m, meaning it has already been intercepted by an earlier stream. For example by the time m=5 runs, numbers like 10, 15, and 20 are already masked out by the ranges/streams for 2 and 3. The first unseen composite is 5 × 5 = 25.
Putting it to the Test
Although the module sparse_range.py has its own tests, to further verify the integrity of the design I put together a test module called sparse_range_sieve_test.py. It packages the sieve creation into an isolated factory function and validates the output against a traditional, trusted array sieve across both a forward sweep and a reversed backward pass.
The Verdict
When running forward, the generator's internal pointers march sequentially alongside the main consumer loop.
The true architectural challenge happens during the backward traversal pass (step = -1). When executing prime_sieve_factory(limit, 1, -1), the engine must manage 13 independent composite exclusion ranges simultaneously (for m = 2, 3, ..., 14). Each sub-range pointer must instantly compute its upper boundary, snap precisely to its maximum valid multiple less than or equal to 200, and step backward in perfect synchronization without dropping or skipping values.
The execution checks out perfectly:
If you are following the Python Discuss thread, this demonstrates that handling arbitrary sequence exclusions cleanly and statelessly via pure index-pointer stream math isn't just an elegant idea—it's highly reliable even under heavy algorithmic stress.
Disclosure
I used Gemini AI to help in this. I was able to state algorithms and get Gemini to fill in with implementations, state changes and get Gemini to implement those too. I am used to creating algorithms without AI, this time I was able to state what I wanted in some detail and have Gemini add yet more detail. I could show python, pseudo-code, r textual descriptions as needed and get Gemini to fill in. The tests went from my description to code by Gemini - the sieve example test idea and spec, and debug was by me with Gemini improving my limit on m from m*2 to m*m for example before implementing as told.
