text: // ==========================================================================
  //                 SeqAn - The Library for Sequence Analysis
  // ==========================================================================
  // Copyright (c) 2006-2018, Knut Reinert, FU Berlin
  // All rights reserved.
  //
  // Redistribution and use in source and binary forms, with or without
  // modification, are permitted provided that the following conditions are met:
  //
  //     * Redistributions of source code must retain the above copyright
  //       notice, this list of conditions and the following disclaimer.
  //     * Redistributions in binary form must reproduce the above copyright
  //       notice, this list of conditions and the following disclaimer in the
  //       documentation and/or other materials provided with the distribution.
  //     * Neither the name of Knut Reinert or the FU Berlin nor the names of
  //       its contributors may be used to endorse or promote products derived
  //       from this software without specific prior written permission.
  //
  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
  // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  // DAMAGE.
  //
  // ==========================================================================
  // Author: Rene Rahn <rene.rahn@fu-berlin.de>
  // ==========================================================================
  
  #ifndef INCLUDE_SEQAN_JOURNALED_STRING_TREE_JST_EXTENSION_SHIFT_AND_H_
  #define INCLUDE_SEQAN_JOURNALED_STRING_TREE_JST_EXTENSION_SHIFT_AND_H_
  
  namespace seqan
  {
  
  // ============================================================================
  // Forwards
  // ============================================================================
  
  // ============================================================================
  // Tags, Classes, Enums
  // ============================================================================
  
  // ----------------------------------------------------------------------------
  // Class PatternStateShiftAnd_
  // ----------------------------------------------------------------------------
  
  template <typename TPattern>
  struct PatternStateShiftAnd_
  {
      using TWord = typename TPattern::TWord;
  
      String<TWord> prefSufMatch;        // Set of all the prefixes of needle that match a suffix of haystack (called D in "Navarro")
  };
  
  // ----------------------------------------------------------------------------
  // Class JstExtension<ShiftAnd>
  // ----------------------------------------------------------------------------
  
  template <typename TNeedle>
  class JstExtension<Pattern<TNeedle, ShiftAnd> > :
      public JstExtensionBase<JstExtension<Pattern<TNeedle, ShiftAnd> >, ContextEnd>
  {
  public:
      using TPattern = Pattern<TNeedle, ShiftAnd>;
      using TBase    = JstExtensionBase<JstExtension<Pattern<TNeedle, ShiftAnd> >, ContextEnd>;
      using TWord    = typename TPattern::TWord;
  
      static constexpr TWord WORD_INDEX_HIGH_BIT = BitsPerValue<TWord>::VALUE - 1;
  
      TPattern&  _pattern;
      TWord      carry;
      TWord      mask;
      bool       isLongNeedle;
  
      JstExtension(TPattern & pattern) : TBase(*this), _pattern(pattern)
      {
          // Explicitly force to initialize pattern due to implementation detail.
          _patternInit(_pattern);
          state(*this).prefSufMatch = _pattern.prefSufMatch;
          mask = static_cast<TWord>(1) << ((_pattern.needleLength - 1) % BitsPerValue<TWord>::VALUE);
          isLongNeedle = _pattern.blockCount > 1;
      }
  };
  
  // ============================================================================
  // Metafunctions
  // ============================================================================
  
  // ----------------------------------------------------------------------------
  // Metafunction GetPatternState
  // ----------------------------------------------------------------------------
  
  template <typename TNeedle>
  struct GetPatternState<JstExtension<Pattern<TNeedle, ShiftAnd> > >
  {
      using Type = PatternStateShiftAnd_<Pattern<TNeedle, ShiftAnd> >;
  };
  
  template <typename TNeedle>
  struct GetPatternState<JstExtension<Pattern<TNeedle, ShiftAnd> > const>
  {
      using Type = PatternStateShiftAnd_<Pattern<TNeedle, ShiftAnd> > const;
  };
  
  // ----------------------------------------------------------------------------
  // Metafunction ProxySelectionMethod
  // ----------------------------------------------------------------------------
  
  template <typename TNeedle>
  struct ProxySelectionMethod<JstExtension<Pattern<TNeedle, ShiftAnd> > >
  {
      using Type = SelectFirstProxy;
  };
  
  // ============================================================================
  // Functions
  // ============================================================================
  
  namespace impl
  {
  
  // ----------------------------------------------------------------------------
  // Function impl::runLongNeedle()
  // ----------------------------------------------------------------------------
  
  template <typename TNeedle, typename TIterator>
  inline std::pair<size_t, bool>
  runLongNeedle(JstExtension<Pattern<TNeedle, ShiftAnd> > & me,
                TIterator const hystkIt)
  {
      using TExt   = JstExtension<Pattern<TNeedle, ShiftAnd> >;
      using TWord  = typename TExt::TWord;
      using TValue = typename Value<TNeedle>::Type;
  
      me.carry = 1;
      for (TWord block = 0; block < me._pattern.blockCount; ++block)
      {
          bool newCarry = isBitSet(state(me).prefSufMatch[block], me.WORD_INDEX_HIGH_BIT);
          state(me).prefSufMatch[block] = ((state(me).prefSufMatch[block] << 1) | me.carry) &
                                          me._pattern.bitMasks[me._pattern.blockCount * ordValue(convert<TValue>(getValue(hystkIt))) + block];
          me.carry = newCarry;
      }
      return std::pair<size_t, bool>(1, (state(me).prefSufMatch[me._pattern.blockCount-1] & me.mask) != 0);
  }
  
  // ----------------------------------------------------------------------------
  // Function impl::runShortNeedle()
  // ----------------------------------------------------------------------------
  
  template <typename TNeedle, typename TIterator>
  inline std::pair<size_t, bool>
  runShortNeedle(JstExtension<Pattern<TNeedle, ShiftAnd> > & me,
                 TIterator const hystkIt)
  {
      using TWord = typename Pattern<TNeedle, ShiftAnd>::TWord;
      using TValue = typename Value<TNeedle>::Type;
  
      state(me).prefSufMatch[0] = ((state(me).prefSufMatch[0] << 1) | static_cast<TWord>(1)) &
                                  me._pattern.bitMasks[ordValue(convert<TValue>(getValue(hystkIt)))];
  
      return std::pair<size_t, bool>(1, (state(me).prefSufMatch[0] & me.mask) != 0);
  }
  }  // namespace impl
  
  // ----------------------------------------------------------------------------
  // Function run()
  // ----------------------------------------------------------------------------
  
  template <typename TNeedle, typename TIterator>
  inline std::pair<size_t, bool>
  run(JstExtension<Pattern<TNeedle, ShiftAnd> > & me,
      TIterator hystkIt)
  {
      return (me.isLongNeedle) ? impl::runLongNeedle(me, hystkIt) : impl::runShortNeedle(me, hystkIt);
  }
  }  // namespace seqan
  
  #endif  // #ifndef INCLUDE_SEQAN_JOURNALED_STRING_TREE_JST_EXTENSION_SHIFT_AND_H_
  