Ladder Structure

Discussion in 'Development General' started by coyotte508, Jun 3, 2010.

  1. coyotte508

    coyotte508 Well-Known Member Administrator Server Owner Administrator Server Owner

    Joined:
    Apr 21, 2010
    Messages:
    6,363
    Likes Received:
    168
    For info, the files weight around 200 kB in total

    Structure

    The tier files are that way:

    Code (text):
    1. [name]%[number of rated battles, 5B]%[Ranking, 5B]
    2. [name]%[number of rated battles, 5B]%[Ranking, 5B]
    3. [name]%[number of rated battles, 5B]%[Ranking, 5B]
    4. [name]%[number of rated battles, 5B]%[Ranking, 5B]
    5. ...
    A sample:
    Code (text):
    1. sawada tsunayoshi%00005%00763
    2. impersonatorx%00026%00870
    3. alex88%00006%01032
    4. freitas%00014%00934
    5. y.sleykii%00010%01166
    6. mr x%00003%01022
    7. ace trainer heart%00014%01079
    8. alex90%00093%00853
    9. sbroncobaldo%00002%00818
    10. el gladio 1%00215%00543
    11. gatoraderob%00008%00802
    There are different tiers, the corresponding files are tier.cpp and tier.h and here is the storage of the data, per-tier.

    Code (cpp):
    1. struct Tier
    2. {
    3.     /* ... */
    4.     QFile *in;
    5.     int lastFilePos;
    6.    
    7.     QHash<QString, MemberRating> ratings;
    8.     RankingTree<QString> rankings;
    9. };
    10.  
    I've only kept member-relevant storing.

    Code (cpp):
    1. /* PROPERTY is just a private variable with access functions added*/
    2. struct MemberRating
    3. {
    4.     PROPERTY(QString, name);
    5.     PROPERTY(int, matches);
    6.     PROPERTY(int, rating);
    7.     PROPERTY(int, filePos);
    8.     PROPERTY(RankingTree<QString>::iterator, node)
    9.  
    10.     /* ... */
    11. }
    So, you're seeing a lot of similitudes with the members storing in the other topic. Though you may be wondering, what's that RankingTree<QString>::iterator?

    There is an internal structure for the rankings. It associates a rating with a player (here the player is a QString). It's a RB-Tree (a balanced tree) that has all the properties of a RB tree (all operations have a complexity of O(log(n))), but it also allows to get the ranking of a player in O(log(n)). It also allows to get a player with a specific ranking in O(log(n)) (actually internally it takes O(log* log(log(n))), but if the function is changed a little it can transform into O(log(n)))

    Because, if I used a standard structure, and say a user was added in the middle, I would have to decrease the rankings of all the users beneath by 1, and that wouldn't do.

    So, I store the users in a Red-Black Tree, and each node has one more data: The size of the associated subtree (including itself). That allows to change only O(log(n)) nodes' infos at each insert / remove in the ranking tree, as this is a balanced tree. If you want me to make drawings, I can.

    The ranking of a node, and the node associated to a ranking can then be gotten with simple logic, and quickly. To get a ranking range (e.g. 250-299) just get the node associated to ranking 250, and iterate 49 times.

    All can be found in Utilities/rankingtree.h

    Code (cpp):
    1. #ifndef RANKINGTREE_H
    2. #define RANKINGTREE_H
    3.  
    4. /* Warning.
    5.  
    6.    Deletion / insertion / key changes are not well protected so the user can do
    7.     too much so test thoroughly after changing any code involving RankingTrees and their node.
    8.  
    9.    changeKey() can be optimized and then would not necessit returning a new node. (removal/reinsertion)
    10. */
    11.  
    12. /* Red - Black tree modified so that ranking is efficiently managed. Everything is in O(log n). */
    13. template <class T>
    14. class RankingTree
    15. {
    16. public:
    17.     enum Color
    18.     {
    19.         Red = 0,
    20.         Black = 1
    21.     };
    22.  
    23.     struct Node
    24.     {
    25.         void changeColor(Color c)
    26.         {
    27.             black = bool(c);
    28.         }
    29.         Color color() const
    30.         {
    31.             return Color(black);
    32.         }
    33.         Node *grandParent() const
    34.         {
    35.             if (parent)
    36.                 return parent->parent;
    37.             else
    38.                 return NULL;
    39.         }
    40.         Node *uncle() const
    41.         {
    42.             Node *g = grandParent();
    43.             if (g) {
    44.                 return g->right == parent ? g->left : g->right;
    45.             } else
    46.                 return NULL;
    47.         }
    48.         Node *sibling() const
    49.         {
    50.             if (this == parent->left)
    51.                 return parent->right;
    52.             else
    53.                 return parent->left;
    54.         }
    55.         void decreaseCountUp()
    56.         {
    57.             count -= 1;
    58.             if (parent)
    59.             {
    60.                 parent->decreaseCountUp();
    61.             }
    62.         }
    63.         void increaseCountUp()
    64.         {
    65.             count += 1;
    66.             if (parent)
    67.                 parent->increaseCountUp();
    68.         }
    69.         int ranking()
    70.         {
    71.             return (right ? right->count : 0) + countUp();
    72.         }
    73.  
    74.         int countUp()
    75.         {
    76.             if (parent == NULL)
    77.                 return 1;
    78.             if (this == parent->right)
    79.                 return parent->countUp();
    80.             else //(this == parent->left)
    81.                 return parent->ranking() + 1;
    82.         }
    83.  
    84.  
    85.         const Node *utmostLeft() const
    86.         {
    87.             return left == NULL ? this : left->utmostLeft();
    88.         }
    89.         const Node *utmostRight() const
    90.         {
    91.             return right == NULL ? this : right->utmostLeft();
    92.         }
    93.         Node *utmostLeft()
    94.         {
    95.             return left == NULL ? this : left->utmostLeft();
    96.         }
    97.         Node *utmostRight()
    98.         {
    99.             return right == NULL ? this : right->utmostRight();
    100.         }
    101.         Node *prev() const
    102.         {
    103.             if (left)
    104.                 return left->utmostRight();
    105.             if (!parent) {
    106.                 /* No left, no parent, its the end! */
    107.                 return NULL;
    108.             }
    109.             if (this == parent->left) {
    110.                 return parent->goLeftUp();
    111.             } else /* this == parent->righ */
    112.                 return parent;
    113.  
    114.         }
    115.         Node *next() const
    116.         {
    117.             if (right)
    118.                 return right->utmostLeft();
    119.             if (!parent) {
    120.                 /* No right, no parent, its the end! */
    121.                 return NULL;
    122.             }
    123.             if (this == parent->right) {
    124.                 return parent->goRightUp();
    125.             } else /* this == parent->left */
    126.                 return parent;
    127.  
    128.         }
    129.         Node *goLeftUp()
    130.         {
    131.             if (!parent)
    132.                 return NULL;
    133.             if (this == parent->right)
    134.                 return parent;
    135.             return parent->goLeftUp();
    136.         }
    137.         Node *goRightUp()
    138.         {
    139.             if (!parent)
    140.                 return NULL;
    141.             if (this == parent->left)
    142.                 return parent;
    143.             return parent->goRightUp();
    144.         }
    145.         void recursiveDelete()
    146.         {
    147.             if (left)
    148.                 left->recursiveDelete();
    149.             if (right)
    150.                 right->recursiveDelete();
    151.             delete this;
    152.         }
    153.  
    154.         Node(int key, Color c = Black, Node *parent = NULL, T data = T()) : parent(parent), left(NULL), right(NULL), key(key), black(c), count(1),
    155.                                                                             data(data)
    156.         {
    157.  
    158.         }
    159.  
    160.  
    161.         Node *parent;
    162.         Node *left, *right;
    163.         int key;
    164.         bool black;
    165.         /* The number of nodes under it */
    166.         int count;
    167.         T data;
    168.     };
    169.  
    170.  
    171.     RankingTree() : root(NULL) {
    172.  
    173.     }
    174.     ~RankingTree() {
    175.         if (root) {
    176.             root->recursiveDelete();
    177.             root = NULL;
    178.         }
    179.     }
    180.  
    181.     int count() const
    182.     {
    183.         return root ? root->count : 0;
    184.     }
    185.  
    186.     Node* insert(int key, T data);
    187.  
    188.     /* Could manage without deleting the node, with proper insertion / removal */
    189.     Node *changeKey(Node *n, int key)
    190.     {
    191.         if (key == n->key)
    192.             return n;
    193.  
    194.         Node *ret = insert(key, n->data);
    195.         deleteNode(n);
    196.  
    197.         return ret;
    198.     }
    199.  
    200.     /*
    201.      * The Node was already inserted, it's red. For all we know,
    202.      * it might be the root.
    203.      */
    204.     void insertCase1(Node *p)
    205.     {
    206.         if (root == p)
    207.         {
    208.             p->changeColor(Black);
    209.         } else {
    210.             insertCase2(p);
    211.         }
    212.     }
    213.  
    214.     /*
    215.      * The Node was already inserted, it's red, and its not the root.
    216.      * We have to fix any violation
    217.      */
    218.     void insertCase2(Node *p)
    219.     {
    220.         /* If the parent is black, its child being red poses no problem */
    221.         if (p->parent->color() != Black)
    222.             insertCase3(p);
    223.     }
    224.  
    225.     /*
    226.      * The Node was already inserted, it's red, and it has a red parent (problem!)
    227.      * We have to fix this!
    228.      */
    229.     void insertCase3(Node *p)
    230.     {
    231.         /* Lets check if the uncle is red. If the uncle is, then we change both the
    232.            parent and the uncle to black. The grandparent was black, as it had red
    233.            children. So we change its color to red (to have the same number of blacks
    234.            in every path. By changing it to red, we may have violated the rule that
    235.            the root is black or that every red node has black leaves.  */
    236.         Node *u = p->uncle();
    237.  
    238.         if (u && u->color() == Red)
    239.         {
    240.             u->changeColor(Black);
    241.             p->parent->changeColor(Black);
    242.             Node *g = p->grandParent();
    243.             g->changeColor(Red);
    244.             insertCase1(g);
    245.         } else {
    246.             insertCase4(p);
    247.         }
    248.     }
    249.  
    250.     /*
    251.      * We have a situation. p is Red and its parent is red and its uncle is black.
    252.      * We'll need two rotations to restore the tree
    253.      */
    254.     void insertCase4(Node *n)
    255.     {
    256.         Node *g = n->grandParent();
    257.  
    258.         if ((n == n->parent->right) && (n->parent == g->left)) {
    259.                 rotateLeft(n->parent);
    260.                 n = n->left;
    261.         } else if ((n == n->parent->left) && (n->parent == g->right)) {
    262.                 rotateRight(n->parent);
    263.                 n = n->right;
    264.         }
    265.  
    266.         if (n)
    267.             insertCase5(n);
    268.     }
    269.  
    270.     /*
    271.      * In continuation of insertCase4
    272.      */
    273.     void insertCase5(Node *n)
    274.     {
    275.         Node *g = n->grandParent();
    276.  
    277.         n->parent->changeColor(Black);
    278.         g->changeColor(Red);
    279.         if ((n == n->parent->left) && (n->parent == g->left)) {
    280.              rotateRight(g);
    281.         } else { /* (n == n->parent->right) and (n->parent == g->right) */
    282.              rotateLeft(g);
    283.         }
    284.     }
    285.  
    286.     void rotateRight(Node *p);
    287.     void rotateLeft(Node *p);
    288.  
    289.     void deleteNode(Node *n);
    290.  
    291.     /*
    292.      * Precondition: n has at most one non-null child.
    293.      */
    294.     void deleteOneChild(Node *n);
    295.  
    296.     /*
    297.      * We must sort out things as in all paths including that node
    298.      * there'll be one less black node
    299.      */
    300.     void deleteCase1(Node *n)
    301.     {
    302.         /* If we are the root, then there's nothing to worry about */
    303.         if (n->parent == NULL) {
    304.  
    305.         } else {
    306.             deleteCase2(n);
    307.         }
    308.  
    309.     }
    310.  
    311.     /*
    312.      * A black node that is not the root will have a black node less
    313.      * in all its paths.
    314.      */
    315.     void deleteCase2(Node *n)
    316.     {
    317.         Node *s = n->sibling();
    318.         if (s->color() == Red)
    319.         {
    320.             /* We must perform a rotation to rebalance the tree.
    321.                Its n's side that loses a black in all its paths, so
    322.                it's why we give more nodes to that side. */
    323.             n->parent->changeColor(Red);
    324.             s->changeColor(Black);
    325.             if (n == n->parent->left) {
    326.                 rotateLeft(n->parent);
    327.             } else {
    328.                 rotateRight(n->parent);
    329.             }
    330.             deleteCase4(n);
    331.         } else {
    332.             deleteCase3(n);
    333.         }
    334.     }
    335.  
    336.     /*
    337.      * The node is black, will have a black node less in all its paths and
    338.      * its sibling is black.
    339.      *
    340.      */
    341.     void deleteCase3(Node *n)
    342.     {
    343.         /* If the parent is also black, and the sibling's children are black / NULL too,
    344.          * then we change the sibling to red. The problem is fixed for the tree under
    345.          * the parent but now the parent will have 1 less black node for path going through it
    346.          * so we go back to the start from the parent this time. */
    347.         Node *s = n->sibling();
    348.         if (n->parent->color() == Black && (!s->left || s->left->color() == Black) && (!s->right || s->right->color() == Black))
    349.         {
    350.             s->changeColor(Red);
    351.             deleteCase1(n->parent);
    352.         } else {
    353.             deleteCase4(n);
    354.         }
    355.     }
    356.  
    357.     /*
    358.      * The node is black, will have a black node less in all its paths and
    359.      * its sibling is black.
    360.      *
    361.      * But either its parent is red or/and the sibling has at least 1 red child.
    362.      */
    363.     void deleteCase4(Node *n)
    364.     {
    365.         Node *s = n->sibling();
    366.  
    367.         /* If the parent is red, we switch colors between the parent and the sibling (if possible) and that's done. */
    368.         if (n->parent->color() == Red && (!s->left || s->left->color() == Black) && (!s->right || s->right->color() == Black)) {
    369.             n->parent->changeColor(Black);
    370.             s->changeColor(Red);
    371.         } else {
    372.             deleteCase5(n);
    373.         }
    374.  
    375.     }
    376.  
    377.     /*
    378.      * The node is black, will have a black node less in all its paths and
    379.      * its sibling is black.
    380.      *
    381.      * But the sibling has at least 1 red child and the parent is unknown color.
    382.      */
    383.     void deleteCase5(Node *n)
    384.     {
    385.         Node *s = n->sibling();
    386.         /* We will have to perform a rotation so we relocate the red child if its not on
    387.            the right side of the sibling.
    388.  
    389.            We force red to be on the right of the right or left of the left of the parent. */
    390.         if ((n == n->parent->left) && (!s->right || s->right->color() == Black)) {
    391.             /* Red child is on left of s */
    392.             s->changeColor(Red);
    393.             s->left->changeColor(Black);
    394.             rotateRight(s);
    395.         } else if ((n == n->parent->right) && (!s->left || s->left->color() == Black)) {
    396.             /* Red child is on right of s */
    397.             s->changeColor(Red);
    398.             s->right->changeColor(Black);
    399.             rotateLeft(s);
    400.         }
    401.         /* And now the rotation... */
    402.         deleteCase6(n);
    403.     }
    404.  
    405.     /*
    406.      * The node is black, will have a black node less in all its paths and
    407.      * its sibling is black.
    408.      *
    409.      * But the sibling has at least 1 red child and the parent is unknown color.
    410.      *
    411.      * If the sibling is left of the parent then its left is a red child, else
    412.      * if the sibling is right of the parent then its right is a red child
    413.      */
    414.     void deleteCase6(Node *n)
    415.     {
    416.         Node *s = n->sibling();
    417.  
    418.         s->changeColor(n->parent->color());
    419.         n->parent->changeColor(Black);
    420.  
    421.         if (n == n->parent->left) {
    422.             s->right->changeColor(Black);
    423.             rotateLeft(n->parent);
    424.         } else {
    425.             s->left->changeColor(Black);
    426.             rotateRight(n->parent);
    427.         }
    428.  
    429.         /* Now n is ready for deletion. Won't cause no damage! */
    430.     }
    431.  
    432.  
    433.  
    434.     struct iterator {
    435.         mutable Node *p;
    436.  
    437.         iterator(Node *p = NULL) : p(p)
    438.         {
    439.  
    440.         }
    441.  
    442.         const iterator& operator ++ () const {
    443.             p = p ? p->next() : p;
    444.             return *this;
    445.         }
    446.  
    447.         iterator& operator ++ () {
    448.             p = p ? p->next() : p;
    449.             return *this;
    450.         }
    451.  
    452.         const iterator& operator -- () const {
    453.             p = p ? p->prev() : p;
    454.             return *this;
    455.         }
    456.  
    457.         iterator& operator -- () {
    458.             p = p ? p->prev() : p;
    459.             return *this;
    460.         }
    461.  
    462.         Node& operator *() const
    463.         {
    464.             return *p;
    465.         }
    466.  
    467.         Node * node() const
    468.         {
    469.             return p;
    470.         }
    471.  
    472.         Node * operator ->() const
    473.         {
    474.             return &(operator *());
    475.         }
    476.  
    477.         bool operator ==(const iterator &other)
    478.         {
    479.             return p == other.p;
    480.         }
    481.  
    482.         bool operator !=(const iterator &other)
    483.         {
    484.             return p != other.p;
    485.         }
    486.     };
    487.  
    488.     typedef const iterator const_iterator;
    489.  
    490.     /* This is something like O(log(n)*log(log(n))).
    491.        Could be O(log(n)) if you aren't lazy */
    492.     iterator getByRanking(int ranking)
    493.     {
    494.         if (root == NULL)
    495.             return iterator();
    496.  
    497.         if (ranking > count()) {
    498.             return root->utmostLeft();
    499.         }
    500.  
    501.         if (ranking <= 1)
    502.             return root->utmostRight();
    503.  
    504.         Node *ptr = root;
    505.  
    506.         int r;
    507.         while ((r = ptr->ranking()) != ranking)
    508.         {
    509.             if (r < ranking)
    510.                 ptr = ptr->left;
    511.             else
    512.                 ptr = ptr->right;
    513.         }
    514.  
    515.         return ptr;
    516.     }
    517.  
    518.     const_iterator getByRanking(int ranking) const
    519.     {
    520.         if (root == NULL)
    521.             return iterator();
    522.  
    523.         if (ranking > count()) {
    524.             return NULL;
    525.         }
    526.  
    527.         if (ranking <= 1)
    528.             return root->utmostRight();
    529.  
    530.         Node *ptr = root;
    531.  
    532.         int r;
    533.         while ((r = ptr->ranking()) != ranking)
    534.         {
    535.             if (r < ranking) {
    536.                 if (ptr->left == NULL) {
    537.                     //qDebug() << "Critical: ranking " << ranking << " left not found, instead " << r;
    538.                     return ptr;
    539.                 }
    540.                 ptr = ptr->left;
    541.             }
    542.             else {
    543.                 if (ptr->right == NULL) {
    544.                     //qDebug() << "Critical: ranking " << ranking << " right not found, instead " << r;
    545.                     return ptr;
    546.                 }
    547.                 ptr = ptr->right;
    548.             }
    549.         }
    550.  
    551.         return ptr;
    552.     }
    553.  
    554.  
    555.     const_iterator begin() const {
    556.         return root ? iterator(root->utmostLeft()) : iterator(root);
    557.     }
    558.  
    559.     const_iterator end() const {
    560.         return iterator(NULL);
    561.     }
    562.  
    563.  
    564.     RankingTree(const RankingTree &other) throw (const char*) {
    565.         if (other.root) {
    566.             throw "Error: Copying ranking tree that's not empty";
    567.         }
    568.         root = NULL;
    569.     }
    570.     Node *root;
    571. };
    572.  
    573. template<class T>
    574. void RankingTree<T>::deleteNode(Node *n)
    575. {
    576.     if (n->left && n->right) {
    577.         /* Two children, we find the one child successor and swap and delete the node */
    578.         /* The reason we swap them is because we MUST KEEP POINTERS VALID! */
    579.         /* And all the tests are to treat special case like when a parent is swapped with
    580.            its child */
    581.         Node * next = n->next();
    582.  
    583.         /* Swap node! */
    584.         Node n_(n->key);
    585.         n_.left = n->left;
    586.         n_.right = n->right;
    587.         n_.parent = n->parent;
    588.         n_.count = n->count;
    589.         n_.changeColor(n->color());
    590.  
    591.         n->left = next->left;
    592.         n->right = next->right;
    593.         n->parent = next->parent == n ? next : next->parent;
    594.         n->changeColor(next->color());
    595.  
    596.         next->parent = n_.parent;
    597.         next->right = n_.right == next ? n : n_.right;
    598.         next->left = n_.left == next ? n : n_.left;
    599.         next->changeColor(n_.color());
    600.  
    601.         n->count = next->count;
    602.         next->count = n_.count;
    603.  
    604.         if (n->left)
    605.             n->left->parent = n;
    606.         if (n->right)
    607.             n->right->parent = n;
    608.         if (n->parent && n->parent!= next)
    609.         {
    610.             if (next == n->parent->left) {
    611.                 n->parent->left = n;
    612.             } else {
    613.                 n->parent->right = n;
    614.             }
    615.         }
    616.         if (next->right)
    617.             next->right->parent = next;
    618.         if (next->left)
    619.             next->left->parent = next;
    620.         if (next->parent) {
    621.             if (n == next->parent->left) {
    622.                 next->parent->left = next;
    623.             } else {
    624.                 next->parent->right = next;
    625.             }
    626.         }
    627.         if (root == n) {
    628.             root = next;
    629.         }
    630.     }
    631.     deleteOneChild(n);
    632. }
    633.  
    634. template <class T>
    635. typename RankingTree<T>::Node* RankingTree<T>::insert(int key, T data)
    636. {
    637.     /* If there's no root, it's trivial... */
    638.     if (root == NULL)
    639.     {
    640.         root = new Node(key, Black, NULL, data);
    641.         return root;
    642.     }
    643.     /* Now, we have to find the correponding leaf, insert it,
    644.        make the necessary color change / rotation */
    645.     /* Finding the leaf */
    646.     Node *ptr = root;
    647.     while (1)
    648.     {
    649.         if (key > ptr->key) {
    650.             /* We have to look to the right side ... */
    651.             if (ptr->right) {
    652.                 ptr = ptr->right;
    653.             } else {
    654.                 /* The right leaf is empty, so we are supposed to insert the new node here */
    655.                 ptr = ptr->right = new Node(key, Red, ptr, data);
    656.                 break;
    657.             }
    658.         } else {
    659.             /* We have to look to the left side ... */
    660.             if (ptr->left) {
    661.                 ptr = ptr->left;
    662.             } else {
    663.                 /* The left leaf is empty, so we are supposed to insert the new node here */
    664.                 ptr = ptr->left = new Node(key, Red, ptr, data);
    665.                 break;
    666.             }
    667.         }
    668.     }
    669.     /* We increase the count of every parent as we keep track of it */
    670.     ptr->parent->increaseCountUp();
    671.     /* Now, we've inserted a new leaf, red, with a parent. */
    672.     /* We need to fix the tree in case the rules are violated */
    673.     insertCase2(ptr);
    674.     return ptr;
    675. }
    676.  
    677. template<class T>
    678. void RankingTree<T>::rotateRight(Node *p)
    679. {
    680.     p->left->parent = p->parent;
    681.     if (p->parent) {
    682.         if (p->parent->left == p)
    683.             p->parent->left = p->left;
    684.         else
    685.             p->parent->right = p->left;
    686.     }
    687.     p->parent = p->left;
    688.  
    689.     p->left = p->parent->right;
    690.     if (p->left)
    691.         p->left->parent = p;
    692.  
    693.     p->parent->right = p;
    694.  
    695.     if (root == p)
    696.         root = p->parent;
    697.  
    698.     /* Updating the count for the rank algorithm */
    699.     p->count = (p->right ? p->right->count : 0) + (p->left ? p->left->count : 0) + 1;
    700.     p->parent->count =  (p->parent->left ? p->parent->left->count : 0) + p->count + 1;
    701. }
    702.  
    703. template<class T>
    704. void RankingTree<T>::rotateLeft(Node *p)
    705. {
    706.     p->right->parent = p->parent;
    707.     if (p->parent) {
    708.         if (p->parent->right == p)
    709.             p->parent->right = p->right;
    710.         else
    711.             p->parent->left = p->right;
    712.     }
    713.     p->parent = p->right;
    714.  
    715.     p->right = p->parent->left;
    716.     if (p->right)
    717.         p->right->parent = p;
    718.  
    719.     p->parent->left = p;
    720.  
    721.     if (root == p)
    722.         root = p->parent;
    723.  
    724.     /* Updating the count for the rank algorithm */
    725.     p->count = (p->right ? p->right->count : 0) + (p->left ? p->left->count : 0) + 1;
    726.     p->parent->count =  (p->parent->right ? p->parent->right->count : 0) + p->count + 1;
    727. }
    728.  
    729. /*
    730.  * Precondition: n has at most one non-null child.
    731.  */
    732. template<class T>
    733. void RankingTree<T>::deleteOneChild(Node *n)
    734. {
    735.     Node *child = n->right ? n->right : n->left;
    736.  
    737.     /* If theres no child, its either a red node (easy) or black node (hard)*/
    738.     if (!child) {
    739.         if (n->color() == Red) {
    740.             /* No worry */
    741.         } else {
    742.             /* We need to rebalance the tree as the parent has 1 black node
    743.              * less coming from us */
    744.             deleteCase1(n);
    745.         }
    746.     } else {
    747.         /* Means 1 child, means we are black and the child is red */
    748.         child->changeColor(Black);
    749.         child->parent = n->parent;
    750.     }
    751.     if (n == root) {
    752.         root = child;
    753.     } else {
    754.         if (n->parent->left == n) {
    755.             n->parent->left = child;
    756.         } else {
    757.             n->parent->right = child;
    758.         }
    759.     }
    760.  
    761.     n->decreaseCountUp();
    762.     delete n;
    763. }
    764.  
    765. #endif // RANKINGTREE_H
    766.  
    I've based my code on one available on wikipedia for the RB-Tree, and then did the changes to make it OO, to remove a few unnecessary checks and to add the subtree-size info.

    Problems

    It isn't linked to the regular member database -- When members are deleted or don't exist anymore, the Tier manager still have them
    Everything is in the RAM - but it's ok, I guess, because even with a client you can explore all the data quite easily, and it doesn't take much space
    Nothing really... Maybe making it easier for webservers to use?


    Way to go

    Actually I've thought of the Tier Manager to call the Member Manager and append the data to the member structs (using pointers?), but that seems kind of ugly.

    We may also use SQL databases, but I fear simple databases like SQLite won't provide an efficient ranking & sorting solution. That's why a PostGreSQL database would be more fit, or the full order would have to be in memory...

    Anyway, feel free to discuss.