chart.h

Go to the documentation of this file.

//
//    FreeLing - Open Source Language Analyzers
//
//    Copyright (C) 2014   TALP Research Center
//                         Universitat Politecnica de Catalunya
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Affero General Public
//    License as published by the Free Software Foundation; either
//    version 3 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Affero General Public License for more details.
//
//    You should have received a copy of the GNU Affero General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
//    contact: Lluis Padro (padro@lsi.upc.es)
//             TALP Research Center
//             despatx C6.212 - Campus Nord UPC
//             08034 Barcelona.  SPAIN
//

#ifndef _CHART
#define _CHART

#include <list>
#include <vector>
#include <string>

#include "freeling/morfo/language.h"
#include "freeling/morfo/grammar.h"

namespace freeling {


  class edge : public rule {

  private:
    std::list<std::wstring> matched;
    // list of cells that matched the currently solved part of the edge.
    // (-1,-1) stands for unary rules producing cell self-references.
    std::list<std::pair<int,int> > backpath;

  public:
    edge(const std::wstring&, const std::list<std::wstring> &, const int posgov);
    edge();
    ~edge();

    const std::list<std::wstring> get_matched() const;
    const std::list<std::pair<int,int> > get_backpath() const;
    bool active() const;
    void shift(int,int);
   
  };


  typedef std::list<edge> cell; 



  class chart {

  private:

    std::vector<cell> table;
    int size;
    const grammar &gram;

    bool better_edge(const edge &, const edge&) const;
    std::list<std::pair<int,int> > cover (int a, int b) const;
    int index(int i, int j) const;
    bool can_extend(const std::wstring &, int, int) const;
    void find_all_rules(const edge &, cell &, int, int) const;
    bool check_match(const std::wstring &, const std::wstring &) const;

    void dump() const;

  public:
    chart(const grammar &);
    ~chart();

    int get_size() const;

    void load_sentence(const sentence &, int k=0);

    void parse();

    parse_tree get_tree(int, int, const std::wstring & =L"") const;
  };

} // namespace

#endif