home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 04 Mommersteeg / Predictors / SimplePredictor.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-09-30  |  1.9 KB  |  54 lines
  1. //----------------------------------------------------------------------------------------------
  2. // Sequential Prediction Demo: The positioning pattern
  3. // 
  4. // Author:  Fri Mommersteeg
  5. // Date:    10-09-2001
  6. // File:    SimplePredictor.h
  7. //----------------------------------------------------------------------------------------------
  8.  
  9. //----------------------------------------------------------------------------------------------
  10. // Include files
  11. //----------------------------------------------------------------------------------------------
  12.  
  13. #include "StdAfx.h"
  14. #include "SimplePredictor.h"
  15.  
  16. //----------------------------------------------------------------------------------------------
  17. // Setup(): sets up the predictor
  18. //----------------------------------------------------------------------------------------------
  19.  
  20. void CSimplePredictor::Setup(int nWindowSize, int nMinPerformance) { 
  21.     // set up window
  22.     WindowSize = nWindowSize; 
  23.     Reset();
  24.     MinPerformance = nMinPerformance; 
  25. }
  26.  
  27. //----------------------------------------------------------------------------------------------
  28. // GetPrediction(): determines the successor using string-matching prediction (complexity O^2)
  29. //----------------------------------------------------------------------------------------------
  30.  
  31. bool CSimplePredictor::GetPrediction(int &Prediction) {
  32.     int N = window.GetSize();
  33.     int MaxStringSize = 0, MaxStringPosition = N-2;
  34.     
  35.     // if the window is empty, we are unable to make a prediction
  36.     if (window.GetSize() > 0) {
  37.                 
  38.         for (int i = N-2; i >= 0; i--) {
  39.             int j = 0;
  40.             while (i-j >= 0 && window[i-j] == window[N-1-j]) {
  41.                 j++;
  42.             }
  43.             if (j > MaxStringSize) {
  44.                 MaxStringPosition = i;
  45.                 MaxStringSize = j;
  46.             }
  47.         }
  48.         Prediction = window[MaxStringPosition+1];        
  49.     }
  50.  
  51.     // performance indicator: is the prediction good enough?
  52.     return (MaxStringSize >= MinPerformance);
  53. }
  54.