SeqAn-1.1/seqan/sequence/lexical.h

   1  /*==========================================================================
   2                 SeqAn - The Library for Sequence Analysis
   3                           http://www.seqan.de
   4  ============================================================================
   5   Copyright (C) 2007
   6
   7   This library is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU Lesser General Public
   9   License as published by the Free Software Foundation; either
  10   version 3 of the License, or (at your option) any later version.
  11
  12   This library is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17  ============================================================================
  18   $Id: lexical.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_LEXICAL_H
  22 #define SEQAN_HEADER_LEXICAL_H
  23
  24
  25 namespace SEQAN_NAMESPACE_MAIN
  26 {
  27 //////////////////////////////////////////////////////////////////////////////
  28 // Switches for prefix ordering mode
  29 //////////////////////////////////////////////////////////////////////////////
  30
  31 /**
  32 .Tag.Prefix Order:
  33 ..summary:Specify whether a prefix is smaller or greater.
  34 ..tag.TagPrefixLess:A prefix is smaller.
  35 ...text:For example: $"abc" < "abcde"$.
  36 ..tag.TagPrefixGreater:A prefix is greater.
  37 ...text:For example: $"abc" > "abcde"$.
  38 ..remarks:The default for all comparison functions is $TagPrefixLess$.
  39 */
  40 struct TagPrefixLess_ {};
  41 typedef Tag<TagPrefixLess_> const TagPrefixLess;
  42
  43 struct TagPrefixGreater_ {};
  44 typedef Tag<TagPrefixGreater_> const TagPrefixGreater;
  45
  46
  47 /**
  48 .Metafunction.DefaultPrefixOrder:
  49 ..hidefromindex
  50 ..summary:The default prefix order.
  51 ..signature:DefaultPrefixOrder<T>::Type
  52 ..param.T:Type for which the prefix order is determined.
  53 ..returns.param.Type:Prefix order tag for type of $T$.
  54 ..see:Tag.Prefix Order
  55 */
  56 template <typename T>
  57 struct DefaultPrefixOrder
  58 {
  59         typedef TagPrefixLess Type;
  60 };
  61
  62 //////////////////////////////////////////////////////////////////////////////
  63 // Lexical
  64 //////////////////////////////////////////////////////////////////////////////
  65
  66 /**
  67 .Class.Lexical:
  68 ..cat:Basic
  69 ..summary:Comparator for lexical comparison.
  70 ..signature:Lexical<TSpec>
  71 ..param.TSpec:The specializing type.
  72 ...metafunction:Metafunction.Spec
  73 ...text:This type can be used for specializations of $Lexical$.
  74 ...remarks:$TSpec$ is by default interpreted as size-type.
  75 ...default:$size_t$
  76 ..remarks:
  77 ...text:This class implement comparator objects that perform (lexical) comparisons between two sequences.
  78 The result of the comparison is stored in the data members of the instance an can be
  79 accessed by some functions, for example @Function.isLess@ or @Function.isEqual@.
  80 ...text:In most cases, there is no need for an explicite use of comparators,
  81 but sometimes this concept provide the opportunity to speed up the code.
  82 ..example:
  83 ...text:This program compares the strings $str1$ and $str2$:
  84 ...code:if (isLess(str1, str2)) //first comparison
  85 {
  86         //str1 < str2
  87 }
  88 else if (isGreater(str1, str2)) //second comparison
  89 {
  90         //str1 > str2
  91 }
  92 else
  93 {
  94         //str == str2
  95 }
  96 ...text:Using a comparator, the same program only needs one comparison instead of two:
  97 ...code:Lexical <> comparator(str1, str2); //comparison is executed here
  98 if (isLess(comparator))
  99 {
 100         //str1 < str2
 101 }
 102 else if (lexGreater(comparator))
 103 {
 104         //str1 > str2
 105 }
 106 else
 107 {
 108         //str == str2
 109 }
 110 ...text:The state of a default constructed $Lexical$ instance is undefined until
 111 it is set by a call of @Function.compare@.
 112 ..see:Metafunction.Comparator
 113 */
 114
 115 template <typename TSpec = size_t>
 116 struct Lexical
 117 {
 118 public:
 119         typename Size<Lexical>::Type data_lcp;
 120         char data_compare;
 121
 122 public:
 123         Lexical()
 124         {
 125 SEQAN_CHECKPOINT
 126         }
 127
 128         template <typename TLeft, typename TRight>
 129         Lexical(TLeft const & left, TRight const & right)
 130         {
 131 SEQAN_CHECKPOINT
 132                 compare(*this, left, right);
 133         }
 134
 135         Lexical(Lexical const & other):
 136                 data_lcp(other.data_lcp),
 137                 data_compare(other.data_compare)
 138         {
 139 SEQAN_CHECKPOINT
 140         };
 141
 142         Lexical & operator=(Lexical const & other)
 143         {
 144 SEQAN_CHECKPOINT
 145                 data_compare = other.data_compare;
 146                 data_lcp = other.data_lcp;
 147                 return *this;
 148         }
 149
 150         ~Lexical() {}
 151 //____________________________________________________________________________
 152
 153         enum
 154         {
 155                 EQUAL = 1,
 156                 LESS = 2,
 157                 GREATER = 4,
 158                 LEFT_IS_PREFIX = 8,
 159                 RIGHT_IS_PREFIX = 16
 160         };
 161 };
 162
 163
 164 //////////////////////////////////////////////////////////////////////////////
 165 // Metafunctions
 166 //////////////////////////////////////////////////////////////////////////////
 167 // Comparator: returns object that can compare objects of type T
 168
 169 /**
 170 .Metafunction.Comparator:
 171 ..summary:Type of comparator object
 172 ..signature:Comparator<T>::Type
 173 ..param.T:Type for which the comparator type is to be determined.
 174 ..returns.param.Type:Comparator type
 175 ..remarks:Comparators are objects that can be used to compare other objects and store the
 176 result of comparisons.
 177 */
 178 template <typename T>
 179 struct Comparator
 180 {
 181         typedef Lexical<typename Size<T>::Type> Type;
 182 };
 183
 184 //////////////////////////////////////////////////////////////////////////////
 185 // Size
 186
 187 template <typename TSpec>
 188 struct Size<Lexical<TSpec> >
 189 {
 190         typedef TSpec Type;
 191 };
 192
 193 template <typename TSpec>
 194 struct Size<Lexical<TSpec> const>
 195 {
 196         typedef TSpec Type;
 197 };
 198
 199 //////////////////////////////////////////////////////////////////////////////
 200 // Spec
 201
 202 template <typename TSpec>
 203 struct Spec<Lexical<TSpec> >
 204 {
 205         typedef TSpec Type;
 206 };
 207
 208 template <typename TSpec>
 209 struct Spec<Lexical<TSpec> const>
 210 {
 211         typedef TSpec Type;
 212 };
 213
 214
 215 //////////////////////////////////////////////////////////////////////////////
 216 //////////////////////////////////////////////////////////////////////////////
 217 // compare
 218 //////////////////////////////////////////////////////////////////////////////
 219
 220 /**
 221 .Function.compare:
 222 ..cat:Comparisons
 223 ..summary:Compares two objects.
 224 ..signature:compare(comparator, left, right)
 225 ..param.left:The first objects.
 226 ..param.right:The second objects that is compared to $left$.
 227 ..param.comparator:Object that stores the results.
 228 ...type:Class.Lexical
 229 ..see:Metafunction.Comparator
 230 */
 231
 232 template <typename TSpec, typename TLeft, typename TRight>
 233 inline void
 234 compare_(Lexical<TSpec> & lexical,
 235                  TLeft & left,
 236                  TRight & right)
 237 {
 238 SEQAN_CHECKPOINT
 239         typedef typename Value<TLeft>::Type TLeftValue;
 240
 241         typename Iterator<TLeft, Standard>::Type left_it = begin(left, Standard());
 242         typename Size<TLeft>::Type left_length = length(left);
 243         typename Iterator<TRight, Standard>::Type right_it = begin(right, Standard());
 244         typename Size<TRight>::Type right_length = length(right);
 245
 246         if (left_length == right_length) lexical.data_compare = Lexical<TSpec>::EQUAL;
 247         else if (left_length < right_length) lexical.data_compare = Lexical<TSpec>::LEFT_IS_PREFIX;
 248         else
 249         {
 250                 lexical.data_compare = Lexical<TSpec>::RIGHT_IS_PREFIX;
 251                 left_length = right_length;
 252         }
 253
 254         lexical.data_lcp = 0;
 255         for (lexical.data_lcp = 0; lexical.data_lcp < left_length; ++lexical.data_lcp)
 256         {
 257                 if (*left_it < *right_it)
 258                 {
 259                         lexical.data_compare = Lexical<TSpec>::LESS;
 260                         break;
 261                 }
 262                 if (*left_it > *right_it)
 263                 {
 264                         lexical.data_compare = Lexical<TSpec>::GREATER;
 265                         break;
 266                 }
 267                 ++left_it;
 268                 ++right_it;
 269         }
 270 }
 271 //////////////////////////////////////////////////////////////////////////////
 272
 273 template <typename TSpec, typename TLeft, typename TRight>
 274 inline void
 275 compare(Lexical<TSpec> & lexical,
 276                 TLeft const & left,
 277                 TRight const & right)
 278 {
 279         compare_(lexical, left, right);
 280 }
 281
 282 //workaround for VC++ "const arrays" bug
 283 template <typename TSpec, typename TLeftValue, typename TRight>
 284 inline void
 285 compare(Lexical<TSpec> & lexical,
 286                 TLeftValue const * left,
 287                 TRight const & right)
 288 {
 289         compare_(lexical, left, right);
 290 }
 291 template <typename TSpec, typename TLeftValue, typename TRightValue>
 292 inline void
 293 compare(Lexical<TSpec> & lexical,
 294                 TLeftValue const * left,
 295                 TRightValue const * right)
 296 {
 297         compare_(lexical, left, right);
 298 }
 299 template <typename TSpec, typename TLeft, typename TRightValue>
 300 inline void
 301 compare(Lexical<TSpec> & lexical,
 302                 TLeft const & left,
 303                 TRightValue const * right)
 304 {
 305         compare_(lexical, left, right);
 306 }
 307
 308 //////////////////////////////////////////////////////////////////////////////
 309 // isEqual
 310 //////////////////////////////////////////////////////////////////////////////
 311
 312 /**
 313 .Function.isEqual:
 314 ..cat:Comparisons
 315 ..summary:Operator "==".
 316 ..signature:isEqual(left, right)
 317 ..signature:isEqual(comparator)
 318 ..param.left:The first parameter.
 319 ..param.right:The second parameter that is compared to $left$.
 320 ..param.comparator:A comparator.
 321 ...type:Class.Lexical
 322 ..returns:$true$ if $left$ equals $right$, $false$ otherwise.
 323 ..see:Metafunction.Comparator
 324 */
 325 template <typename TLeft, typename TRight >
 326 inline bool
 327 isEqual(TLeft const & left,
 328                 TRight const & right)
 329 {
 330 SEQAN_CHECKPOINT
 331         return left == right;
 332 }
 333
 334 template <typename TSpec>
 335 inline bool
 336 isEqual(Lexical<TSpec> const & _lex)
 337 {
 338 SEQAN_CHECKPOINT
 339         return (_lex.data_compare & Lexical<TSpec>::EQUAL);
 340 }
 341
 342 //////////////////////////////////////////////////////////////////////////////
 343 // isNotEqual
 344 //////////////////////////////////////////////////////////////////////////////
 345
 346 /**
 347 .Function.isNotEqual:
 348 ..cat:Comparisons
 349 ..summary:Operator "!=".
 350 ..signature:isNotEqual(left, right)
 351 ..signature:isNotEqual(comparator)
 352 ..param.left:The first parameter.
 353 ..param.right:The second parameter that is compared to $left$.
 354 ..param.comparator:A comparator.
 355 ...type:Class.Lexical
 356 ..returns:$true$ if $left$ is not equal to $right$, $false$ otherwise.
 357 ..see:Metafunction.Comparator
 358 */
 359 template <typename TLeft, typename TRight >
 360 inline bool
 361 isNotEqual(TLeft const & left,
 362                  TRight const & right)
 363 {
 364 SEQAN_CHECKPOINT
 365         return left != right;
 366 }
 367
 368 template <typename TSpec>
 369 inline bool
 370 isNotEqual(Lexical<TSpec> const & _lex)
 371 {
 372 SEQAN_CHECKPOINT
 373         return !(_lex.data_compare & Lexical<TSpec>::EQUAL);
 374 }
 375
 376 //////////////////////////////////////////////////////////////////////////////
 377 // isLess
 378 //////////////////////////////////////////////////////////////////////////////
 379
 380 /**
 381 .Function.isLess:
 382 ..cat:Comparisons
 383 ..summary:Operator "<".
 384 ..signature:isLess(left, right [, prefix_order_tag])
 385 ..signature:isLess(comparator)
 386 ..param.left:The first parameter.
 387 ..param.right:The second parameter that is compared to $left$.
 388 ..param.prefix_order_tag:Tag that specify whether prefixes are less or greater. (optional)
 389 ...text:If omitted, the default tag is determined by @Metafunction.DefaultPrefixOrder@ for the type of $left$.
 390 ...see:Tag.Prefix Order
 391 ..param.comparator:A comparator.
 392 ...type:Class.Lexical
 393 ..returns:$true$ if $left$ is less than $right$, $false$ otherwise.
 394 ..see:Metafunction.Comparator
 395 ..remarks:
 396 ...text:Sequences are compared in lexicographical order.
 397 ..see:Tag.Prefix Order
 398 ..see:Metafunction.DefaultPrefixOrder
 399 */
 400 template <typename TLeft, typename TRight, typename TPrefixOrder >
 401 inline bool
 402 isLess(TLeft const & left,
 403            TRight const & right,
 404            Tag<TPrefixOrder> const tag)
 405 {
 406 SEQAN_CHECKPOINT
 407         typename Comparator<TLeft>::Type _lex(left, right);
 408     return isLess(_lex, tag);
 409 }
 410 template <typename TLeft, typename TRight>
 411 inline bool
 412 isLess(TLeft const & left,
 413            TRight const & right)
 414 {
 415 SEQAN_CHECKPOINT
 416         return left < right;
 417 }
 418
 419 template <typename TSpec>
 420 inline bool
 421 isLess(Lexical<TSpec> const & _lex,
 422            TagPrefixLess)
 423 {
 424 SEQAN_CHECKPOINT
 425    return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::LEFT_IS_PREFIX));
 426 }
 427 template <typename TSpec>
 428 inline bool
 429 isLess(Lexical<TSpec> const & _lex,
 430            TagPrefixGreater)
 431 {
 432 SEQAN_CHECKPOINT
 433    return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::RIGHT_IS_PREFIX));
 434 }
 435 template <typename TSpec>
 436 inline bool
 437 isLess(Lexical<TSpec> const & _lex)
 438 {
 439 SEQAN_CHECKPOINT
 440         return isLess(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
 441 }
 442
 443 //////////////////////////////////////////////////////////////////////////////
 444 // isLessOrEqual
 445 //////////////////////////////////////////////////////////////////////////////
 446
 447 /**
 448 .Function.isLessOrEqual:
 449 ..cat:Comparisons
 450 ..summary:Operator "<=".
 451 ..signature:isLessOrEqual(left, right [, prefix_order_tag])
 452 ..signature:isLessOrEqual(comparator)
 453 ..param.left:The first parameter.
 454 ..param.right:The second parameter that is compared to $left$.
 455 ..param.prefix_order_tag:Tag that specify whether prefixes are less or greater. (optional)
 456 ...text:If omitted, the default tag is determined by @Metafunction.DefaultPrefixOrder@ for the type of $left$.
 457 ...see:Tag.Prefix Order
 458 ..param.comparator:A comparator.
 459 ...type:Class.Lexical
 460 ..returns:$true$ if $left$ is less than or equal to $right$, $false$ otherwise.
 461 ..see:Metafunction.Comparator
 462 ..remarks:
 463 ...text:Sequences are compared in lexicographical order.
 464 ..see:Tag.Prefix Order
 465 ..see:Metafunction.DefaultPrefixOrder
 466 */
 467
 468 template <typename TLeft, typename TRight, typename TPrefixOrder >
 469 inline bool
 470 isLessOrEqual(TLeft const & left,
 471                 TRight const & right,
 472                 Tag<TPrefixOrder> const tag)
 473 {
 474 SEQAN_CHECKPOINT
 475         typename Comparator<TLeft>::Type _lex(left, right);
 476     return isLessOrEqual(_lex, tag);
 477 }
 478 template <typename TLeft, typename TRight>
 479 inline bool
 480 isLessOrEqual(TLeft const & left,
 481                 TRight const & right)
 482 {
 483 SEQAN_CHECKPOINT
 484         return left <= right;
 485 }
 486
 487 template <typename TSpec>
 488 inline bool
 489 isLessOrEqual(Lexical<TSpec> const & _lex,
 490                 TagPrefixLess)
 491 {
 492 SEQAN_CHECKPOINT
 493    return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::EQUAL | Lexical<TSpec>::LEFT_IS_PREFIX));
 494 }
 495 template <typename TSpec>
 496 inline bool
 497 isLessOrEqual(Lexical<TSpec> const & _lex,
 498                 TagPrefixGreater)
 499 {
 500 SEQAN_CHECKPOINT
 501    return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::EQUAL | Lexical<TSpec>::RIGHT_IS_PREFIX));
 502 }
 503 template <typename TSpec>
 504 inline bool
 505 isLessOrEqual(Lexical<TSpec> const & _lex)
 506 {
 507 SEQAN_CHECKPOINT
 508         return isLessOrEqual(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
 509 }
 510
 511 //////////////////////////////////////////////////////////////////////////////
 512 // isGreater
 513 //////////////////////////////////////////////////////////////////////////////
 514
 515 /**
 516 .Function.isGreater:
 517 ..cat:Comparisons
 518 ..summary:Operator ">".
 519 ..signature:isGreater(left, right [, prefix_order_tag])
 520 ..signature:isGreater(comparator)
 521 ..param.left:The first parameter.
 522 ..param.right:The second parameter that is compared to $left$.
 523 ..param.prefix_order_tag:Tag that specify whether prefixes are less or greater. (optional)
 524 ...text:If omitted, the default tag is determined by @Metafunction.DefaultPrefixOrder@ for the type of $left$.
 525 ...see:Tag.Prefix Order
 526 ..param.comparator:A comparator.
 527 ...type:Class.Lexical
 528 ..returns:$true$ if $left$ is greater than $right$, $false$ otherwise.
 529 ..see:Metafunction.Comparator
 530 ..remarks:
 531 ...text:Sequences are compared in lexicographical order.
 532 ..see:Tag.Prefix Order
 533 ..see:Metafunction.DefaultPrefixOrder
 534 */
 535 template <typename TLeft, typename TRight, typename TPrefixOrder >
 536 inline bool
 537 isGreater(TLeft const & left,
 538                 TRight const & right,
 539                 Tag<TPrefixOrder> const tag)
 540 {
 541 SEQAN_CHECKPOINT
 542         typename Comparator<TLeft>::Type _lex(left, right);
 543     return isGreater(_lex, tag);
 544 }
 545 template <typename TLeft, typename TRight>
 546 inline bool
 547 isGreater(TLeft const & left,
 548                 TRight const & right)
 549 {
 550 SEQAN_CHECKPOINT
 551         return left > right;
 552 }
 553
 554 template <typename TSpec>
 555 inline bool
 556 isGreater(Lexical<TSpec> const & _lex,
 557                 TagPrefixLess)
 558 {
 559 SEQAN_CHECKPOINT
 560    return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::RIGHT_IS_PREFIX));
 561 }
 562 template <typename TSpec>
 563 inline bool
 564 isGreater(Lexical<TSpec> const & _lex,
 565                 TagPrefixGreater)
 566 {
 567 SEQAN_CHECKPOINT
 568    return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::LEFT_IS_PREFIX));
 569 }
 570 template <typename TSpec>
 571 inline bool
 572 isGreater(Lexical<TSpec> const & _lex)
 573 {
 574 SEQAN_CHECKPOINT
 575         return isGreater(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
 576 }
 577
 578 //////////////////////////////////////////////////////////////////////////////
 579 // isGreaterOrEqual
 580 //////////////////////////////////////////////////////////////////////////////
 581
 582 /**
 583 .Function.isGreaterOrEqual:
 584 ..cat:Comparisons
 585 ..summary:Operator ">=".
 586 ..signature:isGreaterOrEqual(left, right [, prefix_order_tag])
 587 ..signature:isGreaterOrEqual(comparator)
 588 ..param.left:The first parameter.
 589 ..param.right:The second parameter that is compared to $left$.
 590 ..param.prefix_order_tag:Tag that specify whether prefixes are less or greater. (optional)
 591 ...text:If omitted, the default tag is determined by @Metafunction.DefaultPrefixOrder@ for the type of $left$.
 592 ...see:Tag.Prefix Order
 593 ..param.comparator:A comparator.
 594 ...type:Class.Lexical
 595 ..returns:$true$ if $left$ is greater than or equal to $right$, $false$ otherwise.
 596 ..see:Metafunction.Comparator
 597 ..remarks:
 598 ...text:Sequences are compared in lexicographical order.
 599 ..see:Tag.Prefix Order
 600 ..see:Metafunction.DefaultPrefixOrder
 601 */
 602
 603 template <typename TLeft, typename TRight, typename TPrefixOrder >
 604 inline bool
 605 isGreaterOrEqual(TLeft const & left,
 606                 TRight const & right,
 607                 Tag<TPrefixOrder> const tag)
 608 {
 609 SEQAN_CHECKPOINT
 610         typename Comparator<TLeft>::Type _lex(left, right);
 611     return isGreaterOrEqual(_lex, tag);
 612 }
 613 template <typename TLeft, typename TRight>
 614 inline bool
 615 isGreaterOrEqual(TLeft const & left,
 616                 TRight const & right)
 617 {
 618 SEQAN_CHECKPOINT
 619         return left >= right;
 620 }
 621
 622 template <typename TSpec>
 623 inline bool
 624 isGreaterOrEqual(Lexical<TSpec> const & _lex,
 625                 TagPrefixLess)
 626 {
 627 SEQAN_CHECKPOINT
 628    return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::EQUAL | Lexical<TSpec>::RIGHT_IS_PREFIX));
 629 }
 630 template <typename TSpec>
 631 inline bool
 632 isGreaterOrEqual(Lexical<TSpec> const & _lex,
 633                 TagPrefixGreater)
 634 {
 635 SEQAN_CHECKPOINT
 636    return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::EQUAL | Lexical<TSpec>::LEFT_IS_PREFIX));
 637 }
 638 template <typename TSpec>
 639 inline bool
 640 isGreaterOrEqual(Lexical<TSpec> const & _lex)
 641 {
 642 SEQAN_CHECKPOINT
 643         return isGreaterOrEqual(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
 644 }
 645
 646 //////////////////////////////////////////////////////////////////////////////
 647 // isPrefix
 648 //////////////////////////////////////////////////////////////////////////////
 649
 650 /**
 651 .Function.isPrefix:
 652 ..cat:Comparisons
 653 ..summary:Test whether a sequence is prefix of another sequence.
 654 ..signature:isPrefix(left, right)
 655 ..signature:isPrefix(comparator)
 656 ..param.left:The first sequence, the putative prefix.
 657 ..param.right:The second sequence.
 658 ..param.comparator:A comparator.
 659 ...type:Class.Lexical
 660 ..returns:$true$ if $left$ is a prefix of $right$, $false$ otherwise.
 661 ..see:Metafunction.Comparator
 662 ..remarks:By definition, the whole sequence is a prefix of itself too: $isPrefix("abc", "abc") == true$.
 663 */
 664
 665 template <typename TLeft, typename TRight >
 666 inline bool
 667 isPrefix(TLeft const & left,
 668                 TRight const & right)
 669 {
 670 SEQAN_CHECKPOINT
 671         typename Comparator<TLeft>::Type _lex(left, right);
 672     return isPrefix(_lex);
 673 }
 674 template <typename TSpec>
 675 inline bool
 676 isPrefix(Lexical<TSpec> const & _lex)
 677 {
 678 SEQAN_CHECKPOINT
 679     return (_lex.data_compare & (Lexical<TSpec>::LEFT_IS_PREFIX | Lexical<TSpec>::EQUAL));
 680 }
 681
 682
 683 //////////////////////////////////////////////////////////////////////////////
 684 // hasPrefix
 685 //////////////////////////////////////////////////////////////////////////////
 686
 687 /**
 688 .Function.hasPrefix:
 689 ..cat:Comparisons
 690 ..summary:Test whether a sequence is prefix of another sequence.
 691 ..signature:hasPrefix(left, right)
 692 ..signature:hasPrefix(comparator)
 693 ..param.left:The first sequence.
 694 ..param.right:The second sequence, the putative prefix.
 695 ..param.comparator:A comparator.
 696 ...type:Class.Lexical
 697 ..returns:$true$ if $right$ is a prefix of $left$, $false$ otherwise.
 698 ..see:Metafunction.Comparator
 699 ..see:Function.isPrefix
 700 ..remarks:By definition, the whole sequence is a prefix of itself too: $hasPrefix("abc", "abc") == true$.
 701 */
 702
 703 template <typename TLeft, typename TRight >
 704 inline bool
 705 hasPrefix(TLeft const & left,
 706                 TRight const & right)
 707 {
 708 SEQAN_CHECKPOINT
 709         typename Comparator<TLeft>::Type _lex(left, right);
 710     return hasPrefix(_lex);
 711 }
 712 template <typename TSpec>
 713 inline bool
 714 hasPrefix(Lexical<TSpec> const & _lex)
 715 {
 716 SEQAN_CHECKPOINT
 717     return (_lex.data_compare & (Lexical<TSpec>::RIGHT_IS_PREFIX | Lexical<TSpec>::EQUAL));
 718 }
 719
 720 //////////////////////////////////////////////////////////////////////////////
 721 // lcpLength
 722 //////////////////////////////////////////////////////////////////////////////
 723 /**
 724 .Function.lcpLength:
 725 ..summary:Length of longest common prefix.
 726 ..cat:Comparisons
 727 ..signature:lcpLength(left, right)
 728 ..signature:lcpLength(comparator)
 729 ..param.left:The first sequence.
 730 ..param.right:The second sequence that is compared to $left$.
 731 ..param.comparator:A comparator.
 732 ...type:Class.Lexical
 733 ..returns:The length of the longest common prefix of $left$ and $right$.
 734 ..see:Metafunction.Comparator
 735 */
 736 template <typename TLeft, typename TRight >
 737 inline typename Size<TLeft>::Type
 738 lcpLength(TLeft const & left, TRight const & right)
 739 {
 740 SEQAN_CHECKPOINT
 741         typename Comparator<TLeft>::Type _lex(left, right);
 742     return lcpLength(_lex);
 743 }
 744
 745 template <typename TSpec>
 746 inline typename Size< Lexical<TSpec> >::Type
 747 lcpLength(Lexical<TSpec> const & _lex)
 748 {
 749 SEQAN_CHECKPOINT
 750     return _lex.data_lcp;
 751 }
 752
 753 //////////////////////////////////////////////////////////////////////////////
 754 // lcpLength
 755 //////////////////////////////////////////////////////////////////////////////
 756 /**
 757 .Function.ordValue:
 758 ..summary:Maps an alphabet 1-to-1 to the interval [0..ValueSize).
 759 ..cat:Alphabets
 760 ..signature:ordValue(value)
 761 ..param.value:Arbitrary character value.
 762 ...type:Class.SimpleType
 763 ..returns:An $unsigned int$ between 0 and @Metafunction.ValueSize@ of the type of value.
 764 ..note:This function first converts value to its unsigned value type and after that to an $unsigned int$.
 765 You can't use $(unsigned int)c$ for a character $c$ as on some systems $char$ is signed and a $-1$ would be mapped to $0xffffffff$ instead of $0x000000ff$.
 766 */
 767
 768 template <typename TValue>
 769 inline unsigned ordValue(TValue const &c)
 770 {
 771         return (typename _MakeUnsigned<TValue>::Type const &)c;
 772 }
 773
 774 template <typename TValue, typename TSpec>
 775 inline unsigned ordValue(SimpleType<TValue,TSpec> const &c)
 776 {
 777         return c;
 778 }
 779
 780
 781
 782 //////////////////////////////////////////////////////////////////////////////
 783
 784
 785 } //namespace SEQAN_NAMESPACE_MAIN
 786
 787 #endif //#ifndef SEQAN_HEADER_...