// FixedArray.h

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#ifndef FixedArrayh
#define FixedArrayh

/* This would normally be used to hold an array of sorted data which you need to search very quickly (Binary Chop is used).
A sequential sort is also available for unsorted data.
It was developed for a graphics application which,
while drawing potentially millions of things on the screen,
needed to know if the thing it was currently drawing
was "selected" or not (by the user).
So the array held the ID of selected entites which would be drawn in a specific way.
The array is set up before the redraw and the renderer asks the array if it contains the ID of each entity before it draws it.
Obviously this required a search with minimal overhead - hashing was slower because of the large range of IDs and the small number of entites normally selected.
See the Tester class at the end of this file for usage examples.
The Flat flag and Grow members are intended only for use while developing algorithms which are intended ultimately to result in fixed arrays. */

template <typename T>
struct CFixedArray {
  bool Flat; // Flat Types can use memcpy to Grow
  T*   Data;
  int  Count;
  CFixedArray(bool Flat=false)            : Flat(Flat), Count(0), Data(0) {}
  CFixedArray(int Count, bool Flat=false) : Flat(Flat), Count(Count) {Data=new T[Count];}
  CFixedArray(CFixedArray& FA) {Set(FA.Data, FA.Count, FA.Flat);}
  void Set(T* src, int n, bool _Flat=false) {Flat=_Flat; SetSize(n); memcpy(Data, src, n*sizeof(T));}
  void SetSize(int n)      {Empty(); Data=new T[Count=n];}
  virtual ~CFixedArray()   {try{Empty();}catch(...){ASSERT(0);}}
  T& operator[](T i) const {return Data[i];}
  void Empty() {
    delete[] Data;
    Data=0;
    Count=0;
  }
  int Search(const T& Target) const { // Sequential search, returns the index of the found element or -1 on failure:
    T* it=Data;
    for(int i=Count; i; --i) if(*it++==Target) return Count-i;
    return -1;
  }
  bool Find(const T& Target) const { // Binary chop:
    if(Count==0) return false;
    int stt=0;
    int mid=0;
    int end=Count;
    while(stt!=end) {
      mid=(stt+end)/2;
      if(Data[mid]==Target) break;
      if(Data[mid]> Target) end=mid;
      else stt=mid+1;
    }
    return Data[mid]==Target;
  }
// While developing a new algorithm the following code may be useful until you find a way to fix the size of the array:
// Check that the array can hold n members. If it can't, grow the array by Blocksize members:
  bool Check(int n, int Blocksize=512) {if(n<Count) return true; n=(n+(1<<Blocksize)) & ((1<<Blocksize)-1); return Flat ? memcpyGrow(n) : Grow(n);}
  bool Grow(int n=512) {
    T* OldData=Data;  Data=new T[Count+n];
    if(Data==0) return false;
    T* src=OldData;
    T* dst=Data;
    for(int i=Count; i--; *dst++=*src++);
    delete[] OldData;
    Count+=n;
    return true;
  }
  bool memcpyGrow(int n=512) {
    T* OldData=Data;  Data=new T[Count+n];
    if(Data==0) return false;
    memcpy(Data, OldData, Count*sizeof(T));
    delete[] OldData;
    Count+=n;
    return true;
  }
};

#ifdef Assert
static struct CFixedArrayTester : Tester {
  CFixedArrayTester() {
    CFixedArray<int> Array; // A cached snapshot of the Entities which provides fast searches for renderers.
    Assert(Array.Count==0);
    Array.SetSize(3);
    Assert(Array.Count==3);
    int* dst=Array.Data;
    *dst++=1;
    *dst++=2;
    *dst++=3;
    Assert( Array.Find(1)); // Very fast "Find" function for Renderers.
    Assert( Array.Find(2));
    Assert( Array.Find(3));
    Assert(!Array.Find(4));
    Assert(Array[1]==Array.Data[1]);
    Array.SetSize(2);       // Make it smaller
    Assert(Array.Count==2);
    Array[0]=4;
    Array[1]=5;
    Assert(!Array.Find(3));
    Assert( Array.Find(4));
    Assert( Array.Find(5));
    Array.SetSize(4);       // Make it bigger
    Assert(Array.Count==4);
    Array[0]=6;
    Array[1]=7;
    Array[2]=8;
    Array[3]=9;
    Assert(!Array.Find(5));
    Assert( Array.Find(6));
    Assert( Array.Find(7));
    Assert( Array.Find(8));
    Assert( Array.Find(9));
    Array.Empty();
    Assert(Array.Count==0);
    Array.SetSize(4);       // Make it bigger
    Array[0]=1;
    Array[1]=2;
    Array[2]=3;
    Array[3]=4;
    Array.Grow(4);
    Assert(Array.Count==8);
    Array[4]=5;
    Array[5]=6;
    Array[6]=7;
    Array[7]=8;
    Assert(Array[0]==1);
    Assert(Array[1]==2);
    Assert(Array[2]==3);
    Assert(Array[3]==4);
    Assert(Array[4]==5);
    Assert(Array[5]==6);
    Assert(Array[6]==7);
    Assert(Array[7]==8);
    Array.memcpyGrow(4);
    Assert(Array.Count==12);
    Array[ 8]= 9;
    Array[ 9]=10;
    Array[10]=11;
    Array[11]=12;
    Assert(Array[ 0]== 1);
    Assert(Array[ 1]== 2);
    Assert(Array[ 2]== 3);
    Assert(Array[ 3]== 4);
    Assert(Array[ 4]== 5);
    Assert(Array[ 5]== 6);
    Assert(Array[ 6]== 7);
    Assert(Array[ 7]== 8);
    Assert(Array[ 8]== 9);
    Assert(Array[ 9]==10);
    Assert(Array[10]==11);
    Assert(Array[11]==12);
  }
} CFixedArrayTester;
#endif // def Assert

#endif // ndef FixedArrayh