nodeseq.h

Go to the documentation of this file.

// -*- C++ -*-
// NODE SEQUENCE CLASS
 
#ifndef _NODESEQ_H_
#define _NODESEQ_H_
 
#include <list>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include "node.h"
#include "internal.h"
 
typedef typename std::list<node_t*>::const_iterator node_it;
typedef typename std::list<node_t*>::iterator node_nit;
typedef typename std::list<node_t*>::const_reverse_iterator node_rev_it;

class nodeseq_t : public std::list<node_t*> {
 
private:

  void clean (void) {
    for (node_t *p : *this) delete p;
    clear();
  };
 
public:

  ~nodeseq_t (void) {
    clean();
  };
 
public:
 
  // SERIALIZATION
  size_t bytesize (void) const {
    size_t s = sizeof(size_t);
    for (node_t *p : *this)
      s += p->bytesize();
    return s;
  };

  friend raw_t* operator>> (const nodeseq_t& G, raw_t* o) {
    size_t nnode = G.size();
    memcpy(o,&nnode,sizeof(size_t)); o += sizeof(size_t);
    for (node_t *p : G) {
      o = (*p >> o);
    }
    return o;
  };

  friend raw_t* operator>> (raw_t* o, nodeseq_t& G) {
    G.clean();
    std::unordered_map<name_t,node_t*> node_names;
    std::unordered_map<name_t,ball_t*> ball_names;
    size_t nnode = 0;
    memcpy(&nnode,o,sizeof(size_t)); o += sizeof(size_t);
    node_names.reserve(nnode);
    ball_names.reserve(nnode);
    for (size_t i = 0; i < nnode; i++) {
      node_t *p = new node_t();
      o = (o >> *p);
      G.push_back(p);
      node_names[p->uniq] = p;
    }
    for (node_t *q : G) {
      q->repair_owners(node_names,&ball_names);
    }
    G.repair_owners(ball_names);
    G.trace_lineages();
    return o;
  };
 
private:

  void repair_owners (const std::unordered_map<name_t,ball_t*>& names) {
    for (node_t *p : *this) {
      p->green_ball() = names.at(p->uniq);
    }
  };

  std::unordered_map<name_t, node_t*>
  node_map (void) const {
    std::unordered_map<name_t, node_t*> m;
    m.reserve(size());
    for (node_t* p : *this)
      m[p->uniq] = p;
    return m;
  };
 
public:

  static bool compare (node_t* p, node_t* q) {
    return (p->slate < q->slate) ||
      ((p->slate == q->slate) &&
       ((p == q->parent()) ||
        ((q != p->parent()) && (p->uniq < q->uniq))));
  };

  void sort (void) {
    std::list<node_t*>::sort(compare);
  };
 
public:

  pocket_t* colored (color_t col) const {
    pocket_t *p = new pocket_t;
    for (node_t *q : *this) {
      for (ball_t *b : *q ) {
        if (b->is(col)) p->insert(b);
      }
    }
    return p;
  };

  size_t ntime (slate_t t) const {
    size_t count = 1;
    for (node_t *p : *this) {
      if (t < p->slate) {
        t = p->slate;
        count++;
      }
    }
    return count;
  };

  size_t length (void) const {
    return this->size();
  };

  node_t *position (int n) {
    int i = 0;
    node_it k = cbegin();
    while (i < n && k != cend()) {
      i++; k++;
    }
    assert(k != cend());
    return *k;
  };
 
public:

  void move (ball_t *b, node_t *p, node_t *q) {
    assert(b->holder() == p);
    p->erase(b); q->insert(b);
  };

  void swap (ball_t *a, ball_t *b) {
    node_t *p = a->holder();
    node_t *q = b->holder();
    if (p != q) {
      p->erase(a); q->insert(a);
      q->erase(b); p->insert(b);
    }
  };

  void attach (node_t *p, node_t *q) {
    move(q->green_ball(),q,p);
  };

  void detach (node_t *p) {
    move(p->green_ball(),p->parent(),p);
  };

  void add (node_t *p, ball_t *a) {
    swap(a,p->green_ball());
    p->deme() = a->deme();
    push_back(p);
  };

  void drop (ball_t *a) {
    assert(a->is(black));
    node_t *p = a->holder();
    if (p->size() > 1) {
      p->erase(a);
      delete a;
      if (p->dead_root()) {     // remove isolated root
        destroy_node(p);
      }
    } else {
      swap(a,p->green_ball());
      destroy_node(p);
      drop(a);                  // recurse
    }
  };

  void destroy_node (node_t *p) {
    assert(p->dead_root());
    remove(p);
    delete p;
  };

  void weed (void) {
    node_nit j = begin();
    while (j != end()) {
      if ((*j)->dead_root()) {
        destroy_node(*(j++));
      } else {
        j++;
      }
    }
  };

  void comb (void) {
    for (node_t *p : *this) {
      if (p->size() == 1 && p->holds(green)) {
        swap(p->last_ball(),p->green_ball());
      }
    }
    weed();
  };
 
private:

  void trace_lineage (ball_t *b, name_t u) {
    node_t *p = b->holder();
    while (p->lineage() == null_lineage) {
      p->lineage() = u;
      p = p->parent();
    }
  };
 
public:

  std::unordered_map<name_t, std::vector<node_t*>>
  children_map (void) const {
    std::unordered_map<name_t, std::vector<node_t*>> children;
    children.reserve(size());
    // initialise every node with an empty vector
    for (node_t* p : *this)
      children[p->uniq];
    for (node_t* p : *this) {
      if (!p->is_root())
        children[p->parent()->uniq].push_back(p);
    }
    return children;
  };

  std::vector<node_t*>
  sorted_roots
  (
   const std::unordered_map<name_t, slate_t>& height
   ) const {
    std::vector<node_t*> roots;
    for (node_t* p : *this)
      if (p->is_root()) roots.push_back(p);
    std::sort(roots.begin(), roots.end(),
              [&height](node_t* a, node_t* b) {
                return height.at(a->uniq) > height.at(b->uniq);
              });
    return roots;
  };

  std::vector<node_t*>
  ladderize
  (
   std::unordered_map<name_t,std::vector<node_t*>>& children
   ) const {
    std::unordered_map<name_t, slate_t> height;
    height.reserve(size());
    for (auto it = rbegin(); it != rend(); ++it) {
      node_t* p = *it;
      auto& ch = children.at(p->uniq);
      if (ch.empty()) {
        height[p->uniq] = p->slate;
      } else {
        std::sort(ch.begin(), ch.end(),
                  [&height](node_t* a, node_t* b) {
                    return height.at(a->uniq) > height.at(b->uniq);
                  });
        height[p->uniq] = height.at(ch[0]->uniq);
      }
    }
    return sorted_roots(height);
  };
 
public:

  void trace_lineages (void) {
    // we trace each lineage in turn.
    // because we move from early to late,
    // the order is guaranteed to be valid.
    name_t u = 0;
    for (node_t *p : *this ) {
      for (ball_t *b : *p) {
        if (b->color==blue) {
          trace_lineage(b,u);
          u++;
        }
      }
    }
  };
 
public:

  string_t yaml (string_t tab = "") const;
  SEXP structure (void) const;
  string_t newick (slate_t t, slate_t te, bool showdeme, bool extended) const;
 
};
 
#endif