insert() [1/5]

auto SuffixTree::insert	(	const Word &	s,
		std::vector< Overlap > &	newRightOverlaps )->size_t

Definition at line 142 of file SuffixTree.cpp.

{
  // warning: this function appends the results to the end of right overlaps.
  int wordNum = mMonomials.size();
  auto plList = std::vector<int> {};
  Label tempS(w.begin(),w.end());
  mMonomials.push_back(tempS);
  tempS.push_back(-(wordNum + 1));
  Word s(tempS);
  auto v = mRoot;
  bool isFullPattern = true;
  while (s.size() != 0) 
    {
      InsertType insertType;
      if (v == mRoot) insertType = insertStepD(v,s,isFullPattern);
      else if (v->parent() == mRoot) insertType = insertStepC(v,mRoot,suffix(Word(v->arcLabel()),1),s,isFullPattern);
      else insertType = insertStepC(v,v->parent()->suffixLink(),Word(v->arcLabel()),s,isFullPattern);
      auto newv = std::get<0>(insertType);
      auto roRoot = std::get<1>(insertType);
      auto newLocus = std::get<2>(insertType);
      v = newv;
      if (roRoot != nullptr)
        {
          plList.clear();
          patternLeaves(roRoot,plList);
          for(auto pl : plList)
            {
              auto ro0 = newLocus->getPatternNumber();
              auto ro1 = mMonomials[ro0].size() - roRoot->label().size();
              auto ro2 = pl;
              rightOverlaps.push_back(std::make_tuple(ro0,ro1,ro2,true));
            }
        }
      if (v != mRoot && s.size() == 2)
        {
          v->setSuffixLink(mRoot);
        }
      s = suffix(s,1);
      isFullPattern = false;
    }
  return mMonomials.size();
}

References insertStepC(), insertStepD(), mMonomials, mRoot, patternLeaves(), s, and suffix().