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=d357a5f6833f488b6e3b38c4f1a73d5d9ead1984;hpb=35a80a1e437c4c164cb52a3302ac88679090734e;p=sdk

diff --git a/ecere/src/com/containers/Container.ec b/ecere/src/com/containers/Container.ec
index d357a5f..808251e 100644
--- a/ecere/src/com/containers/Container.ec
+++ b/ecere/src/com/containers/Container.ec
@@ -156,6 +156,7 @@ public:
 
       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;
 
@@ -275,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);
@@ -288,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)
@@ -328,4 +332,94 @@ public:
          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;
+   }
 }