Sparse Ranges

 

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.

 

+----------------------------------------+

               |  Outer Loop: start, stop, step         |

               +----------------------------------------+

                                   |

                  [ Evaluates current candidate value ]

                                   |

                                   v

         +--------------------------------------------------+

         | Is value in any S_in? AND NOT in any S_ex?       |

         +--------------------------------------------------+

             |                                          |

    (Using forward-aligned                     (Using backward-aligned

     RangePointers for step > 0)                RangePointers for step < 0)

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:

1. New Step: The step sign is flipped (-step).

2. 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

    

3. New Stop: The original start boundary shifts out by one step inverted to act as the non-inclusive terminal wall:

   new_stop = start - step

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:

1. The Permitted Range S_in: Our baseline pool of candidate of ints starting at 2: [range(2, limit + 1)].

2. 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.

sparse_range_sieve_test.py

 

 

#!/bin/env python3

# Author: Donald "Paddy" McCarthy. paddy3118@gmail.com

# 27/06/2026

#%%

"""

sparse_range_sieve_test - Prime Generation Performance Test Harness

===================================================================

This module verifies the mathematical integrity of the `sparse_range` tracking

engine by utilizing it to implement a declarative Sieve of Eratosthenes.

It tests overlapping cross-boundary constraints by instantiating dozens of

simultaneous exclusion ranges running with diverse step intervals.

"""

from typing import List

from sparse_range import sparse_range

def traditional_sieve(n: int) -> List[int]:

    """Generates prime numbers up to N using a standard boolean array sieve."""

    if n < 2:

        return []

    sieve = [True] * (n + 1)

    sieve[0] = sieve[1] = False

   

    for p in range(2, int(n**0.5) + 1):

        if sieve[p]:

            for i in range(p * p, n + 1, p):

                sieve[i] = False

               

    return [i for i, is_prime in enumerate(sieve) if is_prime]

def build_prime_sieve(limit: int) -> sparse_range:

    """

    Constructs a sparse_range configured as a declarative Sieve of Eratosthenes.

   

    How S_in and S_ex constitute a "sieved" range:

    ----------------------------------------------

    Instead of tracking a mutable array of booleans in memory and crossing off

    composites procedurally, this factory models the Sieve of Eratosthenes

    declaratively using pure sequence logic.

   

    1. The Permitted Range (S_in):

       We start with the baseline domain of all potential prime candidates. Since

       1 is not prime, our domain is a single continuous range starting at 2:

       S_in = [range(2, limit + 1)]

       

    2. The Exclusion Streams (S_ex):

       To eliminate non-primes, we generate an independent exclusion range for

       every integer 'm' from 2 up to sqrt(limit). Each range tracks the periodic

       sequence of composites generated by that factor.

       

       - Step factor: The range increments by 'm' (e.g., for m=3, it targets

         every 3rd number).

       - Optimization (m * m): Rather than starting at m * 2, each exclusion stream

         starts at m * m. Any composite number smaller than m * m must possess a

         prime factor smaller than 'm', meaning it is already guaranteed to be

         intercepted by a previous exclusion stream.

         

    When the resulting factory is iterated, the sparse_range engine dynamically

    clashes these arithmetic progressions together, masking out composites instantly

    without storing any tables in RAM.

    """

    # Baseline candidate space

    s_in: List[range] = [range(2, limit + 1)]

   

    # Composite elimination progressions

    s_ex: List[range] = [

        range(m * m, limit + 1, m)

        for m in range(2, int((limit + 1)**0.5) + 1)

    ]

   

    return sparse_range(s_in=s_in, s_ex=s_ex)

def run_sieve_tests(limit: int = 200) -> None:

    """Executes forward and backward verification passes against traditional algorithms."""

    print(f"Beginning Sparse Range Sieve Evaluation Suite (N = {limit})...")

    print("----------------------------------------------------------------")

    # 1. Generate baseline ground-truth primes

    expected_forward: List[int] = traditional_sieve(limit)

    expected_backward: List[int] = list(reversed(expected_forward))

    # 2. Build the sieve factory via isolated generator function

    prime_sieve_factory = build_prime_sieve(limit)

    # 3. Test Forward Generation

    print("👉 Running Forward Traversal Validation...")

    actual_forward: List[int] = list(prime_sieve_factory(2, limit + 1, 1))

   

    if actual_forward == expected_forward:

        print(f"   ✅ PASS: Forward matching. Found {len(actual_forward)} primes.")

    else:

        print("   ❌ FAIL: Forward mismatch.")

        print(f"   Expected: {expected_forward}")

        print(f"   Got:      {actual_forward}")

    # 4. Test Backward Generation

    print("👉 Running Backward Traversal Validation...")

    actual_backward: List[int] = list(prime_sieve_factory(limit, 1, -1))

   

    if actual_backward == expected_backward:

        print(f"   ✅ PASS: Backward matching. Reversed sequences match perfectly.")

    else:

        print("   ❌ FAIL: Backward mismatch.")

        print(f"   Expected: {expected_backward}")

        print(f"   Got:      {actual_backward}")

if __name__ == "__main__":

    # Test with a limit of 200 elements to keep visualization digestible

    run_sieve_tests(limit=200)

 

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:

Beginning Sparse Range Sieve Evaluation Suite (N = 200)...
----------------------------------------------------------------
👉 Running Forward Traversal Validation...
   ✅ PASS: Forward matching. Found 46 primes.
👉 Running Backward Traversal Validation...
   ✅ PASS: Backward matching. Reversed sequences match 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.