defmodule Xb5.Bag do
  @moduledoc """
  An ordered [multiset](https://en.wikipedia.org/wiki/Multiset) (bag) backed by
  a [B-tree](https://en.wikipedia.org/wiki/B-tree) of order 5.


  Unlike a set, a bag allows duplicate values — the same value may appear multiple times.
  Elements are kept in ascending Erlang term order. Comparisons use `==` rather than `===` —
  so `1` and `1.0` are treated as the same element.

  ## Pushing vs putting

  Two insert operations are provided:

    * `push/2` — always inserts a new copy, even if the value is already present.
    * `put/2` — inserts only if the value is not already present (idempotent, like `MapSet.put/2`).

  ## Order-statistic operations

  In addition to standard collection operations, `Xb5.Bag` provides:

    * `at/2` — O(log n) element access by index.
    * `index_of/2`, `index_of!/2` — 0-based index of a value.
    * `percentile/3`, `percentile_bracket/3` — percentile queries.
    * `percentile_rank/2` — the percentile position of a value.

  Conversion to a list via `to_list/1` always yields elements in ascending
  order, with duplicates preserved.

  ## Erlang interop

  `Xb5.Bag` is compatible with the Erlang `:xb5_bag` module. Build one from an `:xb5_bag`
  term via `new/1`. To go the other way, call `unwrap!/1` to extract the size and root node,
  then pass the result to `:xb5_bag.wrap/1`.

  ## See also

    * `Xb5.Set` — ordered set, for unique elements and set-algebraic operations.
    * `Xb5.Tree` — ordered key-value store.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 1, 2, 3])
      Xb5.Bag.new([1, 1, 2, 3])
      iex> Xb5.Bag.member?(bag, 2)
      true
      iex> Xb5.Bag.count(bag, 1)
      2

  """

  ## Types

  @enforce_keys [:size, :root]
  defstruct [:size, :root]

  @type t(value) :: %__MODULE__{size: non_neg_integer(), root: :xb5_bag_node.t(value)}
  @type t :: t(value)
  @type order :: :asc | :desc
  @type value :: term

  ## API

  @doc """
  Finds the element at the given `index` (0-based). Returns `default` if `index` is out of bounds.
  Runs in O(log n) time.

  A negative `index` counts from the end: `-1` is the last element, `-2` the second-to-last, etc.

  This function is an optimized version of `Enum.at/2`.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.at(bag, 0)
      1
      iex> Xb5.Bag.at(bag, 2)
      3
      iex> Xb5.Bag.at(bag, -1)
      3
      iex> Xb5.Bag.at(bag, 5)
      nil
      iex> Xb5.Bag.at(bag, 5, :missing)
      :missing

  """
  @spec at(t(value), index, default) :: value | default when index: integer, default: term()
  def at(bag, value, default \\ nil)

  def at(%__MODULE__{size: size, root: root}, index, default) when is_integer(index) do
    resolved_index = resolve_index(size, index)

    if resolved_index < 0 or resolved_index >= size do
      default
    else
      :xb5_bag_node.nth(resolved_index + 1, root)
    end
  end

  @doc """
  Returns the number of times `value` appears in `bag`. Values are matched using `==`.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 1, 1, 2, 3])
      iex> Xb5.Bag.count(bag, 1)
      3
      iex> Xb5.Bag.count(bag, 2)
      1
      iex> Xb5.Bag.count(bag, 4)
      0

  """
  @spec count(t(value), value) :: non_neg_integer()
  def count(%__MODULE__{size: size, root: root}, value) do
    case :xb5_bag_node.rank(value, root) do
      :none ->
        0

      rank ->
        case :xb5_bag_node.rank_larger(value, root) do
          [larger_rank | _] ->
            larger_rank - rank

          :none ->
            size - rank + 1
        end
    end
  end

  @doc """
  Removes one occurrence of `value` from the bag. Returns the bag unchanged if `value` is not present.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 1, 2, 3])
      iex> Xb5.Bag.delete(bag, 1)
      Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.delete(bag, 4)
      Xb5.Bag.new([1, 1, 2, 3])

  """
  @spec delete(t(val1), val2) :: t(val1) when val1: value(), val2: value()
  def delete(%__MODULE__{size: size, root: root} = bag, value) do
    case :xb5_bag_node.delete_att(value, root) do
      :badkey ->
        bag

      root ->
        %{bag | size: size - 1, root: root}
    end
  end

  @doc """
  Removes all occurrences of `value` from the bag. Returns the bag unchanged if `value` is not present.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 1, 2, 3])
      iex> Xb5.Bag.delete_all(bag, 1)
      Xb5.Bag.new([2, 3])
      iex> Xb5.Bag.delete_all(bag, 4)
      Xb5.Bag.new([1, 1, 2, 3])

  """
  @spec delete_all(t(val1), val2) :: t(val1) when val1: value(), val2: value()
  def delete_all(%__MODULE__{size: size, root: root} = bag, value) do
    case :xb5_bag_node.delete_att(value, root) do
      :badkey -> bag
      root -> delete_all_recur(value, size - 1, root)
    end
  end

  @doc """
  Returns a new bag containing only elements for which `fun` returns a truthy value.

  ## Examples

      iex> Xb5.Bag.filter(Xb5.Bag.new([1, 2, 3, 4, 5]), fn x -> x > 3 end)
      Xb5.Bag.new([4, 5])

      iex> Xb5.Bag.filter(Xb5.Bag.new([1, 1, 2, 3]), fn x -> rem(x, 2) != 0 end)
      Xb5.Bag.new([1, 1, 3])

  """
  @spec filter(t(a), (a -> as_boolean(term()))) :: t(a) when a: value()
  def filter(bag, fun) do
    from_ordered_list(for elem <- to_list(bag), fun.(elem), do: elem)
  end

  @doc """
  Returns the first (smallest) element in the bag, or `default` if the bag is empty.

  ## Examples

      iex> Xb5.Bag.first(Xb5.Bag.new([1, 2, 3]))
      1
      iex> Xb5.Bag.first(Xb5.Bag.new())
      nil
      iex> Xb5.Bag.first(Xb5.Bag.new(), :empty)
      :empty

  """
  @spec first(t(value), default) :: value | default when default: term()
  def first(bag, default \\ nil)

  def first(%__MODULE__{size: size, root: root}, default) do
    if size === 0, do: default, else: :xb5_bag_node.smallest(root)
  end

  @doc """
  Returns the first (smallest) element in the bag. Raises `Xb5.EmptyError` if the bag is empty.

  ## Examples

      iex> Xb5.Bag.first!(Xb5.Bag.new([1, 2, 3]))
      1
      iex> Xb5.Bag.first!(Xb5.Bag.new())
      ** (Xb5.EmptyError) empty error

  """
  @spec first!(t(value)) :: value
  def first!(%__MODULE__{size: size, root: root}) do
    if size === 0, do: raise(Xb5.EmptyError), else: :xb5_bag_node.smallest(root)
  end

  @doc """
  Returns the smallest element strictly greater (larger) than `value`, or
  `:error` if none exists.

  `value` does not need to be a member of the bag.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.higher(bag, 1)
      {:ok, 2}
      iex> Xb5.Bag.higher(bag, 1.5)
      {:ok, 2}
      iex> Xb5.Bag.higher(bag, 3)
      :error

  """
  @spec higher(t(value), value) :: {:ok, value} | :error
  def higher(%__MODULE__{root: root}, value) do
    case :xb5_bag_node.larger(value, root) do
      {:found, e} -> {:ok, e}
      :none -> :error
    end
  end

  @doc """
  Returns the 0-based index of `value` in the bag, or `nil` if not present. Runs in O(log n) time.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.index_of(bag, 1)
      0
      iex> Xb5.Bag.index_of(bag, 3)
      2
      iex> Xb5.Bag.index_of(bag, 4)
      nil

  """
  @spec index_of(t(value), value) :: non_neg_integer | nil
  def index_of(%__MODULE__{root: root}, value) do
    case :xb5_bag_node.rank(value, root) do
      :none -> nil
      rank -> rank - 1
    end
  end

  @doc """
  Returns the 0-based index of `value` in the bag. Raises `KeyError` if not present. Runs in O(log n) time.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.index_of!(bag, 1)
      0
      iex> Xb5.Bag.index_of!(bag, 3)
      2
      iex> assert_raise KeyError, fn -> Xb5.Bag.index_of!(bag, 4) end

  """
  @spec index_of!(t(value), value) :: non_neg_integer
  def index_of!(%__MODULE__{root: root} = bag, value) do
    case :xb5_bag_node.rank(value, root) do
      :none -> raise KeyError, term: bag, key: value
      rank -> rank - 1
    end
  end

  @doc """
  Returns the last (largest) element in the bag, or `default` if the bag is empty.

  ## Examples

      iex> Xb5.Bag.last(Xb5.Bag.new([1, 2, 3]))
      3
      iex> Xb5.Bag.last(Xb5.Bag.new())
      nil
      iex> Xb5.Bag.last(Xb5.Bag.new(), :empty)
      :empty

  """
  @spec last(t(value), default) :: value | default when default: term()
  def last(bag, default \\ nil)

  def last(%__MODULE__{size: size, root: root}, default) do
    if size === 0, do: default, else: :xb5_bag_node.largest(root)
  end

  @doc """
  Returns the last (largest) element in the bag. Raises `Xb5.EmptyError` if the bag is empty.

  ## Examples

      iex> Xb5.Bag.last!(Xb5.Bag.new([1, 2, 3]))
      3
      iex> Xb5.Bag.last!(Xb5.Bag.new())
      ** (Xb5.EmptyError) empty error

  """
  @spec last!(t(value)) :: value
  def last!(%__MODULE__{size: size, root: root}) do
    if size === 0, do: raise(Xb5.EmptyError), else: :xb5_bag_node.largest(root)
  end

  @doc """
  Returns the largest element strictly less (smaller) than `value`, or `:error`
  if none exists.

  `value` does not need to be a member of the bag.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.lower(bag, 3)
      {:ok, 2}
      iex> Xb5.Bag.lower(bag, 1.5)
      {:ok, 1}
      iex> Xb5.Bag.lower(bag, 1)
      :error

  """
  @spec lower(t(value), value) :: {:ok, value} | :error
  def lower(%__MODULE__{root: root}, value) do
    case :xb5_bag_node.smaller(value, root) do
      {:found, e} -> {:ok, e}
      :none -> :error
    end
  end

  @doc """
  Checks if `bag` contains `value`. Membership is tested using `==`, not `===`.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.member?(bag, 2)
      true
      iex> Xb5.Bag.member?(bag, 2.0)
      true
      iex> Xb5.Bag.member?(bag, 4)
      false

  """
  @spec member?(t(), value()) :: boolean()
  def member?(%__MODULE__{root: root}, value) do
    :xb5_bag_node.is_member(value, root)
  end

  @doc """
  Merges two bags into a new bag containing all elements from both, preserving duplicates.

  ## Examples

      iex> Xb5.Bag.merge(Xb5.Bag.new([1, 2, 3]), Xb5.Bag.new([2, 3, 4]))
      Xb5.Bag.new([1, 2, 2, 3, 3, 4])

      iex> Xb5.Bag.merge(Xb5.Bag.new([1, 2]), Xb5.Bag.new())
      Xb5.Bag.new([1, 2])

  """
  @spec merge(t(val1), t(val2)) :: t(val1 | val2) when val1: value(), val2: value()
  def merge(%__MODULE__{size: size1, root: root1}, %__MODULE__{size: size2, root: root2}) do
    size = size1 + size2
    root = :xb5_bag_node.merge(size1, root1, size2, root2)
    %__MODULE__{size: size, root: root}
  end

  @doc """
  Returns a new empty bag.

  ## Examples

      iex> Xb5.Bag.new()
      Xb5.Bag.new([])

  """
  @spec new() :: t()
  def new() do
    %__MODULE__{size: 0, root: :xb5_bag_node.new()}
  end

  @doc """
  Creates a bag from an Erlang `:xb5_bag` term or an enumerable.

  When given an enumerable, elements are stored in ascending order with duplicates preserved.
  When given an Erlang `:xb5_bag` term, the underlying structure is reused directly.

  ## Examples

      iex> Xb5.Bag.new([1, 1, 2, 3])
      Xb5.Bag.new([1, 1, 2, 3])

      iex> Xb5.Bag.new([3, :a, :b, :b])
      Xb5.Bag.new([3, :a, :b, :b])

  """
  @spec new(:xb5_bag.bag(value) | Enumerable.t()) :: t(value)
  def new(input) do
    case :xb5_bag.unwrap(input) do
      {:ok, %{size: size, root: root}} ->
        %__MODULE__{size: size, root: root}

      {:error, _} ->
        input
        |> Enum.to_list()
        |> :lists.sort()
        |> from_ordered_list()
    end
  end

  @doc """
  Creates a bag from an Erlang `:xb5_bag` term or an enumerable via the transformation function.

  ## Examples

      iex> Xb5.Bag.new([1, 1, 2], fn x -> x * 2 end)
      Xb5.Bag.new([2, 2, 4])

  """
  @spec new(:xb5_bag.bag() | Enumerable.t(), (term() -> value)) :: t(value)
  def new(input, transform) do
    case :xb5_bag.unwrap(input) do
      {:ok, %{root: root}} ->
        transform
        |> :xb5_bag_node.map_to_list(root)
        |> :lists.sort()
        |> from_ordered_list()

      {:error, _} ->
        input
        |> Enum.map(transform)
        |> :lists.sort()
        |> from_ordered_list()
    end
  end

  @doc """
  Returns the percentile value for the given `percentile` (0.0–1.0) using the given method options.
  Returns `nil` if the bag is empty or the percentile is out of range for the chosen method.
  Runs in O(log n) time.

  Raises `Xb5.Bag.NonNumericInterpolationError` if the percentile falls between two elements
  and those elements are not numbers (interpolation is impossible for non-numeric values).

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3, 4])
      iex> Xb5.Bag.percentile(bag, 0.0)
      1
      iex> Xb5.Bag.percentile(bag, 0.5)
      2.5
      iex> Xb5.Bag.percentile(bag, 1.0)
      4
      iex> Xb5.Bag.percentile(Xb5.Bag.new(), 0.5)
      nil

  """
  @spec percentile(t(value), percentile, opts) :: (value | interpolation_result) | nil
        when percentile: :xb5_bag_utils.percentile(),
             opts: [:xb5_bag_utils.percentile_bracket_opt()],
             interpolation_result: number

  def percentile(bag, percentile, opts \\ [])

  def percentile(%__MODULE__{size: size, root: root}, percentile, opts) do
    value_fun = fn value -> value end

    try do
      case :xb5_bag_utils.percentile(percentile, size, root, value_fun, opts) do
        :none -> nil
        result -> result
      end
    catch
      :error, {:bracket_value_not_a_number, %{value: value, bracket: bracket}} ->
        raise Xb5.Bag.NonNumericInterpolationError, value: value, bracket: bracket
    end
  end

  @doc """
  Returns the percentile bracket for the given `percentile`, or `nil` if the bag is empty or the
  percentile is out of range for the chosen method. Runs in O(log n) time.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3, 4])
      iex> Xb5.Bag.percentile_bracket(bag, 0.0)
      {:exact, 1}
      iex> Xb5.Bag.percentile_bracket(bag, 0.5)
      {:between, 2, 3, 0.5000000000000001}
      iex> Xb5.Bag.percentile_bracket(bag, 1.0)
      {:exact, 4}
      iex> Xb5.Bag.percentile_bracket(Xb5.Bag.new(), 0.5)
      nil

  """
  @spec percentile_bracket(t(value), percentile, opts) ::
          {:exact, value} | {:between, value, value, float} | nil
        when percentile: :xb5_bag_utils.percentile(),
             opts: [:xb5_bag_utils.percentile_bracket_opt()]

  def percentile_bracket(bag, percentile, opts \\ [])

  def percentile_bracket(%__MODULE__{size: size, root: root}, percentile, opts) do
    case :xb5_bag_utils.percentile_bracket(percentile, size, root, opts) do
      :none -> nil
      result -> result
    end
  end

  @doc """
  Returns the percentile rank of `value` in the bag as a float in 0.0–1.0. Runs in O(log n) time.
  Raises `Xb5.EmptyError` if the bag is empty.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3, 4, 5])
      iex> Xb5.Bag.percentile_rank(bag, 3)
      0.5
      iex> Xb5.Bag.percentile_rank(bag, 1)
      0.1
      iex> Xb5.Bag.percentile_rank(Xb5.Bag.new(), 1)
      ** (Xb5.EmptyError) empty error

  """
  @spec percentile_rank(t(value), value) :: float
  def percentile_rank(%__MODULE__{size: size, root: root}, value) when size > 0 do
    :xb5_bag_utils.percentile_rank(value, size, root)
  end

  def percentile_rank(%__MODULE__{}, _value) do
    raise Xb5.EmptyError
  end

  @doc """
  Removes and returns the first (smallest) element. Raises `Xb5.EmptyError` if the bag is empty.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.pop_first!(bag)
      {1, Xb5.Bag.new([2, 3])}
      iex> Xb5.Bag.pop_first!(Xb5.Bag.new())
      ** (Xb5.EmptyError) empty error

  """
  @spec pop_first!(t(value)) :: {value, t(value)}
  def pop_first!(%__MODULE__{size: size, root: root} = bag) do
    if size === 0 do
      raise Xb5.EmptyError
    else
      [value | root] = :xb5_bag_node.take_smallest(root)
      bag = %{bag | size: size - 1, root: root}
      {value, bag}
    end
  end

  @doc """
  Removes and returns the last (largest) element. Raises `Xb5.EmptyError` if the bag is empty.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.pop_last!(bag)
      {3, Xb5.Bag.new([1, 2])}
      iex> Xb5.Bag.pop_last!(Xb5.Bag.new())
      ** (Xb5.EmptyError) empty error

  """
  @spec pop_last!(t(value)) :: {value, t(value)}
  def pop_last!(%__MODULE__{size: size, root: root} = bag) do
    if size === 0 do
      raise Xb5.EmptyError
    else
      [value | root] = :xb5_bag_node.take_largest(root)
      bag = %{bag | size: size - 1, root: root}
      {value, bag}
    end
  end

  @doc """
  Adds `value` to the bag, always inserting a new copy even if already present.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.push(bag, 2)
      Xb5.Bag.new([1, 2, 2, 3])
      iex> Xb5.Bag.push(bag, 4)
      Xb5.Bag.new([1, 2, 3, 4])

  """
  @spec push(t(value), new_value) :: t(value | new_value) when new_value: value()
  def push(%__MODULE__{size: size, root: root} = bag, value) do
    root = :xb5_bag_node.push(value, root)
    %{bag | size: size + 1, root: root}
  end

  @doc """
  Adds `value` to the bag only if it is not already present. Returns the bag unchanged if `value` is present.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.put(bag, 2)
      Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.put(bag, 4)
      Xb5.Bag.new([1, 2, 3, 4])

  """
  @spec put(t(value), new_value) :: t(value | new_value) when new_value: value()
  def put(%__MODULE__{size: size, root: root} = bag, value) do
    case :xb5_bag_node.insert_att(value, root) do
      :key_exists ->
        bag

      root ->
        %{bag | size: size + 1, root: root}
    end
  end

  @doc """
  Returns a new bag containing only elements for which `fun` returns a falsy value.

  ## Examples

      iex> Xb5.Bag.reject(Xb5.Bag.new([1, 2, 3, 4, 5]), fn x -> x > 3 end)
      Xb5.Bag.new([1, 2, 3])

      iex> Xb5.Bag.reject(Xb5.Bag.new([1, 1, 2, 3]), fn x -> rem(x, 2) != 0 end)
      Xb5.Bag.new([2])

  """
  @spec reject(t(a), (a -> as_boolean(term()))) :: t(a) when a: value()
  def reject(bag, fun) do
    from_ordered_list(for elem <- to_list(bag), !fun.(elem), do: elem)
  end

  @doc """
  Returns the number of elements in the bag, counting duplicates.

  ## Examples

      iex> Xb5.Bag.size(Xb5.Bag.new([1, 2, 3]))
      3
      iex> Xb5.Bag.size(Xb5.Bag.new([1, 1, 2]))
      3
      iex> Xb5.Bag.size(Xb5.Bag.new())
      0

  """
  @spec size(t()) :: non_neg_integer()
  def size(%__MODULE__{size: size}) do
    size
  end

  @doc """
  Returns a lazy stream over all elements of `bag`.

  `order` controls traversal direction: `:asc` (ascending, the default) or
  `:desc` (descending).

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3])
      iex> Xb5.Bag.stream(bag) |> Enum.to_list()
      [1, 2, 3]
      iex> Xb5.Bag.stream(bag, :desc) |> Enum.to_list()
      [3, 2, 1]
      iex> Xb5.Bag.stream(Xb5.Bag.new()) |> Enum.to_list()
      []

  """
  @spec stream(t(value), order) :: Enumerable.t()
  def stream(bag, order \\ :asc)

  def stream(%__MODULE__{root: root}, order) do
    erl_iterator_order = erl_iterator_order(order)

    Stream.resource(
      fn -> :xb5_bag_node.iterator(root, erl_iterator_order) end,
      &stream_next/1,
      &stream_after/1
    )
  end

  @doc """
  Returns a lazy stream over elements of `bag` starting from `value`.

  For `:asc` (the default), starts at the first element greater than or
  equal to `value`. For `:desc`, starts at the first element less than or
  equal to `value`. Returns an empty stream if no such element exists.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3, 4, 5])
      iex> Xb5.Bag.stream_from(bag, 3) |> Enum.to_list()
      [3, 4, 5]
      iex> Xb5.Bag.stream_from(bag, 3, :desc) |> Enum.to_list()
      [3, 2, 1]
      iex> Xb5.Bag.stream_from(bag, 6) |> Enum.to_list()
      []

  """
  @spec stream_from(t(value), value, order) :: Enumerable.t()
  def stream_from(bag, value, order \\ :asc)

  def stream_from(%__MODULE__{root: root}, value, order) do
    erl_iterator_order = erl_iterator_order(order)

    Stream.resource(
      fn -> :xb5_bag_node.iterator_from(value, root, erl_iterator_order) end,
      &stream_next/1,
      &stream_after/1
    )
  end

  @doc """
  Returns a lazy stream over elements of `bag` starting from `index` (0-based),
  always in ascending order.

  A negative `index` counts from the end: `-1` starts at the last element.
  Returns an empty stream if `index` is out of bounds.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 2, 3, 4, 5])
      iex> Xb5.Bag.stream_from_index(bag, 2) |> Enum.to_list()
      [3, 4, 5]
      iex> Xb5.Bag.stream_from_index(bag, -2) |> Enum.to_list()
      [4, 5]
      iex> Xb5.Bag.stream_from_index(bag, 10) |> Enum.to_list()
      []

  """
  @spec stream_from_index(t(value), integer) :: Enumerable.t()
  def stream_from_index(%__MODULE__{root: root, size: size}, index) when is_integer(index) do
    resolved_index = resolve_index(size, index)

    if resolved_index < 0 or resolved_index >= size do
      Stream.resource(
        fn -> :ok end,
        fn iter -> {:halt, iter} end,
        fn _iter -> :ok end
      )
    else
      rank = resolved_index + 1

      Stream.resource(
        fn -> :xb5_bag_node.iterator_from_nth(rank, size, root, :ordered) end,
        &stream_next/1,
        &stream_after/1
      )
    end
  end

  @doc """
  Returns structural statistics about the underlying B-tree.

  Useful for inspecting tree balance and node utilization.

  ## Examples

      iex> Xb5.Bag.structural_stats(Xb5.Bag.new(1..100))
      [
        height: 4,
        node_counts: [
          internal4: 2,
          internal3: 3,
          internal2: 3,
          internal1: 1,
          leaf4: 6,
          leaf3: 14,
          leaf2: 5,
          leaf1: 0
        ],
        node_percentages: [
          internal4: 5.9,
          internal3: 8.8,
          internal2: 8.8,
          internal1: 2.9,
          leaf4: 17.6,
          leaf3: 41.2,
          leaf2: 14.7,
          leaf1: 0.0
        ],
        total_keys: 100,
        key_percentages: [
          internal4: 8.0,
          internal3: 9.0,
          internal2: 6.0,
          internal1: 1.0,
          leaf4: 24.0,
          leaf3: 42.0,
          leaf2: 10.0,
          leaf1: 0.0
        ],
        avg_keys_per_node: 2.9411764705882355,
        avg_keys_per_internal_node: 2.6666666666666665,
        avg_keys_per_leaf_node: 3.04
      ]


  """
  @spec structural_stats(t()) :: :xb5_structural_stats.t()
  def structural_stats(%__MODULE__{root: root}) do
    :xb5_bag_node.structural_stats(root)
  end

  @doc """
  Returns all elements as a sorted list, with duplicates.

  ## Examples

      iex> Xb5.Bag.to_list(Xb5.Bag.new([1, 2, 3]))
      [1, 2, 3]
      iex> Xb5.Bag.to_list(Xb5.Bag.new([1, 1, 2]))
      [1, 1, 2]

  """
  @spec to_list(t(value)) :: [value]
  def to_list(%__MODULE__{root: root}) do
    :xb5_bag_node.to_list(root)
  end

  @doc """
  Returns the size and root node of `bag` as `%{size: n, root: node}`.
  Pass the result to `:xb5_bag.wrap/1` to obtain a proper `:xb5_bag` term.

  ## Examples

      iex> bag = Xb5.Bag.new([1, 1, 2, 3])
      iex> %{size: size} = Xb5.Bag.unwrap!(bag)
      iex> size
      4

  """
  @spec unwrap!(t(value)) :: :xb5_bag.unwrapped_bag(value)
  def unwrap!(%__MODULE__{size: size, root: root}) do
    %{size: size, root: root}
  end

  ## Internal

  defp delete_all_recur(value, size, root) do
    case :xb5_bag_node.delete_att(value, root) do
      :badkey -> %__MODULE__{size: size, root: root}
      root -> delete_all_recur(value, size - 1, root)
    end
  end

  defp from_ordered_list(list) do
    size = length(list)
    root = :xb5_bag_node.from_ordered_list(size, list)
    %__MODULE__{size: size, root: root}
  end

  defp resolve_index(size, index) do
    if index < 0 do
      size + index
    else
      index
    end
  end

  ##

  defp erl_iterator_order(:asc), do: :ordered
  defp erl_iterator_order(:desc), do: :reversed

  defp stream_next(iter) do
    case :xb5_bag_node.next(iter) do
      {value, iter} ->
        {[value], iter}

      :none ->
        {:halt, iter}
    end
  end

  defp stream_after(_iter) do
    :ok
  end

  ## Protocols - Enumerable

  defimpl Enumerable do
    # credo:disable-for-next-line Credo.Check.Readability.Specs
    def count(bag) do
      {:ok, Xb5.Bag.size(bag)}
    end

    # credo:disable-for-next-line Credo.Check.Readability.Specs
    def member?(bag, value) do
      # NOTE: not strict comparison
      {:ok, Xb5.Bag.member?(bag, value)}
    end

    # credo:disable-for-next-line Credo.Check.Readability.Specs
    def slice(%Xb5.Bag{size: bag_size, root: root}) do
      {:ok, bag_size, &:xb5_bag_node.elixir_slice(&1, &2, &3, bag_size, root)}
    end

    # credo:disable-for-next-line Credo.Check.Readability.Specs
    def reduce(%Xb5.Bag{root: root}, acc, fun) do
      :xb5_bag_node.elixir_reduce(fun, acc, root)
    end
  end

  ## Protocols - Collectable

  defimpl Collectable do
    # credo:disable-for-next-line Credo.Check.Readability.Specs
    def into(%@for{} = bag) do
      fun = fn
        list, {:cont, x} -> [x | list]
        list, :done -> Xb5.Bag.merge(bag, Xb5.Bag.new(list))
        _, :halt -> :ok
      end

      {[], fun}
    end
  end

  ## Protocols - Inspect

  defimpl Inspect do
    import Inspect.Algebra

    if Version.match?(System.version(), "~> 1.19") do
      # credo:disable-for-next-line Credo.Check.Readability.Specs
      def inspect(bag, %Inspect.Opts{} = opts) do
        {doc, %{limit: limit}} =
          bag
          |> Xb5.Bag.to_list()
          |> to_doc_with_opts(%{opts | charlists: :as_lists})

        {concat(["Xb5.Bag.new(", doc, ")"]), %{opts | limit: limit}}
      end
    else
      # credo:disable-for-next-line Credo.Check.Readability.Specs
      def inspect(bag, %Inspect.Opts{} = opts) do
        limit = limit_override(opts)

        doc =
          bag
          |> Xb5.Bag.to_list()
          |> to_doc(%{opts | limit: limit, charlists: :as_lists})

        concat(["Xb5.Bag.new(", doc, ")"])
      end

      if Mix.env() === :test do
        # Tests that assert_raise KeyError become incredibly slow otherwise. I
        # think this is because KeyError includes the bag term, which is then
        # inspected for the purposes of rendering the exception message.
        defp limit_override(_), do: 5
      else
        defp limit_override(opts), do: opts.limit
      end
    end
  end
end