//     This is a part of the SvmFu library, a library for training//     Support Vector Machines.  Copyright (C) 2000 rif and MIT////     Contact: rif@mit.edu//     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 USAusing namespace std;#include <stdio.h>#include <iostream>#include <fstream>#include "SvmFuSvmKernCache.h"// for set_difference#include <algorithm>#ifdef CallTemplate#undef CallTemplate#endif#define CallTemplate(rettype, funcname) \template<class DataPt, class KernVal> \rettype SvmKernCache<DataPt, KernVal>::funcname#ifdef InlineTemplate#undef InlineTemplate#endif#define InlineTemplate(rettype, funcname) \template<class DataPt, class KernVal> \rettype SvmKernCache<DataPt, KernVal>::funcname/*! \class SvmKernCache * * New design by vking@mit.edu, spring 2001. * * Maintains a row and column for each point in the working set, * plus a configurable number of extra rows which are assigned * to the most violating points from outside the working set. * All kernel computations are now done internally on demand. * Kernel product access functions are available for working set * indices and training set indices. * * Original rif comments: *  * It's designed to be passed and forth between SmallOpt and  * LargeOpt.  There is some redundancy here (both the Svm and the * KernCache store the trnSetPtr and the kernProdFuncPtr, sadly; this * could potentially lead to hard-to-find bugs later) * Even though it is redundant, we store full rows.  We could save half * the space by storing in an upper triangular form, but then we would * take longer and have to copy to provide entire rows, which is the most  * common operation. * * Index arguments to functions are into the full training set, * not the working set. Mappings from working set indices to * training set indices are left to using code. */template<class DataPt, class KernVal>SvmKernCache<DataPt, KernVal>::SvmKernCache(int workingSetSize, int extraRows, int trnSetSize, const DataPt * const trnSetPtr, const KernVal (*kernProdFuncPtr)(const DataPt &,				  const DataPt &))  : columns_(workingSetSize), rows_(workingSetSize + extraRows),    trnSetSize_(trnSetSize), trnSetPtr_(trnSetPtr),    kernProdFuncPtr_(kernProdFuncPtr){   if (rows_ > trnSetSize_) rows_ = trnSetSize_;  kernelRows_ = new KernVal *[rows_];  kernelRowsGeneratedP_ = new bool[rows_];  kernelRowsAllocatedP_ = new bool[rows_];    colToTrnSet_ = new int[columns_];  rowToTrnSet_ = new int[rows_];  trnSetToRow_ = new int[trnSetSize_];  trnSetToCol_ = new int[trnSetSize_];  for (int i = 0; i < columns_; i++)  {    colToTrnSet_[i] = -1;  }    for (int i = 0; i < rows_; i++) {    rowToTrnSet_[i] = -1;    kernelRowsGeneratedP_[i] = false;    kernelRowsAllocatedP_[i] = false;  }    for (int i = 0; i < trnSetSize_; i++)  {    trnSetToRow_[i] = -1;    trnSetToCol_[i] = -1;  }  kernelComputations_ = 0;  readFromFile_ = false;}  template<class DataPt, class KernVal>SvmKernCache<DataPt, KernVal>::~SvmKernCache() {  int rA = 0;  for (int i = 0; i < rows_; i++) {    if (kernelRowsAllocatedP_[i]) {      rA++;      delete[] kernelRows_[i];    }  }  cout << "ROWS ALLOCATED: " << rA << endl;  cout << "KERNEL COMPUTATIONS: " << kernelComputations_ << endl;  delete[] kernelRows_;  delete[] kernelRowsGeneratedP_;  delete[] kernelRowsAllocatedP_;  delete[] rowToTrnSet_;  delete[] colToTrnSet_;  delete[] trnSetToRow_;  delete[] trnSetToCol_;}/*! \fn SvmKernCache<DataPt, KernVal>::workingSetChanged (int *, set<QueueElt_) * * Assign a column to each point specified by workingSetIndices * and an extra row to as many of the points from the top of * others as space allows. * * Algorithm: use the new working set array as our column assignments. * Then compute the set of points to add to rows and the set of points * to remove from rows by subtracting the new set of points we want to * assign rows from the points that are currently assigned to rows, * and swap the two sets pairwise. * */template<class DataPt, class KernVal> voidSvmKernCache<DataPt, KernVal>::workingSetChanged(const int * const workingSet, const priority_queue<QueueElt_> &others){  // copy non-working-set queue  priority_queue<QueueElt_> nonWorkingSet = others;  // for rows and columns  set<int> pointsToCache;  set<int> currentlyCachedPoints;  // for rows  list<int> pointsToRemoveFromRows;  list<int> pointsToAddToRows;  list<int> availableRows;  // for columns  list<int> pointsToRemoveFromCols;  list<int> pointsToAddToCols;  list<int> availableCols;  //////////////////////////////  // update column assignments  //////////////////////////////  // we assign columns in the same order as the working set,  // because it's guaranteed to be an optimal assignment,  // and because it lets us pass out pointers to cache rows  // which are in the same order as the working set.  list<int> reassignedCols;  for (int i = 0; i < columns_; i++)    {      // remember which columns changed, adjust mappings      if (colToTrnSet_[i] != workingSet[i]) {	reassignedCols.push_back(i);	if (colToTrnSet_[i] != -1) {	  trnSetToCol_[colToTrnSet_[i]] = -1;	}	colToTrnSet_[i] = workingSet[i];	trnSetToCol_[workingSet[i]] = i;      }    }    // invalidate the columns row-wise to help linearity of reference  if (!readFromFile_) {    for (int cacheRow = 0; cacheRow < rows_; cacheRow++)      {	kernelRowsGeneratedP_[cacheRow] = false; // sadly...	if (kernelRowsAllocatedP_[cacheRow])	  {	    for (list<int>::iterator it = reassignedCols.begin();		 it != reassignedCols.end(); it++)	      {		invalidateCell(cacheRow, *it);	      }	  }      }  }  ///////////////////////////  // update row assignments  ///////////////////////////      // collect points from the new working set  for (int i = 0; i < columns_; i++)    {      pointsToCache.insert(workingSet[i]);    }  // collect sets from our row mapping  for (int i = 0; i < rows_; i++)    {      if (rowToTrnSet_[i] != -1) {	currentlyCachedPoints.insert(rowToTrnSet_[i]);      } else {	availableRows.push_back(i);      }    }  // gather enough points off the queue to fill up our extra rows  int nws_size = nonWorkingSet.size();  for (int i = 0; (i < rows_ - columns_) && (i < nws_size); i++)    {      pointsToCache.insert(nonWorkingSet.top().elt_);      nonWorkingSet.pop();    }    // compute their differences  set_difference(currentlyCachedPoints.begin(),		 currentlyCachedPoints.end(),		 pointsToCache.begin(),		 pointsToCache.end(),		 inserter(pointsToRemoveFromRows,			  pointsToRemoveFromRows.begin()));    set_difference(pointsToCache.begin(),		 pointsToCache.end(),		 currentlyCachedPoints.begin(),		 currentlyCachedPoints.end(),		 inserter(pointsToAddToRows,			  pointsToAddToRows.begin()));    // for each point to add, either swap it with the next point  // to remove, or assign it to an empty row  list<int>::iterator pointToRemove = pointsToRemoveFromRows.begin();  list<int>::iterator emptyRow = availableRows.begin();  for (list<int>::iterator it = pointsToAddToRows.begin();       it != pointsToAddToRows.end(); it++) {    int trnSetPtToAdd = *it;    int destRow;        if (pointToRemove != pointsToRemoveFromRows.end())      {	int trnSetIndex = *pointToRemove;	pointToRemove++;	destRow = trnSetToRow_[trnSetIndex];		// purge obsolete point from map	trnSetToRow_[trnSetIndex] = -1;      }    else      {	destRow = *emptyRow;	emptyRow++;      }        // update our mappings    rowToTrnSet_[destRow] = trnSetPtToAdd;    trnSetToRow_[trnSetPtToAdd] = destRow;        // mark the row as invalid    if (kernelRowsAllocatedP_[destRow] && !readFromFile_)      {	for (int i = 0; i < columns_; i++)	  {	    invalidateCell(destRow, i);	  }      }  }}CallTemplate(void, saveToFile)(char *fileName){