/**
 * crdt.ts — Conflict-Free Replicated Data Types (CRDTs) in TypeScript
 *
 * Run with: npx ts-node crdt.ts
 *
 * Implements G-Counter, PN-Counter, LWW-Register, and OR-Set
 * with merge logic and a convergence demonstration.
 */

// ---- Helper: Merge two maps by taking the max value per key ----

function mergeMapsMax(a: Map<number, number>, b: Map<number, number>): Map<number, number> {
  const result = new Map(a)
  for (const [key, value] of b) {
    result.set(key, Math.max(result.get(key) ?? 0, value))
  }
  return result
}

// ====================================================================
// G-Counter (Grow-only Counter)
// ====================================================================
// Only supports increment. Merges by taking the max per-node value.
// Cannot decrement. Converges trivially.

class GCounter {
  private counts: Map<number, number> = new Map()

  constructor(private nodeId: number) {}

  increment(by: number = 1) {
    this.counts.set(this.nodeId, (this.counts.get(this.nodeId) ?? 0) + by)
  }

  value(): number {
    let total = 0
    for (const v of this.counts.values()) total += v
    return total
  }

  merge(other: GCounter): void {
    this.counts = mergeMapsMax(this.counts, other.counts)
  }

  getState(): Map<number, number> {
    return new Map(this.counts)
  }

  printState(label: string): void {
    const entries = [...this.counts.entries()].map(([k, v]) => `n${k}:${v}`).join(', ')
    console.log(`   ${label}: value=${this.value()}  [${entries}]`)
  }
}

// ====================================================================
// PN-Counter (Positive-Negative Counter)
// ====================================================================
// Uses two G-Counters: one for increments (P), one for decrements (N).
// Value = sum(P) - sum(N). Converges because both P and N converge.

class PNCounter {
  private p: GCounter
  private n: GCounter

  constructor(nodeId: number) {
    this.p = new GCounter(nodeId)
    this.n = new GCounter(nodeId)
  }

  increment(by: number = 1) {
    this.p.increment(by)
  }

  decrement(by: number = 1) {
    this.n.increment(by)
  }

  value(): number {
    return this.p.value() - this.n.value()
  }

  merge(other: PNCounter): void {
    this.p.merge(other.p)
    this.n.merge(other.n)
  }

  printState(label: string): void {
    console.log(`   ${label}: value=${this.value()}  (P=${this.p.value()}, N=${this.n.value()})`)
  }
}

// ====================================================================
// LWW-Register (Last-Write-Wins Register)
// ====================================================================
// Stores a value + timestamp. The "latest" timestamp wins on merge.
// For simplicity, we use a Lamport-style logical clock (counter per node).

class LWWRegister<T> {
  private value: T | null = null
  private timestamp: number = 0
  private nodeId: number

  constructor(nodeId: number) {
    this.nodeId = nodeId
  }

  assign(newValue: T, clock: number) {
    this.value = newValue
    // Timestamp = (clock, nodeId) — lexicographic comparison
    this.timestamp = clock
  }

  get(): T | null {
    return this.value
  }

  merge(other: LWWRegister<T>): void {
    // Compare (timestamp, nodeId) lexicographically
    if (
      other.timestamp > this.timestamp ||
      (other.timestamp === this.timestamp && other.nodeId > this.nodeId)
    ) {
      this.value = other.value
      this.timestamp = other.timestamp
    }
  }

  printState(label: string): void {
    console.log(`   ${label}: value=${JSON.stringify(this.value)}  (ts=${this.timestamp})`)
  }
}

// ====================================================================
// OR-Set (Observed-Remove Set)
// ====================================================================
// Elements have unique tags. Add inserts a tag. Remove adds all visible
// tags to the tombstone set. Merges by union of both adds and tombstones.
// The visible set = addSet - tombstoneSet.

class ORSet<T> {
  // Map from element -> Set of unique tags for that element
  private addSet: Map<string, Set<string>> = new Map()
  private removeSet: Map<string, Set<string>> = new Map()

  private makeTag(): string {
    return `${Date.now()}-${Math.random().toString(36).slice(2, 8)}`
  }

  add(element: T) {
    const key = JSON.stringify(element)
    if (!this.addSet.has(key)) {
      this.addSet.set(key, new Set())
    }
    this.addSet.get(key)!.add(this.makeTag())
  }

  remove(element: T) {
    const key = JSON.stringify(element)
    const tags = this.addSet.get(key)
    if (tags) {
      if (!this.removeSet.has(key)) {
        this.removeSet.set(key, new Set())
      }
      // Move all current tags to the tombstone
      for (const tag of tags) {
        this.removeSet.get(key)!.add(tag)
      }
    }
  }

  has(element: T): boolean {
    const key = JSON.stringify(element)
    const addTags = this.addSet.get(key)
    const removeTags = this.removeSet.get(key)
    if (!addTags) return false
    if (!removeTags) return true
    // Element exists if any of its add tags is NOT in the remove set
    for (const tag of addTags) {
      if (!removeTags.has(tag)) return true
    }
    return false
  }

  values(): T[] {
    const result: T[] = []
    for (const [key, addTags] of this.addSet) {
      const removeTags = this.removeSet.get(key)
      let visible = true
      if (removeTags) {
        visible = false
        for (const tag of addTags) {
          if (!removeTags.has(tag)) {
            visible = true
            break
          }
        }
      }
      if (visible) {
        result.push(JSON.parse(key))
      }
    }
    return result
  }

  merge(other: ORSet<T>): void {
    // Union of add sets
    for (const [key, tags] of other.addSet) {
      if (!this.addSet.has(key)) {
        this.addSet.set(key, new Set())
      }
      for (const tag of tags) {
        this.addSet.get(key)!.add(tag)
      }
    }
    // Union of remove sets
    for (const [key, tags] of other.removeSet) {
      if (!this.removeSet.has(key)) {
        this.removeSet.set(key, new Set())
      }
      for (const tag of tags) {
        this.removeSet.get(key)!.add(tag)
      }
    }
  }

  printState(label: string): void {
    console.log(`   ${label}: { ${this.values().map(v => JSON.stringify(v)).join(', ')} }`)
  }
}

// ====================================================================
// Simulation
// ====================================================================

function simulateCRDTs() {
  console.log('=== CRDT CONVERGENCE SIMULATION ===\n')

  // --- G-Counter ---
  console.log('--- G-Counter (Grow-only Counter) ---')
  const gc1 = new GCounter(1)
  const gc2 = new GCounter(2)

  gc1.increment(3)   // n1=3
  gc2.increment(5)   // n2=5
  gc1.increment(2)   // n1=5

  console.log('Before merge (diverged):')
  gc1.printState('Node 1')
  gc2.printState('Node 2')

  // Simulate network sync: both nodes exchange states
  gc1.merge(gc2)
  gc2.merge(gc1)

  console.log('After merge (converged):')
  gc1.printState('Node 1')
  gc2.printState('Node 2')
  console.log(`   Converged? ${gc1.value() === gc2.value()} (value=${gc1.value()})\n`)

  // --- PN-Counter ---
  console.log('--- PN-Counter (Positive-Negative Counter) ---')
  const pnc1 = new PNCounter(1)
  const pnc2 = new PNCounter(2)

  pnc1.increment(10)
  pnc2.increment(5)
  pnc1.decrement(3)
  pnc2.decrement(2)

  console.log('Before merge (diverged):')
  pnc1.printState('Node 1')
  pnc2.printState('Node 2')

  pnc1.merge(pnc2)
  pnc2.merge(pnc1)

  console.log('After merge (converged):')
  pnc1.printState('Node 1')
  pnc2.printState('Node 2')
  console.log(`   Converged? ${pnc1.value() === pnc2.value()} (value=${pnc1.value()})\n`)

  // --- LWW-Register ---
  console.log('--- LWW-Register (Last-Write-Wins) ---')
  const r1 = new LWWRegister<string>(1)
  const r2 = new LWWRegister<string>(2)

  r1.assign('hello', 5)   // Node 1 sets "hello" at logical clock 5
  r2.assign('world', 3)   // Node 2 sets "world" at logical clock 3

  console.log('Before merge:')
  r1.printState('Node 1')
  r2.printState('Node 2')

  r1.merge(r2)
  r2.merge(r1)

  console.log('After merge (highest timestamp wins):')
  r1.printState('Node 1')
  r2.printState('Node 2')
  console.log(`   Converged? ${r1.get() === r2.get()} (value="${r1.get()}")\n`)

  // --- OR-Set ---
  console.log('--- OR-Set (Observed-Remove Set) ---')
  const s1 = new ORSet<string>()
  const s2 = new ORSet<string>()

  // Node 1 adds elements
  s1.add('apple')
  s1.add('banana')
  console.log('Node 1 adds: apple, banana')
  s1.printState('Node 1')

  // Node 2 adds and removes concurrently
  s2.add('banana')
  s2.add('cherry')
  s2.remove('banana')
  console.log('\nNode 2 adds: banana (then removes), cherry')
  s2.printState('Node 2')

  console.log('\nBefore merge:')
  console.log(`   Node 1 has: { ${s1.values().join(', ')} }`)
  console.log(`   Node 2 has: { ${s2.values().join(', ')} }`)

  s1.merge(s2)
  s2.merge(s1)

  console.log('\nAfter merge (converged):')
  console.log(`   Node 1 has: { ${s1.values().join(', ')} }`)
  console.log(`   Node 2 has: { ${s2.values().join(', ')} }`)

  // Key OR-Set property: "banana" was removed by Node 2, but the add by Node 1
  // should still make it visible on both replicas
  const bananas = s1.values().filter(v => v === 'banana')
  console.log(`   "banana" visible on merged set: ${bananas.length > 0} (Node 1 added independently)\n`)

  console.log('✅ All CRDT types converge correctly!')
}

simulateCRDTs()

⬇ Download crdt.ts