13.4.45  int_binary_set

The standard library int_binary_set package implements sets of Ints. This is a pure (side-effect free) datastructure.

The implementation is based on Binary search trees of Bounded Balance, similar to NievergeltReingold, SIAM J. Computing 2 (1), March 1973. The main advantage of these trees is that they keep the size of the tree in the node, giving a constant time size operation.

The bounded balance criterion is simpler than NR’s alpha. Simply, one subtree must not have more than ‘weight’ times as many elements as the opposite subtree. Rebalancing is guaranteed to reinstate the criterion for weight>2.23, but the occasional incorrect behaviour for weight=2 is not detrimental to performance.

There are two implementations of union. The default, hedge_union, is much more complex and usually 20am not sure that the performance increase warrants the complexity (and time it took to write), but I am leaving it in for the competition. It is derived from the original union by replacing the split_lt (gt) operations with a lazy version. The ‘obvious’ version is called old_union.

Most time is spent in rebalance, the rebalancing constructor.

The int_binary_set package implements the Set API.

The int_binary_set package source code is in src/lib/src/int-binary-set.pkg.

See also: int_red_black_set.

See also: int_list_set.

See also: int_binary_map.

The above information is manually maintained and may contain errors.


Comments and suggestions to: