tree.h

Go to the documentation of this file.

#ifndef __ZGEN_TYPES_DEPENDENCY_TREE_H__
#define __ZGEN_TYPES_DEPENDENCY_TREE_H__

#include "settings.h"
#include "types/instance.h"

namespace ZGen {

class DependencyTree {
public:
  typedef std::vector<int> edgeset_t;

  DependencyTree();

  ~DependencyTree();

  virtual int set_ref(const dependency_t* _ref);

  //
  friend std::ostream & operator << (std::ostream & ofs, const DependencyTree & tree);

  const edgeset_t& siblings(int i);

  const edgeset_t& descendants(int i);

  const edgeset_t& children(int i);

  int head(int i);

  bool arc(int source, int target);
protected:
  virtual void reset(int N = kMaxNumberOfWords);

  void dependency_to_tree(const dependency_t* parse);

  void go(int now);

  const dependency_t * ref;

  edgeset_t children_[kMaxNumberOfWords];

  int parent_[kMaxNumberOfWords];

  int indgr_[kMaxNumberOfWords];

  edgeset_t descendants_[kMaxNumberOfWords];

  edgeset_t siblings_[kMaxNumberOfWords];

private:
  DependencyTree(DependencyTree & other);

  DependencyTree& operator = (const DependencyTree & other);

  void add_edge(int u, int v);
};


class DependencyTreeWithGuidance: public DependencyTree {
public:
  int set_ref(const dependency_t* ref);

  
  int lvl0(int i) const;

  
  int lvl1(int i) const;

  
  int lvl2(int i) const;

protected:
  void reset(int N = kMaxNumberOfWords);

private:
  void color(int now, int _0, int _1, int _2);

  int lvl0_deprels[kMaxNumberOfWords];
  int lvl1_deprels[kMaxNumberOfWords];
  int lvl2_deprels[kMaxNumberOfWords];
};

//
class DependencyForest : public DependencyTree {
public:
  
  int set_ref(const dependency_t* ref);

  
  int root(int i) const;

  
  int depth(int i) const;

  
  int lca(int u, int v) const;

  
  bool is_root(int i) const;

  
  bool same_ancestor(int u, int v) const;

  //
  friend std::ostream & operator << (std::ostream & ofs, const DependencyForest& tree);
protected:
  void reset(int N = kMaxNumberOfWords);

private:
  void rootize(int now, int root, int depth);

  int root_[kMaxNumberOfWords];
  int depth_[kMaxNumberOfWords];
  int lca_[kMaxNumberOfWords][kMaxNumberOfWords];
};


}

#endif  //  end for __SR_DEPENDENCY_H__