Unordered collections

In unordered.diesel:

An unordered_collection is a group of elements in no particular order. It supports collection operations such as length, is_empty, do, pick_any, includes, find, and copy.

extend module Stdlib;

module UnorderedCollection;
abstract class unordered_collection[T]
                isa collection[T], unordered_collection[`S >= T];
abstract class unordered_collection_exactly[T]
                isa collection_exactly[T], unordered_collection[T];

If the elements of the collection are comparable, then so is the collection. Two such collections are equal (=) if they have the same elements (with the same number of occurrences), independent of order. (By contrast, two ordered collections are equal only if they contain the same elements in the same order.) If the elements of the collection are hashable, then so is the collection.

  extend class unordered_collection_exactly[`T <= comparable[T]]
                isa comparable[unordered_collection_exactly[T]];
  extend class unordered_collection_exactly[`T <= hashable[T]]
                isa hashable[unordered_collection_exactly[T]];

Unordered collections support several functional set-operations which, given argument collections, return a new collection.

union: form the collection whose element counts are the maximum of the element counts of the argument collections

fun union(m1:unordered_collection_exactly[`T <= comparable[T]],
                 m2:unordered_collection_exactly[T]
                 ):m_unordered_collection[T];

intersection: form the collection whose element counts are the minumum of the element counts of the argument collections

fun intersection(m1:unordered_collection_exactly[`T <= comparable[T]],
                        m2:unordered_collection_exactly[T]
                        ):m_unordered_collection[T];

difference: form the collection whose element counts are the element counts of the first collection minus the element counts of the second collection (with a minimum count of 0)

fun difference(m1:unordered_collection_exactly[`T <= comparable[T]],
                      m2:unordered_collection_exactly[T]
                      ):m_unordered_collection[T];

is_disjoint: are there no elements in common?

fun is_disjoint(m1:unordered_collection_exactly[`T <= comparable[T]],
                       m2:unordered_collection_exactly[T]):bool;

overlaps: are there any elements in common?

fun overlaps(m1:unordered_collection_exactly[`T <= comparable[T]],
                    m2:unordered_collection_exactly[T]):bool;

is_subset: are all the elements of m1 also in m2?

fun is_subset(m1:unordered_collection_exactly[`T <= comparable[T]],
                     m2:unordered_collection_exactly[T]):bool;

is_strict_subset: is a strictly smaller subset?

fun is_strict_subset(m1:unordered_collection_exactly[`T <= comparable[T]],
                            m2:unordered_collection_exactly[T]):bool;

Two refinements of unordered_collection indicate whether the collection is known to be immutable (i_unordered_collection) or mutable (m_unordered_collection).

An immutable unordered collection of some type T is a subtype of any immutable unordered collection of a supertype of T. In contrast, a mutable unordered collection of a type T has no subtyping relation to a mutable unordered collection of a different type. Both kinds are subtypes or a generic unordered collection of T or transitively any supertype of T.

abstract class i_unordered_collection[T]
        isa unordered_collection[T], i_unordered_collection[`S >= T];
abstract class i_unordered_collection_exactly[T]
        isa unordered_collection_exactly[T], i_unordered_collection[T];

Mutable collections provide remove, add, and other operations of extensible_collection. Method copy_empty always returns an empty mutable collection with a type like that of its argument.

abstract class m_unordered_collection[T]
        isa unordered_collection_exactly[T], extensible_collection[T];

end module UnorderedCollection;