Ordered Partition Stacks

This section introduces an ordered partition stack. This is used to efficiently represent an ordered partition and the changes which occur to it over time. Before reading this you should read about ordered partitions.

Interface

The exact interface we choose for an ordered partition can vary, but the basic functionality always supported is:

PS_Points(p) # The points p is defined over
PS_Cells(p) # The number of cells in the partition p
PS_Cell(ps, i) # The contents of cell i of partition p, as an unordered list

PS_Cell(ps,i) is not required to return values in any particular ordering – we will see later why this list is unordered.

There are some other functions which are often provided by ordered partitions:

PS_CellOfPoint(p, x) # The cell which contains x
PS_FixedPoints(p) # A list of the points which are in a cell of size one
PS_CellLen(p, i) # The length of cell p

A Partition Stack adds the ability to modify an ordered partition. This modification is extremely restricted, all we are allowed to do is:

Take a subset S of the values in PS_Cell(ps,i)
Move the values in S to a new cell at the end of the partition (which will be cell PS_Cells(p)+1)

There are a few different ways to provide this function – a very low-level interface, and a high-level interface which provides (most) of the functionality that is required in practice. We will only provide the high-level interface here:

PS_SplitCellByFunction(ps, i, f)

This function requires a bit of explanation. f should be a function which accepts integers. The following operation is then performed:

Apply f to each element of PS_Cell(ps,i)
Partition PS_Cell(ps,i) into equivalence classes which return the

The Partition Stack also adds a time-travel function. This an set the partition stack back to an earlier state:

PS_Revert(ps, i) - Set the partition stack back to having i cells. i must be less than or equal to PS_Cells(ps).

Note that partition stacks can only be reverted – there is no method to go forwards again.

TODO