SuffixArraySeqan.h

Go to the documentation of this file.

// --------------------------------------------------------------------------
//                   OpenMS -- Open-Source Mass Spectrometry
// --------------------------------------------------------------------------
// Copyright The OpenMS Team -- Eberhard Karls University Tuebingen,
// ETH Zurich, and Freie Universitaet Berlin 2002-2012.
//
// This software is released under a three-clause BSD license:
//  * 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 any author or any participating institution
//    may be used to endorse or promote products derived from this software
//    without specific prior written permission.
// For a full list of authors, refer to the file AUTHORS.
// --------------------------------------------------------------------------
// 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 ANY OF THE AUTHORS OR THE CONTRIBUTING
// INSTITUTIONS 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.
//
// --------------------------------------------------------------------------
// $Maintainer: Clemens Groepl,Andreas Bertsch$
// $Authors: Chris Bauer $
// --------------------------------------------------------------------------



#ifndef OPENMS_DATASTRUCTURES_SUFFIXARRAYSEQAN_H
#define OPENMS_DATASTRUCTURES_SUFFIXARRAYSEQAN_H

#include <vector>
#include <OpenMS/DATASTRUCTURES/String.h>
#include <OpenMS/DATASTRUCTURES/SuffixArray.h>
#include <OpenMS/DATASTRUCTURES/SeqanIncludeWrapper.h>
#include <OpenMS/CHEMISTRY/WeightWrapper.h>



namespace OpenMS
{

  class OPENMS_DLLAPI SuffixArraySeqan :
    public SuffixArray
    , public WeightWrapper
  {

    typedef seqan::TopDown<seqan::ParentLinks<> > TIterSpec;
    typedef seqan::Index<seqan::String<char>, seqan::IndexEsa<TIterSpec> > TIndex;
    typedef seqan::Iter<TIndex, seqan::VSTree<TIterSpec> > TIter;

    // TODO ??? was: typedef seqan::Index<seqan::String<char>, seqan::Index_ESA<seqan::TopDown<seqan::ParentLinks<seqan::Preorder> > > > TIndex;

public:

    SuffixArraySeqan(const String & st, const String & filename, const WeightWrapper::WEIGHTMODE weight_mode = WeightWrapper::MONO);

    SuffixArraySeqan(const SuffixArraySeqan & source);

    virtual ~SuffixArraySeqan();

    String toString();

    void findSpec(std::vector<std::vector<std::pair<std::pair<SignedSize, SignedSize>, DoubleReal> > > & candidates, const std::vector<DoubleReal> & spec);

    bool save(const String & filename);

    bool open(const String & filename);

    void setTolerance(DoubleReal t);

    DoubleReal getTolerance() const;

    bool isDigestingEnd(const char aa1, const char aa2) const;

    void setTags(const std::vector<OpenMS::String> & tags);

    const std::vector<OpenMS::String> & getTags();

    void setUseTags(bool use_tags);

    bool getUseTags();

    void setNumberOfModifications(Size number_of_mods);

    Size getNumberOfModifications();

    void printStatistic();

protected:

    inline void goNextSubTree_(TIter & it, DoubleReal & m, std::stack<DoubleReal> & allm, std::stack<std::map<DoubleReal, SignedSize> > & mod_map)
    {
      // preorder dfs
      if (!goRight(it))
      {
        while (true)
        {
          if (goUp(it))
          {
            m -= allm.top();
            allm.pop();
            mod_map.pop();
          }
          else
          {
            break;
          }

          if (goRight(it))
          {
            m -= allm.top();
            allm.pop();
            mod_map.pop();
            break;
          }
        }
      }
      else
      {
        m -= allm.top();
        allm.pop();
        mod_map.pop();
      }
      if (isRoot(it))
      {
        clear(it);
      }
    }

    inline void goNextSubTree_(TIter & it)
    {
      // preorder dfs
      if (!goRight(it))
      {
        while (true)
        {
          if (!goUp(it))
          {
            break;
          }
          if (goRight(it))
          {
            break;
          }
        }
      }
      if (isRoot(it))
      {
        clear(it);
      }
    }

    inline void goNext_(TIter & it, DoubleReal & m, std::stack<DoubleReal> & allm, std::stack<std::map<DoubleReal, SignedSize> > & mod_map)
    {
      // preorder dfs
      if (!goDown(it))
      {
        goNextSubTree_(it, m, allm, mod_map);
      }
    }

    inline void parseTree_(TIter & it, std::vector<std::pair<SignedSize, SignedSize> > & out_number, std::vector<std::pair<SignedSize, SignedSize> > & edge_length, std::vector<SignedSize> & leafe_depth)
    {
      SignedSize depth = 1;
      while (!atEnd(it))
      {
        SignedSize le = 0;
        bool isLeaf = false;
        if (length(parentEdgeLabel(it)) > 0)
        {
          if (countChildren(it) > 0)
          {
            edge_length.push_back(std::pair<SignedSize, SignedSize>(depth, length(parentEdgeLabel(it))));
          }
          else
          {
            //le <- length(representative(it));
            //isLeaf = true;
          }
        }
        if (countChildren(it) > 0)
        {
          out_number.push_back(std::pair<SignedSize, SignedSize>(depth, countChildren(it)));
        }
        else
        {
          leafe_depth.push_back(depth);
        }
        if (goDown(it))
        {
          depth++;
        }
        else if (!goRight(it))
        {
          while (!goRight(it))
          {
            goUp(it);
            if (isLeaf)
            {
              edge_length.push_back(std::pair<SignedSize, SignedSize>(depth, le - length(parentEdgeLabel(it))));
              isLeaf = false;
            }
            depth--;
            if (isRoot(it)) return;
          }
        }
        else
        {
        }
      }
    }

    TIndex index_;     

    TIter * it_;    

    SignedSize findFirst_(const std::vector<DoubleReal> & spec, DoubleReal & m);

    SignedSize findFirst_(const std::vector<DoubleReal> & spec, DoubleReal & m, SignedSize start, SignedSize  end);

    const String & s_;    

    DoubleReal masse_[255];     

    SignedSize number_of_modifications_;     

    std::vector<String> tags_;     

    bool use_tags_;     

    DoubleReal tol_;     
  };
}

#endif //OPENMS_DATASTRUCTURES_SUFFIXARRAYSEQAN_H