   @doc """
   Converts the dict to a list.
   """
-  def to_list(ordered(bucket: bucket)) when is_list(bucket) do
+  def to_list(ordered(bucket: bucket)) do
     bucket
   end
 

    :lists.foldl(fun, acc, bucket)
  end

  # Merges two buckets
  defp bucket_merge([{k1, _} = e1|d1], [{k2, _} = e2|d2]) when k1 < k2 do
    [e1|bucket_merge(d1, [e2|d2])]
  end

  defp bucket_merge([{k1, _} = e1|d1], [{k2, _} = e2|d2]) when k1 > k2 do
    [e2|bucket_merge([e1|d1], d2)]
  end

  defp bucket_merge([], d2), do: d2
  defp bucket_merge(d1, []), do: d1

  # Rehashes a bucket into a given segment
  defp rehash_bucket(bucket, segment) do
    :lists.foldl fn { key, value }, acc ->
      pos = bucket_hash(key)
      setelem(acc, pos, bucket_put!(elem(acc, pos), key, value))
    end, segment, bucket
  end

  defp bucket_hash(key) do
    :erlang.phash2(key, @segment_size)
  end

  ## Segments helpers

  # Gets a bucket from a set of segments
  defp segments_get(segments, slot) do
    segment_pos = div(slot, @segment_size)
    bucket_pos  = rem(slot, @segment_size)
    elem(elem(segments, segment_pos), bucket_pos)
  end

  # Puts a bucket in a set of segments
  defp segments_put(segments, slot, bucket) do
    segment_pos = div(slot, @segment_size)
    bucket_pos  = rem(slot, @segment_size)
    segment = setelem(elem(segments, segment_pos), bucket_pos, bucket)
    setelem(segments, segment_pos, segment)
  end

  # Update a bucket in a set of segments
  defp segments_update(segments, slot, fun) do
    segment_pos = div(slot, @segment_size)
    bucket_pos  = rem(slot, @segment_size)

    segment = elem(segments, segment_pos)
    bucket  = elem(segment, bucket_pos)

    { bucket, res } = fun.(bucket)

    segment = setelem(segment, bucket_pos, bucket)
    { setelem(segments, segment_pos, segment), res }
  end

  # Folds a segment and a segments tuple
  defp segment_fold(segment, acc, fun, count) when count >= 1 do
    acc = bucket_fold(:erlang.element(count, segment), acc, fun)
    segment_fold(segment, acc, fun, count - 1)
  end

  defp segment_fold(_segment, acc, _fun, 0) do
    acc
  end

  defp segments_fold(segments, acc, fun, count) when count >= 1 do
    acc = segment_fold(:erlang.element(count, segments), acc, fun, @segment_size)
    segments_fold(segments, acc, fun, count - 1)
  end

  defp segments_fold(_segment, acc, _fun, 0) do
    acc
  end

  defp bucket_slot(segmented(maxn: maxn, n: n, bso: bso), key) do
    h = :erlang.phash2(key, maxn)
    if h >= n, do: h - bso, else: h
  end

  defp rehash([{ key, _ } = keybag|t], slot1, slot2, maxn) do
    { l1, l2 } = rehash(t, slot1, slot2, maxn)
    case :erlang.phash2(key, maxn) do
      ^slot1 -> { [keybag|l1], l2 }
      ^slot2 -> { l1, [keybag|l2] }
    end
  end

  defp rehash([], _, _, _), do: { [], [] }

  defp maybe_expand(dict, segments, 0) do
    segmented(dict, segments: segments)
  end

  defp maybe_expand(segmented(size: size, exp_size: exp_size) = dict, segments, 1) when size >= exp_size do
    dict = maybe_expand_segments(dict, segments)
    n    = segmented(dict, :n) + 1

    segments = segmented(dict, :segments)
    slot1    = (n - segmented(dict, :bso)) - 1
    bucket   = segments_get(segments, slot1)
    slot2    = (n - 1)
    {b1,b2}  = rehash(bucket, slot1, slot2, segmented(dict, :maxn))
    segments = segments_put(segments, slot1, b1)
    segments = segments_put(segments, slot2, b2)

    segmented(dict,
      size: size + 1,
      n: n,
      exp_size: n * @expand_load,
      con_size: n * @contract_load,
      segments: segments)
  end

  defp maybe_expand(segmented(size: size) = dict, segments, 1) do
    segmented(dict, size: size + 1, segments: segments)
  end

  defp maybe_expand_segments(segmented(n: n, maxn: maxn, bso: bso) = dict, segments) when n == maxn do
    segmented(dict,
      maxn: 2 * maxn,
      bso: 2 * bso,
      segments: expand_segments(segments, @segment_template))
  end

  defp maybe_expand_segments(dict, segments) do
    segmented(dict, segments: segments)
  end

  defp expand_segments({b1}, empty), do:
    {b1,empty}
  defp expand_segments({b1,b2}, empty), do:
    {b1,b2,empty,empty}
  defp expand_segments({b1,b2,b3,b4}, empty), do:
    {b1,b2,b3,b4,empty,empty,empty,empty}
  defp expand_segments({b1,b2,b3,b4,b5,b6,b7,b8}, empty), do:
    {b1,b2,b3,b4,b5,b6,b7,b8,
     empty,empty,empty,empty,empty,empty,empty,empty}
  defp expand_segments({b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16}, empty), do:
    {b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,
     empty,empty,empty,empty,empty,empty,empty,empty,
     empty,empty,empty,empty,empty,empty,empty,empty}
  defp expand_segments(segs, empty), do:
    list_to_tuple(tuple_to_list(segs) ++ :lists.duplicate(tuple_size(segs), empty))

  defp maybe_contract(dict, segments, 0) do
    segmented(dict, segments: segments)
  end

  defp maybe_contract(segmented(size: size, con_size: con_size, n: n) = dict, segments, -1)
      when size <= con_size and n > @segment_size do
    slot1 = (n - segmented(dict, :bso)) - 1
    b1    = segments_get(segments, slot1)
    slot2 = (n - 1)
    b2    = segments_get(segments, slot2)

    segments = segments_put(segments, slot1, bucket_merge(b1, b2))
    segments = segments_put(segments, slot2, [])

    n    = n - 1
    dict = segmented(dict,
      n: n,
      size: size - 1,
      exp_size: n * @expand_load,
      con_size: n * @contract_load,
      segments: segments)
    maybe_contract_segments(dict)
  end

  defp maybe_contract(segmented(size: size) = dict, segments, -1) do
    segmented(dict, size: size - 1, segments: segments)
  end

  defp maybe_contract_segments(segmented(n: n, maxn: maxn, bso: bso, segments: segments) = dict) when n == bso do
    segmented(dict,
      maxn: div(maxn, 2),
      bso: div(bso, 2),
      segments: contract_segments(segments))
  end

  defp maybe_contract_segments(dict), do: dict

  defp contract_segments({b1,_}), do:
    {b1}
  defp contract_segments({b1,b2,_,_}), do:
    {b1,b2}
  defp contract_segments({b1,b2,b3,b4,_,_,_,_}), do:
    {b1,b2,b3,b4}
  defp contract_segments({b1,b2,b3,b4,b5,b6,b7,b8,_,_,_,_,_,_,_,_}), do:
    {b1,b2,b3,b4,b5,b6,b7,b8}
  defp contract_segments({b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16,
      _,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_}), do:
    {b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14,b15,b16}
  defp contract_segments(segs), do:
    list_to_tuple(:lists.sublist(tuple_to_list(segs), 1, div tuple_size(segs), 2))
end

defimpl Enum.Iterator, for: HashDict do


  # A dictionary (key-value) implementation based on dynamic hashing.
  #
  # This implementation is based on hash tries. We first start with
  # a set of 8 buckets and expand when the density is about 5 entries
  # per bucket. We use bit shifting to make rehashing faster on
  # expansion.
  #
  # However, compared to dict, it provides many enhancements:
  #
  # 1. HashDict buckets are ordered sets, this gives us faster access
  #    and modification times
  #
  # 2. It uses phash2 to calculate the hash (instead of phash)
  #
  # 3. The dictionary first starts with a single bucket, instead of
  #    a set of buckets with 16 buckets. This allow us to skip hashing
  #    altogher for small dictionaries, providing faster operations
  #    and reducing memory consumption
  #
  # 4. Once we reach 8 elements, the dictionary is promoted to a
  #    set of buckets

  # The ordered record contains a single bucket
  @ordered_threshold 8

  defrecordp :ordered,
    size: 0,
    bucket: []

  # The bucketed record contains a series of buckets.
  @expand_load 5
  @contract_load 2
  @node_bitmap 0b111
  @node_shift 3
  @node_size 8
  @node_template :erlang.make_tuple(@node_size, [])

  defrecordp :trie,
    size: 0,
    depth: 0,
    expand_on: @node_size * @expand_load,
    contract_on: @contract_load,
    root: @node_template

  import Bitwise

  # Let's inline common instructions
  @compile { :inline, bucket_hash: 1, bucket_index: 1, bucket_nth_index: 2, bucket_next: 1 }

  @doc """
  Creates a new empty dict.
