1 /*==========================================================================
2 SeqAn - The Library for Sequence Analysis
4 ============================================================================
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.
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.
17 ============================================================================
18 $Id: lexical.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_LEXICAL_H
22 #define SEQAN_HEADER_LEXICAL_H
25 namespace SEQAN_NAMESPACE_MAIN
27 //////////////////////////////////////////////////////////////////////////////
28 // Switches for prefix ordering mode
29 //////////////////////////////////////////////////////////////////////////////
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$.
40 struct TagPrefixLess_ {};
41 typedef Tag<TagPrefixLess_> const TagPrefixLess;
43 struct TagPrefixGreater_ {};
44 typedef Tag<TagPrefixGreater_> const TagPrefixGreater;
48 .Metafunction.DefaultPrefixOrder:
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
57 struct DefaultPrefixOrder
59 typedef TagPrefixLess Type;
62 //////////////////////////////////////////////////////////////////////////////
64 //////////////////////////////////////////////////////////////////////////////
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.
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.
83 ...text:This program compares the strings $str1$ and $str2$:
84 ...code:if (isLess(str1, str2)) //first comparison
88 else if (isGreater(str1, str2)) //second comparison
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))
102 else if (lexGreater(comparator))
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
115 template <typename TSpec = size_t>
119 typename Size<Lexical>::Type data_lcp;
128 template <typename TLeft, typename TRight>
129 Lexical(TLeft const & left, TRight const & right)
132 compare(*this, left, right);
135 Lexical(Lexical const & other):
136 data_lcp(other.data_lcp),
137 data_compare(other.data_compare)
142 Lexical & operator=(Lexical const & other)
145 data_compare = other.data_compare;
146 data_lcp = other.data_lcp;
151 //____________________________________________________________________________
164 //////////////////////////////////////////////////////////////////////////////
166 //////////////////////////////////////////////////////////////////////////////
167 // Comparator: returns object that can compare objects of type T
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.
178 template <typename T>
181 typedef Lexical<typename Size<T>::Type> Type;
184 //////////////////////////////////////////////////////////////////////////////
187 template <typename TSpec>
188 struct Size<Lexical<TSpec> >
193 template <typename TSpec>
194 struct Size<Lexical<TSpec> const>
199 //////////////////////////////////////////////////////////////////////////////
202 template <typename TSpec>
203 struct Spec<Lexical<TSpec> >
208 template <typename TSpec>
209 struct Spec<Lexical<TSpec> const>
215 //////////////////////////////////////////////////////////////////////////////
216 //////////////////////////////////////////////////////////////////////////////
218 //////////////////////////////////////////////////////////////////////////////
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
232 template <typename TSpec, typename TLeft, typename TRight>
234 compare_(Lexical<TSpec> & lexical,
239 typedef typename Value<TLeft>::Type TLeftValue;
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);
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;
250 lexical.data_compare = Lexical<TSpec>::RIGHT_IS_PREFIX;
251 left_length = right_length;
254 lexical.data_lcp = 0;
255 for (lexical.data_lcp = 0; lexical.data_lcp < left_length; ++lexical.data_lcp)
257 if (*left_it < *right_it)
259 lexical.data_compare = Lexical<TSpec>::LESS;
262 if (*left_it > *right_it)
264 lexical.data_compare = Lexical<TSpec>::GREATER;
271 //////////////////////////////////////////////////////////////////////////////
273 template <typename TSpec, typename TLeft, typename TRight>
275 compare(Lexical<TSpec> & lexical,
277 TRight const & right)
279 compare_(lexical, left, right);
282 //workaround for VC++ "const arrays" bug
283 template <typename TSpec, typename TLeftValue, typename TRight>
285 compare(Lexical<TSpec> & lexical,
286 TLeftValue const * left,
287 TRight const & right)
289 compare_(lexical, left, right);
291 template <typename TSpec, typename TLeftValue, typename TRightValue>
293 compare(Lexical<TSpec> & lexical,
294 TLeftValue const * left,
295 TRightValue const * right)
297 compare_(lexical, left, right);
299 template <typename TSpec, typename TLeft, typename TRightValue>
301 compare(Lexical<TSpec> & lexical,
303 TRightValue const * right)
305 compare_(lexical, left, right);
308 //////////////////////////////////////////////////////////////////////////////
310 //////////////////////////////////////////////////////////////////////////////
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
325 template <typename TLeft, typename TRight >
327 isEqual(TLeft const & left,
328 TRight const & right)
331 return left == right;
334 template <typename TSpec>
336 isEqual(Lexical<TSpec> const & _lex)
339 return (_lex.data_compare & Lexical<TSpec>::EQUAL);
342 //////////////////////////////////////////////////////////////////////////////
344 //////////////////////////////////////////////////////////////////////////////
347 .Function.isNotEqual:
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
359 template <typename TLeft, typename TRight >
361 isNotEqual(TLeft const & left,
362 TRight const & right)
365 return left != right;
368 template <typename TSpec>
370 isNotEqual(Lexical<TSpec> const & _lex)
373 return !(_lex.data_compare & Lexical<TSpec>::EQUAL);
376 //////////////////////////////////////////////////////////////////////////////
378 //////////////////////////////////////////////////////////////////////////////
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
396 ...text:Sequences are compared in lexicographical order.
397 ..see:Tag.Prefix Order
398 ..see:Metafunction.DefaultPrefixOrder
400 template <typename TLeft, typename TRight, typename TPrefixOrder >
402 isLess(TLeft const & left,
403 TRight const & right,
404 Tag<TPrefixOrder> const tag)
407 typename Comparator<TLeft>::Type _lex(left, right);
408 return isLess(_lex, tag);
410 template <typename TLeft, typename TRight>
412 isLess(TLeft const & left,
413 TRight const & right)
419 template <typename TSpec>
421 isLess(Lexical<TSpec> const & _lex,
425 return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::LEFT_IS_PREFIX));
427 template <typename TSpec>
429 isLess(Lexical<TSpec> const & _lex,
433 return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::RIGHT_IS_PREFIX));
435 template <typename TSpec>
437 isLess(Lexical<TSpec> const & _lex)
440 return isLess(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
443 //////////////////////////////////////////////////////////////////////////////
445 //////////////////////////////////////////////////////////////////////////////
448 .Function.isLessOrEqual:
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
463 ...text:Sequences are compared in lexicographical order.
464 ..see:Tag.Prefix Order
465 ..see:Metafunction.DefaultPrefixOrder
468 template <typename TLeft, typename TRight, typename TPrefixOrder >
470 isLessOrEqual(TLeft const & left,
471 TRight const & right,
472 Tag<TPrefixOrder> const tag)
475 typename Comparator<TLeft>::Type _lex(left, right);
476 return isLessOrEqual(_lex, tag);
478 template <typename TLeft, typename TRight>
480 isLessOrEqual(TLeft const & left,
481 TRight const & right)
484 return left <= right;
487 template <typename TSpec>
489 isLessOrEqual(Lexical<TSpec> const & _lex,
493 return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::EQUAL | Lexical<TSpec>::LEFT_IS_PREFIX));
495 template <typename TSpec>
497 isLessOrEqual(Lexical<TSpec> const & _lex,
501 return (_lex.data_compare & (Lexical<TSpec>::LESS | Lexical<TSpec>::EQUAL | Lexical<TSpec>::RIGHT_IS_PREFIX));
503 template <typename TSpec>
505 isLessOrEqual(Lexical<TSpec> const & _lex)
508 return isLessOrEqual(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
511 //////////////////////////////////////////////////////////////////////////////
513 //////////////////////////////////////////////////////////////////////////////
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
531 ...text:Sequences are compared in lexicographical order.
532 ..see:Tag.Prefix Order
533 ..see:Metafunction.DefaultPrefixOrder
535 template <typename TLeft, typename TRight, typename TPrefixOrder >
537 isGreater(TLeft const & left,
538 TRight const & right,
539 Tag<TPrefixOrder> const tag)
542 typename Comparator<TLeft>::Type _lex(left, right);
543 return isGreater(_lex, tag);
545 template <typename TLeft, typename TRight>
547 isGreater(TLeft const & left,
548 TRight const & right)
554 template <typename TSpec>
556 isGreater(Lexical<TSpec> const & _lex,
560 return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::RIGHT_IS_PREFIX));
562 template <typename TSpec>
564 isGreater(Lexical<TSpec> const & _lex,
568 return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::LEFT_IS_PREFIX));
570 template <typename TSpec>
572 isGreater(Lexical<TSpec> const & _lex)
575 return isGreater(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
578 //////////////////////////////////////////////////////////////////////////////
580 //////////////////////////////////////////////////////////////////////////////
583 .Function.isGreaterOrEqual:
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
598 ...text:Sequences are compared in lexicographical order.
599 ..see:Tag.Prefix Order
600 ..see:Metafunction.DefaultPrefixOrder
603 template <typename TLeft, typename TRight, typename TPrefixOrder >
605 isGreaterOrEqual(TLeft const & left,
606 TRight const & right,
607 Tag<TPrefixOrder> const tag)
610 typename Comparator<TLeft>::Type _lex(left, right);
611 return isGreaterOrEqual(_lex, tag);
613 template <typename TLeft, typename TRight>
615 isGreaterOrEqual(TLeft const & left,
616 TRight const & right)
619 return left >= right;
622 template <typename TSpec>
624 isGreaterOrEqual(Lexical<TSpec> const & _lex,
628 return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::EQUAL | Lexical<TSpec>::RIGHT_IS_PREFIX));
630 template <typename TSpec>
632 isGreaterOrEqual(Lexical<TSpec> const & _lex,
636 return (_lex.data_compare & (Lexical<TSpec>::GREATER | Lexical<TSpec>::EQUAL | Lexical<TSpec>::LEFT_IS_PREFIX));
638 template <typename TSpec>
640 isGreaterOrEqual(Lexical<TSpec> const & _lex)
643 return isGreaterOrEqual(_lex, typename DefaultPrefixOrder< Lexical<TSpec> >::Type());
646 //////////////////////////////////////////////////////////////////////////////
648 //////////////////////////////////////////////////////////////////////////////
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$.
665 template <typename TLeft, typename TRight >
667 isPrefix(TLeft const & left,
668 TRight const & right)
671 typename Comparator<TLeft>::Type _lex(left, right);
672 return isPrefix(_lex);
674 template <typename TSpec>
676 isPrefix(Lexical<TSpec> const & _lex)
679 return (_lex.data_compare & (Lexical<TSpec>::LEFT_IS_PREFIX | Lexical<TSpec>::EQUAL));
683 //////////////////////////////////////////////////////////////////////////////
685 //////////////////////////////////////////////////////////////////////////////
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$.
703 template <typename TLeft, typename TRight >
705 hasPrefix(TLeft const & left,
706 TRight const & right)
709 typename Comparator<TLeft>::Type _lex(left, right);
710 return hasPrefix(_lex);
712 template <typename TSpec>
714 hasPrefix(Lexical<TSpec> const & _lex)
717 return (_lex.data_compare & (Lexical<TSpec>::RIGHT_IS_PREFIX | Lexical<TSpec>::EQUAL));
720 //////////////////////////////////////////////////////////////////////////////
722 //////////////////////////////////////////////////////////////////////////////
725 ..summary:Length of longest common prefix.
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
736 template <typename TLeft, typename TRight >
737 inline typename Size<TLeft>::Type
738 lcpLength(TLeft const & left, TRight const & right)
741 typename Comparator<TLeft>::Type _lex(left, right);
742 return lcpLength(_lex);
745 template <typename TSpec>
746 inline typename Size< Lexical<TSpec> >::Type
747 lcpLength(Lexical<TSpec> const & _lex)
750 return _lex.data_lcp;
753 //////////////////////////////////////////////////////////////////////////////
755 //////////////////////////////////////////////////////////////////////////////
758 ..summary:Maps an alphabet 1-to-1 to the interval [0..ValueSize).
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$.
768 template <typename TValue>
769 inline unsigned ordValue(TValue const &c)
771 return (typename _MakeUnsigned<TValue>::Type const &)c;
774 template <typename TValue, typename TSpec>
775 inline unsigned ordValue(SimpleType<TValue,TSpec> const &c)
782 //////////////////////////////////////////////////////////////////////////////
785 } //namespace SEQAN_NAMESPACE_MAIN
787 #endif //#ifndef SEQAN_HEADER_...