-spec add(Element, Bag1) -> Bag2 when Bag1 :: bag(Element), Bag2 :: bag(Element).

Adds element Element to bag Bag1, returning a new bag Bag2. If Element is already a member of Bag1, Bag1 is returned unchanged.

Examples

> S0 = xb5_bag:new().
> xb5_bag:to_list(xb5_bag:add(1, S0)).
[1]
> S1 = xb5_bag:from_list([1, 2, 3]).
> xb5_bag:to_list(xb5_bag:add(2, S1)).
[1, 2, 3]
> xb5_bag:to_list(xb5_bag:add(4, S1)).
[1, 2, 3, 4]

-spec count(Element, Bag) -> Count when Bag :: bag(Element), Count :: non_neg_integer().

Returns the number of occurrences of Element in Bag.

Examples

> B = xb5_bag:from_list([1, 2, 2, 3]).
> xb5_bag:count(2, B).
2
> xb5_bag:count(4, B).
0

-spec delete(Element, Bag1) -> Bag2 | no_return()
                when Element :: term(), Bag1 :: bag(Element), Bag2 :: bag(Element).

Removes one occurrence of Element from Bag1, returning a new bag Bag2.

Raises a {badkey, Element} error if Element is not present.

Examples

> B = xb5_bag:from_list([1, 2, 2, 3]).
> xb5_bag:to_list(xb5_bag:delete(2, B)).
[1, 2, 3]

-spec delete_all(Element, Bag1) -> Bag2
                    when Element :: term(), Bag1 :: bag(Element), Bag2 :: bag(Element).

Removes all occurrences of Element from Bag1, returning a new bag Bag2.

Returns Bag1 unchanged if Element is not present.

Examples

> B = xb5_bag:from_list([1, 2, 2, 3]).
> xb5_bag:to_list(xb5_bag:delete_all(2, B)).
[1, 3]
> xb5_bag:to_list(xb5_bag:delete_all(42, B)).
[1, 2, 2, 3]

-spec delete_any(Element, Bag1) -> Bag2
                    when Element :: term(), Bag1 :: bag(Element), Bag2 :: bag(Element).

Removes one occurrence of Element from Bag1 if present, otherwise returns Bag1 unchanged.

Examples

> B = xb5_bag:from_list([1, 2, 2, 3]).
> xb5_bag:to_list(xb5_bag:delete_any(2, B)).
[1, 2, 3]
> xb5_bag:to_list(xb5_bag:delete_any(42, B)).
[1, 2, 2, 3]

-spec filter(Pred, Bag1) -> Bag2
                when Pred :: fun((Element) -> boolean()), Bag1 :: bag(Element), Bag2 :: bag(Element).

Filters elements of Bag1 using predicate function Pred, returning a new bag Bag2 containing only the elements for which Pred returns true.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4, 5]).
> xb5_bag:to_list(xb5_bag:filter(fun(X) -> X > 3 end, B)).
[4, 5]

-spec filtermap(Fun, Bag1) -> Bag2
                   when
                       Fun :: fun((Element1) -> boolean() | {true, Element2}),
                       Bag1 :: bag(Element1),
                       Bag2 :: bag(Element1 | Element2).

Filters and maps elements of Bag1 using Fun, returning a new bag Bag2.

For each element, Fun must return either true (keep the element), false (discard it), or {true, NewElement} (replace it with NewElement).

Examples

> B = xb5_bag:from_list([1, 2, 3, 4, 5]).
> xb5_bag:to_list(xb5_bag:filtermap(fun(X) when X rem 2 =:= 0 -> {true, X * 10}; (_) -> false end, B)).
[20, 40]

-spec fold(Function, Acc0, Bag) -> Acc1
              when
                  Function :: fun((Element, AccIn) -> AccOut),
                  Acc0 :: Acc,
                  Acc1 :: Acc,
                  AccIn :: Acc,
                  AccOut :: Acc,
                  Bag :: bag(Element).

Folds Function over every element in Bag, returning the final accumulator value. Elements are visited in Erlang term order.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> xb5_bag:fold(fun(X, Acc) -> X + Acc end, 0, B).
6

-spec from_list(List) -> Bag when List :: [Element], Bag :: bag(Element).

Returns a bag of the elements in List. Unlike xb5_sets:from_list/1, duplicate elements are preserved.

It sorts the List and then delegates to from_ordered_list/1 - see that function for performance characteristics.

Examples

> xb5_bag:to_list(xb5_bag:from_list([3, 1, 2, 1])).
[1, 1, 2, 3]
> xb5_bag:to_list(xb5_bag:from_list([])).
[]

-spec from_ordered_list(OrderedList) -> Bag when OrderedList :: [Element], Bag :: bag(Element).

Returns a bag built from the ordered list OrderedList.

Repeated elements are kept.

The bag is built by recursively splitting the list top-down rather than by sequential insertion, yielding an optimally balanced result without intermediate allocations or element comparisons. This is analogous to gb_sets:from_ordset/1 and gb_trees:from_orddict/1.

Examples

> xb5_bag:to_list(xb5_bag:from_ordered_list([1, 2, 3, 3])).
[1, 2, 3, 3]

-spec from_ordset(Ordset) -> Bag when Ordset :: ordsets:ordset(Element), Bag :: bag(Element).

Returns a bag built from the ordered set Ordset.

Since ordsets contain no duplicates, neither will the resulting bag. Delegates to from_ordered_list/1 — see that function for performance characteristics.

Examples

> xb5_bag:to_list(xb5_bag:from_ordset([1, 2, 3])).
[1, 2, 3]

-spec insert(Element, Bag1) -> Bag2 when Bag1 :: bag(Element), Bag2 :: bag(Element).

Inserts element Element into Bag1, returning a new bag Bag2.

Raises a {key_exists, Element} error if Element is already present.

Examples

> B0 = xb5_bag:new().
> B1 = xb5_bag:insert(1, B0).
> xb5_bag:to_list(B1).
[1]

-spec is_empty(Bag) -> boolean() when Bag :: bag().

Returns true if Bag is empty, otherwise false.

Examples

> xb5_bag:is_empty(xb5_bag:new()).
true
> xb5_bag:is_empty(xb5_bag:from_list([1])).
false

-spec is_member(Element, Bag) -> boolean() when Bag :: bag(Element).

Returns true if Element is a member of Bag, otherwise false.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> xb5_bag:is_member(2, B).
true
> xb5_bag:is_member(4, B).
false

-spec iterator(Bag) -> Iter when Bag :: bag(Element), Iter :: iter(Element).

Returns an iterator that can be used for traversing the elements of Bag; see next/1. Equivalent to iterator(Bag, ordered).

Examples

> B = xb5_bag:from_list([3, 1, 2]).
> I = xb5_bag:iterator(B).
> {1, I2} = xb5_bag:next(I).
> {2, I3} = xb5_bag:next(I2).
> {3, I4} = xb5_bag:next(I3).
> xb5_bag:next(I4).
none

-spec iterator(Bag, Order) -> Iter
                  when Bag :: bag(Element), Iter :: iter(Element), Order :: ordered | reversed.

Returns an iterator that can be used for traversing the elements of Bag in the given Order; see next/1.

Order must be ordered (ascending) or reversed (descending).

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> I = xb5_bag:iterator(B, reversed).
> {3, I2} = xb5_bag:next(I).
> {2, I3} = xb5_bag:next(I2).
> {1, I4} = xb5_bag:next(I3).
> xb5_bag:next(I4).
none

-spec iterator_from(Element, Bag) -> Iter when Bag :: bag(Element), Iter :: iter(Element).

Returns an iterator that can be used for traversing the elements of Bag starting from element Element; see next/1. Equivalent to iterator_from(Element, Bag, ordered).

Examples

> B = xb5_bag:from_list([1, 2, 3, 4, 5]).
> I = xb5_bag:iterator_from(3, B).
> {3, I2} = xb5_bag:next(I).
> {4, I3} = xb5_bag:next(I2).
> {5, I4} = xb5_bag:next(I3).
> xb5_bag:next(I4).
none

-spec iterator_from(Element, Bag, Order) -> Iter
                       when Bag :: bag(Element), Iter :: iter(Element), Order :: ordered | reversed.

Returns an iterator that can be used for traversing the elements of Bag starting from element Element in the given Order; see next/1.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4, 5]).
> I = xb5_bag:iterator_from(3, B, reversed).
> {3, I2} = xb5_bag:next(I).
> {2, I3} = xb5_bag:next(I2).
> {1, I4} = xb5_bag:next(I3).
> xb5_bag:next(I4).
none

-spec iterator_from_nth(Rank, Bag) -> Iter
                           when Rank :: pos_integer(), Bag :: bag(Element), Iter :: iter(Element).

Returns an iterator that can be used for traversing the elements of Bag starting from element at Rank; see next/1.

If Rank is larger than the bag size, the iterator will yield no elements.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4, 5]).
> I = xb5_bag:iterator_from_nth(4, B).
> {4, I2} = xb5_bag:next(I).
> {5, I3} = xb5_bag:next(I2).
> xb5_bag:next(I3).
none

-spec larger(Element1, Bag) -> none | {found, Element2}
                when Element1 :: Element, Element2 :: Element, Bag :: bag(Element).

Returns {found, Element2} where Element2 is the least element strictly greater than Element1 in Bag, or none if no such element exists.

Examples

> B = xb5_bag:from_list([1, 3, 5]).
> xb5_bag:larger(2, B).
{found, 3}
> xb5_bag:larger(5, B).
none

-spec largest(Bag) -> Element when Bag :: bag(Element).

Returns the largest element in Bag.

Raises an empty_bag error if the bag is empty.

Examples

> xb5_bag:largest(xb5_bag:from_list([3, 1, 2])).
3

-spec map(Fun, Bag1) -> Bag2
             when Fun :: fun((Element1) -> Element2), Bag1 :: bag(Element1), Bag2 :: bag(Element2).

Maps Fun over all elements of Bag1, returning a new bag Bag2.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> xb5_bag:to_list(xb5_bag:map(fun(X) -> X * 10 end, B)).
[10, 20, 30]

-spec merge(Bag1, Bag2) -> Bag3 when Bag1 :: bag(Element), Bag2 :: bag(Element), Bag3 :: bag(Element).

Merges two bags into one. All elements from both bags are kept, so counts are combined.

Examples

> B1 = xb5_bag:from_list([1, 2, 3]).
> B2 = xb5_bag:from_list([2, 3, 4]).
> xb5_bag:to_list(xb5_bag:merge(B1, B2)).
[1, 2, 2, 3, 3, 4]

-spec new() -> Bag when Bag :: bag(_).

Returns a new empty bag.

Examples

> xb5_bag:is_empty(xb5_bag:new()).
true
> xb5_bag:size(xb5_bag:new()).
0

-spec next(Iter1) -> {Element, Iter2} | none when Iter1 :: iter(Element), Iter2 :: iter(Element).

Returns {Element, Iter2} where Element is the next element referred to by iterator Iter1 and Iter2 is the updated iterator, or none if no more elements remain.

Examples

> B = xb5_bag:from_list([1, 2]).
> I = xb5_bag:iterator(B).
> {1, I2} = xb5_bag:next(I).
> {2, I3} = xb5_bag:next(I2).
> xb5_bag:next(I3).
none

-spec nth(Rank, Bag) -> Element when Rank :: pos_integer(), Bag :: bag(Element).

Returns the element at 1-based rank Rank in Bag in O(log n) time.

Raises a {badarg, Rank} error if Rank is not a valid position (i.e. less than 1 or greater than the bag size).

Examples

> B = xb5_bag:from_list([10, 20, 30]).
> xb5_bag:nth(1, B).
10
> xb5_bag:nth(3, B).
30

-spec percentile(Percentile, Bag) -> {value, Element | InterpolationResult} | none
                    when
                        Percentile :: xb5_bag_utils:percentile(),
                        Bag :: bag(Element),
                        InterpolationResult :: number().

Calculates a percentile value in O(log n) time, using linear interpolation of the inclusive percentile bracket. Returns {value, Result} or none. Equivalent to percentile(Percentile, Bag, []).

Raises a {bracket_value_not_a_number, #{value => Bound, bracket => Bracket}} error if linear interpolation is required but the bracketing elements are not numbers.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4]).
> xb5_bag:percentile(0, B).
{value, 1}
> xb5_bag:percentile(0.5, B).
{value, 2.5}
> xb5_bag:percentile(1, B).
{value, 4}

-spec percentile(Percentile, Bag, Opts) -> {value, Element | InterpolationResult} | none
                    when
                        Percentile :: xb5_bag_utils:percentile(),
                        Bag :: bag(Element),
                        InterpolationResult :: number(),
                        Opts :: [xb5_bag_utils:percentile_bracket_opt()].

Like percentile/2, but accepts a list of options. Runs in O(log n) time. The only supported option is {method, Method}; see xb5_bag_utils:percentile_bracket_method/0.

Raises a {bracket_value_not_a_number, #{value => Bound, bracket => Bracket}} error if linear interpolation is required but the bracketing elements are not numbers.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4]).
> xb5_bag:percentile(0.5, B, [{method, nearest_rank}]).
{value, 2}

-spec percentile_bracket(Percentile, Bag) -> Bracket
                            when
                                Percentile :: xb5_bag_utils:percentile(),
                                Bag :: bag(Element),
                                Bracket :: xb5_bag_utils:percentile_bracket(Element).

Returns the percentile bracket for Percentile in Bag in O(log n) time, using the inclusive method. Returns {exact, Element} when the percentile falls exactly on an element, {between, Low, High} when it falls between two elements, or none if the bag is empty.

Raises a {badarg, Percentile} error if Percentile is not a number in [0.0, 1.0]. See percentile_bracket/3 for other methods.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4]).
> xb5_bag:percentile_bracket(0, B).
{exact, 1}
> xb5_bag:percentile_bracket(1, B).
{exact, 4}

-spec percentile_bracket(Percentile, Bag, Opts) -> Bracket
                            when
                                Percentile :: xb5_bag_utils:percentile(),
                                Bag :: bag(Element),
                                Opts :: [xb5_bag_utils:percentile_bracket_opt()],
                                Bracket :: xb5_bag_utils:percentile_bracket(Element).

Like percentile_bracket/2, but accepts a list of options. Runs in O(log n) time. The only supported option is {method, Method}; see xb5_bag_utils:percentile_bracket_method/0.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4]).
> xb5_bag:percentile_bracket(0.5, B, [{method, nearest_rank}]).
{exact, 2}

-spec percentile_rank(Element, Bag) -> Rank when Bag :: bag(Element), Rank :: float().

Returns the percentile rank of Element in Bag as a float in [0.0, 1.0], in O(log n) time.

Element does not have to be in the bag.

Raises an empty_bag error if the bag is empty.

Examples

> B = xb5_bag:from_list([1, 2, 3, 4]).
> xb5_bag:percentile_rank(2, B).
0.375

-spec push(Element, Bag1) -> Bag2 when Bag1 :: bag(Element), Bag2 :: bag(Element).

Pushes element Element into Bag1, returning a new bag Bag2. If Element is already present, a duplicate is added.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> xb5_bag:to_list(xb5_bag:push(2, B)).
[1, 2, 2, 3]
> xb5_bag:size(xb5_bag:push(2, B)).
4

-spec rank(Element, Bag) -> {rank, Rank} | none when Bag :: bag(Element), Rank :: pos_integer().

Returns {rank, Rank} where Rank is the 1-based position of Element in Bag, or none if Element is not present. When duplicates exist, the lowest rank is returned. Runs in O(log n) time.

Examples

> B = xb5_bag:from_list([10, 20, 30]).
> xb5_bag:rank(20, B).
{rank, 2}
> xb5_bag:rank(42, B).
none

With duplicates, the lowest rank is returned:

> B = xb5_bag:from_list([f, g, g, h, i]).
> xb5_bag:rank(g, B).
{rank, 2}

-spec rank_larger(Element1, Bag) -> {Rank, Element2} | none
                     when
                         Element1 :: Element,
                         Element2 :: Element,
                         Bag :: bag(Element),
                         Rank :: pos_integer().

Returns {Rank, Element2} where Element2 is the least element strictly greater than Element1 and Rank is its 1-based position, or none if no such element exists. When Element2 has duplicates, the lowest rank (first occurrence) is returned. Runs in O(log n) time.

Examples

> B = xb5_bag:from_list([10, 20, 30]).
> xb5_bag:rank_larger(15, B).
{2, 20}
> xb5_bag:rank_larger(30, B).
none

With duplicates, the lowest rank (first occurrence) is returned:

> B = xb5_bag:from_list([f, g, g, h, i]).
> xb5_bag:rank_larger(f, B).
{2, g}

-spec rank_smaller(Element1, Bag) -> {Rank, Element2} | none
                      when
                          Element1 :: Element,
                          Element2 :: Element,
                          Bag :: bag(Element),
                          Rank :: pos_integer().

Returns {Rank, Element2} where Element2 is the greatest element strictly less than Element1 and Rank is its 1-based position, or none if no such element exists. When Element2 has duplicates, the highest rank (last occurrence) is returned. Runs in O(log n) time.

Examples

> B = xb5_bag:from_list([10, 20, 30]).
> xb5_bag:rank_smaller(25, B).
{2, 20}
> xb5_bag:rank_smaller(10, B).
none

With duplicates, the highest rank (last occurrence) is returned:

> B = xb5_bag:from_list([f, g, g, g, h]).
> xb5_bag:rank_smaller(h, B).
{4, g}

-spec size(Bag) -> non_neg_integer() when Bag :: bag().

Returns the number of elements in Bag, including duplicates.

Examples

> xb5_bag:size(xb5_bag:new()).
0
> xb5_bag:size(xb5_bag:from_list([1, 2, 2, 3])).
4

-spec smaller(Element1, Bag) -> none | {found, Element2}
                 when Element1 :: Element, Element2 :: Element, Bag :: bag(Element).

Returns {found, Element2} where Element2 is the greatest element in Bag that is strictly less than Element1, or none if no such element exists.

Examples

> B = xb5_bag:from_list([1, 3, 5]).
> xb5_bag:smaller(4, B).
{found, 3}
> xb5_bag:smaller(1, B).
none

-spec smallest(Bag) -> Element when Bag :: bag(Element).

Returns the smallest element in Bag.

Raises an empty_bag error if the bag is empty.

Examples

> xb5_bag:smallest(xb5_bag:from_list([3, 1, 2])).
1

-spec structural_stats(Bag) -> Stats when Bag :: bag(), Stats :: xb5_structural_stats:t().

Returns structural statistics about the B-tree backing Bag.

This is primarily intended for debugging and testing. The result is a proplist with keys such as height, total_keys, node_counts, node_percentages, and others.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> Stats = xb5_bag:structural_stats(B).
> {height, 1} = lists:keyfind(height, 1, Stats).
> {total_keys, 3} = lists:keyfind(total_keys, 1, Stats).

-spec take_largest(Bag1) -> {Element, Bag2} when Bag1 :: bag(Element), Bag2 :: bag(Element).

Returns {Element, Bag2}, where Element is the largest element in Bag1 and Bag2 is the remaining bag.

Raises an empty_bag error if the bag is empty.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> {3, B2} = xb5_bag:take_largest(B).
> xb5_bag:to_list(B2).
[1, 2]

-spec take_smallest(Bag1) -> {Element, Bag2} when Bag1 :: bag(Element), Bag2 :: bag(Element).

Returns {Element, Bag2}, where Element is the smallest element in Bag1 and Bag2 is the remaining bag.

Raises an empty_bag error if the bag is empty.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> {1, B2} = xb5_bag:take_smallest(B).
> xb5_bag:to_list(B2).
[2, 3]

-spec to_list(Bag) -> List when Bag :: bag(Element), List :: [Element].

Returns the elements of Bag as an ordered list, including duplicates.

Examples

> xb5_bag:to_list(xb5_bag:from_list([3, 1, 2, 1])).
[1, 1, 2, 3]
> xb5_bag:to_list(xb5_bag:new()).
[]

-spec unwrap(Term) -> {ok, Unwrapped} | {error, Reason}
                when
                    Term :: bag(Element) | term(), Unwrapped :: unwrapped_bag(Element), Reason :: term().

Unwraps an opaque bag into a plain map representation suitable for cross-language interop (for example, converting to an Elixir struct that uses the same underlying node module). Returns {ok, Unwrapped} on success or {error, Reason} if Term is not a valid bag.

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> {ok, Unwrapped} = xb5_bag:unwrap(B).
> maps:get(size, Unwrapped).
3
> {error, _} = xb5_bag:unwrap(not_a_bag).

-spec wrap(unwrapped_bag(Element)) -> bag(Element).

Wraps a plain map representation back into an opaque bag.

This is the inverse of unwrap/1 and is intended for cross-language interop (for example, converting from an Elixir struct that shares the same underlying node module).

Examples

> B = xb5_bag:from_list([1, 2, 3]).
> {ok, U} = xb5_bag:unwrap(B).
> B2 = xb5_bag:wrap(U).
> xb5_bag:to_list(B2).
[1, 2, 3]