 
   # A dictionary (key-value) implementation based on dynamic hashing.
   #
-  # This implementation is based on Erlang's dict implementation which
-  # is based on "The Design and Implementation of Dynamic Hashing for
-  # Sets and Tables in Icon" by Griswold and Townsend.
+  # 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 segment with 16 buckets. This allow us to skip hashing
+  #    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 12 elements, the bucket is promoted to a segment
-  #    (i.e. a set of buckets). At this point, it works as a simple
-  #    hash table with fixed size of 32
-  # 5. Once the segment starts having high density (~32 * 5 items),
-  #    we promote it to a full Dict, similar to one that we would find
-  #    in Erlang. However, since this promotion happens just late, we
-  #    can afford larger segments which results in faster times
-  #
-  # Notice that promotions are not expensive because a dict is actually
-  # made of segments, and each segment is made of buckets. Starting with
-  # a bucket simply allows us to remove considerably overhead compared to
-  # managing all those structures from scratch.
-
-  # Constants values used to rehash the dictionary
-  @expand_load 5
-  @contract_load 3
-  @segment_size 32
-  @segment_template :erlang.make_tuple(@segment_size, [])
-  @ordered_threshold 12
-  @bucketed_threshold @segment_size * @expand_load
+  #
+  # 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
-  # represented exactly by one segment
-  defrecordp :bucketed,
+  # 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,
-    buckets: @segment_template
-
-  # The segmented record contains one or more segments
-  # (i.e. a series of buckets)
-  defrecordp :segmented,
-    size: 0,
-    n: @segment_size,
-    maxn: @segment_size,
-    bso: div(@segment_size, 2),
-    exp_size: @expand_load * @segment_size,
-    con_size: @contract_load * @segment_size,
-    segments: nil
+    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.


  ## Dict-wide functions

  defp dict_get(ordered(bucket: bucket), key) when is_list(bucket) do
    :lists.keyfind(key, 1, bucket)
  end

  defp dict_get(bucketed(buckets: buckets), key) do
    pos = bucket_hash(key)
    :lists.keyfind(key, 1, elem(buckets, pos))
  end

  defp dict_get(segmented(segments: segments) = dict, key) do
    slot   = bucket_slot(dict, key)
    bucket = segments_get(segments, slot)
    :lists.keyfind(key, 1, bucket)
  end

  defp dict_fold(ordered(bucket: bucket), acc, fun) when is_list(bucket) do
    bucket_fold(bucket, acc, fun)
  end

  defp dict_fold(bucketed(buckets: segment), acc, fun) do
    segment_fold(segment, acc, fun, @segment_size)
  end

  defp dict_fold(segmented(segments: segments), acc, fun) do
    segments_fold(segments, acc, fun, tuple_size(segments))
  end

  defp dict_put(ordered(size: size, bucket: bucket) = dict, key, value) when is_list(bucket) do
    case bucket_put(bucket, key, value) do
      { new_bucket, 0 } ->
        { ordered(dict, bucket: new_bucket), 0 }
      { new_bucket, 1 } ->
        if size == @ordered_threshold do
          buckets = rehash_bucket(new_bucket, @segment_template)
          { bucketed(size: size + 1, buckets: buckets), 1 }
        else
          { ordered(dict, size: size + 1, bucket: new_bucket), 1 }
        end
    end
  end

  defp dict_put(bucketed(buckets: buckets, size: size) = dict, key, value) do
    pos = bucket_hash(key)
    case bucket_put(elem(buckets, pos), key, value) do
      { new_bucket, 0 } ->
        { bucketed(dict, buckets: setelem(buckets, pos, new_bucket)), 0 }
      { new_bucket, 1 } ->
        if size == @bucketed_threshold do
          { maybe_expand(segmented(size: size), { setelem(buckets, pos, new_bucket) }, 1), 1 }
        else
          { bucketed(dict, size: size + 1, buckets: setelem(buckets, pos, new_bucket)), 1 }
        end
    end
  end

  defp dict_put(segmented(segments: segments) = dict, key, value) do
    slot = bucket_slot(dict, key)
    { segments, count } = segments_update segments, slot, bucket_put(&1, key, value)
    { maybe_expand(dict, segments, count), count }
  end

  ## Bucket helpers

    end
  end

  def delete(trie(root: root, size: size, depth: depth) = dict, key) do
    pos = bucket_hash(key)
    case node_delete(root, depth, pos, key) do
      { _, 0 } ->
        dict
      { root, -1 } ->
        res = if depth > 0 and trie(dict, :contract_on) == size do
          root = node_contract(root, depth, depth - 1)
          trie(dict,
            root: root,
            size: size - 1,
            depth: depth - 1,
            contract_on: div(size, @node_size),
            expand_on: div(trie(dict, :expand_on), @node_size))
        else
          trie(dict, size: size - 1, root: root)
        end
    end
  end

  @doc """
