1 //------------------------------------------------------------------------------ 2 // GB_semiring_template.c: built-in unary and binary functions and operators 3 //------------------------------------------------------------------------------ 4 5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved. 6 // SPDX-License-Identifier: Apache-2.0 7 8 //------------------------------------------------------------------------------ 9 10 // This file is #include'd many times in GB_ops.c to define the built-in 11 // semirings. That file has defined either GB_BOOLEAN, or GB_TYPE as one of 12 // the 10 non-boolean types. 13 14 // Using built-in types and operators, many unique semirings can be built. 15 // Below is the list of pre-defined semirings in SuiteSparse:GraphBLAS: 16 17 // 1000 semirings with a multiply operator TxT -> T where T is non-Boolean, from 18 // the complete cross product of: 19 20 // 5 monoids: MIN, MAX, PLUS, TIMES, ANY 21 // 20 multiply operators: 22 // FIRST, SECOND, PAIR, MIN, MAX, PLUS, MINUS, RMINUS, TIMES, DIV, RDIV 23 // ISEQ, ISNE, ISGT, ISLT, ISGE, ISLE, 24 // LOR, LAND, LXOR 25 // 10 non-Boolean types, T 26 27 // a single instance of this file creates 100 semirings of this 28 // form, of one type T, when T is not BOOL 29 30 // 300 semirings with a comparison operator TxT -> bool, where T is 31 // non-Boolean, from the complete cross product of: 32 33 // 5 Boolean monoids: LAND, LOR, LXOR, EQ, ANY 34 // 6 multiply operators: EQ, NE, GT, LT, GE, LE 35 // 10 non-Boolean types, T 36 37 // a single instance of this file creates 30 semirings of this form, 38 // of one type T, when T is not BOOL 39 40 // 55 semirings with purely Boolean types, bool x bool -> bool, from the 41 // complete cross product of: 42 43 // 5 Boolean monoids: LAND, LOR, LXOR, EQ, ANY 44 // 11 multiply operators: 45 // FIRST, SECOND, PAIR, LOR, LAND, LXOR, EQ, GT, LT, GE, LE 46 47 // a single instance of this file creates all 5*11 = 55 purely Boolean 48 // semirings, when T is BOOL and GB_BOOLEAN is defined 49 50 // 54 complex semirings: 51 52 // 3 complex monoids: PLUS, TIMES, ANY 53 // 9 multiply operators: FIRST, SECOND, PAIR, PLUS, MINUS, TIMES, 54 // DIV, RDIV, RMINUS 55 // 2 complex types (FC32 and FC64) 56 57 // 64 bitwise semirings: 58 59 // 4 bitwise monoids: BOR, BAND, BXOR, BXNOR 60 // 4 bitwise multiply operators: BOR, BAND, BXOR, BXNOR 61 // 4 unsigned integer types: UINT8, UINT16, UINT32, UINT64 62 63 // 80 positional semirings: 64 65 // 5 monoids: MIN, MAX, PLUS, TIMES, ANY 66 // 8 multiply operators: 67 // FIRSTI, FIRSTI1, FIRSTJ, FIRSTJ1, 68 // SECONDI, SECONDI1, SECONDJ, SECONDJ1 69 // 2 types: INT32, INT64 70 71 #if defined ( GB_BOOLEAN ) 72 73 //-------------------------------------------------------------------------- 74 // 55 purely Boolean semirings 75 //-------------------------------------------------------------------------- 76 77 // All types in these 44 semirings are BOOL 78 79 // 11 semirings with LOR monoid; the 2nd argument is the multiply operator 80 GXB_SEMIRING ( LOR , FIRST ) 81 GXB_SEMIRING ( LOR , SECOND ) 82 GXB_SEMIRING ( LOR , PAIR ) 83 GXB_SEMIRING ( LOR , LOR ) 84 GXB_SEMIRING ( LOR , LAND ) 85 GXB_SEMIRING ( LOR , LXOR ) 86 GXB_SEMIRING ( LOR , EQ ) 87 GXB_SEMIRING ( LOR , GT ) 88 GXB_SEMIRING ( LOR , LT ) 89 GXB_SEMIRING ( LOR , GE ) 90 GXB_SEMIRING ( LOR , LE ) 91 92 // 11 semirings with LAND monoid; the 2nd argument is the multiply operator 93 GXB_SEMIRING ( LAND , FIRST ) 94 GXB_SEMIRING ( LAND , SECOND ) 95 GXB_SEMIRING ( LAND , PAIR ) 96 GXB_SEMIRING ( LAND , LOR ) 97 GXB_SEMIRING ( LAND , LAND ) 98 GXB_SEMIRING ( LAND , LXOR ) 99 GXB_SEMIRING ( LAND , EQ ) 100 GXB_SEMIRING ( LAND , GT ) 101 GXB_SEMIRING ( LAND , LT ) 102 GXB_SEMIRING ( LAND , GE ) 103 GXB_SEMIRING ( LAND , LE ) 104 105 // 11 semirings with LXOR monoid; the 2nd argument is the multiply operator 106 GXB_SEMIRING ( LXOR , FIRST ) 107 GXB_SEMIRING ( LXOR , SECOND ) 108 GXB_SEMIRING ( LXOR , PAIR ) 109 GXB_SEMIRING ( LXOR , LOR ) 110 GXB_SEMIRING ( LXOR , LAND ) 111 GXB_SEMIRING ( LXOR , LXOR ) 112 GXB_SEMIRING ( LXOR , EQ ) 113 GXB_SEMIRING ( LXOR , GT ) 114 GXB_SEMIRING ( LXOR , LT ) 115 GXB_SEMIRING ( LXOR , GE ) 116 GXB_SEMIRING ( LXOR , LE ) 117 118 // 11 semirings with EQ monoid; the 2nd argument is the multiply operator 119 GXB_SEMIRING ( EQ , FIRST ) 120 GXB_SEMIRING ( EQ , SECOND ) 121 GXB_SEMIRING ( EQ , PAIR ) 122 GXB_SEMIRING ( EQ , LOR ) 123 GXB_SEMIRING ( EQ , LAND ) 124 GXB_SEMIRING ( EQ , LXOR ) 125 GXB_SEMIRING ( EQ , EQ ) 126 GXB_SEMIRING ( EQ , GT ) 127 GXB_SEMIRING ( EQ , LT ) 128 GXB_SEMIRING ( EQ , GE ) 129 GXB_SEMIRING ( EQ , LE ) 130 131 // 11 semirings with ANY monoid; the 2nd argument is the multiply operator 132 GXB_SEMIRING ( ANY , FIRST ) 133 GXB_SEMIRING ( ANY , SECOND ) 134 GXB_SEMIRING ( ANY , PAIR ) 135 GXB_SEMIRING ( ANY , LOR ) 136 GXB_SEMIRING ( ANY , LAND ) 137 GXB_SEMIRING ( ANY , LXOR ) 138 GXB_SEMIRING ( ANY , EQ ) 139 GXB_SEMIRING ( ANY , GT ) 140 GXB_SEMIRING ( ANY , LT ) 141 GXB_SEMIRING ( ANY , GE ) 142 GXB_SEMIRING ( ANY , LE ) 143 144 #elif defined ( GB_COMPLEX ) 145 146 //-------------------------------------------------------------------------- 147 // 27 complex semirings of the form TxT->t 148 //-------------------------------------------------------------------------- 149 150 // 9 semirings with PLUS monoid 151 GXB_SEMIRING ( PLUS , FIRST ) 152 GXB_SEMIRING ( PLUS , SECOND ) 153 GXB_SEMIRING ( PLUS , PAIR ) 154 GXB_SEMIRING ( PLUS , PLUS ) 155 GXB_SEMIRING ( PLUS , MINUS ) 156 GXB_SEMIRING ( PLUS , RMINUS ) 157 GXB_SEMIRING ( PLUS , TIMES ) 158 GXB_SEMIRING ( PLUS , DIV ) 159 GXB_SEMIRING ( PLUS , RDIV ) 160 161 // 9 semirings with TIMES monoid 162 GXB_SEMIRING ( TIMES , FIRST ) 163 GXB_SEMIRING ( TIMES , SECOND ) 164 GXB_SEMIRING ( TIMES , PAIR ) 165 GXB_SEMIRING ( TIMES , PLUS ) 166 GXB_SEMIRING ( TIMES , MINUS ) 167 GXB_SEMIRING ( TIMES , RMINUS ) 168 GXB_SEMIRING ( TIMES , TIMES ) 169 GXB_SEMIRING ( TIMES , DIV ) 170 GXB_SEMIRING ( TIMES , RDIV ) 171 172 // 9 semirings with ANY monoid 173 GXB_SEMIRING ( ANY , FIRST ) 174 GXB_SEMIRING ( ANY , SECOND ) 175 GXB_SEMIRING ( ANY , PAIR ) 176 GXB_SEMIRING ( ANY , PLUS ) 177 GXB_SEMIRING ( ANY , MINUS ) 178 GXB_SEMIRING ( ANY , RMINUS ) 179 GXB_SEMIRING ( ANY , TIMES ) 180 GXB_SEMIRING ( ANY , DIV ) 181 GXB_SEMIRING ( ANY , RDIV ) 182 183 #else 184 185 //-------------------------------------------------------------------------- 186 // 100 semirings of the form TxT->T 187 //-------------------------------------------------------------------------- 188 189 // All types in these semirings are the same. These are defined for 190 // the 10 non-Boolean types, not when T is BOOL. 191 192 // 20 semirings with MIN monoid; the 2nd argument is the multiply operator 193 GXB_SEMIRING ( MIN , FIRST ) 194 GXB_SEMIRING ( MIN , SECOND ) 195 GXB_SEMIRING ( MIN , PAIR ) 196 GXB_SEMIRING ( MIN , MIN ) 197 GXB_SEMIRING ( MIN , MAX ) 198 GXB_SEMIRING ( MIN , PLUS ) 199 GXB_SEMIRING ( MIN , MINUS ) 200 GXB_SEMIRING ( MIN , RMINUS ) 201 GXB_SEMIRING ( MIN , TIMES ) 202 GXB_SEMIRING ( MIN , DIV ) 203 GXB_SEMIRING ( MIN , RDIV ) 204 GXB_SEMIRING ( MIN , ISEQ ) 205 GXB_SEMIRING ( MIN , ISNE ) 206 GXB_SEMIRING ( MIN , ISGT ) 207 GXB_SEMIRING ( MIN , ISLT ) 208 GXB_SEMIRING ( MIN , ISGE ) 209 GXB_SEMIRING ( MIN , ISLE ) 210 GXB_SEMIRING ( MIN , LOR ) 211 GXB_SEMIRING ( MIN , LAND ) 212 GXB_SEMIRING ( MIN , LXOR ) 213 214 // 20 semirings with MAX monoid; the 2nd argument is the multiply operator 215 GXB_SEMIRING ( MAX , FIRST ) 216 GXB_SEMIRING ( MAX , SECOND ) 217 GXB_SEMIRING ( MAX , PAIR ) 218 GXB_SEMIRING ( MAX , MIN ) 219 GXB_SEMIRING ( MAX , MAX ) 220 GXB_SEMIRING ( MAX , PLUS ) 221 GXB_SEMIRING ( MAX , MINUS ) 222 GXB_SEMIRING ( MAX , RMINUS ) 223 GXB_SEMIRING ( MAX , TIMES ) 224 GXB_SEMIRING ( MAX , DIV ) 225 GXB_SEMIRING ( MAX , RDIV ) 226 GXB_SEMIRING ( MAX , ISEQ ) 227 GXB_SEMIRING ( MAX , ISNE ) 228 GXB_SEMIRING ( MAX , ISGT ) 229 GXB_SEMIRING ( MAX , ISLT ) 230 GXB_SEMIRING ( MAX , ISGE ) 231 GXB_SEMIRING ( MAX , ISLE ) 232 GXB_SEMIRING ( MAX , LOR ) 233 GXB_SEMIRING ( MAX , LAND ) 234 GXB_SEMIRING ( MAX , LXOR ) 235 236 // 20 semirings with PLUS monoid; the 2nd argument is the multiply operator 237 GXB_SEMIRING ( PLUS , FIRST ) 238 GXB_SEMIRING ( PLUS , SECOND ) 239 GXB_SEMIRING ( PLUS , PAIR ) 240 GXB_SEMIRING ( PLUS , MIN ) 241 GXB_SEMIRING ( PLUS , MAX ) 242 GXB_SEMIRING ( PLUS , PLUS ) 243 GXB_SEMIRING ( PLUS , MINUS ) 244 GXB_SEMIRING ( PLUS , RMINUS ) 245 GXB_SEMIRING ( PLUS , TIMES ) 246 GXB_SEMIRING ( PLUS , DIV ) 247 GXB_SEMIRING ( PLUS , RDIV ) 248 GXB_SEMIRING ( PLUS , ISEQ ) 249 GXB_SEMIRING ( PLUS , ISNE ) 250 GXB_SEMIRING ( PLUS , ISGT ) 251 GXB_SEMIRING ( PLUS , ISLT ) 252 GXB_SEMIRING ( PLUS , ISGE ) 253 GXB_SEMIRING ( PLUS , ISLE ) 254 GXB_SEMIRING ( PLUS , LOR ) 255 GXB_SEMIRING ( PLUS , LAND ) 256 GXB_SEMIRING ( PLUS , LXOR ) 257 258 // 20 semirings with TIMES monoid; the 2nd argument is the multiply operator 259 GXB_SEMIRING ( TIMES , FIRST ) 260 GXB_SEMIRING ( TIMES , SECOND ) 261 GXB_SEMIRING ( TIMES , PAIR ) 262 GXB_SEMIRING ( TIMES , MIN ) 263 GXB_SEMIRING ( TIMES , MAX ) 264 GXB_SEMIRING ( TIMES , PLUS ) 265 GXB_SEMIRING ( TIMES , MINUS ) 266 GXB_SEMIRING ( TIMES , RMINUS ) 267 GXB_SEMIRING ( TIMES , TIMES ) 268 GXB_SEMIRING ( TIMES , DIV ) 269 GXB_SEMIRING ( TIMES , RDIV ) 270 GXB_SEMIRING ( TIMES , ISEQ ) 271 GXB_SEMIRING ( TIMES , ISNE ) 272 GXB_SEMIRING ( TIMES , ISGT ) 273 GXB_SEMIRING ( TIMES , ISLT ) 274 GXB_SEMIRING ( TIMES , ISGE ) 275 GXB_SEMIRING ( TIMES , ISLE ) 276 GXB_SEMIRING ( TIMES , LOR ) 277 GXB_SEMIRING ( TIMES , LAND ) 278 GXB_SEMIRING ( TIMES , LXOR ) 279 280 // 20 semirings with ANY monoid; the 2nd argument is the multiply operator 281 GXB_SEMIRING ( ANY , FIRST ) 282 GXB_SEMIRING ( ANY , SECOND ) 283 GXB_SEMIRING ( ANY , PAIR ) 284 GXB_SEMIRING ( ANY , MIN ) 285 GXB_SEMIRING ( ANY , MAX ) 286 GXB_SEMIRING ( ANY , PLUS ) 287 GXB_SEMIRING ( ANY , MINUS ) 288 GXB_SEMIRING ( ANY , RMINUS ) 289 GXB_SEMIRING ( ANY , TIMES ) 290 GXB_SEMIRING ( ANY , DIV ) 291 GXB_SEMIRING ( ANY , RDIV ) 292 GXB_SEMIRING ( ANY , ISEQ ) 293 GXB_SEMIRING ( ANY , ISNE ) 294 GXB_SEMIRING ( ANY , ISGT ) 295 GXB_SEMIRING ( ANY , ISLT ) 296 GXB_SEMIRING ( ANY , ISGE ) 297 GXB_SEMIRING ( ANY , ISLE ) 298 GXB_SEMIRING ( ANY , LOR ) 299 GXB_SEMIRING ( ANY , LAND ) 300 GXB_SEMIRING ( ANY , LXOR ) 301 302 //-------------------------------------------------------------------------- 303 // 30 semirings of the form TxT -> bool 304 //-------------------------------------------------------------------------- 305 306 // The multiply operator has the form z=compare(x,y), where x and y are of 307 // type T, and z is Boolean. These operators are combined with the four 308 // Boolean monoids. 309 310 // These are defined when T is one of the 10 non-Boolean types, not when T 311 // is BOOL 312 313 // 6 semrings with LOR monoid; the 2nd argument is the comparison operator 314 GXB_SEMIRING_COMPARE ( LOR , EQ ) 315 GXB_SEMIRING_COMPARE ( LOR , NE ) 316 GXB_SEMIRING_COMPARE ( LOR , GT ) 317 GXB_SEMIRING_COMPARE ( LOR , LT ) 318 GXB_SEMIRING_COMPARE ( LOR , GE ) 319 GXB_SEMIRING_COMPARE ( LOR , LE ) 320 321 // 6 semrings with LAND monoid; the 2nd argument is the comparison operator 322 GXB_SEMIRING_COMPARE ( LAND , EQ ) 323 GXB_SEMIRING_COMPARE ( LAND , NE ) 324 GXB_SEMIRING_COMPARE ( LAND , GT ) 325 GXB_SEMIRING_COMPARE ( LAND , LT ) 326 GXB_SEMIRING_COMPARE ( LAND , GE ) 327 GXB_SEMIRING_COMPARE ( LAND , LE ) 328 329 // 6 semrings with LXOR monoid; the 2nd argument is the comparison operator 330 GXB_SEMIRING_COMPARE ( LXOR , EQ ) 331 GXB_SEMIRING_COMPARE ( LXOR , NE ) 332 GXB_SEMIRING_COMPARE ( LXOR , GT ) 333 GXB_SEMIRING_COMPARE ( LXOR , LT ) 334 GXB_SEMIRING_COMPARE ( LXOR , GE ) 335 GXB_SEMIRING_COMPARE ( LXOR , LE ) 336 337 // 6 semrings with EQ monoid; the 2nd argument is the comparison operator 338 GXB_SEMIRING_COMPARE ( EQ , EQ ) 339 GXB_SEMIRING_COMPARE ( EQ , NE ) 340 GXB_SEMIRING_COMPARE ( EQ , GT ) 341 GXB_SEMIRING_COMPARE ( EQ , LT ) 342 GXB_SEMIRING_COMPARE ( EQ , GE ) 343 GXB_SEMIRING_COMPARE ( EQ , LE ) 344 345 // 6 semrings with ANY monoid; the 2nd argument is the comparison operator 346 GXB_SEMIRING_COMPARE ( ANY , EQ ) 347 GXB_SEMIRING_COMPARE ( ANY , NE ) 348 GXB_SEMIRING_COMPARE ( ANY , GT ) 349 GXB_SEMIRING_COMPARE ( ANY , LT ) 350 GXB_SEMIRING_COMPARE ( ANY , GE ) 351 GXB_SEMIRING_COMPARE ( ANY , LE ) 352 353 #endif 354 355 #if defined ( GB_UNSIGNED_INT ) 356 357 //-------------------------------------------------------------------------- 358 // 16 bitwise semirings (for unsigned integers only) 359 //-------------------------------------------------------------------------- 360 361 GXB_SEMIRING ( BOR , BOR ) 362 GXB_SEMIRING ( BOR , BAND ) 363 GXB_SEMIRING ( BOR , BXOR ) 364 GXB_SEMIRING ( BOR , BXNOR ) 365 366 GXB_SEMIRING ( BAND , BOR ) 367 GXB_SEMIRING ( BAND , BAND ) 368 GXB_SEMIRING ( BAND , BXOR ) 369 GXB_SEMIRING ( BAND , BXNOR ) 370 371 GXB_SEMIRING ( BXOR , BOR ) 372 GXB_SEMIRING ( BXOR , BAND ) 373 GXB_SEMIRING ( BXOR , BXOR ) 374 GXB_SEMIRING ( BXOR , BXNOR ) 375 376 GXB_SEMIRING ( BXNOR , BOR ) 377 GXB_SEMIRING ( BXNOR , BAND ) 378 GXB_SEMIRING ( BXNOR , BXOR ) 379 GXB_SEMIRING ( BXNOR , BXNOR ) 380 381 #endif 382 383 #if defined ( GB_POSITIONAL ) 384 385 //-------------------------------------------------------------------------- 386 // 40 positional semirings: 387 //-------------------------------------------------------------------------- 388 389 GXB_SEMIRING ( MIN , FIRSTI ) 390 GXB_SEMIRING ( MIN , FIRSTI1 ) 391 GXB_SEMIRING ( MIN , FIRSTJ ) 392 GXB_SEMIRING ( MIN , FIRSTJ1 ) 393 GXB_SEMIRING ( MIN , SECONDI ) 394 GXB_SEMIRING ( MIN , SECONDI1 ) 395 GXB_SEMIRING ( MIN , SECONDJ ) 396 GXB_SEMIRING ( MIN , SECONDJ1 ) 397 398 GXB_SEMIRING ( MAX , FIRSTI ) 399 GXB_SEMIRING ( MAX , FIRSTI1 ) 400 GXB_SEMIRING ( MAX , FIRSTJ ) 401 GXB_SEMIRING ( MAX , FIRSTJ1 ) 402 GXB_SEMIRING ( MAX , SECONDI ) 403 GXB_SEMIRING ( MAX , SECONDI1 ) 404 GXB_SEMIRING ( MAX , SECONDJ ) 405 GXB_SEMIRING ( MAX , SECONDJ1 ) 406 407 GXB_SEMIRING ( ANY , FIRSTI ) 408 GXB_SEMIRING ( ANY , FIRSTI1 ) 409 GXB_SEMIRING ( ANY , FIRSTJ ) 410 GXB_SEMIRING ( ANY , FIRSTJ1 ) 411 GXB_SEMIRING ( ANY , SECONDI ) 412 GXB_SEMIRING ( ANY , SECONDI1 ) 413 GXB_SEMIRING ( ANY , SECONDJ ) 414 GXB_SEMIRING ( ANY , SECONDJ1 ) 415 416 GXB_SEMIRING ( PLUS , FIRSTI ) 417 GXB_SEMIRING ( PLUS , FIRSTI1 ) 418 GXB_SEMIRING ( PLUS , FIRSTJ ) 419 GXB_SEMIRING ( PLUS , FIRSTJ1 ) 420 GXB_SEMIRING ( PLUS , SECONDI ) 421 GXB_SEMIRING ( PLUS , SECONDI1 ) 422 GXB_SEMIRING ( PLUS , SECONDJ ) 423 GXB_SEMIRING ( PLUS , SECONDJ1 ) 424 425 GXB_SEMIRING ( TIMES , FIRSTI ) 426 GXB_SEMIRING ( TIMES , FIRSTI1 ) 427 GXB_SEMIRING ( TIMES , FIRSTJ ) 428 GXB_SEMIRING ( TIMES , FIRSTJ1 ) 429 GXB_SEMIRING ( TIMES , SECONDI ) 430 GXB_SEMIRING ( TIMES , SECONDI1 ) 431 GXB_SEMIRING ( TIMES , SECONDJ ) 432 GXB_SEMIRING ( TIMES , SECONDJ1 ) 433 434 #endif 435 436 #undef GB_XTYPE 437 #undef GB_BOOLEAN 438 #undef GB_COMPLEX 439 #undef GB_UNSIGNED_INT 440 #undef GB_POSITIONAL 441 442