The Ecere SDK - sdk/blob - ecere/src/com/containers/Container.ec

   1 namespace com;
   2
   3 import "BuiltInContainer"
   4
   5 default:
   6
   7 static __attribute__((unused)) void UnusedFunction()
   8 {
   9    int a;
  10    a.OnCompare(null);
  11    a.OnCopy(null);
  12    a.OnGetString(null, null, null);
  13    a.OnSerialize(null);
  14    a.OnUnserialize(null);
  15 }
  16
  17 extern int __ecereVMethodID_class_OnCompare;
  18 extern int __ecereVMethodID_class_OnGetString;
  19 extern int __ecereVMethodID_class_OnSerialize;
  20 extern int __ecereVMethodID_class_OnUnserialize;
  21 private:
  22
  23 // CAUSES PROBLEM WHEN AFTER
  24 public struct Iterator<class T, class IT = int>
  25 {
  26    Container<T, IT> container;
  27 // private:
  28    IteratorPointer pointer;
  29
  30 public:
  31    property T data
  32    {
  33       get { return container.GetData(pointer); }
  34       set { container.SetData(pointer, value); }
  35    }
  36
  37    bool Prev()
  38    {
  39       if(pointer && container)
  40          pointer = container.GetPrev(pointer);
  41       else if(container)
  42          pointer = container.GetLast();
  43       return pointer != null;
  44    }
  45
  46    bool Next()
  47    {
  48       if(pointer && container)
  49          pointer = container.GetNext(pointer);
  50       else if(container)
  51          pointer = container.GetFirst();
  52       return pointer != null;
  53    }
  54
  55    T GetData()
  56    {
  57       return container.GetData(pointer);
  58    }
  59
  60    bool SetData(T value)
  61    {
  62       return container.SetData(pointer, value);
  63    };
  64
  65    bool Find(const T value)
  66    {
  67       if(container)
  68       {
  69          Free();
  70          pointer = container.Find(value);
  71       }
  72       return pointer != null;
  73    }
  74
  75    void Remove()
  76    {
  77       if(container)
  78          container.Remove(pointer);
  79       pointer = null;
  80    }
  81
  82    void Free()
  83    {
  84       if(container)
  85          container.FreeIterator(pointer);
  86    }
  87
  88    bool Index(const IT index, bool create)
  89    {
  90       if(container)
  91       {
  92          bool justAdded = false;
  93          Free();
  94          pointer = container.GetAtPosition(index, create, &justAdded);
  95          return !justAdded && pointer != null;
  96       }
  97       return false;
  98    }
  99 };
 100
 101 public class Container<class T, class I = int, class D = T>
 102 {
 103 public:
 104    class_fixed
 105    public property Container<T> copySrc { set { if(value) Copy(value); } }
 106    property Iterator<T> firstIterator { get { value = { (Container<T>)this, pointer = GetFirst() }; } }
 107    property Iterator<T> lastIterator  { get { value = { (Container<T>)this, pointer = GetLast() }; } }
 108
 109    virtual IteratorPointer GetFirst() { return null; }
 110    virtual IteratorPointer GetLast()  { return null; }
 111    virtual IteratorPointer GetPrev(IteratorPointer pointer) { return null; }
 112    virtual IteratorPointer GetNext(IteratorPointer pointer) { return null; }
 113    virtual D GetData(IteratorPointer pointer) { return (D)0; }
 114    virtual bool SetData(IteratorPointer pointer, D data);
 115    virtual IteratorPointer GetAtPosition(const I pos, bool create, bool * justAdded) { return null; }
 116
 117    virtual IteratorPointer Insert(IteratorPointer after, T value);
 118    virtual IteratorPointer Add(T value);
 119    virtual void Remove(IteratorPointer it);
 120    virtual void Move(IteratorPointer it, IteratorPointer after);
 121
 122    virtual void RemoveAll()
 123    {
 124       IteratorPointer i, next;
 125       for(i = GetFirst(), next = i ? GetNext(i) : null; i; i = next, next = i ? GetNext(i) : null)
 126          Remove(i);
 127    }
 128
 129    virtual void Copy(Container<T> source)
 130    {
 131       IteratorPointer i;
 132       RemoveAll();
 133       for(i = source.GetFirst(); i; i = source.GetNext(i))
 134       {
 135          D data = source.GetData(i);
 136          // WARNING: This doesn't make a new copy of the elements it adds
 137          Add(data);
 138       }
 139    }
 140
 141    void OnFree()
 142    {
 143       if(this)
 144       {
 145          Free();
 146          delete this;
 147       }
 148    }
 149
 150    int OnCompare(Container<T> b)
 151    {
 152       IteratorPointer ia, ib;
 153       Class Dclass = class(D);
 154       bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
 155       int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
 156
 157       if(this && !b) return 1;
 158       if(b && !this) return -1;
 159       if(!b && !this) return 0;
 160       if(GetCount() > b.GetCount()) return 1;
 161       if(GetCount() < b.GetCount()) return -1;
 162
 163       ia = GetFirst();
 164       ib = b.GetFirst();
 165       while(ia && ib)
 166       {
 167          D dataA = GetData(ia);
 168          D dataB = b.GetData(ib);
 169          int r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
 170          if(r) return r;
 171          ia = GetNext(ia);
 172          ib = b.GetNext(ib);
 173       }
 174       if(ia) return 1;
 175       if(ib) return -1;
 176       return 0;
 177    }
 178
 179    void OnCopy(Container<T> source)
 180    {
 181       if(source)
 182       {
 183          // BUG IN this = SYNTAX
 184          Container<T> container = eInstance_New(source._class);
 185          // See WARNING in Copy()
 186          container.Copy(source);
 187          //*(void **)this = container;
 188          this = container;
 189       }
 190       else
 191       {
 192          this = null;
 193       }
 194    }
 195
 196    virtual IteratorPointer Find(const D value)
 197    {
 198       IteratorPointer i;
 199       Class Dclass = class(D);
 200       bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
 201       int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
 202
 203       if(byRef)
 204       {
 205          for(i = GetFirst(); i; i = GetNext(i))
 206          {
 207             D data = GetData(i);
 208             int result = onCompare(Dclass, &value, &data);
 209             if(!result)
 210                return i;
 211          }
 212       }
 213       else
 214       {
 215          for(i = GetFirst(); i; i = GetNext(i))
 216          {
 217             D data = GetData(i);
 218             int result = onCompare(Dclass, (const void *)(uintptr) value, (const void *)(uintptr) data);
 219             if(!result)
 220                return i;
 221          }
 222       }
 223       return null;
 224    }
 225
 226    virtual void FreeIterator(IteratorPointer it);
 227
 228    virtual int GetCount()
 229    {
 230       int count = 0;
 231       IteratorPointer i;
 232       for(i = GetFirst(); i; i = GetNext(i)) count++;
 233       return count;
 234    }
 235
 236    virtual void Free()
 237    {
 238       IteratorPointer i;
 239       while((i = GetFirst()))
 240          Delete(i);
 241    }
 242
 243    virtual void Delete(IteratorPointer i)
 244    {
 245       D data = GetData(i);
 246       delete data;
 247       Remove(i);
 248    }
 249
 250    const char * OnGetString(char * tempString, void * fieldData, bool * needClass)
 251    {
 252       if(this)
 253       {
 254          char itemString[4096];//1024];
 255          bool first = true;
 256          IteratorPointer i;
 257          tempString[0] = '\0';
 258          for(i = GetFirst(); i; i = GetNext(i))
 259          {
 260             Class Dclass = class(D);
 261             D data = GetData(i);
 262             const char * result;
 263
 264             itemString[0] = '\0';
 265
 266             result = ((const char *(*)(void *, void *, char *, void *, bool *))(void *)Dclass._vTbl[__ecereVMethodID_class_OnGetString])(Dclass,
 267                ((Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass) ? &data : (void *)data, itemString, null, null);
 268             if(!first) strcat(tempString, ", ");
 269
 270             strcat(tempString, result);
 271             first = false;
 272          }
 273       }
 274       else
 275          tempString[0] = 0;
 276       return tempString;
 277    }
 278
 279    // TODO: Warn against the danger of using TakeOut with 'normal' classes, as they will be considered equivalent if onCompare says so
 280    void TakeOut(const D d)
 281    {
 282       IteratorPointer i = Find(d);
 283       if(i) Remove(i);
 284    }
 285
 286    ~Container()
 287    {
 288       RemoveAll();
 289    }
 290
 291    void OnSerialize(IOChannel channel)
 292    {
 293       // NOTE: Null containers currently get serialized as empty
 294       uint count = this ? GetCount() : 0;
 295       IteratorPointer i;
 296       Class Dclass = class(D);
 297       bool isNormalClass = (Dclass.type == normalClass) && Dclass.structSize;
 298
 299       channel.Put(count);
 300       if(this)
 301          for(i = GetFirst(); i; i = GetNext(i))
 302          {
 303             D data = GetData(i);
 304             Class Eclass = isNormalClass ? ((Instance)data)._class : Dclass;
 305             ((void (*)(void *, void *, void *))(void *)Eclass._vTbl[__ecereVMethodID_class_OnSerialize])(Eclass,
 306                ((Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass) ? &data : (void *)data, channel);
 307          }
 308    }
 309
 310    void OnUnserialize(IOChannel channel)
 311    {
 312       Container container = eInstance_New(_class.fullName);
 313       uint count, c;
 314       Class Dclass = class(D);
 315       D data;
 316       bool isStruct = Dclass.type == structClass;
 317
 318       channel.Get(count);
 319       if(isStruct)
 320          data = (D)(new byte[Dclass.structSize]);
 321       for(c = 0; c < count; c++)
 322       {
 323          if(isStruct)
 324             memset((char *)data, 0, Dclass.structSize);
 325          else
 326             data = (D)0;
 327          ((void (*)(void *, void *, void *))(void *)Dclass._vTbl[__ecereVMethodID_class_OnUnserialize])
 328             (Dclass, isStruct ? (void *)data : &data, channel);
 329          container.Add(data);
 330       }
 331       if(isStruct)
 332          delete (void *)data;
 333       this = container;
 334    }
 335 private:
 336    // FIXME: Static is not overriding private
 337    static void _Sort(bool ascending, Container * lists)
 338    {
 339       // Only sort containers with more than 1 items and which are integer indexable
 340       int count = GetCount();
 341       if(count >= 2 && class(I) == class(int))
 342       {
 343          Iterator a { this };
 344          Iterator b { this };
 345          Iterator mid { this };
 346
 347          Class Dclass = class(D);
 348          bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
 349          int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
 350
 351          Container listA = lists[0];
 352          Container listB = lists[1];
 353
 354          // Find midpoint
 355          mid.Index(count / 2-1, false);
 356
 357          // Split into 2 lists
 358          while(a.Next())
 359          {
 360             listA.Add(a.data);
 361             if(a.pointer == mid.pointer)
 362                break;
 363          }
 364
 365          b.pointer = mid.pointer;
 366          while(b.Next())
 367             listB.Add(b.data);
 368
 369          RemoveAll();
 370
 371          // Sort each of the 2 lists
 372          listA._Sort(ascending, lists + 2);
 373          listB._Sort(ascending, lists + 2);
 374
 375          // Merge
 376          a = { listA };
 377          b = { listB };
 378          a.Next();
 379          b.Next();
 380
 381          while(a.pointer || b.pointer)
 382          {
 383             int r;
 384             if(a.pointer && b.pointer)
 385             {
 386                D dataA = a.data, dataB = b.data;
 387                r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
 388             }
 389             else if(a.pointer)
 390                r = -1;
 391             else
 392                r = 1;
 393             if(!ascending) r *= -1;
 394
 395             if(r < 0)
 396             {
 397                Add(a.data);
 398                a.Next();
 399             }
 400             else
 401             {
 402                Add(b.data);
 403                b.Next();
 404             }
 405          }
 406
 407          listA.RemoveAll();
 408          listB.RemoveAll();
 409       }
 410    }
 411
 412 public:
 413    virtual void Sort(bool ascending)
 414    {
 415       // Pre-allocate 2 log2(n) containers
 416       int i, numLists = log2i(GetCount()) * 2;
 417       Container * lists = new Container[numLists];
 418       for(i = 0; i < numLists; i++)
 419          lists[i] = eInstance_New(_class);
 420       _Sort(ascending, lists);
 421       for(i = 0; i < numLists; i++)
 422          delete lists[i];
 423       delete lists;
 424    }
 425 }