cannam@0: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
cannam@0: 
cannam@0: /*
cannam@0:     Vamp feature extraction plugin using the MATCH audio alignment
cannam@0:     algorithm.
cannam@0: 
cannam@0:     Centre for Digital Music, Queen Mary, University of London.
cannam@0:     This file copyright 2007 Simon Dixon, Chris Cannam and QMUL.
cannam@0:     
cannam@0:     This program is free software; you can redistribute it and/or
cannam@0:     modify it under the terms of the GNU General Public License as
cannam@0:     published by the Free Software Foundation; either version 2 of the
cannam@0:     License, or (at your option) any later version.  See the file
cannam@0:     COPYING included with this distribution for more information.
cannam@0: */
cannam@0: 
cannam@0: #include "Finder.h"
cannam@0: 
Chris@30: #include "Path.h"
Chris@30: 
Chris@30: #include <algorithm>
Chris@30: 
cannam@0: 
cannam@0: Finder::Finder(Matcher *p1, Matcher *p2)
cannam@0: {
cannam@0:     if (!p1->firstPM)
cannam@0:         std::cerr << "Warning: wrong args in Finder()" << std::endl;
cannam@0:     pm1 = p1;
cannam@0:     pm2 = p2;
cannam@0:     index1 = 0;
cannam@0:     index2 = 0;
cannam@0:     rowRange = new int[2];
cannam@0:     colRange = new int[2];
cannam@0: } // constructor
cannam@0: 
cannam@0: Finder::~Finder()
cannam@0: {
cannam@0:     delete[] rowRange;
cannam@0:     delete[] colRange;
cannam@0: }
cannam@0: 
cannam@0: bool
cannam@0: Finder::find(int i1, int i2)
cannam@0: {
cannam@0:     if (i1 >= 0) {
cannam@0:         index1 = i1;
cannam@0:         index2 = i2 - pm1->first[i1];
cannam@0:     }
cannam@0:     return (i1 >= 0) && (i2 >= pm1->first[i1]) && (i2 < pm1->last[i1]);
cannam@0: } // find()
cannam@0: 
cannam@0: void
cannam@0: Finder::getColRange(int row, int *range)
cannam@0: {
cannam@0:     range[0] = pm1->first[row];
cannam@0:     range[1] = pm1->last[row];
cannam@0: } // getColRange()
cannam@0: 
cannam@0: void
cannam@0: Finder::getRowRange(int col, int *range)
cannam@0: {
cannam@0:     range[0] = pm2->first[col];
cannam@0:     range[1] = pm2->last[col];
cannam@0: } // getRowRange()
cannam@0: 
cannam@0: int
cannam@0: Finder::getExpandDirection(int row, int col)
cannam@0: {
cannam@0:     return getExpandDirection(row, col, false);
cannam@0: } // getExpandDirection()
cannam@0: 
cannam@0: int
cannam@0: Finder::getExpandDirection(int row, int col, bool check)
cannam@0: {
cannam@0:     int min = getPathCost(row, col);
cannam@0:     bestRow = row;
cannam@0:     bestCol = col;
cannam@0:     getRowRange(col, rowRange);
cannam@0:     if (rowRange[1] > row+1)
cannam@0:         rowRange[1] = row+1;	// don't cheat by looking at future :)
cannam@0:     for (int index = rowRange[0]; index < rowRange[1]; index++) {
cannam@0:         int tmp = getPathCost(index, col);
cannam@0:         if (tmp < min) {
cannam@0:             min = tmp;
cannam@0:             bestRow = index;
cannam@0:         }
cannam@0:     }
cannam@0:     getColRange(row, colRange);
cannam@0:     if (colRange[1] > col+1)
cannam@0:         colRange[1] = col+1;	// don't cheat by looking at future :)
cannam@0:     for (int index = colRange[0]; index < colRange[1]; index++) {
cannam@0:         int tmp = getPathCost(row, index);
cannam@0:         if (tmp < min) {
cannam@0:             min = tmp;
cannam@0:             bestCol = index;
cannam@0:             bestRow = row;
cannam@0:         }
cannam@0:     }
cannam@0:     //	System.err.print("  BEST: " + bestRow + " " + bestCol + " " + check);
cannam@0:     //	System.err.println(" " + pm1->frameCount + " " + pm2->frameCount);
cannam@0:     if (check) {
cannam@0:         //		System.err.println(find(row+1, col) + " " + find(row, col+1));
cannam@0:         if (!find(row, col+1))
cannam@0:             return ADVANCE_THIS;
cannam@0:         if (!find(row+1, col))
cannam@0:             return ADVANCE_OTHER;
cannam@0:     }
cannam@0:     return ((bestRow==row)? ADVANCE_THIS: 0) |
cannam@0:         ((bestCol==col)? ADVANCE_OTHER: 0);
cannam@0: 
cannam@0: } // getExpandDirection()
cannam@0: 	
cannam@0: unsigned char
cannam@0: Finder::getDistance(int row, int col) 
cannam@0: {
cannam@0:     if (find(row, col)) {
cannam@0:         return pm1->distance[row][col - pm1->first[row]];
cannam@0:     }
cannam@0:     std::cerr << "getDistance(" << row << "," << col << "): out of bounds" << std::endl;
cannam@0:     throw "getDistance index out of bounds";
cannam@0: } // getDistance()/2
cannam@0: 
cannam@0: void
cannam@0: Finder::setDistance(int row, int col, unsigned char b)
cannam@0: {
cannam@0:     if (find(row, col)) {
cannam@0:         pm1->distance[row][col - pm1->first[row]] = b;
cannam@0:         return;
cannam@0:     }
cannam@0:     std::cerr << "setDistance(" << row << "," << col << "," << b << "): out of bounds" << std::endl;
cannam@0:     throw "setDistance index out of bounds";
cannam@0: } // setDistance()
cannam@0: 
cannam@0: int
cannam@0: Finder::getPathCost(int row, int col)
cannam@0: {
cannam@0:     if (find(row, col)) // "1" avoids div by 0 below
cannam@0:         return pm1->bestPathCost[row][col - pm1->first[row]]*100/ (1+row+col);
cannam@0:     std::cerr << "getPathCost(" << row << "," << col << "): out of bounds" << std::endl;
cannam@0:     throw "getPathCost index out of bounds";
cannam@0: } // getPathCost()
cannam@0: 	
cannam@0: int
cannam@0: Finder::getRawPathCost(int row, int col)
cannam@0: {
cannam@0:     if (find(row, col))
cannam@0:         return pm1->bestPathCost[row][col - pm1->first[row]];
cannam@0:     std::cerr << "getRawPathCost(" << row << "," << col << "): out of bounds" << std::endl;
cannam@0:     throw "getRawPathCost index out of bounds";
cannam@0: } // getRawPathCost()
cannam@0: 
cannam@0: void
cannam@0: Finder::setPathCost(int row, int col, int i)
cannam@0: {
cannam@0:     if (find(row, col)) {
cannam@0:          pm1->bestPathCost[row][col - pm1->first[row]] = i;
cannam@0:          return;
cannam@0:     }
cannam@0:     std::cerr << "setPathCost(" << row << "," << col << "," << i << "): out of bounds" << std::endl;
cannam@0:     throw "setPathCost index out of bounds";
cannam@0: } // setPathCost()
cannam@0: 
cannam@0: unsigned char
cannam@0: Finder::getDistance() 
cannam@0: {
cannam@0:     return pm1->distance[index1][index2];
cannam@0: } // getDistance()/0
cannam@0: 
cannam@0: void
cannam@0: Finder::setDistance(int b)
cannam@0: {
cannam@0:     pm1->distance[index1][index2] = (unsigned char)b;
cannam@0: } // setDistance()
cannam@0: 
cannam@0: int
cannam@0: Finder::getPathCost()
cannam@0: {
cannam@0:     return pm1->bestPathCost[index1][index2];
cannam@0: } // getPathCost()
cannam@0: 
cannam@0: void
cannam@0: Finder::setPathCost(int i)
cannam@0: {
cannam@0:     pm1->bestPathCost[index1][index2] = i;
cannam@0: } // setPathCost()
cannam@0: 
cannam@0: void
cannam@0: Finder::recalculatePathCostMatrix(int r1, int c1, int r2, int c2) 
cannam@0: {
cannam@0:     if (!find(r1,c1)) {
cannam@0:         std::cerr << "recalculatePathCostMatrix(" << r1 << "," << c1 << "): out of bounds" << std::endl;
cannam@0:         throw "recalculatePathCostMatrix index out of bounds";
cannam@0:     }
cannam@0:     int thisRowStart, c;
cannam@0:     int prevRowStart = 0, prevRowStop = 0;
cannam@0:     for (int r = r1; r <= r2; r++) {
cannam@0:         thisRowStart = pm1->first[r];
cannam@0:         if (thisRowStart < c1)
cannam@0:             thisRowStart = c1;
cannam@0:         for (c = thisRowStart; c <= c2; c++) {
cannam@0:             if (find(r,c)) {
cannam@0:                 int i2 = index2;
cannam@0:                 int newCost = pm1->distance[r][i2];
cannam@0:                 int dir = 0;
cannam@0:                 if (r > r1) {	// not first row
cannam@0:                     int min = -1;
cannam@0:                     if ((c > prevRowStart) && (c <= prevRowStop)) {
cannam@0:                         // diagonal from (r-1,c-1)
cannam@0:                         min = pm1->bestPathCost[r-1][c-pm1->first[r-1]-1] +
cannam@0:                             newCost * 2;
cannam@0:                         dir = ADVANCE_BOTH;
cannam@0:                     }
cannam@0:                     if ((c >= prevRowStart) && (c < prevRowStop)) {
cannam@0:                         // vertical from (r-1,c)
cannam@0:                         int cost = pm1->bestPathCost[r-1][c-pm1->first[r-1]] +
cannam@0:                             newCost;
cannam@0:                         if ((min == -1) || (cost < min)) {
cannam@0:                             min = cost;
cannam@0:                             dir = ADVANCE_THIS;
cannam@0:                         }
cannam@0:                     }
cannam@0:                     if (c > thisRowStart) {
cannam@0:                         // horizontal from (r,c-1)
cannam@0:                         int cost =pm1->bestPathCost[r][i2-1]+newCost;
cannam@0:                         if ((min == -1) || (cost < min)) {
cannam@0:                             min = cost;
cannam@0:                             dir = ADVANCE_OTHER;
cannam@0:                         }
cannam@0:                     }
cannam@0:                     pm1->bestPathCost[r][i2] = min;
cannam@0:                 } else if (c > thisRowStart) {	// first row
cannam@0:                     // horizontal from (r,c-1)
cannam@0:                     pm1->bestPathCost[r][i2] = pm1->bestPathCost[r][i2-1] +
cannam@0:                         newCost;
cannam@0:                     dir = ADVANCE_OTHER;
cannam@0:                 }
cannam@0:                 if ((r != r1) || (c != c1)) {
cannam@0:                     pm1->distance[r][i2] = (unsigned char)
cannam@0:                         ((pm1->distance[r][i2] & MASK) | dir);
cannam@0:                 }
cannam@0:             } else
cannam@0:                 break;	// end of row
cannam@0:         }
cannam@0:         prevRowStart = thisRowStart;
cannam@0:         prevRowStop = c;
cannam@0:     }
cannam@0: } // recalculatePathCostMatrix()
Chris@30: 
Chris@30: int
Chris@31: Finder::retrievePath(bool smooth, vector<int> &pathx, vector<int> &pathy)
Chris@30: {
Chris@30:     int x = pm2->getFrameCount() - 1;
Chris@30:     int y = pm1->getFrameCount() - 1;
Chris@30: 
Chris@30:     pathx.clear();
Chris@30:     pathy.clear();
Chris@30: 
Chris@30:     while (find(y, x) && ((x > 0) || (y > 0))) {
Chris@30: 
Chris@30:         pathx.push_back(x);
Chris@30:         pathy.push_back(y);
Chris@30: 
Chris@30:         switch (getDistance() & ADVANCE_BOTH) {
Chris@30:         case ADVANCE_THIS:  y--; break;
Chris@30:         case ADVANCE_OTHER: x--; break;
Chris@30:         case ADVANCE_BOTH:  x--; y--; break;
Chris@30:         default: // this would indicate a bug, but we wouldn't want to hang
Chris@30:             cerr << "WARNING: Neither matcher advanced in path backtrack at (" << x << "," << y << ")" << endl;
Chris@30:             if (x > y) x--; else y--; break;
Chris@30:         }
Chris@30:     }
Chris@30: 
Chris@30:     std::reverse(pathx.begin(), pathx.end());
Chris@30:     std::reverse(pathy.begin(), pathy.end());
Chris@30: 
Chris@31:     if (smooth) {
Chris@31:         int smoothedLen = Path().smooth(pathx, pathy, pathx.size());
Chris@31:         return smoothedLen;
Chris@31:     } else {
Chris@31:         return pathx.size();
Chris@31:     }
Chris@30: }
Chris@30: 
Chris@30: