X-Git-Url: https://ecere.com/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=ecere%2Fsrc%2Fcom%2Fcontainers%2FContainer.ec;h=808251e38962c2ac32165d44eb19a01e6c42897a;hb=daf98d47563fa5e2e35963153384168c3b54d326;hp=3674273e5148d288be4883c3722063da414af34a;hpb=2959ab13dcbe496ec67252b44a1b8ace1aa6d9d9;p=sdk

diff --git a/ecere/src/com/containers/Container.ec b/ecere/src/com/containers/Container.ec
index 3674273..808251e 100644
--- a/ecere/src/com/containers/Container.ec
+++ b/ecere/src/com/containers/Container.ec
@@ -89,9 +89,10 @@ public:
    {
       if(container)
       {
+         bool justAdded = false;
          Free();
-         pointer = container.GetAtPosition(index, create);
-         return pointer != null;
+         pointer = container.GetAtPosition(index, create, &justAdded);
+         return !justAdded && pointer != null;
       }
       return false;
    }
@@ -101,7 +102,7 @@ public class Container<class T, class I = int, class D = T>
 {
 public:
    class_fixed
-   public property Container<T> copySrc { set { Copy(value); } }
+   public property Container<T> copySrc { set { if(value) Copy(value); } }
    property Iterator<T> firstIterator { get { value = { (Container<T>)this, pointer = GetFirst() }; } }
    property Iterator<T> lastIterator  { get { value = { (Container<T>)this, pointer = GetLast() }; } }
 
@@ -111,7 +112,7 @@ public:
    virtual IteratorPointer GetNext(IteratorPointer pointer) { return null; }
    virtual D GetData(IteratorPointer pointer) { return (D)0; }
    virtual bool SetData(IteratorPointer pointer, D data);
-   virtual IteratorPointer GetAtPosition(const I pos, bool create) { return null; }
+   virtual IteratorPointer GetAtPosition(const I pos, bool create, bool * justAdded) { return null; }
 
    virtual IteratorPointer Insert(IteratorPointer after, T value);
    virtual IteratorPointer Add(T value);
@@ -146,6 +147,35 @@ public:
       }
    }
 
+   int OnCompare(Container<T> b)
+   {
+      IteratorPointer ia, ib;
+      Class Dclass = class(D);
+      bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
+      int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
+
+      if(this && !b) return 1;
+      if(b && !this) return -1;
+      if(!b && !this) return 0;
+      if(GetCount() > b.GetCount()) return 1;
+      if(GetCount() < b.GetCount()) return -1;
+
+      ia = GetFirst();
+      ib = b.GetFirst();
+      while(ia && ib)
+      {
+         D dataA = GetData(ia);
+         D dataB = b.GetData(ib);
+         int r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
+         if(r) return r;
+         ia = GetNext(ia);
+         ib = b.GetNext(ib);
+      }
+      if(ia) return 1;
+      if(ib) return -1;
+      return 0;
+   }
+
    void OnCopy(Container<T> source)
    {
       if(source)
@@ -167,12 +197,15 @@ public:
    {
       IteratorPointer i;
       Class Dclass = class(D);
-      if(((Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass))
+      bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
+      int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
+
+      if(byRef)
       {
          for(i = GetFirst(); i; i = GetNext(i))
          {
             D data = GetData(i);
-            int result = ((int (*)(void *, const void *, const void *))(void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare])(Dclass, &value, &data);
+            int result = onCompare(Dclass, &value, &data);
             if(!result)
                return i;
          }
@@ -182,7 +215,7 @@ public:
          for(i = GetFirst(); i; i = GetNext(i))
          {
             D data = GetData(i);
-            int result = ((int (*)(void *, const void *, const void *))(void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare])(Dclass, (const void *)(uintptr) value, (const void *)(uintptr) data);
+            int result = onCompare(Dclass, (const void *)(uintptr) value, (const void *)(uintptr) data);
             if(!result)
                return i;
          }
@@ -243,6 +276,7 @@ public:
       return tempString;
    }
 
+   // TODO: Warn against the danger of using TakeOut with 'normal' classes, as they will be considered equivalent if onCompare says so
    void TakeOut(const D d)
    {
       IteratorPointer i = Find(d);
@@ -256,19 +290,21 @@ public:
 
    void OnSerialize(IOChannel channel)
    {
-      uint count = GetCount();
+      // NOTE: Null containers currently get serialized as empty
+      uint count = this ? GetCount() : 0;
       IteratorPointer i;
       Class Dclass = class(D);
       bool isNormalClass = (Dclass.type == normalClass) && Dclass.structSize;
 
       channel.Put(count);
-      for(i = GetFirst(); i; i = GetNext(i))
-      {
-         D data = GetData(i);
-         Class Eclass = isNormalClass ? ((Instance)data)._class : Dclass;
-         ((void (*)(void *, void *, void *))(void *)Eclass._vTbl[__ecereVMethodID_class_OnSerialize])(Eclass,
-            ((Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass) ? &data : (void *)data, channel);
-      }
+      if(this)
+         for(i = GetFirst(); i; i = GetNext(i))
+         {
+            D data = GetData(i);
+            Class Eclass = isNormalClass ? ((Instance)data)._class : Dclass;
+            ((void (*)(void *, void *, void *))(void *)Eclass._vTbl[__ecereVMethodID_class_OnSerialize])(Eclass,
+               ((Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass) ? &data : (void *)data, channel);
+         }
    }
 
    void OnUnserialize(IOChannel channel)
@@ -293,7 +329,97 @@ public:
          container.Add(data);
       }
       if(isStruct)
-         delete data;
+         delete (void *)data;
       this = container;
    }
+private:
+   // FIXME: Static is not overriding private
+   static void _Sort(bool ascending, Container * lists)
+   {
+      // Only sort containers with more than 1 items and which are integer indexable
+      int count = GetCount();
+      if(count >= 2 && class(I) == class(int))
+      {
+         Iterator a { this };
+         Iterator b { this };
+         Iterator mid { this };
+
+         Class Dclass = class(D);
+         bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
+         int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
+
+         Container listA = lists[0];
+         Container listB = lists[1];
+
+         // Find midpoint
+         mid.Index(count / 2-1, false);
+
+         // Split into 2 lists
+         while(a.Next())
+         {
+            listA.Add(a.data);
+            if(a.pointer == mid.pointer)
+               break;
+         }
+
+         b.pointer = mid.pointer;
+         while(b.Next())
+            listB.Add(b.data);
+
+         RemoveAll();
+
+         // Sort each of the 2 lists
+         listA._Sort(ascending, lists + 2);
+         listB._Sort(ascending, lists + 2);
+
+         // Merge
+         a = { listA };
+         b = { listB };
+         a.Next();
+         b.Next();
+
+         while(a.pointer || b.pointer)
+         {
+            int r;
+            if(a.pointer && b.pointer)
+            {
+               D dataA = a.data, dataB = b.data;
+               r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
+            }
+            else if(a.pointer)
+               r = -1;
+            else
+               r = 1;
+            if(!ascending) r *= -1;
+
+            if(r < 0)
+            {
+               Add(a.data);
+               a.Next();
+            }
+            else
+            {
+               Add(b.data);
+               b.Next();
+            }
+         }
+
+         listA.RemoveAll();
+         listB.RemoveAll();
+      }
+   }
+
+public:
+   virtual void Sort(bool ascending)
+   {
+      // Pre-allocate 2 log2(n) containers
+      int i, numLists = log2i(GetCount()) * 2;
+      Container * lists = new Container[numLists];
+      for(i = 0; i < numLists; i++)
+         lists[i] = eInstance_New(_class);
+      _Sort(ascending, lists);
+      for(i = 0; i < numLists; i++)
+         delete lists[i];
+      delete lists;
+   }
 }