//     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 USA#ifndef SVMFU_SVM_KERN_CACHE_HEADER#define SVMFU_SVM_KERN_CACHE_HEADER#include "SvmFuSvmConstants.h"#include "SvmFuSvmTypedefs.h"#include <set>#include <list>#include <map>#include <queue>//! Contains a index into the training set and a priority./*! For use in a priority queue.   * \sa SvmLargeOpt */class QueueElt_ { public:  int elt_;  double priority_;    bool operator<(const QueueElt_& x) const {     return priority_ < x.priority_;   }  QueueElt_(int elt, double priority) : elt_(elt), priority_(priority) {}};//! This is a helper class for SvmFu.  It stores cached kernel values.template <class DataPt, class KernVal> class SvmKernCache { public:    //! Constructor  SvmKernCache(int workingSetSize, int extraRows, int trnSetSize, 	       const DataPt * const trnSetPtr,	       const KernVal (*kernProdFuncPtr)(const DataPt &,						const DataPt &));    //! Destructor  ~SvmKernCache();    /////////////  // Mutators  /////////////  //! Notify of new working set and KKT violations  void workingSetChanged (const int * const workingSet,			  const priority_queue<QueueElt_> &others);  void saveToFile(char *filename);  void readFromFile(char *kernelTrainFile);  int getColToTrnSet(int ex) const;  int getTrnSetToCol(int ex) const;  int getTrnSetToRow(int ex) const;    //////////////  // Accessors  //////////////    //! Returns the kernel product of the pair of working set points  KernVal cachedKernProd (int ex1, int ex2) const;  //! Returns the kernel product of the pair of training set points  KernVal trnSetKernProd (int ex1, int ex2) const;    //! Returns a pointer to the kernel row for the working set point  KernVal *cachedKernProdRowPtr (int ex) const;  //! Return our number of extra rows  int numExtraRows () const;  bool readFromFile_;protected:    //! Allocates, updates data structures, and populates with invalid values  inline void initializeRow (int row) const;  //! Indicates whether the specified cell is valid or not  inline bool cellValid (int row, int col) const;    //! Marks the cell as invalid  inline void invalidateCell (int row, int col) const;  //! Number of rows in our matrix  int rows_;  //! Number of columns in our matrix  int columns_;  //! Number of examples in the working set  int trnSetSize_;  //! The full data set  const DataPt * const trnSetPtr_;  //! The kernel function  const KernVal(*kernProdFuncPtr_) (const DataPt &pt1, const DataPt &pt2);  //! Marks which cache rows have been allocated  mutable BoolVec kernelRowsAllocatedP_;  //! Marks which cache rows have been fully computed  mutable BoolVec kernelRowsGeneratedP_;  //! Maps our rows to their training set positions  int *rowToTrnSet_;  //! Maps our columns to their training set positions  int *colToTrnSet_;  // NOTE: Equivalent to "workingSet"  //! Maps the training set examples to their rows  int *trnSetToRow_;  //! Maps the training set examples to their columns  int *trnSetToCol_;  // NOTE: Equivalent to "workingSetPos"  //! The cache of kernel values  mutable KernVal **kernelRows_;  // statistics  mutable int kernelComputations_;};#endif // SVMFU_SVM_KERN_CACHE_HEADER