关于“前排非空”（non-empty front） #81
Description
除了早期从 WLS 抄来的那些改进之外，rlifsrc 引入的改进中最简单又有效的是这两个：前排非空（non-empty front），和对角宽度。其中前排非空的选项已在 4.0 版删除：这个功能还在，只是改成根据对称性、位移、搜索顺序等条件自动开启。
不过和对角宽度比起来，前排非空不是这么直观直观。我也一直害怕有 bug，还是要写点文档总结一下，顺便也为实现 #51 中提到的更多对称性作准备。
前排非空
前排非空的想法很简单：比如说，假如我们要搜 17x5 大小向上飞的 c/3 飞船，搜索顺序是从左到右一列一列地搜，找到了这么一个玩意儿：
注意它在一个周期中的三代，最左边一列都是空的。如果我们把它 ⬅️ 向左移动一列，结果还是满足所有的条件：
于是，我们可以干脆增加一个第一列非空的条件，这样可以有效地缩减搜索空间。
这种情况下我们把第一列叫做前排（front）。如果搜索顺序是一行一行地搜，则把第一行叫做前排；如果搜索顺序是对角方向，则把第一行和第一列都算作前排。
不过，我们还需要定义什么是空——由于 B0 规则的存在，我们不能简单地把死细胞定义为空。这里我们采取的定义是：对于每一代，如果一个细胞的状态和搜索范围之外的细胞一致，则称其为空。也就是说：
- 对于无 B0 的规则，“空”的定义很简单：死细胞即为空。
- 对于有 B0 没有 S8 的 Life-like （含 non-totalistic）的规则，第奇数代死细胞为空，第偶数代活细胞为空。这里把每个周期的最前面一代称为第一代，而非第零代。
- 对于有 B0 没有 S8 的 Generations 规则，若共有 n 种状态，则对于第 i 代，i 模 n 余 1 时死细胞为空，余 2 时活细胞为空，余 3 时刚开始死亡的第一代为空，依此类推。上一条可看作这一条的特例。
- rlifesrc 不支持既有 B0 又有 S8 的规则，此类规则需手动转化为无 B0 的规则再搜。
当我们说一个细胞集合（比如说前排）为空时，指的是集合中每一个细胞都为空。同样到了，说这个集合非空指的是至少有一个细胞非空。
搜索的时候，我们可以用一个变量来记录前排中未知或已知非空的细胞的数量；每次搜到一个在前排的细胞，都根据其状态的变换来更新这个变量；如果变量变成了0，则说明当前的 partial result 不满足前排非空的条件，没必要在它上面浪费时间，可以直接回头。
然后问题来了：什么时候可以要求前排非空？
或者换句话说，怎样的搜索条件有平移不变性，即任何满足此条件的图样在向指定方向平移之后还满足同样的条件？
条件的平移不变性
我们按网页版的 Setting，从上到下一条一条分析：
- 规则：这个当然无关。
- 宽度：
- ⬆️ 向上平移一格不影响宽度。
- ⬅️ 向左平移一格会改变图样的左边界，但平移的前提是最左一列为空，因此此条件也不影响结果。
↖️ 向左上（对角方向）平移时的前提是第一行第一列皆空，因此也没有影响。
- 高度：与宽度同理。
- 周期：也无关。
- dx：只是平移的话没有问题。
- dy：也没问题。
- 对角宽度：
- ⬆️ 向上平移一格时可能会把图样移出对角宽度的范围。这是第一个不满足平移不变性的条件。
- ⬅️ 同上。
↖️ 向左上平移的话不会有影响。- 因此，在设了对角宽度的时候，除非搜索方向是对角方向，否则都不能要求前排非空。
- 变换：
- Id：恒等变换，完全不变，完全无关。
- 旋转：平移会导致旋转中心移动，因此不满足平移不变性。
- 翻转：要翻转轴和平移的方向平行才行，其它情况下不满足平移不变性。
- 对称：
- C1：没问题。
- C2/C4：和前面旋转变换的情况一样，不满足平移不变性。
- D2：要对称轴和平移的方向平行才行，其它情况下不满足平移不变性。
- D4/D8：不可能两条对称轴都和平移的方向平行，因此不满足平移不变性。
- 最大活细胞数：当然无关。
- 搜索顺序：这不是图样要满足的条件的一部分，但决定了前排的定义。
- 未知细胞的状态选取：这也不是图样要满足的条件的一部分。
- 已知的细胞：已知细胞的坐标是固定的，不满足平移不变性。
后面几个选项也都无关，不一一讨论了。
也就是说，我们需要考虑的只有对角宽度、变换、对称、已知的细胞这几个选项。
半个前排
但有时我们不需要考虑整个前排：比如说，假如我们要搜 45x10 大小向左飞的 c/4 飞船，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿：
注意它一个周期的四个回合中，第一列的上半部分都是空的。如果我们把它上下翻转一下，结果还是满足所有的条件：
因此，我们可以要求一个第一列的上半部分非空，进一步缩减搜索空间。
（写到这里忽然发现这个条件还可以进一步加强：把第一列所有回合的细胞状态写成一个二进制数，然后要求这个二进制数不能小于把它所有数位左右翻转的结果；或者把第一列的上半部分和下半部分写到两个二进制数中，然后比较这两个数就行了。不过 Rust 中整数大小是有限的，用 64 位的整数表示的话就不支持前排超过 64 个细胞的情形；Generations 的规则要把二进制改成 n 进制，能支持的前排细胞数更少，实现上也更复杂一些。）
类似地，如果搜索顺序是一行一行地搜，则只考虑第一行的左半边；如果搜索顺序是对角方向，只考虑第一列。
为了能加上这个条件，我们要要求搜索条件在翻转变换下不变。
如果以图样中心处为原点的话，这里涉及到的三种翻转如下：
- 左右翻转：
(x,y) => (-x,y) - 上下翻转：
(x,y) => (x,-y) - 以对角线为轴翻转：
(x,y) => (y,x)
（等等，写到这里我发现我的实现有个严重的 Bug：非各向同性的规则是不能随便翻转的！这有点难办……等改好这个 Bug 再继续写吧。）
（以上 Bug 已修复……希望不要引入新 Bug……）
和之前一样，所有设置从上到下一条一条分析：
- 规则：如果是各向同性的规则就不要紧，但各向异性的规则就要讨论规则的对称性，不然会出前面说的这个 Bug……
- 宽度、高度：
- ⬆️⬅️ 左右翻转和上下翻转都不影响宽度、高度。
↖️ 能以对角线为轴翻转的前提是宽度等于高度。
- dx、dy
- ⬆️ 左右翻转会使 dx 变成 -dx，因此 dx 必须为 0；dy 不影响。
- ⬅️ 上下翻转会使 dy 变成 -dy，因此 dy 必须为 0；dx 不影响。
↖️ 以对角线为轴翻转会让 dx 和 dy 互换，因此 dx 必须等于 dy。
- 对角宽度：
- ⬆️⬅️ 只有无对角宽度时才能左右翻转和上下翻转。
↖️ 以对角线为轴翻转的话不会有影响。
- 变换：此变换必须和相应的翻转可交换。
- Id：恒等变换，完全不变，完全无关。
- 旋转 90°/270°：和所有翻转都不可交换，也就是说先旋转后翻转和先翻转后旋转结果不同。
- 旋转 180°：这个和所有翻转都交换。
- 翻转：任一个翻转都和自己可交换。此外左右翻转和上下翻转可交换，以对角线为轴和以反对角线为轴的两个翻转也可交换。别的都不行。
- 对称：这次需要此对称性要求不变的所有变换都和该翻转可交换
- C1：没问题。
- C2：和前面旋转 180° 的情形一样，都可以。
- C4：和前面旋转 90° 的情况一样，都不行。
- D2：需要 D2 的对称轴和翻转轴平行或垂直才行。
- D4：需要 D4 的对称轴和翻转轴平行或垂直才行。两个对称轴，一个平行一个垂直。
- D8：不行。
- 最大活细胞数：当然无关。
- 搜索顺序：这不是图样要满足的条件的一部分，但决定了沿哪条轴翻转。
- 未知细胞的状态选取：这也不是图样要满足的条件的一部分。
- 已知的细胞：已知细胞的坐标是固定的，不满足翻转不变性，除非它就在翻转轴上。
看起来变换、对称和已知细胞的条件比前排非空要宽松。不过我们是在要求前排非空的前提下才能考虑半个前排，所以实际新增的条件只有规则（差点又忘了）、宽度、高度、dx、dy 这些。
前排的第一代
前面说的前排指的是前排的每一代。要求前排非空等价于要求至少有一代的前排非空。于是，对于振荡子（也就是 dx、dy 为 0 的情形），只要规则没有 B0，我们可以干脆前排非空的那一代定为第一代，于是可以要求前排的第一代非空，进一步缩减搜索空间。
但对飞船来说，问题没这么简单。事实上，对于周期为 p 的振荡子，第 p+1 代和第一代是一样的，因此第二代到第 p+1 代也满足原本的条件。但对飞船来说，第 p+1 代相比第一代还会有一个平移，可能会平移出原本的高度和宽度所规定的范围。
不过，搜索飞船的一种常见情况是：每个周期仅平移一格，而且平移的方向正好是向着前排。
比如说，假如我们要搜 21x13 大小向左飞的 c/4 飞船，对称性是 D2-，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿（这次把每一代都画出来了，从左到右）：
这飞船前排的第一代是空的。于是，它的第五代只是把第一代向前平移一格，并不会移出规定的范围。也就是说，它的第二到第五代也满足原本的条件：
因此，这种情况下也可以要求前排的第一代非空。
也就是说，如果要要求前排的第一代非空，在前排非空的条件的基础上，我们还需要：
- ⬆️ 一行一行搜时，要 dx = 0, 0 <= dy <= 1，而且规则不能有 B0。
- ⬅️ 一列一列搜时，要 dy = 0, 0 <= dx <= 1，而且规则不能有 B0。
↖️ 对角方向搜时，要 dx = dy, 0 <= dx <= 1，而且规则不能有 B0。
（写到这里忽然发现，没必要完全禁掉 B0 的规则，其实可以改成要求前排的前两代非空；对于 Generations 的规则，若有 n 种状态，则可以改为前排的前 n 代非空。这里需要的改动很小，已改。）
没那么前的前排
上一节的讨论只适合飞船每个周期向前平移一格的情形。如果平移不止一格呢？
此时，我们不能再要求前排的第一代非空。事实上，此时前排的第一代必须是空的，因为这些细胞的前一代的整个邻域都已经在搜索范围之外。
不过，我们可以把“前排”往后挪一挪。
比如说，假如我们要搜 12x15 大小向左飞的 2c/5 飞船，对称性是 D2-，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿（这次把每一代都画出来了，从左到右）：
它第一代前两列都是空的。第六代只是把第一代向前移动两格，不会移出规定的范围。于是，和之前一样，我们可以考虑它的第二到第六代：
于是，我们可以干脆把前排的定义从第一列移到第二列，继续要求新的“前排”的第一代非空。
一般地，如果飞船每个周期向前平移 d 格（平移的方向必须向着前排），我们就可以把前排的定义修改为第 d-1 行/列/行加列。
但我们还要说明新的要求比原本要求的前排（所有代）非空要强，不然直接用原本的要求不就行了吗？
这也不难。一个细胞非空的必要条件是它前一代的邻域中至少有一个细胞非空。若飞船周期为 p，新的前排是第 d-1 列，那么新前排的前一代对应于第 p 代往前刚离开搜索范围的那一列，其邻域的三列只有一列在搜索范围之内，也就是第 p 代的第一列。因此，只要要求新的前排第一代非空，旧的前排就一定也非空。
于是，我们可以把上一节的条件改进为：
- ⬆️ 一行一行搜时，要 dx = 0, dy >= 0，而且规则不能有 B0，此时。
- ⬅️ 一列一列搜时，要 dy = 0, dx >= 0，而且规则不能有 B0。
↖️ 对角方向搜时，要 dx = dy, dx >= 0，而且规则不能有 B0。
此时“前排”的定义为：
- ⬆️ 若 dy = 0，则前排还是第一行，否则改为第 dy-1 行。
- ⬅️ 若 dx = 0，则前排还是第一列，否则改为第 dx-1 列。
↖️ 若 dx = 0，则前排还是第一行加第一列，否则改为第 dy-1 行加第 dx-1 列。
目前 rlifesrc 采用的前排非空的条件就是这么多。
自定义对称性
前面说了这么多，一方面是为了总结和查 bug，另一方面是为实现 #51 中提到的自定义对称性做准备。
其实说“自定义对称性”有点不准确，因为这也包含了一些不属于对称性的条件。
我们想要支持哪些条件呢？先试着列举一下。
- 给定一个细胞，指定其状态。这个其实已经通过“已知的细胞”实现了。
- 给定一个细胞，要求其状态和另一个指定的细胞一致/不一致。
- 给定一个区域，要求区域内的所有细胞都处于某个指定的状态。
- 给定一个区域，要求其状态和该区域通过某种变换得到的另一个区域一致/不一致。
区域怎么定义，允许哪些变换，都是需要讨论的。
自定义对称性最好还能写成一种方便读取的格式，比如说 JSON。
（未完待续）