Logo Search packages:      
Sourcecode: pan version File versions  Download package

void DataImpl::MyTree::add_articles ( const const_nodes_v &  nodes_in ) [private]

1. add the new articles

2. find parents for the new articles

3. possibly reparent other articles

Definition at line 364 of file my-tree.cc.

{
  NodeMidCompare compare;

  ///
  ///  1. add the new articles
  ///

  // sort the nodes by Message-ID
  // so that we can use `nodes' for set operations
  const_nodes_v nodes (nodes_in);
  std::sort (nodes.begin(), nodes.end(), compare);

  // nodes -= this->_nodes;
  // (don't try to add articles we've already got.)
  if (1) {
    const_nodes_v tmp;
    tmp.reserve (nodes.size());
    std::set_difference (nodes.begin(), nodes.end(),
                         _nodes.begin(), _nodes.end(),
                         inserter (tmp, tmp.begin()),
                         compare);
    nodes.swap (tmp);
    //std::cerr << LINE_ID << ' ' << nodes.size() << " unique nodes\n";
  }

  // build new MyTree nodes for each of the articles being added
  int node_index (_node_chunk.size());
  _node_chunk.resize (_node_chunk.size() + nodes.size());
  nodes_v tree_nodes;
  tree_nodes.reserve (nodes.size());
  foreach_const (const_nodes_v, nodes, it) {
    const Article * a ((*it)->_article);
    ArticleNode * node (&_node_chunk[node_index++]);
    node->_mid = a->message_id;
    node->_article = const_cast<Article*>(a);
    //std::cerr << LINE_ID << " added " << node->_mid << " to the tree\n";
    std::pair<nodes_t::iterator,bool> result (
      _nodes.insert (std::pair<Quark,ArticleNode*>(node->_mid, node)));
    g_assert (result.second); // freshly added; not a duplicate
    tree_nodes.push_back (node);
  }

  ///
  ///  2. find parents for the new articles
  ///

  ArticleTree::Diffs diffs;
  for (size_t i(0), n(nodes.size()); i!=n; ++i)
  {
    const ArticleNode * node (nodes[i]);
    ArticleNode * tree_node (tree_nodes[i]);
    g_assert (node->_mid == tree_node->_mid);

    Diffs::Added added;
    added.message_id = tree_node->_mid;

    // find the first ancestor that's present in our tree
    ArticleNode * parent (0);
    const nodes_t::const_iterator nend (_nodes.end());
    for (const ArticleNode *it(node->_parent); it && !parent; it=it->_parent) {
      nodes_t::iterator nit (_nodes.find (it->_mid));
      if (nit != nend)
        parent = nit->second;
    }

    // if we found a parent, use it.
    if (parent) {
      tree_node->_parent = parent;
      parent->_children.push_back (tree_node);
      added.parent = parent->_mid;
    }

    diffs.added.insert (diffs.added.end(),
                        std::pair<Quark,Diffs::Added>(added.message_id, added));
    //std::cerr << LINE_ID << " child " << added.message_id
    //                     << " has parent " << added.parent << std::endl;
  }

  ///
  ///  3. possibly reparent other articles
  ///

  // get a list of all articles that are descendants of the new articles
  const_nodes_v descendants;
  if (1) {
    unique_nodes_t tmp;
    foreach (const_nodes_v, nodes, it)
      accumulate_descendants (tmp, *it);
    descendants.assign (tmp.begin(), tmp.end());
  }

  // descendants = descendants - nodes;
  // (we parented `nodes' in step 2.)
  if (1) {
    const_nodes_v tmp;
    std::set_difference (descendants.begin(), descendants.end(),
                         nodes.begin(), nodes.end(),
                         inserter (tmp, tmp.begin()));
    descendants.swap (tmp);
  }

  // map the 'canonical' nodes to MyTree nodes...
  typedef std::vector<TwoNodes> twonodes_v;
  twonodes_v descend;
  descend.reserve (descendants.size());
  if (1) {
    nodes_t::iterator nit(_nodes.begin()), nend(_nodes.end());
    const_nodes_v::const_iterator dit(descendants.begin()),
                                 dend(descendants.end());
    while (nit!=nend && dit!=dend) {
      if (nit->second->_mid < (*dit)->_mid)
        ++nit;
      else if ((*dit)->_mid < nit->second->_mid)
        ++dit;
      else {
        g_assert (nit->second->_mid == (*dit)->_mid);
        descend.push_back (TwoNodes (*dit, nit->second));
        ++nit;
        ++dit;
      }
    }
  }

  // now walk though the descendants and possibly reparent them.
  foreach_const (twonodes_v, descend, it)
  {
    ArticleNode * tree_node (it->tree_node);
    const ArticleNode * node (it->node);
    g_assert (node->_mid == tree_node->_mid);

    //std::cerr << LINE_ID << " looking for a new parent for "
    //          << tree_node->_mid << std::endl;
    ArticleNode * new_parent (0);
    node = node->_parent;
    while (node && !new_parent) {
      //std::cerr << LINE_ID << " maybe " << node->_mid
      //                     << " can be its new parent..." << std::endl;
      nodes_t::iterator nit (_nodes.find (node->_mid));
      if (nit != _nodes.end())
        new_parent = nit->second;
      else {
        node = node->_parent;
        //std::cerr << LINE_ID << " but no, that's not in the tree.\n";
      }
    }
    //std::cerr << LINE_ID << " " << tree_node->_mid << "'s best parent is "
    //          << new_parent << std::endl;

    if (new_parent == tree_node->_parent)
      continue;

    ArticleNode * old_parent (tree_node->_parent);
    ArticleTree::Diffs::Reparent reparent;
    if (old_parent) {
      reparent.old_parent = old_parent->_mid;
      old_parent->_children.remove (tree_node);
    }
    new_parent->_children.push_back (tree_node);
    tree_node->_parent = new_parent;
    reparent.message_id = tree_node->_mid;
    reparent.new_parent = new_parent->_mid;
    diffs.reparented.insert (diffs.reparented.end(),
                             std::pair<Quark,Diffs::Reparent>(reparent.message_id, reparent));
    //std::cerr << LINE_ID << " REPARENTED: " << reparent.message_id
    //          << " has a new parent " << reparent.new_parent << std::endl;
  }

  // std::cerr << LINE_ID << ' ' << _nodes.size() << " articles in the tree\n";
  if (!diffs.reparented.empty() || !diffs.added.empty())
    fire_diffs (diffs);
}

Generated by  Doxygen 1.6.0   Back to index