# 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*