ryzom/tools/assoc_mem/tree.h

   1 // Ryzom - MMORPG Framework <http://dev.ryzom.com/projects/ryzom/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #ifndef NL_TREE_H_
  18 #define NL_TREE_H_
  19
  20 #include <vector>
  21 #include <map>
  22 #include "record.h"
  23 #include "node.h"
  24 #include "field.h"
  25
  26
  27 class CTree
  28 {
  29         private:
  30                 //std::vector<std::string>      _Fields;
  31                 int                                                     _Key;
  32                 INode                                           *_RootNode;
  33
  34         public:
  35
  36                 struct greater : public std::binary_function<std::pair<double,int> , std::pair<double,int> , bool> {
  37                         bool operator()(std::pair<double,int> x, std::pair<double,int> y) const
  38                         {
  39                                 return x.first > y.first;
  40                         }
  41                 };
  42
  43         public:
  44                 CTree();
  45                 ~CTree();
  46                 void setKey(int);
  47                 int getKey();
  48
  49                 bool getOutput(CRecord *);
  50
  51                 int getNbRecords(std::vector<CRecord *> &,int,IValue *);
  52
  53                 std::vector<CRecord *> getRecords(std::vector<CRecord *> &, int , bool);
  54
  55                 void splitRecords(std::vector<CRecord *> &, int, int &, int &);
  56                 void splitRecords(std::vector<CRecord *> &, int, std::vector<CField *> &, std::vector< std::vector<CRecord *> > &);
  57
  58                 void splitRecords(std::vector<CRecord *> &, int, IValue *, int &, int &);
  59                 void splitRecords(std::vector<CRecord *> &, int, IValue *, bool, int &, int &);
  60
  61                 float findNumKeyValue(std::vector<CRecord *> &, int);
  62
  63                 double log2(double) const;
  64
  65                 double entropy(double, double) const;
  66                 double entropy(std::vector<double> &) const;
  67                 double gain(std::vector<CRecord *> &, int, CField *);
  68
  69                 std::vector<std::pair<double,int> > getSortedFields(std::vector<int> &, std::vector<CRecord *> &, std::vector<CField *> &);
  70                 int getBestAttrib( std::vector<int> &, std::vector<CRecord *> &,  std::vector<CField *> &);
  71                 void rebuild(std::vector<CRecord *> &, std::vector<CField *> &);
  72
  73                 std::string getDebugString(std::vector<CRecord *> &, std::vector<CField *> &);
  74
  75                 // returns the root node of a decision tree built with the ID3 algorithm
  76                 INode *ID3(std::vector<int> &, std::vector<CRecord *> &, std::vector<CField *> &);
  77 };
  78
  79 #endif