Owned PCG Operations

Collapse

The operation $collapse(p,\mathcal{E},\mathcal{C})$ modifies place expansions $\mathcal{E}$ and set of place capabilities $\mathcal{C}$ such that $p$ becomes a leaf in the forest corresponding to $\mathcal{E}$. Stated more formally it modifies $\mathcal{E}$ to ensure that $\mathcal{E}$ contains an expansion $\overline{p}$ containing $p$, and $p$ is not the base of any expansion in $\mathcal{E}$. Capabilities in $\mathcal{C}$ are updated to account for the removal of expansions from $\mathcal{E}$.

collapse returns the set of Owned PCG Actions corresponding to the removed expansions.

The algorithm is implemented as follows:

1. Let ${\mathcal{E}}^{\prime }$ be the subset of place expansions in $\mathcal{E}$ such that for each $\overline{p^{\prime }}$ in ${\mathcal{E}}^{\prime }$, the base place $p^{\prime }$ is a prefix of $p$.
2. Let ${\mathcal{E}}^{\prime \prime }$ be an ordered list of the expansions in ${\mathcal{E}}^{\prime }$ sorted in order of descending length of the projections of their base place
3. Let $R$ be the list of operations to return
4. For each $\overline{p^{\prime }}$ in ${\mathcal{E}}^{\prime \prime }$
   1. Let $\overline{c^{\prime }}$ be the capabilities of $p^{\prime }$ in $\mathcal{C}$
   2. Let $c$ be the minimum common capabiility of $\overline{c^{\prime }}$.
   3. Let $p^{\prime }$ be the base of $\overline{p^{\prime }}$
   4. Remove capabilities to the places in $\overline{p^{\prime }}$ from $\mathcal{C}$
   5. Assign capability $c$ to $p^{\prime }$ in $\mathcal{C}$
   6. Remove $\overline{p^{\prime }}$ from $\mathcal{E}$
   7. Add $\text{collapse}(p^{\prime },\overline{p^{\prime }},c)$ to $R$
5. return $R$