Valid-by-construction table UI component data structure with merged cells

Question

TL;DR: I’m looking for a data structure for a set of non-overlapping axis-aligned integer rectangles.

I’m making a terminal user interface^† that involves rendering tables. They’re akin to HTML tables or spreadsheet cells, in that adjacent cells may be merged in rows and/or columns. I’ve figured out how I can solve for the cell dimensions based on their contents and render the result as UI components, once I’ve accumulated all the constraints. However, the input to the constraint generator is currently a data structure based on HTML tables: a list of rows of cells, where each cell has a “row span” and “column span” attribute.

data Table1 a = Table1 { table1Rows :: [Row1 a] }

data Row1 a = Row1 { row1Cells :: [Cell1 a] }

data Cell1 a = Cell1
  { cell1Rowspan :: !Rowspan
  , cell1Colspan :: !Colspan
  , cell1Contents :: !a
  }

newtype Rowspan = Rowspan Int

newtype Colspan = Colspan Int

This is not only somewhat unwieldy, but also allows various kinds of invalid table that I can’t render (or that simply aren’t relevant for my purposes). It would be useful for correctness guarantees and automated testing if there were a relatively straightforward way to enforce the structure with the type system. Table1 has a few issues, for instance:

The total number of cell positions in each row or column may differ, so the table may be jagged
Computing cell placements requires a linear traversal of the whole table, because a merged cell from a previous row may occupy the position where a cell in the current row would have been otherwise
I cannot simply traverse all cells in a single row or column to accumulate height/width constraints

So my next thought was to use a 2D array of cells, where each position either has some content or is marked as “merged” with the cell above or to the left of it, or both:

data Table2 a = Table2
  { table2Cells :: Array (RowIndex, ColumnIndex) (Cell2 a) }

data Cell2 a
  = Cell2Content !a
  | Cell2MergeUp
  | Cell2MergeLeft
  | Cell2MergeUpLeft

newtype RowIndex = RowIndex Int

newtype ColumnIndex = ColumnIndex Int

Unfortunately, this still allows some invalid tables because it doesn’t require merged cells to be square:

render $ Table2 $ array ((0, 0), (1, 1))
  [ ((0, 0), Cell2Content "...")
  , ((0, 1), Cell2MergeLeft)
  , ((1, 0), Cell2MergeUp)
  , ((1, 1), Cell2Content "...")
  ]

⇓

┌───────────┐
│ ...       │
│     ┌─────┤
│     │ ... │
└─────┴─────┘

Next, I thought of a mapping from cell ranges to cells, but I realised I would still have to index by position and annotate with rowspan and colspan.

data Table3 = Table3
  { table3Cells :: Map (RowIndex, ColumnIndex) (Cell1 a) }
  deriving stock (Show)

This allows the table to be sparse, but that’s not strictly a problem, as all my tables will be fully packed/rectangular, and I could just render nonexistent cells as empty anyway. It also constrains merged cells to be rectangular, which is desirable. Unfortunately, it allows cells to overlap incorrectly, for example, a 2×2 cell at (0, 0) would collide with a 2×2 cell at (1, 1). And I can’t just put the width and height into the map key.

I think a set or associative structure of some kind makes sense, but instead of a single “primary key” (position, in Table3 above), I have a “compound” key due to the constraint that no two cells may overlap the same position. In other words, if a cell overlaps the same row or column as another cell, it must not overlap in any column or row therein, respectively. (Obviously, many cells will have the same row or column: every cell in the same row has the same row index!)

So, is there a simple way I can enforce this? If I can’t do it with e.g. Array/Map/IntMap, are there libraries available that will let me store a set of non-overlapping “occupied ranges” in multiple dimensions like this? I’m fine with using “advanced” type system features as long as I can enforce the constraints on runtime-specified data. I’m fine with generating tables from scratch every time the input changes, as long as it’s efficient, but it’s a plus if it’s easy to modify tables (namely, inserting new rows/cells) while continuing to enforce constraints.

If there isn’t a suitable data structure, I’ll probably just make one that enforces the constraints at runtime using smart constructors, but that’s no fun. :)

I’ve discovered that an easy runtime option is an IntMap from cell IDs to cell dimensions (or separate IntMaps for row dimensions, column dimensions, and cell contents); then safe insertion can be implemented as unsafe insertion directly into the map(s), followed by checking for overlaps, which is the intersection (by set union) of the maps of conflicting rows and columns, given by the (non-empty) sets of cells in each row (resp. column) overlapping distinct cells in each column (resp. row).

^† Using Brick, but this should not be relevant.

Valid-by-construction table UI component data structure with merged cells

0 Answers