/***************************************************************************
                          MetricTree.cpp  -  description
                             -------------------
    begin                : Don Aug 14 2003
    copyright            : (C) 2003 by klaus frieler
    email                : kgf@omniversum.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/
#include "Types.h"
#include "MetricTree.h"
#include "Misc.h"


char *MetricLeaf::getPointer(void *p)
{
   static char buf[128] ="";

   sprintf(buf, "0x%p", p);
   
   return buf;
   
}
void MetricLeaf::setName()
{
   char buf[128];
   m_sName = "";
   sprintf(buf, "%d=", metricStruct[0]);
   m_sName += string(buf);
   for(uint i = 1; i<metricStruct.size()-1; ++i){
      sprintf(buf, "%d+", metricStruct[i]);
      m_sName += string(buf);
   }
   sprintf(buf, "%d", metricStruct[metricStruct.size()-1]);
   m_sName += string(buf);
   
}
vector<uint> MetricLeaf::getPrimaryBeats()
{
   vector<uint> beats;
   uint sum = 1;
   beats.push_back(sum);
   //cout<<"Added Beat: "<<sum<<endl;
   for(uint i = 1; i<metricStruct.size()-1;++i){
      sum +=metricStruct[i];
      beats.push_back(sum);
      //cout<<"Added Beat: "<<sum<<endl;
   }
   return beats;   
}

vector<uint> MetricLeaf::getSecondaryBeats()
{
   vector<uint> beats;
   uint sum = 1;
   for(uint i = 1; i<metricStruct.size();++i){
      sum++;
      beats.push_back(sum);
      //cout<<"Added Beat: "<<sum<<endl;
      sum++;
      if(metricStruct[i] == 3){
         beats.push_back(sum);
         //cout<<"Added Beat: "<<sum<<endl;
         sum++;
      }
   }
   return beats;
}

bool MetricLeaf::buildTree(uint val, vector<MetricLeaf*>& endLeaves)
{
   bool right = false, left = false;
   if(val<2){
      m_pLeft = 0;
      m_pRight = 0;
      m_val = 0;
      //cout<<"No leaves built."<<endl;
      return false;
   }

   if(val == 2){      
      m_pRight   = new MetricLeaf(2, metricStruct, this);
      m_pLeft    = 0;
      m_val = 2;
      endLeaves.push_back(m_pLeft);
      //cout<<"Built 2-leaf."<<endl;
      return true;
   }
   if(val == 3){
      m_pRight = 0;
      m_pLeft  = new MetricLeaf(3, metricStruct,this);
      //cout<<"Built 3-leaf."<<endl;
      m_val = 3;
      endLeaves.push_back(m_pRight);
      return true;
   }
   
   m_pRight= new  MetricLeaf(2, metricStruct, this);
   m_pLeft     = new  MetricLeaf(3, metricStruct,this);
   
   //cout<<"Built 2 leaves."<<endl;
   right = m_pRight->buildTree(val - 2, endLeaves);
   left  =  m_pLeft->buildTree(val - 3, endLeaves);
   
   if(!left){
      delete m_pLeft;
      m_pLeft = 0;
   }
   if(!right){
      delete m_pRight;
      m_pRight = 0;
   }

   return left || right;
}


uint MetricLeaf::getLeafCount()
{
   uint lCount = 0, rCount = 0;
   if(m_pLeft != 0){
       lCount = m_pLeft->getLeafCount();
   }
   if(m_pRight != 0){
      rCount = m_pRight->getLeafCount();
   }
   return 1+lCount + rCount;
}


void MetricLeaf::dumpSubTree()
{
   if(m_pLeft){
      m_pLeft->dumpSubTree();
   }
   if(m_pRight){
         m_pRight->dumpSubTree();
   }
   if(!m_pLeft && !m_pRight){
      cout<<m_sName.c_str()<<endl;
   }

}
   

void MetricTree::buildTree(uint val )
{
   vector<uint> dummy;
   if(m_pHead){
      delete m_pHead;
   }
   m_pHead = new MetricLeaf(val, dummy);
   if(val<2) return;
   if(!m_pHead->buildTree(val, m_EndLeaves) )
      delete m_pHead;   
}

void MetricTree::dumpTree()
{
  if(!m_pHead) return;
  m_pHead->dumpSubTree(); 
}

uint MetricTree::getLeafCount()
{
   uint nCount = 0;
   if(m_pHead)
      nCount = m_pHead->getLeafCount();

   return nCount;
   
}
vector<uint> MetricTree::getPrimaryBeats(uint ndx)
{
   vector<uint> ret;
   if(ndx>=m_EndLeaves.size()) return ret;
   ret = m_EndLeaves[ndx]->getPrimaryBeats();
   return ret;
}

vector<uint> MetricTree::getSecondaryBeats(uint ndx)
{
   vector<uint> ret;
   if(ndx>=m_EndLeaves.size()) return ret;
   ret = m_EndLeaves[ndx]->getSecondaryBeats();
   return ret;
}

eBeatType MetricTree::getBeatType(uint val)
{
   vector<uint> ret = getPrimaryBeats(0);
   size_t i = 0;
   for(i = 0; i<ret.size(); ++i){
      if(ret[i] == val) return eBeat_primary;
   }      
   ret = getSecondaryBeats(0);
   for(i = 0; i<ret.size(); ++i){
      if(ret[i] == val) return eBeat_secondary;
   }      
   return eBeat_unknown;
}

//MetricTree2 iplementation
vector<uint> MetricTree2::getMinimalPartition(const uint val)
{  
   vector<uint> ret;
   if(val<4) return ret;
   if(val%2 == 0){
      ret.push_back(val/2);
      ret.push_back(val/2);
      return ret;
   }
   if(val%3 == 0){
      ret.push_back(val/3);
      ret.push_back(val/3);
      ret.push_back(val/3);
      return ret;
   }
   uint bigHalf = val/2 + 1;
   uint smallHalf = val/2;
   uint bigThird = val/3 + 1;
   uint smallThird = val/3;
   uint duplePoints = (bigHalf % 2)*(bigHalf % 3) + (smallHalf % 2)*(smallHalf % 3);
   uint triplePoints = (bigThird % 2) * (bigThird % 3)+ (smallThird % 2) *(smallThird % 3);
   if(duplePoints<=triplePoints){
      if(smallHalf % 2 ==0 ) swap<uint>(bigHalf, smallHalf);
      ret.push_back(bigHalf);
      ret.push_back(smallHalf);
   }
   else{
      if(smallThird % 2 ==0 ) swap<uint>(bigThird, smallThird);
      ret.push_back(bigThird);
      if(val % 2 == 1){
         ret.push_back(bigThird);      
      }
      else{
         ret.push_back(smallThird);            
      }
      ret.push_back(smallThird);            
   }
   return ret;
}
void MetricTree2::buildTree()
{
   switch(m_nSize){
      case 0:
      case 1:
         return;
      break;
      case 2:
      {
         MetricTree2* pNew = new MetricTree2(1, m_nVal);
         m_pNodes.push_back(pNew);
         pNew = new MetricTree2(1, m_nVal+ 1);
         m_pNodes.push_back(pNew);
      }
      break;
      case 3:
      {
         MetricTree2* pNew = new MetricTree2(1, m_nVal);
         m_pNodes.push_back(pNew);
         pNew = new MetricTree2(1, m_nVal+ 1);
         m_pNodes.push_back(pNew);
         pNew = new MetricTree2(1, m_nVal + 2);
         m_pNodes.push_back(pNew);
                
      }
      break;
      default:
      {
         vector<uint> part = getMinimalPartition(m_nSize);
         uint offset = m_nVal;
         for(uint i = 0; i<part.size(); ++i){           
            //cout<<"Offset = "<<offset<<endl;
            MetricTree2* pNew = new MetricTree2(part[i], offset);
            m_pNodes.push_back(pNew);
            offset +=part[i];             
         }
      }
      break;
   }
}
void MetricTree2::dump()const
{
   if(m_pNodes.empty()){
      cout<<m_nVal<<" ";
      return;
   }
   for(uint i = 0; i<m_pNodes.size(); ++i){
      m_pNodes[i]->dump();
   }
   cout<<endl;
}

uint MetricTree2::getMinUnit()const
{ 
   if(m_pNodes.empty()){
      return 1;
   }
   uint max = m_pNodes[m_pNodes.size()-1]->getVal();
   return m_nSize - m_pNodes[m_pNodes.size()-1]->getVal();
} 

uint MetricTree2::getBeatLevel(const uint beat)const
{
   return count(beat-1)-1;
}
eBeatType MetricTree2::getBeatType(const uint beat)const
{
   uint depth = getDepth();
   uint beatLevel = getBeatLevel(beat);
   //if(beatLevel == depth || beatLevel == depth -1) return eBeat_primary;
   if(beatLevel >0) return eBeat_primary;
   return eBeat_secondary;
}

uint MetricTree2::getDepth()const
{
   return getBeatLevel(1);
}

uint MetricTree2::count(const uint val)const
{
   uint sum = 0;
   if(val == m_nVal)
      sum = 1;
   if(m_pNodes.empty()){ 
      return sum;
   }
   for(uint i = 0; i<m_pNodes.size(); ++i){
      sum +=m_pNodes[i]->count(val);
   }
   return sum;
}
void testMetricTree2()
{   
   for(uint k = 2; k<16; ++k){ 
      MetricTree2 mTree(k);
      cout<<"Signature = "<<k<<" Depth = "<<mTree.getDepth()<<endl;
      //mTree.dump();
      for(uint i = 0; i<k; ++i){
         eBeatType bt = mTree.getBeatType(i+1);
         switch(bt){
            case eBeat_primary:
               cout<<"+";
               break;
            case eBeat_secondary:
               cout<<"-";
               break;
         }
      }
      cout<<endl;
      for(uint i = 0; i<k; ++i){
         int bt = mTree.getBeatLevel(i+1);
         cout<<bt<<" ";
      }
      cout<<endl;
   }
}
