SeqAn-1.1/seqan/index/index_qgram_find.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: index_qgram_find.h,v 1.1 2008/08/25 16:20:05 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_INDEX_QGRAM_FIND_H
  22 #define SEQAN_HEADER_INDEX_QGRAM_FIND_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26
  27 //////////////////////////////////////////////////////////////////////////////
  28 // QGram finders
  29
  30         struct _Finder_QGramLookup; //Finder that simply looks up the q-gram in the hash table
  31
  32 /**
  33 .Tag.Index Find Algorithm
  34 ..tag.QGram_FIND_Lookup:q-gram search.
  35 Finds q-grams in a @Spec.Index_QGram@ index using the hash table.
  36 */
  37
  38         typedef Tag<_Finder_QGramLookup> const QGram_FIND_Lookup;
  39
  40 //____________________________________________________________________________
  41
  42
  43         template < typename TText, typename TShapeSpec, typename TSpec >
  44         struct DefaultFinder<Index<TText, Index_QGram<TShapeSpec, TSpec> > > {
  45         typedef QGram_FIND_Lookup Type;
  46     };
  47
  48
  49 //////////////////////////////////////////////////////////////////////////////
  50 // _findFirstIndex implementation
  51
  52         template < typename TText, typename TSpec, typename TSpecFinder, typename TPattern >
  53         inline void _findFirstIndex(
  54                 Finder< Index<TText, TSpec>, TSpecFinder > &finder,
  55                 TPattern const &pattern,
  56                 QGram_FIND_Lookup const)
  57         {
  58                 typedef Index<TText, TSpec>                                                                     TIndex;
  59                 typedef typename Fibre<TIndex, QGram_SA>::Type                          TSA;
  60                 typedef typename Fibre<TIndex, QGram_Shape>::Type                       TShape;
  61                 typedef typename Fibre<TIndex, QGram_Dir>::Type                         TDir;
  62                 typedef typename Iterator<TSA const, Standard>::Type            TSAIterator;
  63                 typedef typename Iterator<TPattern const, Standard>::Type       TPatternIterator;
  64
  65                 TIndex &index = haystack(finder);
  66                 indexRequire(index, QGram_SADir());
  67
  68                 TSAIterator saIt = begin(indexSA(index), Standard());
  69                 TPatternIterator pIt = begin(pattern, Standard());
  70                 TDir const &dir = indexDir(index);
  71                 TShape &shape = indexShape(index);
  72
  73                 finder.range.i1 = saIt + dir[hash(shape, pIt, length(pattern))];
  74                 finder.range.i2 = saIt + dir[hashUpper(shape, pIt, length(pattern))];
  75         }
  76
  77
  78 //////////////////////////////////////////////////////////////////////////////
  79
  80 } //namespace SEQAN_NAMESPACE_MAIN
  81
  82 #endif //#ifndef SEQAN_HEADER_