public import "ecere"

import "ArrayFactoredGrowth"

private:

public import "ecere"

import "ArrayUtilities"

private:

public struct BIloc
{
   bool valid;
   uint offset;
   uint pos;

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

public class BinaryIndex : Array
{
   type = class(uint);
   BinaryIndex()
   {
      threshold = 8;
   }
public:
   uint * const _;
   uint threshold;
   void * client;

   int (*Compare)(void * client, uint offset, typed_object data);

   BIloc Find(typed_object data)
   {
      BIloc result { };
      if(_count && data._class)
      {
         uint lo = 0, hi = _count - 1;
         for( ; hi - lo >= threshold; )
         {
            uint tri = (hi - lo) / 3;
            uint i = lo + tri;
            if(Compare(client, _[i], data) > 0)
               hi = i;
            else
            {
               i = hi - tri;
               if(Compare(client, _[i], data) < 0)
                  lo = i;
               else
                  lo += tri, hi -= tri;
            }
         }
         if(Compare(client, _[lo], data) <= 0)
         {
            if(Compare(client, _[hi], data) >= 0)
            {
               uint i;
               for(i = lo + 1; Compare(client, _[i], data) <= 0; i++);
               result.pos = i;
               if(Compare(client, _[i], data) == 0)
                  result.valid = true, result.offset = _[i];
            }
            else
            {
               if(Compare(client, _[hi], data) <= 0)
                  result.pos = hi + 1;
               else
                  result.valid = true, result.pos = hi, result.offset = _[hi];
            }
         }
         else
         {
            result.pos = lo;
            if(Compare(client, _[lo], data) == 0)
               result.valid = true, result.offset = _[lo];
         }
      }
      return result;
   }
   
   //void OnSerialize(IOChannel channel)
   //void OnUnserialize(IOChannel channel)
}

public class StringBIArray : Array
{
   // can simply implement multiple compare modes and allow nice switching using enum for method names
   type = class(String);
public:
   String * const _;
   private BinaryIndex index { client = this, Compare = (void *)Compare };
   int Compare(uint offset, typed_object data)
   {
      return strcmp(_[offset], (String)data);
   }
   BIloc Add(String item)
   {
      BIloc result = index.Find(item);
      if(!result.valid)
      {
         result.offset = _count;
         Append(1);
         _[result.offset] = item;
         index.Insert(result.pos, 1);
      }
      return result;
   }
   BIloc Remove(String item)
   {
      
   }
}