具有合并单元格的按构造表 UI 组件数据结构

Question

TL;DR：我正在寻找一组非重叠轴对齐整数矩形的数据结构。

我正在制作一个涉及渲染表的终端用户界面^†。它们类似于 HTML 表格或电子表格单元格，因为相邻的单元格可以合并为行和/或列。一旦我累积了所有约束，我已经想出了如何根据单元格的内容解决单元格尺寸并将结果呈现为 UI 组件。然而，约束生成器的输入目前是基于 HTML 表格的数据结构：一个单元格行列表，其中每个单元格都有一个“行跨度”和“列跨度”属性。

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

这不仅有点笨拙，而且还允许我无法呈现的各种无效表（或者根本与我的目的无关）。如果有一种相对简单的方法来使用类型系统强制执行结构，那么它对于正确性保证和自动化测试将非常有用。Table1有几个问题，例如：

• 每行或每列的单元格位置总数可能不同，因此表格可能呈锯齿状

• 计算单元的展示位置需要整个表的直线穿越，因为从前一行合并单元格可能占据其中当前行中的单元格的位置本来否则

• 我不能简单地遍历单行或单列中的所有单元格来累积高度/宽度限制

所以我的下一个想法是使用一个 2D 单元格数组，其中每个位置要么有一些内容，要么被标记为与其上方或左侧的单元格“合并”，或两者兼而有之：

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

不幸的是，这仍然允许一些无效的表格，因为它不需要合并的单元格是方形的：

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

?

?????????????
? ...       ?
?     ???????
?     ? ... ?
?????????????

接下来，我想到了从单元格范围到单元格的映射，但我意识到我仍然必须按位置索引并使用 rowspan 和 colspan 进行注释。

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

这允许表格变得稀疏，但这并不是严格意义上的问题，因为我的所有表格都将完全填充/矩形，并且无论如何我都可以将不存在的单元格呈现为空。它还将合并的单元格限制为矩形，这是可取的。不幸的是，它允许单元格错误地重叠，例如，(0, 0) 处的 2×2 单元格会与 (1, 1) 处的 2×2 单元格发生碰撞。而且我不能只将宽度和高度放入地图键中。

我认为某种集合或关联结构是有道理的，但Table3由于没有两个单元格可能重叠相同位置的限制，我有一个“复合”键，而不是单个“主键”（位置，在上面）。换句话说，如果一个单元格与另一个单元格在同一行或列上重叠，则它不得分别在其中的任何列或行中重叠。（显然，许多单元格将具有相同的行或列：同一行中的每个单元格具有相同的行索引！）

那么，有没有一种简单的方法可以强制执行此操作？如果我不能如做Array/ Map/ IntMap，还有库中可用，这将让我保存了一组非重叠的多个维度这样的“占领范围”？只要我可以对运行时指定的数据强制执行约束，我就可以使用“高级”类型系统功能。每次输入更改时我都可以从头开始生成表，只要它是有效的，但是如果在继续强制执行约束的同时很容易修改表（即插入新行/单元格），那就更好了。

如果没有合适的数据结构，我可能只会创建一个使用智能构造函数在运行时强制执行约束的数据结构，但这并不有趣。:)

我发现一个简单的运行时选项是IntMap从单元格 ID 到单元格维度（或单独IntMap的行维度、列维度和单元格内容）；然后可以将安全插入实现为直接插入映射中的不安全插入，然后检查重叠，这是由（非空）集合给出的冲突行和列的映射的交集（通过集合并集）每行（相应列）中的单元格与每列（相应行）中的不同单元格重叠。

^†使用Brick，但这不应该是相关的。