Click here to Skip to main content
11,639,178 members (68,156 online)
Click here to Skip to main content
Articles » Database » Database » General » Downloads
Add your own
alternative version

Tagged as

Generating Keys for a Custom Sort Order

, 7 Sep 2012 CPOL 12.2K 119 15
ORDER BY what-the-user-said
#include "stdafx.h"
#include <vector>
#include <stdio.h>
#include "SortOrder.h"


extern "C" int getch();

int statsOpPrepend = 0;
int statsOpAppend = 0;
int statsOpDelete = 0;
int statsOpInsert = 0;
int statsOpInsertAt7 = 0;

using PHLib::CSortOrder;


void TestBefore(CSortOrder const & so, CStringA const & original, CStringA const & expected)
{
   CStringA before = so.Before(original);
   _ASSERTE(before == expected);
   _ASSERTE(before < original);
}

void TestAfter(CSortOrder const & so, CStringA const & original, CStringA const & expected)
{
   CStringA after = so.After(original);
   _ASSERTE(after == expected);
   _ASSERTE(after > original);
}

void TestBetween(CSortOrder const & so, CStringA const & a, CStringA const & b)
{
   CStringA between = so.Between(a,b);
   // _ASSERTE(between == expected);
   _ASSERTE(between > a);
   _ASSERTE(between < b);
}



void Test()
{
   CSortOrder so;

   TestBefore(so, "abc", "abb");
   TestBefore(so, "abb", "aaz");
   TestBefore(so, "aab", "aaazz");

   TestAfter(so, "abc", "abd");
   TestAfter(so, "abz", "acb");
   TestAfter(so, "abzzz", "acaab");
   TestAfter(so, "zzz", "zzzab");

   TestBetween(so, "b", "d");
   TestBetween(so, "b", "c");
   TestBetween(so, "x", "xb");
   TestBetween(so, "x", "xab");
   TestBetween(so, "xz", "y");
}



void CheckLT(int i, CStringA const & a, CStringA const & b)
{
   if (a < b)
      return;

   printf("@%d: '%s' < '%s' FAILS\r\n", i, a, b);
}

int _tmain(int argc, _TCHAR* argv[])
{
   Test();  

   std::vector<CStringA> values;

   CSortOrder so('!', '~');

   if ("Random Insert" != 0)
   {
      int startCount = 5;
      int insertCount = 100000;

                  // before, after, insert, delete, insert @ fixed pos
      int weights[] = { 0, 0, 10, 0, 0 };
      int weightSum = weights[0]+weights[1]+weights[2]+weights[3]+weights[4];

      srand(0);

      int maxLen = 0;
      values.clear();
      values.reserve(startCount + insertCount);

      // feed initial sequence
      CStringA startWith = "m";
      for(int i=0; i<startCount; ++i)
      {
         values.push_back(startWith);
         startWith = so.After(startWith);
         startWith = so.After(startWith);
      }

      // feed extra data
      statsOpPrepend = statsOpAppend = statsOpDelete = statsOpInsert = statsOpInsertAt7 = 0;

      for(int i=0; i<insertCount; ++i)
      {
         if (!(i % (insertCount / 100)))
         {
            printf("%d%%\r", i*100 / insertCount);
         }

         int idx = 0;
         CStringA newValue;

         int rnd = rand() % weightSum;
         int type = -1;
         do 
         {
            ++type;
            rnd -= weights[type];
         } while (rnd >= 0);


         switch (type)
         {
         case 0:     // insert in front
            newValue = so.Before(values[0]);
            ++statsOpPrepend;
            CheckLT(i, newValue, values[0]);
            values.insert(values.begin(), newValue);
            break;

         case 1:     // insert in back
            newValue = so.After(values[values.size()-1]);
            ++statsOpAppend;
            CheckLT(i, values[values.size()-1], newValue);
            values.insert(values.end(), newValue);
            break;

         case 2:  // insert at random
            if (values.size() < 2)
               continue;
            ++statsOpInsert;
            idx = (rand() % (values.size()-1)) + 1;
            newValue = so.Between(values[idx-1], values[idx]);
            _ASSERTE(so.IsValid(newValue));
            CheckLT(i, values[idx-1], newValue); 
            CheckLT(i, newValue, values[idx]);
            values.insert(values.begin()+idx, newValue);
            break;

         case 3:  // delete random
            if (values.size() < 1)
               break;
            ++statsOpDelete;
            idx = rand() % values.size();
            values.erase(values.begin() + idx);
            break;

         case 4:
            // insert at fixed position (7)
            if (values.size() < 8)
               continue;
            ++statsOpInsertAt7;
            idx = 7;
            newValue = so.Between(values[idx-1], values[idx]);
            _ASSERTE(so.IsValid(newValue));
            CheckLT(i, values[idx-1], newValue); 
            CheckLT(i, newValue, values[idx]);
            values.insert(values.begin()+idx, newValue);
            break;




         default:
            _ASSERTE(false); // Hammer nich
         }

         int len = newValue.GetLength();
         if (len > maxLen)
            maxLen = len;
      }

      double oppct = 100.0/(statsOpDelete + statsOpAppend + statsOpInsert + statsOpPrepend + statsOpInsertAt7);

      printf("%d start values, %d random inserts, maxlen = %d\r\n", startCount, insertCount, maxLen);
      printf("Prepend: %.f%%, Insert:%.f%%, Append: %.f%%, Delete:%.f%%, Insert@7:%.f%%\r\n", 
         statsOpPrepend*oppct, statsOpInsert * oppct, statsOpAppend*oppct, statsOpDelete * oppct, statsOpInsertAt7*oppct);

         
      if (!getch()) getch();
      
      for(unsigned i=0; i<values.size(); ++i)
         printf("%s\r\n", values[i]);

      if (!getch()) getch();
   }
}

/*

Original, ExpandBy=2:

5 start values, 100000 random inserts, maxlen = 29
MidTruncate: 4, Before: 33287, After: 33305, FillA: 0, FillB: 0, Append:33404
Prepend: 0%, Insert:100%, Append: 0%, Delete:0%, Insert@7:0%


Original, ExpandBy=3:   INSERT ONLY

5 start values, 100000 random inserts, maxlen = 43
MidTruncate: 4, Before: 33287, After: 33305, FillA: 0, FillB: 0, Append:33404
Prepend: 0%, Insert:100%, Append: 0%, Delete:0%, Insert@7:0%


Original, ExpandBy=3:      BASELINE (HEALTHY MIX)

5 start values, 100000 random inserts, maxlen = 22
MidTruncate: 1287, Before: 8908, After: 8669, FillA: 0, FillB: 0, Append:17713
Prepend: 18%, Insert:37%, Append: 36%, Delete:9%


Original, ExpandBy=3, values = "!" .. "~" BASELINE + WIDE RANGE

5 start values, 100000 random inserts, maxlen = 22
MidTruncate: 1376, Before: 8890, After: 8633, FillA: 0, FillB: 0, Append:17678
Prepend: 18%, Insert:37%, Append: 36%, Delete:9%


Original, ExpandBy=2, values = "!" .. "~" BASELINE + WIDE RANGE + EXPAND 2

5 start values, 100000 random inserts, maxlen = 15
MidTruncate: 1376, Before: 8890, After: 8633, FillA: 0, FillB: 0, Append:17678
Prepend: 18%, Insert:37%, Append: 36%, Delete:9%


Original, ExpandBy=2:   BASELINE + EXPAND 2

5 start values, 100000 random inserts, maxlen = 113
MidTruncate: 1290, Before: 8907, After: 8668, FillA: 0, FillB: 0, Append:17712
Prepend: 18%, Insert:37%, Append: 36%, Delete:9%


Original, ExpandLen = 4

5 start values, 100000 random inserts, maxlen = 29
MidTruncate: 1287, Before: 8908, After: 8669, FillA: 0, FillB: 0, Append:17713
Prepend: 18%, Insert:37%, Append: 36%, Delete:9%


Original + dynamic ExpandBy
   ExpandBy = min((length / 10)+1, 5);

5 start values, 100000 random inserts, maxlen = 36
MidTruncate: 1290, Before: 8909, After: 8666, FillA: 0, FillB: 0, Append:17712
Prepend: 18%, Insert:37%, Append: 36%, Delete:9%


Original + ExpandBy = 3, mostly inserts

5 start values, 100000 random inserts, maxlen = 31
MidTruncate: 929, Before: 17925, After: 17493, FillA: 0, FillB: 0, Append:25212
Prepend: 16%, Insert:62%, Append: 15%, Delete:8%


Original + Dynamic ExpandBy, mostly inserts
   ExpandBy = min((length / 10)+1, 5);

5 start values, 100000 random inserts, maxlen = 40
MidTruncate: 932, Before: 17926, After: 17496, FillA: 0, FillB: 0, Append:25205
Prepend: 16%, Insert:62%, Append: 15%, Delete:8%


Original + Dynamic ExpandBy, mostly inserts
ExpandBy = min((length / 10)+1, 3);

5 start values, 100000 random inserts, maxlen = 38
MidTruncate: 932, Before: 17926, After: 17496, FillA: 0, FillB: 0, Append:25205
Prepend: 16%, Insert:62%, Append: 15%, Delete:8%


Original + ExpandBy = 3, almost completely inserts

5 start values, 100000 random inserts, maxlen = 43
MidTruncate: 121, Before: 30873, After: 30909, FillA: 0, FillB: 0, Append:32166
Prepend: 2%, Insert:94%, Append: 2%, Delete:1%


Original + ExpandBy = 3, almost completely appends

5 start values, 100000 random inserts, maxlen = 16
MidTruncate: 311, Before: 845, After: 764, FillA: 0, FillB: 0, Append:6083
Prepend: 8%, Insert:8%, Append: 80%, Delete:4%


Original + ExpandBy = 3, almost completely prepends

5 start values, 100000 random inserts, maxlen = 19
MidTruncate: 211, Before: 442, After: 449, FillA: 0, FillB: 0, Append:6901
Prepend: 80%, Insert:8%, Append: 8%, Delete:4%



Original + ExpandBy = 3, Many Inserts at the same position

5 start values, 100000 random inserts, maxlen = 11
MidTruncate: 333, Before: 43766, After: 3836, FillA: 0, FillB: 0, Append:18802
Prepend: 10%, Insert:19%, Append: 19%, Delete:5%, Insert@7:48%

------------------------




*/

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

peterchen
Klippel
Germany Germany
Peter is tired of being called "Mr. Chen", even so certain individuals insist on it. No, he's not chinese.

Peter has seen lots of boxes you youngsters wouldn't even accept as calculators. He is proud of having visited the insides of a 16 Bit Machine.

In his spare time he ponders new ways of turning groceries into biohazards, or tries to coax South American officials to add some stamps to his passport.

Beyond these trivialities Peter works for Klippel[^], a small german company that wants to make mankind happier by selling them novel loudspeaker measurement equipment.


Where are you from?[^]



Please, if you are using one of my articles for anything, just leave me a comment. Seeing that this stuff is actually useful to someone is what keeps me posting and updating them.
Should you happen to not like it, tell me, too

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150728.1 | Last Updated 7 Sep 2012
Article Copyright 2012 by peterchen
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid