SeqAn-1.1/seqan/index/index_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_find.h,v 1.1 2008/08/25 16:20:05 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_INDEX_FIND_H
  22 #define SEQAN_HEADER_INDEX_FIND_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26
  27 //////////////////////////////////////////////////////////////////////////////
  28
  29         template < typename TText, typename TSpec, typename TSpecFinder >
  30         struct Position< Finder< Index<TText, TSpec>, TSpecFinder > >:
  31                 SAValue< Index<TText, TSpec> > {};
  32
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 // generic Finder class for all indices containing a suffix array or
  36 // similar table, where a query result is an interval in this table
  37 //
  38 // your index must specialize the function _findFirstIndex and set
  39 // finder.range to the interval containing the query hits. See:
  40 //
  41 //      template < typename TText, typename TSpec, typename TSpecFinder, typename TPattern >
  42 //      inline void _findFirstIndex(
  43 //              Finder< Index<TText, TSpec>, TSpecFinder > &finder,
  44 //              TPattern const &pattern,
  45 //              ESA_FIND_MLR const)
  46 //      {
  47 //              Index<TText, TSpec> &index = haystack(finder);
  48 //              indexRequire(index, ESA_SA());
  49 //              finder.range = equalRangeSAIterator(indexText(index), indexSA(index), pattern);
  50 //      }
  51
  52         template < typename TText, typename TSpec, typename TSpecFinder >
  53         class Finder< Index<TText, TSpec>, TSpecFinder >
  54         {
  55     protected:
  56                 typedef Index<TText, TSpec>                                                             TIndex;
  57                 typedef typename Fibre<TIndex, Fibre_SA>::Type                  TSA;
  58                 typedef typename Iterator<TSA const, Standard>::Type    TIterator;
  59
  60         public:
  61                 Holder<TIndex>  index;
  62                 Pair<TIterator> range;
  63                 TIterator               data_iterator;
  64
  65                 Finder()
  66                 {
  67                         clear(*this);
  68                 }
  69                 Finder(TIndex &_index): index(_index)
  70                 {
  71                         clear(*this);
  72                 }
  73                 Finder(TIndex const &_index): index(_index)
  74                 {
  75                         clear(*this);
  76                 }
  77         };
  78
  79 //____________________________________________________________________________
  80
  81         template < typename TText, typename TSpec, typename TSpecFinder >
  82         inline typename _Parameter< Index<TText, TSpec> >::Type
  83         host(Finder< Index<TText, TSpec>, TSpecFinder > & me)
  84         {
  85 SEQAN_CHECKPOINT
  86                 return value(me.index);
  87         }
  88
  89         template < typename TText, typename TSpec, typename TSpecFinder >
  90         inline typename _Parameter< Index<TText, TSpec> >::Type
  91         host(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
  92         {
  93 SEQAN_CHECKPOINT
  94                 return value(me.index);
  95         }
  96
  97         template < typename TText, typename TSpec, typename TSpecFinder >
  98         inline typename _Parameter< Index<TText, TSpec> >::Type
  99         container(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 100         {
 101 SEQAN_CHECKPOINT
 102                 return value(me.index);
 103         }
 104
 105         template < typename TText, typename TSpec, typename TSpecFinder >
 106         inline typename _Parameter< Index<TText, TSpec> >::Type
 107         container(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
 108         {
 109 SEQAN_CHECKPOINT
 110                 return value(me.index);
 111         }
 112
 113 //____________________________________________________________________________
 114
 115         template < typename TText, typename TSpec, typename TSpecFinder >
 116         inline void
 117         setHost(
 118                 Finder< Index<TText, TSpec>, TSpecFinder > & me,
 119                 typename _Parameter<Index<TText, TSpec> >::Type container_)
 120         {
 121 SEQAN_CHECKPOINT
 122                 me.index = container;
 123         }
 124
 125         template < typename TText, typename TSpec, typename TSpecFinder >
 126         inline void
 127         setContainer(
 128                 Finder< Index<TText, TSpec>, TSpecFinder > & me,
 129                 typename _Parameter<Index<TText, TSpec> >::Type container_)
 130         {
 131 SEQAN_CHECKPOINT
 132                 me.index = container;
 133         }
 134
 135 //____________________________________________________________________________
 136
 137         template < typename TText, typename TSpec, typename TSpecFinder >
 138         inline typename Iterator< typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type, Standard>::Type &
 139         hostIterator(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 140         {
 141 SEQAN_CHECKPOINT
 142                 return me.data_iterator;
 143         }
 144
 145         template < typename TText, typename TSpec, typename TSpecFinder >
 146         inline typename Iterator< typename Fibre<Index<TText, TSpec>, Fibre_SA>::Type, Standard>::Type const &
 147         hostIterator(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
 148         {
 149 SEQAN_CHECKPOINT
 150                 return me.data_iterator;
 151         }
 152
 153
 154 //____________________________________________________________________________
 155
 156         template < typename TText, typename TSpec, typename TSpecFinder >
 157         inline bool
 158         empty(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 159         {
 160 SEQAN_CHECKPOINT
 161                 return me.range.i1 == me.range.i2;
 162         }
 163
 164         template < typename TText, typename TSpec, typename TSpecFinder >
 165         inline void
 166         clear(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 167         {
 168 SEQAN_CHECKPOINT
 169                 typedef Index<TText, TSpec>                                             TIndex;
 170                 typedef typename Fibre<TIndex, Fibre_SA>::Type  TSA;
 171                 typedef typename Iterator<TSA, Standard>::Type  TIterator;
 172                 me.range.i1 = me.range.i2 = TIterator();
 173         }
 174
 175 //____________________________________________________________________________
 176
 177         template < typename TText, typename TSpec, typename TSpecFinder >
 178         inline bool
 179         atBegin(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 180         {
 181 SEQAN_CHECKPOINT
 182                 return (empty(me) || hostIterator(me) == me.range.i1);
 183         }
 184
 185         template < typename TText, typename TSpec, typename TSpecFinder >
 186         inline bool
 187         atEnd(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 188         {
 189 SEQAN_CHECKPOINT
 190                 return (empty(me) || hostIterator(me) == me.range.i2);
 191         }
 192
 193 //____________________________________________________________________________
 194
 195         template < typename TText, typename TSpec, typename TSpecFinder >
 196         inline void
 197         goBegin(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 198         {
 199 SEQAN_CHECKPOINT
 200                 hostIterator(me) = me.range.i1;
 201         }
 202
 203         template < typename TText, typename TSpec, typename TSpecFinder >
 204         inline void
 205         goEnd(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 206         {
 207 SEQAN_CHECKPOINT
 208                 hostIterator(me) = me.range.i2;
 209         }
 210
 211 //____________________________________________________________________________
 212 /*
 213         template < typename TText, typename TSpec, typename TSpecFinder, typename TPosition >
 214         inline void
 215         setPosition(Finder< Index<TText, TSpec>, TSpecFinder > & me, TPosition pos_)
 216         {
 217 SEQAN_CHECKPOINT
 218                 hostIterator(me) = me.range.i1 + pos_;
 219         }
 220 */
 221 //____________________________________________________________________________
 222
 223         template < typename TText, typename TSpec, typename TSpecFinder >
 224         inline typename Position< Finder< Index<TText, TSpec>, TSpecFinder > >::Type
 225         position(Finder< Index<TText, TSpec>, TSpecFinder > & me)
 226         {
 227 SEQAN_CHECKPOINT
 228                 SEQAN_ASSERT(!empty(me))
 229                 return *me.data_iterator;
 230         }
 231
 232         template < typename TText, typename TSpec, typename TSpecFinder >
 233         inline typename Position< Finder< Index<TText, TSpec>, TSpecFinder > >::Type
 234         position(Finder< Index<TText, TSpec>, TSpecFinder > const & me)
 235         {
 236 SEQAN_CHECKPOINT
 237                 SEQAN_ASSERT(!empty(me))
 238                 return hostIterator(me) - begin(container(me), Rooted());
 239         }
 240
 241
 242 //////////////////////////////////////////////////////////////////////////////
 243 // find
 244
 245         template < typename TText, typename TSpec, typename TSpecFinder, typename TPattern >
 246         inline bool find(
 247                 Finder<Index<TText, TSpec>, TSpecFinder> &finder,
 248                 TPattern const &pattern)
 249         {
 250                 if (empty(finder)) {
 251                         _findFirstIndex(finder, needle(pattern), TSpecFinder());
 252                         hostIterator(finder) = finder.range.i1;
 253                 } else
 254                         ++hostIterator(finder);
 255                 return !atEnd(finder);
 256         }
 257
 258         template < typename TText, typename TSpec, typename TSpecFinder >
 259         inline bool find(Finder<Index<TText, TSpec>, TSpecFinder> &finder)
 260         {
 261                 if (empty(finder)) return false;
 262                 ++hostIterator(finder);
 263                 return !atEnd(finder);
 264         }
 265
 266 }
 267
 268 #endif