   Returns the value under key from the dict as well as the dict without key.
   """
   def pop(dict, key, default // nil) do
-    { get(dict, key, default), delete(dict, key) }
+    case dict_delete(dict, key) do
+      { dict, _, 0 } -> { default, dict }
+      { dict, value, _ } -> { value, dict }
+    end
   end
 
   @doc """
   Deletes a value from the dict.
   """
-  def delete(ordered(bucket: bucket, size: size) = dict, key) do
+  def delete(dict, key) do
+    { dict, _, _ } = dict_delete(dict, key)
+    dict
+  end
+
+  @doc """
+  Returns the dict size.
+  """
+  def size(dict) do
+    elem(dict, 1)
+  end
+
+  @doc """
+  Returns an empty dict.
+  """
+  def empty(_) do
+    ordered()
+  end
+
+  def equal?(ordered(bucket: a, size: size), ordered(bucket: b, size: ^size)) do
+    a == b
+  end
+
+  def equal?(trie(size: size) = a, trie(size: ^size) = b) do
+    a == b
+  end
+
+  def equal?(ordered() = a, trie() = b) do
+    equal?(b, a)
+  end
+
+  def equal?(trie(size: size) = a, ordered(bucket: b, size: ^size)) do
+    :lists.keysort(1, to_list(a)) == :lists.keysort(1, b)
+  end
+
+  def equal?(_, _) do
+    false
+  end
+
+  @doc """
+  Converts the dict to a list.
+  """
+  def to_list(ordered(bucket: bucket)) do
+    bucket
+  end
+
+  def to_list(dict) do
+    dict_fold(dict, [], [&1|&2])
+  end
+
+  @doc """
+  Get all keys in the dict.
+  """
+  def keys(dict) do
+    dict_fold(dict, [], fn { k, _ }, acc -> [k|acc] end)
+  end
+
+  @doc """
+  Get all values in the dict.
+  """
+  def values(dict) do
+    dict_fold(dict, [], fn { _, v }, acc -> [v|acc] end)
+  end
+
+  @doc """
+  Merges two dictionaries.
+  """
+  def merge(dict, enum, callback // fn(_k, _v1, v2) -> v2 end)
+
+  def merge(dict1, dict2, callback) when is_record(dict1, HashDict) and is_record(dict2, HashDict) and elem(dict1, 1) < elem(dict2, 1) do
+    dict_fold dict1, dict2, fn { k, v1 }, acc ->
+      update(acc, k, v1, callback.(k, v1, &1))
+    end
+  end
+
+  def merge(dict1, dict2, callback) when is_record(dict1, HashDict) and is_record(dict2, HashDict) do
+    dict_fold dict2, dict1, fn { k, v2 }, acc ->
+      update(acc, k, v2, callback.(k, &1, v2))
+    end
+  end
+
+  def merge(dict1, dict2, callback) when is_record(dict1, HashDict) do
+    Enum.reduce dict2, dict1, fn { k, v2 }, acc ->
+      update(acc, k, v2, callback.(k, &1, v2))
+    end
+  end
+
+  ## Dict-wide functions
+
+  defp dict_get(ordered(bucket: bucket), key) do
+    :lists.keyfind(key, 1, bucket)
+  end
+
+  defp dict_get(trie(root: root, depth: depth), key) do
+    :lists.keyfind(key, 1, node_bucket(root, depth, bucket_hash(key)))
+  end
+
+  defp dict_fold(ordered(bucket: bucket), acc, fun) do
+    bucket_fold(bucket, acc, fun)
+  end
+
+  defp dict_fold(trie(root: root, depth: depth), acc, fun) do
+    node_fold(root, depth, acc, fun, @node_size)
+  end
+
+  defp dict_put(ordered(size: @ordered_threshold, bucket: bucket), key, value) do
+    root = node_relocate(bucket, 0)
+    dict_put(trie(size: @ordered_threshold, root: root), key, value)
+  end
+
+  defp dict_put(ordered(size: size, bucket: bucket) = dict, key, value) do
+    { new, count } = bucket_put(bucket, key, value)
+    { ordered(dict, size: size + count, bucket: new), count }
+  end
+
+  defp dict_put(trie(root: root, depth: depth, size: size, expand_on: size, contract_on: contract_on) = dict, key, value) do
+    root = node_expand(root, depth, depth + 1)
+    dict = trie(dict, root: root, depth: depth + 1,
+      expand_on: size * @node_size, contract_on: contract_on * @node_size)
+    dict_put(dict, key, value)
+  end
+
+  defp dict_put(trie(root: root, size: size, depth: depth) = dict, key, value) do
+    pos = bucket_hash(key)
+    { root, count } = node_put(root, depth, pos, key, value)
+    { trie(dict, size: size + count, root: root), count }
+  end
+
+  defp dict_delete(ordered(bucket: bucket, size: size) = dict, key) do
     case bucket_delete(bucket, key) do
-      { _, 0 } ->
-        dict
-      { new_bucket, -1 } ->
-        ordered(dict, size: size - 1, bucket: new_bucket)
-    end
-  end
-
-  def delete(trie(root: root, size: size, depth: depth) = dict, key) do
+      { _, value, 0 } ->
+        { dict, value, 0 }
+      { new_bucket, value, -1 } ->
+        { ordered(dict, size: size - 1, bucket: new_bucket), value, -1 }
+    end
+  end
+
+  defp dict_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 } ->
-        if depth > 0 and trie(dict, :contract_on) == size do
+      { _, value, 0 } ->
+        { dict, value, 0 }
+      { root, value, -1 } ->
+        { if depth > 0 and trie(dict, :contract_on) == size do
           root = node_contract(root, depth, depth - 1)
           trie(dict,
             root: root,

  defp node_delete(node, 0, hash, key) do
    pos = bucket_index(hash)
    case bucket_delete(elem(node, pos), key) do
      { _, 0 }    -> { node, 0 }
      { new, -1 } -> { set_elem(node, pos, new), -1 }
    end
  end

  defp node_delete(node, depth, hash, key) do
    pos = bucket_index(hash)
    case node_delete(elem(node, pos), depth - 1, bucket_next(hash), key) do
      { _, 0 }    -> { node, 0 }
      { new, -1 } -> { set_elem(node, pos, new), -1 }
    end
  end



  # Deletes a key from the bucket
  defp bucket_delete([{k,_}|_] = bucket, key) when key < k do
    { bucket, nil, 0 }
  end

  defp bucket_delete([{k,_}=e|bucket], key) when key > k do
    { rest, value, count } = bucket_delete(bucket, key)
    { [e|rest], value, count }
  end

  defp bucket_delete([{_,value}|bucket], _key) do
    { bucket, value, -1 }
  end

  defp bucket_delete([], _key) do
    { [], nil, 0 }
  end

  # Folds the bucket
