Hash

class Hash(K, V)

  # Two tables are equal when they hold the same pairs, in any order, as the
  # other library's are: `Reference#==` asked whether they were one object,
  # so `{"a" => 1} == {"a" => 1}` was false and a table could not be found
  # as a key by an equal one.
  def ==(other : Hash(K, V)) : Bool

  def [](key : K) : V

  def []=(key : K, value : V) : V

  def []?(key : K) : V | ::Nil

  def all?(& : (K, V -> Bool)) : Bool

  def any?(& : (K, V -> Bool)) : Bool

  # Every entry forgotten, and the room with them; a default stays.
  def clear : Hash(K, V)

  # The pairs whose value is not nil, in a table whose value type says so.
  def compact

  # The questions a table gets asked of its pairs, each block handed the key
  # and the value.
  def count(& : (K, V -> Bool)) : Int32

  # The value the key had, or nil. The entry is marked gone where it
  # stands, so the order of what remains is the order it went in, and its
  # index slot becomes a tombstone. `each` starts past the gone at the
  # front: from entry 0, taking the oldest key and deleting it until none
  # was left stepped over every one gone before, 197 ms for 40,000.
  def delete(key : K) : V | ::Nil

  # The value the key had, deleted, or what the block answers for a key
  # that was not there.
  def delete(key : K, & : (K -> U)) : V | U forall U

  # `table.dig("a", "b")`: the value at the first key, then the value at the
  # next key inside that, for every key given. A value that cannot be dug
  # into with the keys left is refused, naming the key that led to it, and
  # a missing key is refused as `[]` refuses it; `dig?` answers nil for both.
  def dig(key : K)

  def dig(key : K, *subkeys)

  def dig?(key : K)

  def dig?(key : K, *subkeys)

  # A table of its own with the same pairs in the same order, and the same
  # default; what is in the keys and values is shared, as an array's dup
  # shares its elements.
  def dup : Hash(K, V)

  # Every pair, in the order it went in.
  def each(& : (K, V -> Nil)) : Nil

  def each_key(& : (K -> Nil)) : Nil

  def each_value(& : (V -> Nil)) : Nil

  def empty? : Bool

  # The value, or *default* when the key has none: the call says what a
  # missing key answers, so a default the table was made with is not asked.
  def fetch(key : K, default : D) : V | D forall D

  # The value, or what the block answers for the missing key.
  def fetch(key : K, & : (K -> U)) : V | U forall U

  def first_key : K

  # The oldest pair's key and value, nil when the table is empty; `first_key`
  # and `first_value` refuse an empty table as `Array#first` refuses one.
  def first_key? : K | ::Nil

  def first_value : V

  def first_value? : V | ::Nil

  def has_key?(key : K) : Bool

  # Whether a value is in the table: a walk, since the index is of keys.
  def has_value?(value : V) : Bool

  # Hashing follows `==`, so the order cannot count: each pair is hashed as
  # a tuple is, mixed, and the pairs added up, which any order adds alike.
  def hash : Int32

  def inspect : String

  # Values to keys; a value two keys share keeps the later key.
  def invert : Hash(V, K)

  def key_for(value : V) : K

  # The first key, in insertion order, whose value is *value*; `key_for`
  # refuses a value no key has, and `key_for?` answers nil for it.
  def key_for?(value : V) : K | ::Nil

  # The keys, and the values, each in the order they went in.
  def keys : Array(K)

  # An array of what the block answers for each pair, in order.
  def map(& : (K, V -> U)) : Array(U) forall U

  # A new table with this one's pairs and then *other*'s, the second value
  # winning for a key both have; the key and value types are both tables'.
  # Neither table changes, and the copy has no default: one made for these
  # keys and values need not answer for the wider types.
  def merge(other : Hash(L, W)) : Hash(K | L, V | W) forall L, W

  # The same, with the block answering for a key both tables have: it is
  # handed the key, this table's value and *other*'s.
  def merge(other : Hash(L, W), & : (L, V | W, W -> V | W)) : Hash(K | L, V | W) forall L, W

  # *other*'s pairs written into this table, which is answered: the other
  # library's `merge!`, spelled as SPEC.md III.1.7a spells the mutating one.
  def merge_in_place(other : Hash(L, W)) : Hash(K, V) forall L, W

  def merge_in_place(other : Hash(L, W), & : (L, V, W -> V)) : Hash(K, V) forall L, W

  def new

  def new(&block : (Hash(K, V), K -> V))

  # The key's value when it has one, and otherwise *value* written and
  # answered: one probe for a key that is there.
  def put_if_absent(key : K, value : V) : V

  # The same with the value computed only when the key is missing.
  def put_if_absent(key : K, & : (K -> V)) : V

  def reject(& : (K, V -> Bool)) : Hash(K, V)

  def reject_in_place(& : (K, V -> Bool)) : Hash(K, V)

  # The pairs the block answers true for, or false for, as a new table.
  def select(& : (K, V -> Bool)) : Hash(K, V)

  # The same, in place. A delete inside `each` is safe in this table: it
  # marks the entry gone where it stands and nothing moves until a growth,
  # which only a write of a new key starts.
  def select_in_place(& : (K, V -> Bool)) : Hash(K, V)

  # The oldest pair taken out and answered, the table drained as a queue in
  # the order it was filled; `shift?` answers nil when it is empty.
  def shift : Tuple(K, V)

  def shift? : Tuple(K, V) | ::Nil

  def size : Int32

  # The pairs sorted on the key the block answers for each, ascending and
  # stable: `to_a.sorted_by` with the pair taken apart for the block.
  def sorted_by(& : (K, V -> U)) : Array(Tuple(K, V)) forall U

  # The sum of what the block answers for each pair, and the block's own
  # zero when there are none, as `Array#sum` answers.
  def sum(& : (K, V -> U)) : U forall U

  # Every pair as a tuple, in the order it went in - what a sort by value
  # starts from.
  def to_a : Array(Tuple(K, V))

  # The table itself, as the other library's `to_h` answers it.
  def to_h : Hash(K, V)

  # `{"a" => 1}`, in insertion order, both sides inspected; a first key in
  # braces is spaced off, `{ {1, 2} => 3 }`, as a tuple's: `{{` is a macro.
  def to_s : String

  # Every key through the block, in order; two keys that become one keep the
  # later value, as two writes of one key do.
  def transform_keys(& : (K, V -> L)) : Hash(L, V) forall L

  # Every value through the block, the keys and their order kept; the block
  # may take the key as well, after the value, as the other library's does.
  def transform_values(& : (V, K -> W)) : Hash(K, W) forall W

  # The same in place, which is why the type cannot change.
  def transform_values_in_place(& : (V, K -> V)) : Hash(K, V)

  # The key's value replaced by what the block answers for it, and the old
  # value answered, as the other library answers it. A missing key is handed
  # to the table's default and the block answers for that; with no default
  # it is refused as `[]` refuses it.
  def update(key : K, & : (V -> V)) : V

  def values : Array(V)

  # The values of the keys given, in that order, each answered as `[]`
  # answers it - so a missing key is refused, or the default's.
  def values_at(*keys : K) : Array(V)

  def self.new(default : V) : Hash(K, V)
end