The Ecere SDK - ede/blob - explorer/src/Structures/ArrayBinaryIndexed.ec

   1 public import "ecere"
   2
   3 import "ArrayFactoredGrowth"
   4
   5 private:
   6
   7 public import "ecere"
   8
   9 import "ArrayUtilities"
  10
  11 private:
  12
  13 public struct BIloc
  14 {
  15    bool valid;
  16    uint offset;
  17    uint pos;
  18
  19    String ToString()
  20    {
  21       String result = new char[30 + 6 + 11 + 11];
  22       sprintf(result, "BIloc { valid=%d, offset=%u, pos=%u }\n", valid, offset, pos);
  23       return result;
  24    }
  25 };
  26
  27 public class BinaryIndex : Array
  28 {
  29    type = class(uint);
  30    BinaryIndex()
  31    {
  32       threshold = 8;
  33    }
  34 public:
  35    uint * const _;
  36    uint threshold;
  37    void * client;
  38
  39    int (*Compare)(void * client, uint offset, typed_object data);
  40
  41    BIloc Find(typed_object data)
  42    {
  43       BIloc result { };
  44       if(_count && data._class)
  45       {
  46          uint lo = 0, hi = _count - 1;
  47          for( ; hi - lo >= threshold; )
  48          {
  49             uint tri = (hi - lo) / 3;
  50             uint i = lo + tri;
  51             if(Compare(client, _[i], data) > 0)
  52                hi = i;
  53             else
  54             {
  55                i = hi - tri;
  56                if(Compare(client, _[i], data) < 0)
  57                   lo = i;
  58                else
  59                   lo += tri, hi -= tri;
  60             }
  61          }
  62          if(Compare(client, _[lo], data) <= 0)
  63          {
  64             if(Compare(client, _[hi], data) >= 0)
  65             {
  66                uint i;
  67                for(i = lo + 1; Compare(client, _[i], data) <= 0; i++);
  68                result.pos = i;
  69                if(Compare(client, _[i], data) == 0)
  70                   result.valid = true, result.offset = _[i];
  71             }
  72             else
  73             {
  74                if(Compare(client, _[hi], data) <= 0)
  75                   result.pos = hi + 1;
  76                else
  77                   result.valid = true, result.pos = hi, result.offset = _[hi];
  78             }
  79          }
  80          else
  81          {
  82             result.pos = lo;
  83             if(Compare(client, _[lo], data) == 0)
  84                result.valid = true, result.offset = _[lo];
  85          }
  86       }
  87       return result;
  88    }
  89
  90    //void OnSerialize(IOChannel channel)
  91    //void OnUnserialize(IOChannel channel)
  92 }
  93
  94 public class StringBIArray : Array
  95 {
  96    // can simply implement multiple compare modes and allow nice switching using enum for method names
  97    type = class(String);
  98 public:
  99    String * const _;
 100    private BinaryIndex index { client = this, Compare = (void *)Compare };
 101    int Compare(uint offset, typed_object data)
 102    {
 103       return strcmp(_[offset], (String)data);
 104    }
 105    BIloc Add(String item)
 106    {
 107       BIloc result = index.Find(item);
 108       if(!result.valid)
 109       {
 110          result.offset = _count;
 111          Append(1);
 112          _[result.offset] = item;
 113          index.Insert(result.pos, 1);
 114       }
 115       return result;
 116    }
 117    BIloc Remove(String item)
 118    {
 119
 120    }
 121 }
 122