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

   1 public import "ecere"
   2
   3 import "ArrayUtilities"
   4
   5 private:
   6
   7 define array = ((BinarySortedArrayImpl)this).a;
   8
   9 public struct BSloc
  10 {
  11    bool valid;
  12    uint pos;
  13    //void * item;
  14
  15    String ToString()
  16    {
  17       String result = new char[30 + 6 + 11];
  18       sprintf(result, "BSloc { valid=%d, pos=%u }\n", valid, pos);
  19       return result;
  20    }
  21 };
  22
  23 class BinarySortedArrayImpl
  24 {
  25    uint _size;
  26    uint _count;
  27    uint _factor;
  28    uint _threshold;
  29    Class type;
  30    void ** a;
  31 };
  32
  33 // do another class that uses a compare method or modify to use the compare method if it was provided
  34 public class ArrayBinarySorted
  35 {
  36    uint _size;
  37    uint _count;
  38    uint _factor;
  39    uint _threshold;
  40
  41    ~ArrayBinarySorted()
  42    {
  43       delete array;
  44    }
  45
  46 public:
  47    Class type;
  48    property uint count
  49    {
  50       set
  51       {
  52          if(value != _count)
  53          {
  54             int newsize = (value / _factor + 1) * _factor;
  55             if(newsize != _size)
  56                size = value ? newsize : 0;
  57             _count = value;
  58          }
  59       }
  60       get { return _count; }
  61    }
  62    property uint size
  63    {
  64       set
  65       {
  66          if(value != _size)
  67          {
  68             if(array)
  69             {
  70                if(value)
  71                   array = renew array void * [value * sizeof(void *)];
  72                else
  73                   delete array;
  74             }
  75             else if(value)
  76                array = new void * [value * sizeof(void *)];
  77             _size = value;
  78          }
  79       }
  80       get { return _size; }
  81    }
  82    property uint growingFactor { set { _factor = value; } get { return _factor; } }
  83    property void * data
  84    {
  85       set
  86       {
  87          memcpy(array, value, _size * sizeoftype);
  88       }
  89    }
  90    void Append(int n)
  91    {
  92       count += n;
  93    }
  94    void Insert(uint position, int n)
  95    {
  96       Append(n);
  97       if(position < _count - 1)
  98          MoveBytes(array + (position + n) * sizeoftype, array + position * sizeoftype, (_count - position - n) * sizeoftype);
  99    }
 100    void Trim(int n)
 101    {
 102       count -= n;
 103    }
 104    void Remove(uint position, int n)
 105    {
 106       if(position + n - 1 < _count - 1)
 107          MoveBytes(array + position * sizeoftype, array + (position + n) * sizeoftype, (_count - position - n) * sizeoftype);
 108       Trim(n);
 109    }
 110    BSloc Find(void * item)
 111    {
 112       BSloc result { };
 113       if(_count && item)
 114       {
 115          uint lo = 0, hi = _count - 1;
 116          for( ; hi - lo >= _threshold; )
 117          {
 118             uint tri = (hi - lo) / 3;
 119             uint i = lo + tri;
 120             //if(Compare(client, _[i], item) > 0)
 121             if(array[i] > item)
 122                hi = i;
 123             else
 124             {
 125                i = hi - tri;
 126                if(array[i] < item)
 127                   lo = i;
 128                else
 129                   lo += tri, hi -= tri;
 130             }
 131          }
 132          if(array[lo] <= item)
 133          {
 134             if(array[hi] >= item)
 135             {
 136                uint i;
 137                for(i = lo + 1; array[i] <= item; i++);
 138                //result.oldpos = i;
 139                if(array[i] == item)
 140                   result.valid = true, result.pos = i;
 141             }
 142             else
 143             {
 144                if(array[hi] <= item)
 145                   ;//result.oldpos = hi + 1;
 146                else
 147                   result.valid = true/*, result.oldpos = hi*/, result.pos = hi;
 148             }
 149          }
 150          else
 151          {
 152             //result.oldpos = lo;
 153             if(array[lo] == item)
 154                result.valid = true, result.pos = lo;
 155          }
 156       }
 157       return result;
 158    }
 159
 160 };
 161
 162 public class StringBSArray : ArrayBinarySorted
 163 {
 164    type = class(String);
 165 public:
 166    String * const _;
 167    BSloc Add(String item)
 168    {
 169       BSloc result = Find(item);
 170       if(!result.valid)
 171       {
 172          Insert(result.pos, 1);
 173          _[result.pos] = item;
 174       }
 175       return result;
 176    }
 177    BSloc Remove(String item)
 178    {
 179
 180    }
 181 }
 182