Update score and get rank in real time

score_rank.cc

#include <vector>
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

typedef int32_t Score;
typedef int32_t UserId;
typedef int32_t Rank;
const Score kInvalidScore = -1;

enum ErrorCode
{
  kSucceed, kFailed
};

struct Result
{
  ErrorCode error;
  Rank rank;
  int32_t numUsersOfSameScore;

  Result()
    : error(kFailed),
      rank(0),
      numUsersOfSameScore(0)
  {
  }
};

const int kMaxUsers = 1000; // 200*1000*1000;
const int kMaxScore = 20; // 1*1000*1000;

const bool kDebug= false;

class ScoreTable
{
 public:
  ScoreTable()
  {
    usersAtScore_.resize(kMaxScore+1);
    for (UserId userId = 1; userId <= kMaxUsers; ++userId)
    {
      Score score = rand() % (kMaxScore+1);
      assert(0 <= score && score <= kMaxScore);
      usersAtScore_[score] += 1;
    }
    partialSum().swap(usersAboveScore_);
    assert(usersAtScore_[0] + usersAboveScore_[0] == kMaxUsers);
  }

  Result getRank(Score score) const
  {
    Result result;
    assert(0 <= score && score <= kMaxScore);
    result.error = kSucceed;
    result.rank = usersAboveScore_[score] + 1;
    result.numUsersOfSameScore = usersAtScore_[score];
    return result;
  }

  Result updateScore(Score oldScore, Score newScore)
  {
    Result result;
    if (0 <= newScore && newScore <= kMaxScore)
    {
      if (oldScore == kInvalidScore)
      {
        oldScore = 0;
      }
      else
      {
        assert(0 <= oldScore && oldScore <= kMaxScore);
        usersAtScore_[oldScore] -= 1;
        if (usersAtScore_[oldScore] < 0)
        {
          // error !!
          usersAtScore_[oldScore] = 0;
        }
      }
      usersAtScore_[newScore] += 1;

      updateCache(oldScore, newScore);
      result = getRank(newScore);
    }
    return result;
  }

 private:
  std::vector<int32_t> usersAtScore_;     // radix bucket
  std::vector<int32_t> usersAboveScore_;  // partial sum of above

  std::vector<int32_t> partialSum()
  {
    std::vector<int32_t> sum;
    assert(usersAtScore_.size() == kMaxScore+1);
    sum.resize(usersAtScore_.size());
    int32_t count = 0;
    for (int score = kMaxScore; score >= 0; --score)
    {
      sum[score] = count;
      count += usersAtScore_[score];
    }
    return sum;
  }

  void updateCache(Score oldScore, Score newScore)
  {
    if (oldScore < newScore)
    {
      for (int i = oldScore; i < newScore; ++i)
      {
        usersAboveScore_[i] += 1;
      }
    }
    else if (oldScore > newScore)
    {
      for (int i = newScore; i < oldScore; ++i)
      {
        usersAboveScore_[i] -= 1;
      }
    }

    if (kDebug)
    {
      assert(partialSum() == usersAboveScore_);
    }
  }
};

int main()
{
  ScoreTable table;
  for (Score score = kMaxScore; score >= 0; --score)
  {
    Result rank = table.getRank(score);
    printf("%3d %5d %5d\n", score, rank.rank, rank.numUsersOfSameScore);
  }

  {
  Score oldScore = 10;
  Result oldRank = table.getRank(oldScore);
  printf("\nbefore update\n%3d %5d %5d\n",
      oldScore, oldRank.rank, oldRank.numUsersOfSameScore);
  Score newScore = 15;
  Result newRank = table.updateScore(10, newScore);
  printf("after update\n%3d %5d %5d\n\n",
      newScore, newRank.rank, newRank.numUsersOfSameScore);
  }
  for (Score score = kMaxScore; score >= 0; --score)
  {
    Result rank = table.getRank(score);
    printf("%3d %5d %5d\n", score, rank.rank, rank.numUsersOfSameScore);
  }
}