Dgim.py

from concurrent.futures import ThreadPoolExecutor


def dgim(stream, window):
    # Buckets stored oldest -> newest as [size, timestamp_of_most_recent_1]
    buckets = []

    for time, bit in enumerate(stream, 1):
        if bit == 1:
            buckets.append([1, time])

            # If 3 buckets have the same size, merge the two oldest of them
            i = 0
            while i < len(buckets) - 2:
                if buckets[i][0] == buckets[i + 1][0] == buckets[i + 2][0]:
                    buckets[i + 1][0] *= 2      # keep the newer timestamp
                    buckets.pop(i)
                    i = max(i - 2, 0)           # re-check for cascaded merges
                else:
                    i += 1

        # Remove buckets that are completely outside the window
        buckets = [b for b in buckets if time - b[1] < window]

    count = sum(b[0] for b in buckets)

    # Oldest bucket may be partly outside the window: count only half
    if buckets:
        count -= buckets[0][0] // 2

    return count


def exact_count(stream, window):
    return sum(stream[-window:])


def process_stream(data):
    stream, window = data
    return dgim(stream, window)


def main():
    try:
        n = int(input("Enter number of streams: "))
        streams = []
        for k in range(1, n + 1):
            line = input(f"Enter Stream {k} (0s and 1s): ")
            streams.append(list(map(int, line.split())))
        window = int(input("Enter window size: "))
    except ValueError:
        print("Invalid input! Please enter only numbers.")
        return

    if (n <= 0 or window <= 0
            or any(not s or any(b not in (0, 1) for b in s) for s in streams)):
        print("Invalid input!")
        return

    # Each stream is processed concurrently (one worker per stream)
    with ThreadPoolExecutor(max_workers=n) as executor:
        results = list(executor.map(process_stream,
                                    [(s, window) for s in streams]))

    print()
    for k, (s, r) in enumerate(zip(streams, results), 1):
        print(f"Stream {k}: estimated = {r}, exact = {exact_count(s, window)}")

    print("Total estimated 1s:", sum(results))
    print("Total exact 1s:", sum(exact_count(s, window) for s in streams))


if __name__ == "__main__":
    main()