Node.cxx

Go to the documentation of this file.

// C++
#include <cmath>
#include <iostream>

#include "Node.h"
 
//-------------------------------------------------------------------------------------------
Lit::Node::Node(const Node *parent, const Event &event, const int mod) 
   :fNodeP(parent),
    fNodeL(0),
    fNodeR(0),
    fEvent(event),
    fVarDis(event.GetVar(mod)),
    fVarMin(fVarDis),
    fVarMax(fVarDis),
    fMod(mod)
{   
}

//-------------------------------------------------------------------------------------------
Lit::Node::~Node()
{
   if(fNodeL) delete fNodeL;
   if(fNodeR) delete fNodeR;
}

//-------------------------------------------------------------------------------------------
const Lit::Node* Lit::Node::Add(const Event &event, const unsigned int depth)
{
   assert(fMod == depth % event.GetNVar());
   
   const VarType value = event.GetVar(fMod);

   fVarMin = std::min(fVarMin, value);
   fVarMax = std::max(fVarMax, value);

   Node *node = 0;
   if(value < fVarDis)
   {
      if(fNodeL)
      {
         return fNodeL -> Add(event, depth + 1);
      }
      else
      {
         fNodeL = new Node(this, event, (depth + 1) % event.GetNVar());
         node = fNodeL;
      }
   }
   else
   {
      if(fNodeR)
      {
         return fNodeR -> Add(event, depth + 1);
      }
      else
      {
         fNodeR = new Node(this, event, (depth + 1) % event.GetNVar());
         node = fNodeR;
      }      
   }
   
   return node;
}

//-------------------------------------------------------------------------------------------
unsigned int Lit::Find(List &list, const Node *node, const Event &event, const unsigned int nfind)
{
   if(!node)
   {
      return 0;
   }

   const VarType value = event.GetVar(node -> GetMod());

   if(node -> GetWeight() > 0.0)
   {      
      VarType max_dist = 0.0;
      if(!list.empty())
      {
         max_dist = list.back().second;
      
         if(list.size() == nfind)
         {
            if(value > node -> GetVarMax() && Lit::Distance(value, node -> GetVarMax()) > max_dist)
            {
               return 0;
            }  
            if(value < node -> GetVarMin() && Lit::Distance(value, node -> GetVarMin()) > max_dist)
            {
               return 0;
            }
         }
      }
      
      const VarType distance = Lit::Distance(event, node -> GetEvent());
      
      bool insert_this = false;
      bool remove_back = false;
      
      if(list.size() == nfind && !list.empty())
      {
         if(distance < max_dist)
         {
            insert_this = true;
            remove_back = true;
         }
      }
      else if(list.size() < nfind)
      {
         insert_this = true;
      }
      else
      {
         std::cerr << "Lit::Find() - logic error in recursive procedure" << std::endl;
         return 1;
      }

      if(insert_this)
      {
         List::iterator lit = list.begin();
         for(; lit != list.end(); ++lit)
         {
            if(distance < lit -> second)
            {
               break;
            }
            else
            {
               continue;
            }
         }
         
         list.insert(lit, Lit::Elem(node, distance));
      
         if(remove_back)
         {
            list.pop_back();
         }
      }
   }

   unsigned int count = 1;
   if(node -> GetNodeL() && node -> GetNodeR())
   {
      if(value < node -> GetVarDis())
      {
         count += Find(list, node -> GetNodeL(), event, nfind);
         count += Find(list, node -> GetNodeR(), event, nfind);
      }
      else
      {  
         count += Find(list, node -> GetNodeR(), event, nfind);
         count += Find(list, node -> GetNodeL(), event, nfind);
      }
   }
   else
   {
      if(node -> GetNodeL())
      {
         count += Find(list, node -> GetNodeL(), event, nfind);
      }
      if(node -> GetNodeR())
      {
         count += Find(list, node -> GetNodeR(), event, nfind);
      }
   }

   return count;
}
//-------------------------------------------------------------------------------------------
unsigned int Lit::Find(List &list, const Node *node, const Event &event,
                       const double nfind, double ncurr)
{
   if(!node || !(nfind > 0.0))
   {
      return 0;
   }

   const VarType value = event.GetVar(node -> GetMod());

   if(node -> GetWeight() > 0.0)
   {
      VarType max_dist = 0.0;
      if(!list.empty())
      {
         max_dist = list.back().second;
      
         if(!(ncurr < nfind))
         {
            if(value > node -> GetVarMax() && Lit::Distance(value, node -> GetVarMax()) > max_dist)
            {
               return 0;
            }
            if(value < node -> GetVarMin() && Lit::Distance(value, node -> GetVarMin()) > max_dist)
            {
               return 0;
            }
         }
      }
      
      const VarType distance = Lit::Distance(event, node -> GetEvent());
      
      bool insert_this = false;
      
      if(ncurr < nfind)
      {
         insert_this = true;
      }
      else if(!list.empty())
      {
         if(distance < max_dist)
         {
            insert_this = true;
         }
      }
      else
      {
         std::cerr << "Lit::Find() - logic error in recursive procedure" << std::endl;
         return 1;
      }

      if(insert_this)
      {
         ncurr = 0;

         List::iterator lit = list.begin();
         for(; lit != list.end(); ++lit)
         {
            if(distance < lit -> second)
            {
               break;
            }
          
            ncurr += lit -> first -> GetWeight();
         }
         
         lit = list.insert(lit, Lit::Elem(node, distance));     

         for(; lit != list.end(); ++lit)
         {
            ncurr += lit -> first -> GetWeight();
            if(!(ncurr < nfind))
            {
               ++lit;
               break;          
            }
         }

         if(lit != list.end())
         {
            list.erase(lit, list.end());
         }
      }
   }

   unsigned int count = 1;
   if(node -> GetNodeL() && node -> GetNodeR())
   {
      if(value < node -> GetVarDis())
      {
         count += Find(list, node -> GetNodeL(), event, nfind, ncurr);
         count += Find(list, node -> GetNodeR(), event, nfind, ncurr);
      }
      else
      {  
         count += Find(list, node -> GetNodeR(), event, nfind, ncurr);
         count += Find(list, node -> GetNodeL(), event, nfind, ncurr);
      }
   }
   else
   {
      if(node -> GetNodeL())
      {
         count += Find(list, node -> GetNodeL(), event, nfind, ncurr);
      }
      if(node -> GetNodeR())
      {
         count += Find(list, node -> GetNodeR(), event, nfind, ncurr);
      }
   }

   return count;
}

//-------------------------------------------------------------------------------------------
void Lit::Node::Print() const
{
   Print(std::cout);
}

//-------------------------------------------------------------------------------------------
void Lit::Node::Print(std::ostream& os, const std::string &offset) const
{
   os << offset << "-----------------------------------------------------------" << std::endl;
   os << offset << "Node: mod " << fMod 
      << " at " << fVarDis 
      << " with weight: " << GetWeight() << std::endl
      << offset << fEvent;
   
   if(fNodeL)
   {
      os << offset << "Has left node " << std::endl;
   }
   if(fNodeR)
   {
      os << offset << "Has right node" << std::endl;
   }

   if(fNodeL)
   {
      os << offset << "Print left node " << std::endl;
      fNodeL -> Print(os, offset + " ");
   }
   if(fNodeR)
   {
      os << offset << "Print right node" << std::endl;
      fNodeR -> Print(os, offset + " ");
   }
   
   if(!fNodeL && !fNodeR)
   {
      os << std::endl;
   }
}


//-------------------------------------------------------------------------------------------
std::ostream& Lit::operator<<(std::ostream& os, const Lit::Node &node)
{ 
   node.Print(os);
   return os;
}

---