public import "ecere"

import "ArrayUtilities"

private:

define array = ((BinarySortedArrayImpl)this).a;

public struct BSloc
{
   bool valid;
   uint pos;
   //void * item;

   String ToString()
   {
      String result = new char[30 + 6 + 11];
      sprintf(result, "BSloc { valid=%d, pos=%u }\n", valid, pos);
      return result;
   }
};

class BinarySortedArrayImpl
{
   uint _size;
   uint _count;
   uint _factor;
   uint _threshold;
   Class type;
   void ** a;
};

// do another class that uses a compare method or modify to use the compare method if it was provided
public class ArrayBinarySorted
{
   uint _size;
   uint _count;
   uint _factor;
   uint _threshold;

   ~ArrayBinarySorted()
   {
      delete array;
   }

public:   
   Class type;
   property uint count
   {
      set
      {
         if(value != _count)
         {
            int newsize = (value / _factor + 1) * _factor;
            if(newsize != _size)
               size = value ? newsize : 0;
            _count = value;
         }
      }
      get { return _count; }
   }
   property uint size
   {
      set
      {
         if(value != _size)
         {
            if(array)
            {
               if(value)
                  array = renew array void * [value * sizeof(void *)];
               else
                  delete array;
            }
            else if(value)
               array = new void * [value * sizeof(void *)];
            _size = value;
         }
      }
      get { return _size; }
   }
   property uint growingFactor { set { _factor = value; } get { return _factor; } }
   property void * data
   {
      set
      {
         memcpy(array, value, _size * sizeoftype);
      }
   }
   void Append(int n)
   {
      count += n;
   }
   void Insert(uint position, int n)
   {
      Append(n);
      if(position < _count - 1)
         MoveBytes(array + (position + n) * sizeoftype, array + position * sizeoftype, (_count - position - n) * sizeoftype);
   }
   void Trim(int n)
   {
      count -= n;
   }
   void Remove(uint position, int n)
   {
      if(position + n - 1 < _count - 1)
         MoveBytes(array + position * sizeoftype, array + (position + n) * sizeoftype, (_count - position - n) * sizeoftype);
      Trim(n);
   }
   BSloc Find(void * item)
   {
      BSloc result { };
      if(_count && item)
      {
         uint lo = 0, hi = _count - 1;
         for( ; hi - lo >= _threshold; )
         {
            uint tri = (hi - lo) / 3;
            uint i = lo + tri;
            //if(Compare(client, _[i], item) > 0)
            if(array[i] > item)
               hi = i;
            else
            {
               i = hi - tri;
               if(array[i] < item)
                  lo = i;
               else
                  lo += tri, hi -= tri;
            }
         }
         if(array[lo] <= item)
         {
            if(array[hi] >= item)
            {
               uint i;
               for(i = lo + 1; array[i] <= item; i++);
               //result.oldpos = i;
               if(array[i] == item)
                  result.valid = true, result.pos = i;
            }
            else
            {
               if(array[hi] <= item)
                  ;//result.oldpos = hi + 1;
               else
                  result.valid = true/*, result.oldpos = hi*/, result.pos = hi;
            }
         }
         else
         {
            //result.oldpos = lo;
            if(array[lo] == item)
               result.valid = true, result.pos = lo;
         }
      }
      return result;
   }
   
};

public class StringBSArray : ArrayBinarySorted
{
   type = class(String);
public:
   String * const _;
   BSloc Add(String item)
   {
      BSloc result = Find(item);
      if(!result.valid)
      {
         Insert(result.pos, 1);
         _[result.pos] = item;
      }
      return result;
   }
   BSloc Remove(String item)
   {
      
   }
}