"SortedMultiset" (Data Structure)

"SortedMultiset"

represents a multiset where the members are general expressions and are kept in a sorted order.

Details

A sorted multiset is useful for efficient insertion and removal as well as membership testing where the same element can appear more than once:

	CreateDataStructure["SortedMultiset"]	create a new empty "SortedMultiset" that uses canonical ordering
	CreateDataStructure["SortedMultiset",elems]	create a new "SortedMultiset" with elements elems
	CreateDataStructure["SortedMultiset",elems,p]	create a new "SortedMultiset" with specified elements and ordering function p
	Typed[x,"SortedMultiset"]	give x the type "SortedMultiset"

For a data structure of type "SortedMultiset", the following operations can be used:

ds["Cases",elem]	returns members of the multiset that match elem	time: O(log n)
ds["Count", elem]	returns the number of elements that match elem	time: O(log n)
ds["Delete",x]	delete one instance of x from ds; return True if x was actually an element	time: O(log n)
ds["DeleteAll"]	delete all the elements from ds	time: O(n)
ds["DeleteCases",x]	delete all instances of x from ds; return True if x was actually an element	time: O(log n)
ds["Elements"]	return a list of the elements of ds	time: O(n)
ds["EmptyQ"]	True, if ds has no members	time: O(1)
ds["Insert",x]	add x to the multiset	time: O(log n)
ds["Length"]	returns the number of members stored in ds	time: O(1)
ds["MemberQ",x]	True, if x is a member of ds	time: O(log n)
ds["Visualization"]	return a visualization of ds	time: O(n)

	ds_i===ds_j	True, if ds_i equals ds_j
	FullForm[ds]	full form of ds
	Information[ds]	information about ds
	InputForm[ds]	input form of ds
	Normal[ds]	convert ds to a normal expression

open allclose all

A new "HashSet" can be created with CreateDataStructure:

Insert into the set:

There is one element in the set:

Test if an expression is stored:

If an expression is not stored, False is returned:

Remove an element from the set. If something was actually removed, return True:

Now there are two elements in the set:

Return an expression version of ds:

Insert a number of elements:

A visualization of the data structure can be generated:

This shows how the data is sorted and contains multiple elements.

An ordering function can be given for a sorted multiset:

Insert two elements:

These elements are all equal according to the ordering function:

Remove an element:

A new "SortedMultiset" can be created with CreateDataStructure:

Information about the data structure ds:

If an ordering function is given, this is used to specify set membership:

This returns True because the ordering function only looks at the first element:

Top