import { Equal, Hash, HashMap, Option, Result } from "effect"
import { FastCheck as fc } from "effect/testing"
import { describe, expect, it } from "vitest"

describe("HashMap", () => {
  describe("constructors", () => {
    it("empty", () => {
      const map = HashMap.empty<string, number>()
      expect(HashMap.isEmpty(map)).toBe(true)
      expect(HashMap.size(map)).toBe(0)
    })

    it("make", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      expect(HashMap.size(map)).toBe(3)
      expect(HashMap.get(map, "a")).toEqual(Option.some(1))
      expect(HashMap.get(map, "b")).toEqual(Option.some(2))
      expect(HashMap.get(map, "c")).toEqual(Option.some(3))
    })

    it("fromIterable", () => {
      const entries = [["a", 1], ["b", 2], ["c", 3]] as const
      const map = HashMap.fromIterable(entries)
      expect(HashMap.size(map)).toBe(3)
      expect(HashMap.get(map, "a")).toEqual(Option.some(1))
      expect(HashMap.get(map, "b")).toEqual(Option.some(2))
      expect(HashMap.get(map, "c")).toEqual(Option.some(3))
    })
  })

  describe("basic operations", () => {
    it("get - existing key", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      expect(HashMap.get(map, "a")).toEqual(Option.some(1))
      expect(HashMap.get(map, "b")).toEqual(Option.some(2))
    })

    it("get - non-existing key", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      expect(HashMap.get(map, "c")).toEqual(Option.none())
    })

    it("has - existing key", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      expect(HashMap.has(map, "a")).toBe(true)
      expect(HashMap.has(map, "b")).toBe(true)
    })

    it("has - non-existing key", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      expect(HashMap.has(map, "c")).toBe(false)
    })

    it("set - new key", () => {
      const map1 = HashMap.make(["a", 1])
      const map2 = HashMap.set(map1, "b", 2)
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(1))
      expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
      // Original should be unchanged
      expect(HashMap.size(map1)).toBe(1)
      expect(HashMap.has(map1, "b")).toBe(false)
    })

    it("set - existing key", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.set(map1, "a", 10)
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(10))
      expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
      // Original should be unchanged
      expect(HashMap.get(map1, "a")).toEqual(Option.some(1))
    })

    it("remove - existing key", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const map2 = HashMap.remove(map1, "b")
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.has(map2, "a")).toBe(true)
      expect(HashMap.has(map2, "b")).toBe(false)
      expect(HashMap.has(map2, "c")).toBe(true)
      // Original should be unchanged
      expect(HashMap.size(map1)).toBe(3)
      expect(HashMap.has(map1, "b")).toBe(true)
    })

    it("remove - non-existing key", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.remove(map1, "c")
      expect(map1).toBe(map2) // Should return same reference
      expect(HashMap.size(map2)).toBe(2)
    })

    it("getUnsafe - existing key", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      expect(HashMap.getUnsafe(map, "a")).toBe(1)
      expect(HashMap.getUnsafe(map, "b")).toBe(2)
    })

    it("getUnsafe - non-existing key", () => {
      const map = HashMap.make(["a", 1])
      expect(() => HashMap.getUnsafe(map, "b")).toThrow("HashMap.getUnsafe: key not found")
    })
  })

  describe("iterators and getters", () => {
    it("keys", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const keys = Array.from(HashMap.keys(map)).sort()
      expect(keys).toEqual(["a", "b", "c"])
    })

    it("values", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const values = Array.from(HashMap.values(map)).sort()
      expect(values).toEqual([1, 2, 3])
    })

    it("toValues", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const values = HashMap.toValues(map).sort()
      expect(values).toEqual([1, 2, 3])
    })

    it("entries", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      const entries = Array.from(HashMap.entries(map)).sort(([a], [b]) => a.localeCompare(b))
      expect(entries).toEqual([["a", 1], ["b", 2]])
    })

    it("toEntries", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      const entries = HashMap.toEntries(map).sort(([a], [b]) => a.localeCompare(b))
      expect(entries).toEqual([["a", 1], ["b", 2]])
    })

    it("Symbol.iterator", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      const entries = Array.from(map).sort(([a], [b]) => a.localeCompare(b))
      expect(entries).toEqual([["a", 1], ["b", 2]])
    })
  })

  describe("bulk operations", () => {
    it("removeMany", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
      const map2 = HashMap.removeMany(map1, ["b", "d"])
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.has(map2, "a")).toBe(true)
      expect(HashMap.has(map2, "b")).toBe(false)
      expect(HashMap.has(map2, "c")).toBe(true)
      expect(HashMap.has(map2, "d")).toBe(false)
    })

    it("setMany", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const newEntries = [["c", 3], ["d", 4], ["a", 10]] as const // "a" should be overwritten
      const map2 = HashMap.setMany(map1, newEntries)

      expect(HashMap.size(map2)).toBe(4)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(10)) // overwritten
      expect(HashMap.get(map2, "b")).toEqual(Option.some(2)) // preserved
      expect(HashMap.get(map2, "c")).toEqual(Option.some(3)) // new
      expect(HashMap.get(map2, "d")).toEqual(Option.some(4)) // new
    })

    it("setMany - pipe syntax", () => {
      const map1 = HashMap.empty<string, number>()
      const map2 = HashMap.setMany([["x", 100], ["y", 200]])(map1)

      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.get(map2, "x")).toEqual(Option.some(100))
      expect(HashMap.get(map2, "y")).toEqual(Option.some(200))
    })

    it("setMany - different iterables", () => {
      const map1 = HashMap.make(["existing", 1])

      // Test with Map
      const jsMap = new Map([["from-map", 2], ["another", 3]])
      const map2 = HashMap.setMany(map1, jsMap)

      expect(HashMap.size(map2)).toBe(3)
      expect(HashMap.get(map2, "existing")).toEqual(Option.some(1))
      expect(HashMap.get(map2, "from-map")).toEqual(Option.some(2))
      expect(HashMap.get(map2, "another")).toEqual(Option.some(3))

      // Test with Set of tuples
      const setOfTuples = new Set([["from-set", 4]] as const)
      const map3 = HashMap.setMany(map2, setOfTuples)

      expect(HashMap.size(map3)).toBe(4)
      expect(HashMap.get(map3, "from-set")).toEqual(Option.some(4))
    })

    it("union", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.make(["b", 20], ["c", 3])
      const map3 = HashMap.union(map1, map2)
      expect(HashMap.size(map3)).toBe(3)
      expect(HashMap.get(map3, "a")).toEqual(Option.some(1))
      expect(HashMap.get(map3, "b")).toEqual(Option.some(20)) // map2 wins
      expect(HashMap.get(map3, "c")).toEqual(Option.some(3))
    })
  })

  describe("mapping operations", () => {
    it("map", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const map2 = HashMap.map(map1, (value, _key) => value * 2)
      expect(HashMap.size(map2)).toBe(3)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(2))
      expect(HashMap.get(map2, "b")).toEqual(Option.some(4))
      expect(HashMap.get(map2, "c")).toEqual(Option.some(6))
    })

    it("flatMap", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.flatMap(map1, (value, key) => HashMap.make([key + "1", value], [key + "2", value * 2]))
      expect(HashMap.size(map2)).toBe(4)
      expect(HashMap.get(map2, "a1")).toEqual(Option.some(1))
      expect(HashMap.get(map2, "a2")).toEqual(Option.some(2))
      expect(HashMap.get(map2, "b1")).toEqual(Option.some(2))
      expect(HashMap.get(map2, "b2")).toEqual(Option.some(4))
    })
  })

  describe("filtering operations", () => {
    it("filter", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
      const map2 = HashMap.filter(map1, (value) => value % 2 === 0)
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.has(map2, "a")).toBe(false)
      expect(HashMap.has(map2, "b")).toBe(true)
      expect(HashMap.has(map2, "c")).toBe(false)
      expect(HashMap.has(map2, "d")).toBe(true)
    })

    it("compact", () => {
      const map1 = HashMap.make(
        ["a", Option.some(1)],
        ["b", Option.none()],
        ["c", Option.some(3)]
      )
      const map2 = HashMap.compact(map1)
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(1))
      expect(HashMap.has(map2, "b")).toBe(false)
      expect(HashMap.get(map2, "c")).toEqual(Option.some(3))
    })

    it("filterMap", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
      const map2 = HashMap.filterMap(map1, (value) => value % 2 === 0 ? Result.succeed(value * 2) : Result.failVoid)
      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.get(map2, "b")).toEqual(Option.some(4))
      expect(HashMap.get(map2, "d")).toEqual(Option.some(8))
      expect(HashMap.has(map2, "a")).toBe(false)
      expect(HashMap.has(map2, "c")).toBe(false)
    })

    it("filterMap - key argument", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2], ["c", 3], ["d", 4])
      const map2 = HashMap.filterMap(
        map1,
        (value, key) => key < "c" ? Result.succeed(`${key}:${value}`) : Result.failVoid
      )

      expect(HashMap.size(map2)).toBe(2)
      expect(HashMap.get(map2, "a")).toEqual(Option.some("a:1"))
      expect(HashMap.get(map2, "b")).toEqual(Option.some("b:2"))
      expect(HashMap.has(map2, "c")).toBe(false)
      expect(HashMap.has(map2, "d")).toBe(false)
    })
  })

  describe("search operations", () => {
    it("findFirst returns an entry matching both key and value", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const result = HashMap.findFirst(map, (value) => value > 1)
      expect(result).toEqual(Option.some(["c", 3]))
    })

    it("findFirst - not found", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      const result = HashMap.findFirst(map, (value) => value > 5)
      expect(result).toEqual(Option.none())
    })

    it("some", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      expect(HashMap.some(map, (value) => value > 2)).toBe(true)
      expect(HashMap.some(map, (value) => value > 5)).toBe(false)
    })

    it("every", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      expect(HashMap.every(map, (value) => value > 0)).toBe(true)
      expect(HashMap.every(map, (value) => value > 1)).toBe(false)
    })

    it("hasBy", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      expect(HashMap.hasBy(map, (value, key) => key === "b" && value === 2)).toBe(true)
      expect(HashMap.hasBy(map, (value, key) => key === "b" && value === 5)).toBe(false)
    })
  })

  describe("modification operations", () => {
    it("modifyAt - existing key", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.modifyAt(
        map1,
        "a",
        (option) => Option.isSome(option) ? Option.some(option.value * 2) : Option.none()
      )
      expect(HashMap.get(map2, "a")).toEqual(Option.some(2))
    })

    it("modifyAt - non-existing key", () => {
      const map1 = HashMap.make(["a", 1])
      const map2 = HashMap.modifyAt(map1, "b", (option) => Option.isSome(option) ? option : Option.some(10))
      expect(HashMap.get(map2, "b")).toEqual(Option.some(10))
    })

    it("modifyAt - remove via None", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.modifyAt(map1, "a", () => Option.none())
      expect(HashMap.has(map2, "a")).toBe(false)
      expect(HashMap.has(map2, "b")).toBe(true)
    })

    it("modify", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.modify(map1, "a", (value) => value * 3)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(3))
      expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
    })
  })

  describe("reduction operations", () => {
    it("reduce", () => {
      const map = HashMap.make(["a", 1], ["b", 2], ["c", 3])
      const sum = HashMap.reduce(map, 0, (acc, value) => acc + value)
      expect(sum).toBe(6)
    })

    it("forEach visits each key and value", () => {
      const map = HashMap.make(["a", 1], ["b", 2])
      const collected: Array<[string, number]> = []
      HashMap.forEach(map, (value, key) => {
        collected.push([key, value])
      })
      expect(collected.sort()).toEqual([["a", 1], ["b", 2]])
    })
  })

  describe("mutation helpers", () => {
    it("mutate allows in-place modifications", () => {
      const map1 = HashMap.make(["a", 1])
      const map2 = HashMap.mutate(map1, (mutable) => {
        HashMap.set(mutable, "b", 2)
        HashMap.set(mutable, "c", 3)
      })
      // Original should be unchanged
      expect(HashMap.size(map1)).toBe(1)
      // Mutated map should have all entries
      expect(HashMap.size(map2)).toBe(3)
      expect(HashMap.get(map2, "a")).toEqual(Option.some(1))
      expect(HashMap.get(map2, "b")).toEqual(Option.some(2))
      expect(HashMap.get(map2, "c")).toEqual(Option.some(3))
    })

    it("beginMutation creates distinct mutable instance", () => {
      const map1 = HashMap.make(["a", 1])
      const mutable = HashMap.beginMutation(map1)

      // Should be different instances
      expect(map1).not.toBe(mutable)

      // Mutations on mutable should not affect original
      HashMap.set(mutable, "b", 2)
      expect(HashMap.size(map1)).toBe(1)
      expect(HashMap.size(mutable)).toBe(2)

      // endMutation returns same instance
      const immutable = HashMap.endMutation(mutable)
      expect(mutable).toBe(immutable)
    })

    it("mutations are isolated from original", () => {
      const original = HashMap.make(["a", 1], ["b", 2])
      const mutated = HashMap.mutate(original, (m) => {
        HashMap.set(m, "a", 100)
        HashMap.remove(m, "b")
        HashMap.set(m, "c", 3)
      })

      // Original unchanged
      expect(HashMap.get(original, "a")).toEqual(Option.some(1))
      expect(HashMap.get(original, "b")).toEqual(Option.some(2))
      expect(HashMap.has(original, "c")).toBe(false)

      // Mutated has changes
      expect(HashMap.get(mutated, "a")).toEqual(Option.some(100))
      expect(HashMap.has(mutated, "b")).toBe(false)
      expect(HashMap.get(mutated, "c")).toEqual(Option.some(3))
    })
  })

  describe("equality and hashing", () => {
    it("Equal.equals", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.make(["b", 2], ["a", 1]) // Different order
      const map3 = HashMap.make(["a", 1], ["b", 3]) // Different value

      expect(Equal.equals(map1, map2)).toBe(true)
      expect(Equal.equals(map1, map3)).toBe(false)
    })

    it("Hash.hash", () => {
      const map1 = HashMap.make(["a", 1], ["b", 2])
      const map2 = HashMap.make(["b", 2], ["a", 1]) // Different order

      expect(Hash.hash(map1)).toBe(Hash.hash(map2))
    })
  })

  describe("custom hash with Equal objects", () => {
    class Person implements Equal.Equal {
      constructor(readonly name: string, readonly age: number) {}

      [Equal.symbol](that: Equal.Equal): boolean {
        return that instanceof Person &&
          this.name === that.name &&
          this.age === that.age
      }

      [Hash.symbol](): number {
        return Hash.string(this.name) ^ Hash.number(this.age)
      }
    }

    it("should work with Equal objects as keys", () => {
      const person1 = new Person("Alice", 25)
      const person2 = new Person("Alice", 25) // Same data, different instance
      const person3 = new Person("Bob", 30)

      const map = HashMap.make([person1, "value1"], [person3, "value3"])

      // Should find value using structurally equal key
      expect(HashMap.get(map, person2)).toEqual(Option.some("value1"))
      expect(HashMap.has(map, person2)).toBe(true)

      // Should work with set operation
      const map2 = HashMap.set(map, person2, "updated")
      expect(HashMap.get(map2, person1)).toEqual(Option.some("updated"))
      expect(HashMap.size(map2)).toBe(2) // Should not increase size
    })
  })

  describe("regressions", () => {
    class FixedHashKey implements Equal.Equal {
      constructor(readonly id: string, readonly hash: number) {}

      [Equal.symbol](that: Equal.Equal): boolean {
        return that instanceof FixedHashKey && this.id === that.id
      }

      [Hash.symbol](): number {
        return this.hash
      }
    }

    it("keeps entries addressable when bit 31 is present in indexed leaf insert", () => {
      const bit31Key = new FixedHashKey("bit31", 31)
      const bit30Key = new FixedHashKey("bit30", 30)

      let map = HashMap.empty<FixedHashKey, string>()
      map = HashMap.set(map, bit31Key, "session1")
      map = HashMap.set(map, bit30Key, "session2")

      expect(HashMap.size(map)).toBe(2)
      expect(HashMap.get(map, bit31Key)).toEqual(Option.some("session1"))
      expect(HashMap.get(map, bit30Key)).toEqual(Option.some("session2"))
    })

    it("keeps entries addressable when mergeLeaves sees bit 31", () => {
      const collisionA = new FixedHashKey("collisionA", 31)
      const collisionB = new FixedHashKey("collisionB", 31)
      const bit30Key = new FixedHashKey("bit30", 30)

      let map = HashMap.empty<FixedHashKey, string>()
      map = HashMap.set(map, collisionA, "a")
      map = HashMap.set(map, collisionB, "b")
      map = HashMap.set(map, bit30Key, "c")

      expect(HashMap.size(map)).toBe(3)
      expect(HashMap.get(map, collisionA)).toEqual(Option.some("a"))
      expect(HashMap.get(map, collisionB)).toEqual(Option.some("b"))
      expect(HashMap.get(map, bit30Key)).toEqual(Option.some("c"))
    })

    it("keeps all inserted entries addressable across random bit-31-heavy shapes", () => {
      const entriesArbitrary = fc.array(fc.integer({ min: 0, max: 31 }), { minLength: 0, maxLength: 80 }).chain(
        (hashes) => {
          const allHashes = [31, 31, 30, ...hashes]
          return fc.uniqueArray(fc.uuid(), { minLength: allHashes.length, maxLength: allHashes.length }).map((ids) =>
            allHashes.map((hash, i) => ({ id: ids[i], hash }))
          )
        }
      )

      fc.assert(
        fc.property(entriesArbitrary, (entries) => {
          let map = HashMap.empty<FixedHashKey, string>()
          const inserted: Array<readonly [FixedHashKey, string]> = []

          for (const entry of entries) {
            const key = new FixedHashKey(entry.id, entry.hash)
            const value = `value-${entry.id}`
            map = HashMap.set(map, key, value)
            inserted.push([key, value])
          }

          expect(HashMap.size(map)).toBe(inserted.length)
          for (const [key, value] of inserted) {
            expect(HashMap.has(map, key)).toBe(true)
            expect(HashMap.get(map, key)).toEqual(Option.some(value))
          }
        }),
        { numRuns: 200 }
      )
    })
  })

  describe("type guards", () => {
    it("isHashMap", () => {
      const map = HashMap.make(["a", 1])
      const notMap = { a: 1 }

      expect(HashMap.isHashMap(map)).toBe(true)
      expect(HashMap.isHashMap(notMap)).toBe(false)
      expect(HashMap.isHashMap(null)).toBe(false)
      expect(HashMap.isHashMap(undefined)).toBe(false)
    })
  })

  describe("stress tests", () => {
    it("handles many inserts, lookups, and removals", () => {
      let map = HashMap.empty<number, string>()

      // Add many entries
      for (let i = 0; i < 1000; i++) {
        map = HashMap.set(map, i, `value${i}`)
      }

      expect(HashMap.size(map)).toBe(1000)

      // Check random entries
      for (let i = 0; i < 100; i++) {
        const key = Math.floor(Math.random() * 1000)
        expect(HashMap.get(map, key)).toEqual(Option.some(`value${key}`))
      }

      // Remove half the entries
      for (let i = 0; i < 500; i++) {
        map = HashMap.remove(map, i)
      }

      expect(HashMap.size(map)).toBe(500)

      // Verify removals
      for (let i = 0; i < 500; i++) {
        expect(HashMap.has(map, i)).toBe(false)
      }
      for (let i = 500; i < 1000; i++) {
        expect(HashMap.has(map, i)).toBe(true)
      }
    })

    it("should handle hash collisions", () => {
      // Create objects with same hash but different equality
      class CollidingKey implements Equal.Equal {
        constructor(readonly id: number) {}

        [Equal.symbol](that: Equal.Equal): boolean {
          return that instanceof CollidingKey && this.id === that.id
        }

        [Hash.symbol](): number {
          return 42 // Same hash for all instances
        }
      }

      const key1 = new CollidingKey(1)
      const key2 = new CollidingKey(2)
      const key3 = new CollidingKey(3)

      let map = HashMap.empty<CollidingKey, string>()
      map = HashMap.set(map, key1, "value1")
      map = HashMap.set(map, key2, "value2")
      map = HashMap.set(map, key3, "value3")

      expect(HashMap.size(map)).toBe(3)
      expect(HashMap.get(map, key1)).toEqual(Option.some("value1"))
      expect(HashMap.get(map, key2)).toEqual(Option.some("value2"))
      expect(HashMap.get(map, key3)).toEqual(Option.some("value3"))

      // Remove one
      map = HashMap.remove(map, key2)
      expect(HashMap.size(map)).toBe(2)
      expect(HashMap.has(map, key1)).toBe(true)
      expect(HashMap.has(map, key2)).toBe(false)
      expect(HashMap.has(map, key3)).toBe(true)
    })
  })
})