logicdatastructure.cpp.svn-base

一个巴西大学编写的2D仿真组足球机器人程序

/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program 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 General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*! \file LogicDataStructure.cpp
<pre>
<b>File:</b>          LogicDataStructure.cpp
<b>Project:</b>       Robocup Soccer Simulation Team: MecaTeam
<b>Authors:</b>       Orivaldo Vieira e Acassio
<b>Created:</b>       10/09/2006
<b>Last Revision:</b> $ID$
<b>Contents:</b>      Este arquivo cont�m a declara��o da classe para 
               LogicDataStructure e suas classes componentes. A LogicDataStructure � 
               classe que disponibiliza uma estrutura de dados para se armazenar 
               os padr�es l�gicos. Classes componentes:
               - QueryTree: �rvore de busca bin�ria;
               - TreeNodo: n� da �rvore bin�ria;
<hr size=2>
<h2><b>Changes</b></h2>
<b>Date</b>             <b>Author</b>          <b>Comment</b>
19/09/2006       Orivaldo Vieira      Documenta��o
</pre>
*/

#include "LogicDataStructure.h"

using namespace std;

/*! Este contrutor cria as duas �rvores de objeto e de atributo. */
LogicDataStructure::LogicDataStructure ()
{
    mpQueryPattern = new LogicPattern();
    m_objectTree = new QueryTree();
    m_attributeTree = new QueryTree();
}

/*! Este m�todo destr�i as duas �rvores de objeto e de atributo. */
LogicDataStructure::~LogicDataStructure ()
{
    delete m_objectTree;
    delete m_attributeTree;
}

/*! Este m�todo imprimi uma das duas �rvores de busca.
    \param _type indica qual a sera a �rovere a ser impressa. Caso 1 � a �rvore ordenada pelo objeto, caso 2 � a �rvore de atributo. */
void LogicDataStructure::printTree(int _type)
{
    switch (_type)
    {
       case 1: m_objectTree->printTree();
               break;
       case 2: m_attributeTree->printTree();
               break;
    }
}

LogicPattern* LogicDataStructure::selectObjectAndAttribute( LogicPattern* pattern )
{
   return m_objectTree->selectObjectAndAttribute( pattern );
}

/*! Este m�todo chama o m�todo queryPattern da �rvore de objetos. */
bool LogicDataStructure::query (LogicPattern* pattern)
{
    return m_objectTree->queryPattern(pattern);
}

/*! Este m�todo cria um ponteiro para um padr�o l�gico a partir do par�mentros dados e adiciona na �vore.
    \param object nome do objeto do padr�o l�gico
    \param attribute nome do atributo do padr�o l�gico
    \param value valor do padr�o l�gico do padr�o l�gico 
    \return true caso o padr�o l�gico n�o exista, se n�o retorna false */
bool LogicDataStructure::insert(string object, string attribute, string value)
{

//    pattern = new LogicPattern(object,attribute,value);
    mpQueryPattern->setObject( object );
    mpQueryPattern->setAttribute( attribute );
    mpQueryPattern->setValue( value );
//    m_attributeTree->addPtrLogicPattern(pattern);
    return m_objectTree->addPtrLogicPattern( mpQueryPattern );
}

/*! Este m�todo encapsula o m�todo addPtrLogicPattern do QueryTree. Ele recebe como par�metro um ponteiro para um padr�o l�gico e adiciona na arvore.
   \param _ptrLogicPattern
   \return true caso o padr�o l�gico n�o exista, se n�o retorna false */
bool LogicDataStructure::insert (LogicPattern* _pLP)
{
   m_objectTree->addPtrLogicPattern(_pLP);
   return m_attributeTree->addPtrLogicPattern(_pLP);
}


/*! Este construtor inicializa o ponteiro da raiz �rvore como nulo.*/
QueryTree::QueryTree()
{
    m_ptrRootNodo = NULL;
}

/*! Este destruidor desaloca o N� raiz da mem�ria */
QueryTree::~QueryTree()
{
    delete m_ptrRootNodo;
}

/*! Este m�todo � utilizado para chamar o m�todo de imprimir a �rvore a partir da raiz */
void QueryTree::printTree()
{
   printTree( m_ptrRootNodo );
}

/*! Este m�todo imprime a �rvore, percorrendo-a utilizando o algoritmo de travessia In-Order.
    \param _printNodo Par�metro utilizado para implementar a recuss�o do m�todo. */
void QueryTree::printTree( TreeNodo* ptrNodo )
{
   if ( ptrNodo != NULL )
   {
      printTree( ptrNodo->m_ptrLeftNodo );
      ptrNodo->print();
      printTree( ptrNodo->m_ptrRightNodo );
   }
}

/*! Este m�todo adiciona um ponteiro para um padr�o l�gico na �rvore. Utiliza como auxiliar o m�todo de inser��o que recebe como par�metros um ponteiro para raiz e um ponteiro para o padr�o l�gico.
    \param _ptrLogicTerm ponteiro a ser adicionado na arvore de ponteiros.
    \return false se j� existe o padr�o l�gico na �rvore.*/
bool QueryTree::addPtrLogicPattern (LogicPattern* ptrPattern)
{
   return addPtrLogicPattern( &m_ptrRootNodo, ptrPattern );
}

/*! Este m�todo adiciona na �rvore um ponteiro para um padr�o l�gico. Ele recebe dois par�metros, um ponteiro para o ponteiro de um n� da �rvore e um ponteiro para padr�o l�gico. Ele desce a �rvore recursivamente at� achar um n� nulo ou um n� que contenha o objeto e atributo iguais aos a serem inseridos. Caso o ponteiro de n� da �rvore seja nulo ent�o um novo n� � criado com um ponteiro para o padr�o l�gico. Caso o n� encontrado tenha o objeto e do atributo igual ao que esta sendo inserido e o valor diferente ent�o atualiza o valor se o valor for igual ent�o retorna falso. 
    \param ptrNodo ponteiro de pontairo para n�, o usado acessar um n� filho a cada chamada recursiva
    \param ptrPattern ponteiro para o padr�o l�gico a ser inserido
    \return false caso j� exista tal padr�o l�gico na �rvore, true caso contr�rio. */
bool QueryTree::addPtrLogicPattern( TreeNodo** ptrNodo, LogicPattern* ptrPattern )
{
   if ( *ptrNodo == NULL )
   {
      LogicPattern* pattern = new LogicPattern(ptrPattern->getObject(),ptrPattern->getAttribute(),ptrPattern->getValue());
      *ptrNodo = new TreeNodo(pattern);
   }
   else 
   {
      int compare = comparePattern( ptrPattern, (*ptrNodo)->m_ptrLogicPattern);
      if (compare == 0)
      {
         (*ptrNodo)->m_ptrLogicPattern->setValue( ptrPattern->getValue() );
         return true;
      }
      else if ( compare == 1 )
         addPtrLogicPattern( &((*ptrNodo)->m_ptrRightNodo), ptrPattern );
      else if ( compare == -1 )
         addPtrLogicPattern( &((*ptrNodo)->m_ptrLeftNodo), ptrPattern );
      else 
         return false;
   }
   return true;
}

/*! Este m�todo compara o "objeto" e "atributo" de dois padr�es l�gicos caso sejam iguais ent�o retorna o valor inteiro zero, se n�o retorna um n�mero diferente de zero. Quando o padr�o A � menor que ent�o retorna -1, se maior retorna 1. Caso o ponteiro para o padr�o l�gico esteja nulo ent�o retorna -2. 
    \param ptrPatternA ponteiro para o padr�o l�gico A a ser comparado.
    \param ptrPatternB ponteiro para o padr�o l�gico B a ser comparado.
    \return -2: ponteiro para padr�o l�gico nulo;
            -1: Esquerda;
             1: Direita;
             0: Objeto e atributo, iguais ao procurado.*/
int QueryTree::comparePattern (LogicPattern* ptrPatternA, LogicPattern* ptrPatternB)
{
  if ((ptrPatternA != NULL) and (ptrPatternB != NULL))
  {
     int compare = ptrPatternA->getObject().compare(ptrPatternB->getObject());
     if ((compare == 0) and (ptrPatternA->getAttribute() != ""))
         compare = ptrPatternA->getAttribute().compare(ptrPatternB->getAttribute());
     return compare;
  }
  return -2;
}

/*! Este m�todo compara os campos objeto, atributo e valor de dois padr�es l�gicos semelhante ao comparePattern.
    \param ptrPatternA ponteiro para o padr�o l�gico A a ser comparado.
    \param ptrPatternB ponteiro para o padr�o l�gico B a ser comparado.
    \return -2: ponteiro para padr�o l�gico nulo;
            -1: Esquerda;
             1: Direita;
             0: Objeto e atributo, iguais ao procurado.*/
int QueryTree::compareFullPattern (LogicPattern* ptrPatternA, LogicPattern* ptrPatternB)
{
   if ((ptrPatternA != NULL) && (ptrPatternB != NULL))
   {

      int compare = ptrPatternA->getObject().compare(ptrPatternB->getObject());
      if ((compare == 0) && (ptrPatternA->getAttribute() != ""))
      {
         compare = ptrPatternA->getAttribute().compare(ptrPatternB->getAttribute());
         if ( compare == 0 )
            compare = ptrPatternA->getValue().compare(ptrPatternB->getValue());
         return compare;
      }
      return compare;
   }
   return -2;
}

/*! Este m�todo consulta a partir do N� raiz da �rvore - m_ptrRootNodo -, um padr�o l�gico dado pelo ponteiro. Este ponteiro para o padr�o l�gico � passado como param�ntro para o m�todo. A consulta � realizada com o aux�lio do m�todo findPtrLogicPattern, encarregado de usar o atributo m_ptrCurrenteNodo para colocar o resultado da busca.
    \param ptrPattern ponteiro para padr�o l�gico a ser consultado.
    \return true caso encontre o padr�o l�gico e false caso n�o encontre. */
bool QueryTree::queryPattern (LogicPattern* ptrPattern)
{
   findPtrLogicPattern(&m_ptrRootNodo, ptrPattern);
   if (m_ptrCurrentNodo != NULL)
      return true;
   return false;
}

/*! Este m�todo seleciona um padr�o l�gico na �rvore, ou seja faz uma busca pelo padr�o l�gico e ao encontralo retorna o ponteiro para o padr�o l�gico. Essa busca � feita por considerando apenas o objete e o atributo do padr�o l�gico.
   \param ptrPattern ponteiro para o padr�o l�gico a ser buscado.
   \return ponteiro para padr�o l�gico encontrado, caso n�o encontre retorna NULL. */ 
LogicPattern* QueryTree::selectObjectAndAttribute (LogicPattern* ptrPattern)
{
   return findPtrObjectAndAttribute(&m_ptrRootNodo, ptrPattern);
}

/*! Este m�todo recursivo procura pelo padr�o l�gico que tem o objeto e o atributo igual ao padr�o l�gico dado.
   \param ptrNodo ponteiro para o no da �rvore.
   \param ptrPattern ponteiro para o pardr�o l�gico procurado.
   \return ponteiro para o pardr�o l�gico procurado. */
LogicPattern* QueryTree::findPtrObjectAndAttribute (TreeNodo** ptrNodo, LogicPattern* ptrPattern)
{
   LogicPattern*  rPattern = NULL; //guardo o valdor de retorno do m�todo
   if ( *ptrNodo == NULL )
   {
      return NULL;
   }
   else
   {
      int compare = comparePattern( ptrPattern, (*ptrNodo)->m_ptrLogicPattern);
      if (compare == 0)
      {
         return (*ptrNodo)->m_ptrLogicPattern;
      }
      else if ( compare == 1 )
         rPattern = findPtrObjectAndAttribute( &((*ptrNodo)->m_ptrRightNodo), ptrPattern );
      else if ( compare == -1 )
         rPattern = findPtrObjectAndAttribute( &((*ptrNodo)->m_ptrLeftNodo), ptrPattern );
      else 
         return NULL;
   }
   return rPattern;
}

/*! Este m�todo atualiza a atributo m_ptrCurrentNodo que equivale ao n� selecionado no momento. Ao final da execu��o deste m�todo o n� selecionado � nulo ou � exatamente igual ao n� procurado, com o objeto, o atributo e o valor iguais ao do ponteiro para padr�o l�gico que foi passado como par�metro. A recurs�o � utilizada para navegar na �rvore, sendo que a primira vez que ele � chamdo o ptrNodo cont�m o endere�o da raiz da �rovre.
    \param ptrNodo endere�o do n� a ser visitado.
    \param ptrPattern ponteiro para padr�o l�gico � localizar.
    \return padr�o l�gico encontrado ou NULL caso contr�rio. */
bool QueryTree::findPtrLogicPattern(TreeNodo** ptrNodo, LogicPattern* ptrPattern)
{
   if ( *ptrNodo == NULL )
   {
      m_ptrCurrentNodo = NULL;
      return false;
   }
   else 
   {
      int compare = compareFullPattern( ptrPattern, (*ptrNodo)->m_ptrLogicPattern);
      if (compare == 0){
         m_ptrCurrentNodo = (*ptrNodo);
         return true;
      }
      else if ( compare == 1 )
         findPtrLogicPattern( &((*ptrNodo)->m_ptrRightNodo), ptrPattern );
      else if ( compare == -1 )
         findPtrLogicPattern( &((*ptrNodo)->m_ptrLeftNodo), ptrPattern );
      else 
      {
         m_ptrCurrentNodo = NULL;
         return false;
      }
   }
   return false;
}

/*! Este construtor inicializa os tr�s ponteiros com nulo, para o padr�o l�gico, para o n� esquerdo e n� direito.*/
TreeNodo::TreeNodo ()
{
    m_ptrLogicPattern = 0;
    m_ptrLeftNodo = 0;
    m_ptrRightNodo = 0;
}

/*! Este construtor de n� da arvore inicializa o seu ponteiro para o padr�o com aquelhe que e lhe dado como par�metro. Os outros ponteiros s�o inicializados com NULL.
    \param ptrPattern ponteiro padr�o l�gico a ser associado com o do n�.*/
TreeNodo::TreeNodo ( LogicPattern* ptrPattern )
{
    m_ptrLogicPattern = ptrPattern;
    m_ptrLeftNodo = 0;
    m_ptrRightNodo = 0;
}

/*! Este destrutor desaloca o ponteiro para o padr�o l�gico, o n� esquerto e direito da mem�ria. */
TreeNodo::~TreeNodo ()
{
    if (m_ptrLogicPattern == NULL)
       delete m_ptrLogicPattern;
    if (m_ptrLeftNodo == NULL)
       delete m_ptrLeftNodo;
    if (m_ptrRightNodo == NULL)
       delete m_ptrRightNodo;
}

/*! Este m�todo imprime o n� da �rvore, ou seja o conte�do do padr�o l�gico associado a este n�.*/
void TreeNodo::print()
{
   m_ptrLogicPattern->print();
}