#!/usr/bin/env python3
"""A G-Counter CRDT converges; a naive replicated counter loses increments, DDIA 2e Ch. 6.

Three replicas each increment a shared counter while partitioned (offline), then
reconcile. The true total is fixed: A does +100, B does +50, C does +30, so the
answer must be 180.

The surprise is what "merge" means. Model the counter naively -- as a single
integer register merged by last-write-wins -- and reconciliation keeps only ONE
replica's work: the survivor is 100, and the other 80 increments are silently
gone. Model it as a G-Counter CRDT instead -- each replica keeps a vector of
per-replica sub-counts, increment bumps its OWN entry, merge takes the
element-wise MAX, value is the sum -- and the replicas converge to exactly 180,
in every merge order.

Pure standard library, deterministic -> reproducible.
"""
import itertools

# Each replica increments its counter this many times while partitioned.
WORK = {"A": 100, "B": 50, "C": 30}
TRUE_TOTAL = sum(WORK.values())


# --- Naive replicated counter: a single integer register, merged last-write-wins ---

class NaiveCounter:
    """One integer per replica. Increment bumps it. Merge = last-write-wins."""

    def __init__(self):
        self.value = 0

    def increment(self):
        self.value += 1

    def merge(self, other):
        # Last-write-wins on a single register: keep the larger value. There is
        # no per-replica bookkeeping, so concurrent increments cannot be summed
        # -- one register simply overwrites the other.
        self.value = max(self.value, other.value)


# --- G-Counter CRDT: a vector of per-replica sub-counts, merged element-wise max ---

class GCounter:
    """A dict {replica_id: count}. Increment bumps own id. Merge = element-wise max."""

    def __init__(self, replica_id):
        self.replica_id = replica_id
        self.counts = {}

    def increment(self):
        self.counts[self.replica_id] = self.counts.get(self.replica_id, 0) + 1

    def merge(self, other):
        merged = dict(self.counts)
        for rid, count in other.counts.items():
            merged[rid] = max(merged.get(rid, 0), count)
        self.counts = merged

    def value(self):
        return sum(self.counts.values())


def make_naive():
    reps = {}
    for rid, work in WORK.items():
        c = NaiveCounter()
        for _ in range(work):
            c.increment()
        reps[rid] = c
    return reps


def make_gcounters():
    reps = {}
    for rid, work in WORK.items():
        c = GCounter(rid)
        for _ in range(work):
            c.increment()
        reps[rid] = c
    return reps


def merge_naive_in_order(order):
    reps = make_naive()
    acc = NaiveCounter()
    for rid in order:
        acc.merge(reps[rid])
    return acc.value


def merge_gcounter_in_order(order):
    reps = make_gcounters()
    acc = GCounter("_")
    for rid in order:
        acc.merge(reps[rid])
    return acc.value()


def main():
    print("3 replicas increment a shared counter while partitioned, then merge.")
    print(f"    A: +{WORK['A']}   B: +{WORK['B']}   C: +{WORK['C']}")
    print(f"    true total = {TRUE_TOTAL}\n")

    # Naive register merged last-write-wins.
    naive_final = merge_naive_in_order(["A", "B", "C"])
    lost = TRUE_TOTAL - naive_final
    print("naive replicated counter (single integer register, last-write-wins merge):")
    print(f"    after merging A, B, C -> {naive_final}")
    print(f"    LOST {lost} of {TRUE_TOTAL} increments ({lost * 100 // TRUE_TOTAL}%) -- "
          f"the merge kept one replica and dropped the rest.\n")

    # G-Counter CRDT.
    gcounter_final = merge_gcounter_in_order(["A", "B", "C"])
    print("G-Counter CRDT (per-replica sub-counts, element-wise max merge):")
    print(f"    after merging A, B, C -> {gcounter_final}")
    print(f"    LOST {TRUE_TOTAL - gcounter_final} increments -- converged to the exact total.\n")

    # Order-independence: every merge order yields the same value.
    print("order-independence -- merge the three G-Counters in every order:")
    for order in itertools.permutations(["A", "B", "C"]):
        result = merge_gcounter_in_order(list(order))
        print(f"    merge order {' -> '.join(order)}  =  {result}")
    print("    every order converges to the same value: the CRDT is order-independent.")


if __name__ == "__main__":
    main()