insertStepD()

auto SuffixTree::insertStepD	(	SuffixTreeNode *	y,
		const Word &	s,
		bool	isFullPattern )->InsertType

Definition at line 259 of file SuffixTree.cpp.

{
  // Carries out step D in the algorithm.  This amounts to constructing
  // the locus of the head of s (which is not yet known before calling this function).
  // find the contracted locus of s, starting from the node y
  auto clType = contractedLocus(y,s,isFullPattern);
  auto newy = std::get<0>(clType);
  auto f = std::get<1>(clType);
  auto pre = std::get<2>(clType);
  auto tmpNode = y;
  auto tmpLabel = s;
 
  // drop the letters from s along the path traversed from y to std::get<0>(clType);
  tmpLabel = suffix(tmpLabel, newy->label().size() - tmpNode->label().size());
  tmpNode = newy;
  if (f == nullptr)
    {
      // in this case, there is no common prefix of a label of any child of y and s
      // so just create a leaf immediately.
      auto v = new SuffixTreeNode(tmpNode,tmpLabel,isFullPattern);
      if (tmpNode->label().size() != 0 && v->arcLabel().size() == 1)
    return std::make_tuple(tmpNode,tmpNode,v);
      else
    return std::make_tuple(tmpNode,nullptr,v);
    }
  // in this case, f is the extended locus of s.  We need to split the arc from y to f
  auto p = splitArc(f,pre);
  // update the patternLeafCount of p if necessary
  p->setPatternLeafCount(f->patternLeafCount());
  p->addToPatternLeafCount(isFullPattern);
  p->addToPatternLeafCount(f->isFullPattern());
  // drop common prefix
  tmpLabel = suffix(tmpLabel,pre.size());
  // create new leaf under p for s
  auto w = new SuffixTreeNode (p,tmpLabel,isFullPattern);
  // return overlap and head information
  if (tmpLabel.size() == 1)
    return std::make_tuple(p,p,w);
  else
    return std::make_tuple(p,nullptr,w);
}

References contractedLocus(), p, s, splitArc(), and suffix().

Referenced by insert(), insertStepC(), and insertWorker().