1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470
|
/*
Copyright (C) 2000-2001 Jae Choon Cha.
This file is part of CBraid.
CBraid is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
any later version.
CBraid is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with CBraid. If not, see <https://www.gnu.org/licenses/>.
*/
/*
$Id: cbraid_interface.h,v 1.11 2001/12/07 10:12:13 jccha Exp $
Jae Choon CHA <jccha@knot.kaist.ac.kr>
This is interface declarations of cbraid library.
*/
// For portablity, we use our own primitive types. The following
// definitions may need to be modified for your compiler.
typedef char sint8;
typedef unsigned char uint8;
/* JLT: Don't use short ints... */
// typedef short sint16;
// typedef unsigned short uint16;
typedef int sint16;
typedef unsigned int uint16;
typedef int sint32;
typedef unsigned int uint32;
typedef long long sint64;
typedef unsigned long long uint64;
// Implementation limits.
// Maximum braid index.
const sint16 MaxBraidIndex = 300;
// Algorithms useful in managing standard containers of Factor objects.
// Apply a binary function f on pairs (first,first+1),
// (first+1,first+2), ... , sequentially, where f is allowed to change
// the arguments. The algorithm stops if either the binary function f
// returns false or (last-2,last-1) has been processed. An iterator
// pointing the first untouched element is returned. For example, if
// the entire [first, last[ has been processed, then last is returned.
// One may easily recognize that this can be used is for the inner
// loop of the bubble sort algorithm. In Cbraid, this is used to make
// a given sequence of canonical factors weighted, under the
// assumption that all adjancent pairs but the first one are weighted.
// Obviously the execution time is linear in the length of the
// sequence.
template<class ForItr, class BinFunc>
ForItr apply_binfun(ForItr first, ForItr last, BinFunc f);
// The reverse version of apply_binfun. By reverse_apply_binfun, f is
// applied on (last-2,last-1), (last-3,last-2), ... , sequentially.
// It returns the first(leftmost) element that has been processed.
template<class BiItr, class BinFunc>
BiItr reverse_apply_binfun(BiItr first, BiItr last, BinFunc f);
// A bubble sort algorithm. It executes apply_binfun for
// [last-2,last[, [last-3,last[, ... , [first, last[ sequentialy. To
// sort a sequence with respect to an order "<", f(x, y) should be a
// function that swaps x and y and returns true if x > y, and unless
// does nothing but returns false. This is an O(l^2) algorithm, where
// l is the length of the range.
template <class ForItr, class BinFun>
void bubble_sort(ForItr first, ForItr last, BinFun f);
// Erase consecutive elements at the beginning of a sequence
// satisfying a given predicate, and return the number of erased
// elements. In order to remove elements from the sequence really,
// the container must have erase() member function.
template <class Seq, class UnaPre>
typename Seq::difference_type erase_front_if(Seq& s, UnaPre f);
// Reverse version of erase_front_if. It erases consecutive elements
// at the end of the sequence which satisfies a given predicate.
template <class Seq, class UnaPre>
typename Seq::difference_type erase_back_if(Seq& s, UnaPre f);
// Exception class.
struct OddIndexError {};
struct NegativeBraidError {};
// Class describing the Artin presentation and the band generator
// presentation. Basically they consist of the description of delta
// and the meet operation.
class ArtinPresentation {
protected:
sint16 PresentationIndex;
public:
ArtinPresentation(sint16 n);
sint16 Index() const;
// Return the i-th entry of the permutation table of delta^k.
sint16 DeltaTable(sint16 i, sint32 k = 1) const;
// Compute the meet r of the two factors a and b. A factor is
// given as the associated permutation, which is viewed as a
// bijection on the set {1,...n} and represented as an array whose
// i-th entry is the image of i under the inverse of the
// permutation (this convention is different from that in the
// AsiaCrypt 2001 paper of the author). The range of indices is
// [1,n], not [0,n[. We use a C style array of size (n+1) to
// represent an n-permutation (the first entry is not used).
// We define the left meet of two factors a and b to be the
// longest factor r such that a=ra' and b=rb' for some factors a'
// and b'. This coincides with the convention of the paper of
// Birman, Ko, and Lee, but different from that of the article of
// Thurston (in Epstein's book). Indeed, Thurston's is the
// "right" meet in our sense.
void LeftMeet(const sint16* a, const sint16* b, sint16* r) const;
void RightMeet(const sint16* a, const sint16* b, sint16* r) const;
// Generate a random factor.
void Randomize(sint16* r) const;
private:
// Subroutine called by LeftMeet() and RightMeet()
static void MeetSub(const sint16* a, const sint16* b, sint16* r,
sint16 s, sint16 t);
};
class BandPresentation {
protected:
sint16 PresentationIndex;
public:
BandPresentation(sint16 n);
sint16 Index() const;
// Return the i-th entry of the permutation table of delta^k.
sint16 DeltaTable(sint16 i, sint32 k = 1) const;
// Conversions between permutation table and disjoint cycle
// decomposition table. They are those described in the AsiaCrypt
// 2001 paper of the author, which uses different convention of
// permutation table. (In other parts of this program, a[i] is
// the inverse image of i, but in the paper and in these
// conversion functions, a[i] is the image of i.)
void PTtoDCDT(const sint16* a, sint16* x) const;
void DCDTtoPT(const sint16* x, sint16* a) const;
// Conversion of a ballot sequence into a permutation table. The
// convention of the AsiaCrypt 2001 paper is also used here (see
// the above remark).
void BStoPT(const sint8* s, sint16* a) const;
// Generate a random factor. It works properly only if USE_CLN
// macro is defined at compile time.
void Randomize(sint16* r) const;
// Compute the meet r of two factors a and b.
void LeftMeet(const sint16* a, const sint16* b, sint16* r) const;
void RightMeet(const sint16* a, const sint16* b, sint16* r) const;
};
// Class for a canonical factor, which is represented as a
// permutation.
template<class P> class Factor {
private:
// The presentation description.
P Pres;
// Permutation table.
sint16* pTable;
public:
// Constructor. The permutation table is initialized as
// delta^k. If k == Uninitialize, the table is left uninitialized.
enum { Uninitialize = 0x80000000 };
Factor(sint16 n, sint32 k = Uninitialize);
// Copy constructor.
Factor(const Factor& f);
// Conversion operator to the sint16* type. The address of the
// permutation table is returned. Recall that the index range is
// [1..n], not [0,n[; when the return value is r, r[1], ... , r[n]
// contains the permutation table. r[0] may be an invalid memory
// and must not be accessed.
operator sint16*();
operator const sint16*() const;
// Destructor.
~Factor();
// Initialize as a power of delta.
Factor& Delta(sint32 k = 1);
Factor& Identity();
// Initialize as a power of lower/upper delta.
Factor& LowerDelta(sint32 k = 1);
Factor& UpperDelta(sint32 k = 1);
// Get the index.
sint16 Index() const;
// Access to the n-th element of the permutation table. We follow
// the standard mathematical convention; the argument should be
// between 1 and Index.
sint16& At(sint16 n);
sint16 At(sint16 n) const;
sint16& operator[](sint16 n);
sint16 operator[](sint16 n) const;
// Assignment operator.
Factor& Assign(const Factor& f);
Factor& operator=(const Factor& f);
// Comparison operator.
bool Compare(const Factor& f) const;
bool operator==(const Factor& f) const;
bool operator!=(const Factor& f) const;
// Comparison with special elements.
bool CompareWithDelta(sint32 k = 1) const;
bool CompareWithIdentity() const;
// Composition operators, viewing factors as elements of the
// permutation group. We have several variants:
// b.Composition(a) return the composition of a and b
// b.AssignComposition(a) assign to b the composition of b and a.
// a*b the operator form of b.Composition(a).
// b *= a the operator form of b.AssignComposition(a).
Factor Composition(const Factor& a) const;
Factor& AssignComposition(const Factor& a);
Factor& operator*=(const Factor& a);
Factor operator*(const Factor& a) const;
// Inversion operators. We also have variants:
// a.Inverse() return the inverse of a.
// a.AssignInverse() invert a.
// !a the operator form of a.Inverse().
Factor Inverse() const;
Factor& AssignInverse();
Factor operator!() const;
// Complement operations. For a factor a, ~a=a^(-1) delta is
// called the complement (i.e. a(~a) = delta). We provide
// variants similar to those of inversion.
/* JLT: bugfix: the function Complement was using ~a (which
doesn't even compile) rather than the inverse of *this. Juan
Gonzales-Menenes had noticed the same thing in his "braiding"
code; he had used !(*this) rather than this->Inverse(). */
/* Factor Complement() const { return ~a*Factor(Index(), -1); } */
Factor Complement() const { return this->Inverse()*Factor(Index(), 1); }
Factor& AssignComplement() { return *this = Complement(); }
Factor operator~() const { return Complement(); }
// Flip operations (conjugation by delta^k, i,e. delta^(-k) a
// delta^k).
Factor Flip(sint32 k = 1) const;
Factor& AssignFlip(sint32 k = 1);
// Meet operations. b.LeftMeet(a) (resp. b.RightMeet(a)) returns
// the left (resp. right) meet of b and a.
Factor LeftMeet(const Factor& a) const;
Factor RightMeet(const Factor& a) const;
// Generate a random factor.
Factor& Randomize();
};
// Binary function form of the meet operators.
template<class P>
Factor<P> LeftMeet(const Factor<P>& a, const Factor<P>& b);
template<class P>
Factor<P> RightMeet(const Factor<P>& a, const Factor<P>& b);
// Make two factors left (or right) weighted. false is returned if
// and only if they are already weighted.
template<class P> bool MakeLeftWeighted(Factor<P>& a, Factor<P>& b);
template<class P> bool MakeRightWeighted(Factor<P>& a, Factor<P>& b);
// Output (the permutation table of) a factor through ostream.
template<class P>
std::ostream& operator<<(std::ostream& os, const Factor<P>& f);
// Short type names for canonical factors in Artin's and the band
// generator presentation.
typedef Factor<ArtinPresentation> ArtinFactor;
typedef Factor<BandPresentation> BandFactor;
// Class for a braid. A braid is represented as a triple (l,
// A_1...A_n, r), where l and r represent the powers of deltas at the
// left and right ends, and A_1,...,A_n is a list of canonical
// factors.
template<class P> class Braid;
// Friend functions.
template<class P>
std::ostream& operator<<(std::ostream& os, const Braid<P>& b);
// Real declaration.
template<class P> class Braid {
public:
// Type for canonical factors.
/* JLT: the old code was typedef Factor<P> Factor, which is no
longer legal C++. Hence, Factor had to be changed to Factor<P>
or CanonicalFactor in many places. */
typedef Factor<P> CanonicalFactor;
private:
// Presentation description.
P Pres;
// We allow direct access to the internal data structure, because
// their meanings are clear without any additional interfaces, and
// this is efficient for time-critical jobs.
public:
// Powers of deltas at ends.
sint32 LeftDelta, RightDelta;
// Length of the canonical factor list.
sint32 CLength;
// List of canonical factors. According to my experiments, usual
// operations on a list of pointers to objects is much faster
// (about twice) than corresponding operations on a list of
// objects, especially in the case of STL lists. Because of this,
// the following type declaration will be changed later.
std::list<Factor<P> > FactorList;
public:
// Iterator types for canonical factors.
typedef typename std::list<Factor<P> >::iterator FactorItr;
typedef typename std::list<Factor<P> >::const_iterator ConstFactorItr;
typedef typename std::list<Factor<P> >::reverse_iterator RevFactorItr;
typedef typename std::list<Factor<P> >::const_reverse_iterator ConstRevFactorItr;
public:
// Constructor which creates a trivial braid.
Braid(sint16 n);
// Copy constructor.
Braid(const Braid& b);
// Construct from a factor.
Braid(const Factor<P>& f);
// Destructor.
~Braid();
// Get the index.
sint16 Index() const;
// Initialize as a trivial braid.
Braid& Identity();
// Assignment operator.
Braid& Assign(const Braid& b);
Braid& operator=(const Braid& b);
// Comparison operator. Two braids are viewed as the same ones if
// and only if they have the same internal representation. Hence
// braids are usually converted to canonical forms before
// comparison.
bool Compare(const Braid& b) const;
bool operator==(const Braid& b) const;
bool operator!=(const Braid& b) const;
// Compare with the trivial representation of the identity braid.
// true is returned iff both LeftDelta and RightDelta are zero and
// FactorList is empty.
bool CompareWithIdentity() const;
// Inverting operators. a.Inverse() returns the inverse of
// a. !a is the operator form of Inverse().
Braid Inverse() const;
Braid operator!() const;
// Mutiplication operators. By b.LeftMultiply(a) and
// b.RightMultiply(a), b becomes a*b and b*a, respectively. a
// can be either a braid or a factor. More functions are
// provided for braids. c.Multiply(a,b), c becomes a*b. a*b
// returns the multiplication. By a*=b, a becomes a*b.
Braid& LeftMultiply(const Factor<P>& f);
Braid& RightMultiply(const Factor<P>& f);
Braid& LeftMultiply(const Braid& a);
Braid& RightMultiply(const Braid& a);
Braid& Multiply(const Braid& a, const Braid& b);
Braid operator*(const Braid& a) const;
Braid& operator*=(const Braid& a);
// Get the permutation associated to the braid.
Factor<P> GetPerm() const;
// Convertion into canonical forms.
Braid& MakeLCF();
Braid& MakeRCF();
// Reduce the maximal left/right lower/upper subbraid. By
// definition, a is the maximal left lower subbraid of a
// positive braid b if a is maximal among positive left lower
// braids such that a^(-1) b is positive. b.MaxLeftLower() set
// x to b return a. The other three are similar.
Braid ReduceLeftLower();
Braid ReduceLeftUpper();
Braid ReduceRightLower();
Braid ReduceRightUpper();
private:
// Subroutines used by Reduce{Left, Right}{Upper,Lower}().
Braid ReduceLeftSub(const Factor<P>& f);
Braid ReduceRightSub(const Factor<P>& f);
public:
// Generate a random braid. The result is a braid consisting
// of cl randomly chosen canonical factors with RightDelta and
// LeftDelta zero.
Braid& Randomize(sint32 cl = 1);
// Friend functions.
// Print a braid through ostream.
friend std::ostream& operator<< <>(std::ostream& os, const Braid& b);
};
// Short names for braid types.
typedef Braid<ArtinPresentation> ArtinBraid;
typedef Braid<BandPresentation> BandBraid;
// Conversion between ArtinBraid and BandBraid.
BandBraid ToBandBraid(const ArtinBraid& a);
ArtinBraid ToArtinBraid(const BandBraid& b);
#ifdef USE_CLN
// Catalan number function.
const cln::cl_I& GetCatalanNumber(sint16 n);
// Generate the k-th ballot sequence of length 2n and store it in
// s[1..2n] (note that s[0] is not used). It is internally used by
// Randomize(), but is declared as public since it has its own worth.
void BallotSequence(CBraid::sint16 n, const cln::cl_I k,
CBraid::sint8* s);
#endif // USE_CLN
|