mutations.myr

   1 use std
   2
   3 use "types"
   4 use "kc"
   5 use "roots"
   6 use "util"
   7
   8 pkg =
   9         /*
  10            Return things like [ "v1;1", "v2;9", ... ]. No spacing is
  11            provided, so these are horrible to look at. No vertex
  12            renaming is implemented.
  13          */
  14         const get_murot : (t : KC_type -> std.result(byte[:][:], byte[:]))
  15         const get_mutwistingrot : (t : KC_type -> std.result(byte[:][:], byte[:]))
  16         const get_muflip : (t : KC_type -> std.result(byte[:][:], byte[:]))
  17         const get_mutwistingflip : (t : KC_type -> std.result(byte[:][:], byte[:]))
  18 ;;
  19
  20 var murot_stored : std.htab(KC_type, std.result(byte[:][:], byte[:]))#
  21 var mutwistingrot_stored : std.htab(KC_type, std.result(byte[:][:], byte[:]))#
  22 var muflip_stored : std.htab(KC_type, std.result(byte[:][:], byte[:]))#
  23 var mutwistingflip_stored : std.htab(KC_type, std.result(byte[:][:], byte[:]))#
  24
  25 const __init__ = {
  26         murot_stored = std.mkht()
  27         mutwistingrot_stored = std.mkht()
  28         muflip_stored = std.mkht()
  29         mutwistingflip_stored = std.mkht()
  30 }
  31
  32 const __finit__ = {
  33         for (key, val) : std.byhtkeyvals(murot_stored)
  34                 match val
  35                 | `std.Ok mu:
  36                         for var k = 0; k < mu.len; ++k
  37                                 std.slfree(mu[k])
  38                         ;;
  39                         std.slfree(mu)
  40                 | `std.Err e: std.slfree(e)
  41                 ;;
  42         ;;
  43         std.htfree(murot_stored)
  44
  45         for (key, val) : std.byhtkeyvals(mutwistingrot_stored)
  46                 match val
  47                 | `std.Ok mu:
  48                         for var k = 0; k < mu.len; ++k
  49                                 std.slfree(mu[k])
  50                         ;;
  51                         std.slfree(mu)
  52                 | `std.Err e: std.slfree(e)
  53                 ;;
  54         ;;
  55         std.htfree(mutwistingrot_stored)
  56
  57         for (key, val) : std.byhtkeyvals(muflip_stored)
  58                 match val
  59                 | `std.Ok mu:
  60                         for var k = 0; k < mu.len; ++k
  61                                 std.slfree(mu[k])
  62                         ;;
  63                         std.slfree(mu)
  64                 | `std.Err e: std.slfree(e)
  65                 ;;
  66         ;;
  67         std.htfree(muflip_stored)
  68
  69         for (key, val) : std.byhtkeyvals(mutwistingflip_stored)
  70                 match val
  71                 | `std.Ok mu:
  72                         for var k = 0; k < mu.len; ++k
  73                                 std.slfree(mu[k])
  74                         ;;
  75                         std.slfree(mu)
  76                 | `std.Err e: std.slfree(e)
  77                 ;;
  78         ;;
  79         std.htfree(mutwistingflip_stored)
  80 }
  81
  82 /*
  83    Component functions. namef is expected to be one of `vname' or `wname'.
  84  */
  85 const muT = {namef, T : weyl_reflection[:][:], i : int, j : int, mu : byte[:][:]#
  86         if i < 0 || i >= T.len
  87                 -> void
  88         ;;
  89
  90         for z : T[i]
  91                 std.slpush(mu, namef(z, j))
  92         ;;
  93 }
  94
  95 const mucol = {namef, kc : KC_type, T : weyl_reflection[:][:], j : int, mu : byte[:][:]#
  96         for var i = 1; i < T.len; ++i
  97                 muT(namef, T, i, j, mu)
  98         ;;
  99 }
 100
 101 const mucolrev = {namef, kc : KC_type, T : weyl_reflection[:][:], j : int, mu : byte[:][:]#
 102         for var i = T.len - 1; i >= 1; --i
 103                 muT(namef, T, i, j, mu)
 104         ;;
 105 }
 106
 107 const musigmaGoncol = {namef, kc : KC_type, T : weyl_reflection[:][:], j : int, mu : byte[:][:]#
 108         if is_sigmaG_trivial(kc)
 109                 -> void
 110         ;;
 111
 112         /*
 113            This is really “Do the longest word (so l+1 copies of
 114            mutation in the order of the coxeter element, which is given
 115            by mucol), then one more linear pass (so one more mucol).”
 116          */
 117         var h : int = coxeter_num(kc)
 118         var l = h / 2 - 1
 119         for var i = 0; i < l + 2; ++i
 120                 mucol(namef, kc, T, j, mu)
 121         ;;
 122 }
 123
 124 const murowfromleft = {namef, kc : KC_type, T : weyl_reflection[:][:], i : int, width : int, last : int, mu : byte[:][:]#
 125         for var j = width; j >= last; --j
 126                 muT(namef, T, i, j, mu)
 127         ;;
 128 }
 129
 130 const musigmaGonrow = {namef, kc : KC_type, T : weyl_reflection[:][:], i : int, start : int, end : int, mu : byte[:][:]#
 131         /*
 132            Fundamentally the same as musigmaGoncol: “Perform the
 133            mutation in the ordering of the longest word, then one more
 134            pass through”. start and end are because I want to use this
 135            in muflip.
 136          */
 137         var length = end - start
 138
 139         if length == 0
 140                 -> void
 141         ;;
 142
 143         /* First, the longest word bit */
 144         for var l = length; l >= 0; --l
 145                 for var j = 0; j <= l; ++j
 146                         muT(namef, T, i, start + j, mu)
 147                 ;;
 148         ;;
 149
 150         /* Now sweep back */
 151         for var j = end; j >= start; --j
 152                 muT(namef, T, i, j, mu)
 153         ;;
 154 }
 155
 156 const get_mutwistingrot = {kc
 157         match std.htget(mutwistingrot_stored, kc)
 158         | `std.Some stored: -> stored
 159         | `std.None:
 160         ;;
 161
 162         var mu = [][:]
 163
 164         var h : int = coxeter_num(kc)
 165         if h % 2 != 0
 166                 /* Should be impossible */
 167                 var ret = `std.Err std.fmt("Coxeter number {} must be even", h)
 168                 std.htput(mutwistingrot_stored, kc, ret)
 169                 -> ret
 170         ;;
 171         var ell = h / 2 - 1
 172         var T : weyl_reflection[:][:] = get_tree_partition(kc)
 173
 174         /* 0 rotation, trivial sigmaG action */
 175
 176         for var x = 1; x <= ell; ++x
 177                 for var y = 1; y <= ell + 1 - x; ++y
 178                         mucol(vname, kc, T, y, &mu)
 179                 ;;
 180         ;;
 181
 182         /* 1/3rd rotation, non-trivial sigmaG action */
 183
 184         for var j = 0; j < T.len; ++j
 185                 std.slfree(T[j])
 186         ;;
 187         std.slfree(T)
 188
 189         var ret = `std.Ok mu
 190         std.htput(mutwistingrot_stored, kc, ret)
 191         -> ret
 192 }
 193
 194
 195 const get_murot = {kc
 196         match std.htget(murot_stored, kc)
 197         | `std.Some stored: -> stored
 198         | `std.None:
 199         ;;
 200
 201         var mu = [][:]
 202
 203         var h : int = coxeter_num(kc)
 204         if h % 2 != 0
 205                 /* Should be impossible */
 206                 var ret = `std.Err std.fmt("Coxeter number {} must be even", h)
 207                 std.htput(murot_stored, kc, ret)
 208                 -> ret
 209         ;;
 210         var ell = h / 2 - 1
 211         var T : weyl_reflection[:][:] = get_tree_partition(kc)
 212
 213         /* 0 rotation, trivial sigmaG action */
 214
 215         for var x = 1; x <= ell; ++x
 216                 for var y = 1; y <= ell + 1 - x; ++y
 217                         mucol(vname, kc, T, y, &mu)
 218                 ;;
 219         ;;
 220
 221         /* 1/3rd rotation, non-trivial sigmaG action */
 222
 223         for var x = 1; x <= ell; ++x
 224                 musigmaGoncol(vname, kc, T, x, &mu)
 225         ;;
 226
 227         for var y = 1; y <= T.len; ++y
 228                 musigmaGonrow(vname, kc, T, y, 1, ell, &mu)
 229         ;;
 230
 231         /* 1/3rd rotation, trivial sigmaG action */
 232
 233         for var j = 0; j < T.len; ++j
 234                 std.slfree(T[j])
 235         ;;
 236         std.slfree(T)
 237
 238         var ret = `std.Ok mu
 239         std.htput(murot_stored, kc, ret)
 240         -> ret
 241 }
 242
 243 const get_muflip = {kc
 244         match std.htget(muflip_stored, kc)
 245         | `std.Some stored: -> stored
 246         | `std.None:
 247         ;;
 248
 249         var mu = [][:]
 250         var h : int = coxeter_num(kc)
 251         if h % 2 != 0
 252                 /* Should be impossible */
 253                 var ret = `std.Err std.fmt("Coxeter number {} must be even", h)
 254                 std.htput(muflip_stored, kc, ret)
 255                 -> ret
 256         ;;
 257         var l = h / 2 - 1
 258         var T : weyl_reflection[:][:] = get_tree_partition(kc)
 259         var L = 2 * l + 1
 260
 261         /*
 262            This particular realization of the mutation is not optimized
 263            for brevity. By analyzing which pieces commute, it can be
 264            shown that there are much shorter versions. However, this
 265            particular sequence of mutations seems to *run* quickly, on
 266            my machine, at the time I write this.
 267          */
 268
 269         /*
 270            Start off with mutwistingrot^-1 on the left-hand side. Since
 271            this involves the twisting, we need to refer to the vertices
 272            by their twisted names. Since it's on the left, we need to
 273            add l. Thankfully, we don't care about the sigmaG action on
 274            each column, since those mutations are guaranteed to commute.
 275          */
 276         for var x = 1; x <= l; ++x
 277                 for var y = l - x + 1; y <= l; ++y
 278                         mucolrev(wname, kc, T, (l + 1) + y, &mu)
 279                 ;;
 280         ;;
 281
 282         /* Now mutwistingrot^-1 on the right-hand side. */
 283         for var x = 1; x <= l; ++x
 284                 for var y = l - x + 1; y <= l; ++y
 285                         mucolrev(wname, kc, T, y, &mu)
 286                 ;;
 287         ;;
 288
 289         /*
 290            The core of muflip: the thing that moves the outside of the
 291            diagonal grid.
 292          */
 293         for var last = 1; last <= L; ++last
 294                 for var j = last; j <= L; ++j
 295                         mucol(wname, kc, T, L + last - j, &mu)
 296                 ;;
 297         ;;
 298
 299         /*
 300            Finally, apply some irritating sigmaG actions of A_L. If
 301            you're implementing this, and you're willing to just move the
 302            vertices around, you can probably omit the mutations that
 303            follow and save a bit of time.
 304          */
 305         for var i = T.len - 1; i >= 0; --i
 306                 musigmaGonrow(wname, kc, T, i, 1, L, &mu)
 307         ;;
 308
 309         for var i = T.len - 1; i >= 0; --i
 310                 musigmaGonrow(wname, kc, T, i, l + 2, L, &mu)
 311         ;;
 312
 313         for var i = T.len - 1; i >= 0; --i
 314                 musigmaGonrow(wname, kc, T, i, 1, l, &mu)
 315         ;;
 316
 317
 318         for var j = 0; j < T.len; ++j
 319                 std.slfree(T[j])
 320         ;;
 321         std.slfree(T)
 322
 323         var ret = `std.Ok mu
 324         std.htput(muflip_stored, kc, ret)
 325         -> ret
 326 }
 327
 328 const get_mutwistingflip = {kc
 329         /*
 330            As get_muflip, but we cut out all the ending parts that move
 331            things to the correct positions
 332          */
 333         match std.htget(mutwistingflip_stored, kc)
 334         | `std.Some stored: -> stored
 335         | `std.None:
 336         ;;
 337
 338         var mu = [][:]
 339         var h : int = coxeter_num(kc)
 340         if h % 2 != 0
 341                 /* Should be impossible */
 342                 var ret = `std.Err std.fmt("Coxeter number {} must be even", h)
 343                 std.htput(mutwistingflip_stored, kc, ret)
 344                 -> ret
 345         ;;
 346         var l = h / 2 - 1
 347         var T : weyl_reflection[:][:] = get_tree_partition(kc)
 348         var L = 2 * l + 1
 349
 350         for var x = 1; x <= l; ++x
 351                 for var y = l - x + 1; y <= l; ++y
 352                         mucolrev(wname, kc, T, (l + 1) + y, &mu)
 353                 ;;
 354         ;;
 355
 356         for var x = 1; x <= l; ++x
 357                 for var y = l - x + 1; y <= l; ++y
 358                         mucolrev(wname, kc, T, y, &mu)
 359                 ;;
 360         ;;
 361
 362         for var last = 1; last <= L; ++last
 363                 for var i = 1; i < T.len; ++i
 364                         murowfromleft(wname, kc, T, i, L, last, &mu)
 365                 ;;
 366         ;;
 367
 368         for var j = 0; j < T.len; ++j
 369                 std.slfree(T[j])
 370         ;;
 371         std.slfree(T)
 372
 373         var ret = `std.Ok mu
 374         std.htput(mutwistingflip_stored, kc, ret)
 375         -> ret
 376 }