// Program: fibonacci.cpp
// Purpose: Demonstrate a search of a sorted array using Fibonacci numbers
// Copyright (c) 1999 scott c rogan
// Date:  2 October 1999

// Problem definition specifies a maximum array size
#define ARRAYSIZE 1000
 

// Shell sort class
// list is the list to be sorted; n is the number of elements in list
template <class Comparable>
void shellsort (vector <Comparable> &list, unsigned long n)
{
 unsigned long lInc = 0;    // Shell increment
 unsigned long i;
 unsigned long j;
 Comparable tmp;      // Hold list element
 

 // Calculate an increment of form 3^k - 1
 
 do
 {
  lInc *= 3;
  lInc++;
 } while (lInc <= n);
 

 do
 {
  // Loop thru the partially sorted array

  lInc /= 3;
  for (i = lInc + 1; i <= n; i++)
  {
   tmp = list[i];
   j = i;

   // Straight insertion

   while (list[j - lInc] > tmp)
   {
    list[j] = list[j - lInc];
    j -= lInc;
    if ( j <= lInc)
     break;
   }
   list[j] = tmp;
  }
 } while (lInc > 1);
}
 
 

class FibSearch
{

private:
 int fibs[ARRAYSIZE];    // Array of fibonacci numbers
 int nNumber;      // Number of elements to search thru
 int nLowq;       // Left part of array pointer
 int nHighp;       // Right part of array pointer
 int nIndex;       // Element currently being examined
 int nSplits;      // Number of times array was split

public:
 FibSearch(int);
 bool find(vector<int> const &, int);
 int getSplits() { return nSplits; }

private:
 fibnums();       // Build array of fibonacci numbers

};

FibSearch::fibnums()
{
 // Generate the fibonacci numbers in fibs[].  Establish upper and lower
 // pointers.  Determine starting index.
 
 int k;

 fibs[0] = fibs[1] = 1;
 
 k = 1;
 do
 {
  nLowq = fibs[k - 1];
  nHighp = fibs[k];
  k++;
  fibs[k] = fibs[k - 1] + fibs[k - 2];

  // Dont allow index to go beyond boundary of array to be searched
  if (fibs[k] <= nNumber)
   nIndex = fibs[k];
 
 } while (fibs[k] < nNumber);

 
}

// Find element nTargetValue in list, list.  Return true if found
// false otherwise.

bool FibSearch::find(vector<int> const &list, int nTargetValue)
{
 int nTemp;
 bool bResult = false;
 bool bContinue = true;
 int nElement;

 nSplits = 0;
 while (bContinue)
 {
  nElement = list[nIndex];
  if (nTargetValue == nElement)
  {
   // Found it!  No need to continue
   bContinue = false;
   bResult = true;
  }
  else if (nTargetValue < nElement)
  {
 
   if (nLowq == 0)
    // Did not find element
    bContinue = false;
   else
   {
    // Adjust search to left part of array
    nSplits++;
    nIndex -= nLowq;
    nTemp = nHighp;
    nHighp = nLowq;
    nLowq = nTemp - nLowq;
 
   }

  }
  else if (nTargetValue > nElement)
  {
   if (nHighp == 1)
    // Did not find element
    bContinue = false;
   else
   {
    // Adjust search to right part of array
    nSplits++;
    if (nIndex + nLowq <= nNumber)
     nIndex += nLowq;
    nHighp -= nLowq;
    nLowq -= nHighp;
   }

  }
 
 }

 return bResult;

}
 

FibSearch::FibSearch(int nMyNum)
{
 nNumber = nMyNum;
 fibnums();
}
 
 
 

int main()
{

 vector<int> myList(ARRAYSIZE + 1);
 int i;
 int nTarget;
 FibSearch *fbs;

 
 // Get target value
 cout << "Enter value to search for (1 - 6765): ";
 cin >> nTarget;
 cout << endl;

 // Keep target value within desired bounds
 if (nTarget > 6765 || nTarget < 1)
 {
  cout << "Try again." << endl;
  exit(1);
 }
 
 

 
 // Reseed "random" number generator with current time
 // and populate list with numbers between 1 and 6765
 srand( (unsigned)time( NULL ) );

 for(i = 1; i < (ARRAYSIZE + 1); i++)
  myList[i] = (rand() % 6765) + 1;

 
 // Sort the list
 shellsort(myList, ARRAYSIZE);

 // Display the sorted array
 cout << "Generated List:" << endl << endl;

 for(i = 1; i < (ARRAYSIZE + 1); i++)
  cout << myList[i] << ",";
 cout << endl;

 // Instantiate a FibSearch object to search list for a target value
 fbs = new FibSearch(ARRAYSIZE);

 cout << "Found value (" << nTarget << "): ";
 
 // Search list and report result
 if (fbs -> find(myList, nTarget))
  cout << "YES" << endl;
 else
  cout << "NO" << endl;
 

 // Report number of array splits
 cout << "Number of splits: " << fbs -> getSplits() << endl;
 
 

 return 0;

}