app/ranklist/ranker.py
author Lennard de Rijk <ljvderijk@gmail.com>
Tue, 30 Jun 2009 14:56:48 +0200
changeset 2464 64b241a237b2
parent 1597 e7b7ea113a3b
permissions -rwxr-xr-x
Merge params from inheriting Survey views so functionality can be reused.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1597
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     1
#!/usr/bin/python
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     2
#
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     3
# Copyright 2008 Google Inc.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     4
#
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     5
# Licensed under the Apache License, Version 2.0 (the "License");
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     6
# you may not use this file except in compliance with the License.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     7
# You may obtain a copy of the License at
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     8
#
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
     9
#      http://www.apache.org/licenses/LICENSE-2.0
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    10
#
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    11
# Unless required by applicable law or agreed to in writing, software
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    12
# distributed under the License is distributed on an "AS IS" BASIS,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    13
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    14
# See the License for the specific language governing permissions and
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    15
# limitations under the License.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    16
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    17
from google.appengine.api import datastore
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    18
from google.appengine.api import datastore_types
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    19
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    20
from common import transactional
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    21
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    22
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    23
class Ranker(object):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    24
  """A data structure for storing integer scores and quickly retrieving their
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    25
  relative ranks.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    26
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    27
  Scores are stored as "name: score" mapping. A score is inserted by
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    28
  calling SetScore with a new name. The score can later be updated by
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    29
  calling SetScore again with the same name.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    30
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    31
  The scores are actually lists of integers with the same number of elements,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    32
  and their ordering is lexicographic.  That is to say that score A is higher
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    33
  than score B if they are different, and the first element that differs between
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    34
  the two is higher in A.  Thus [5, 3] is ranked higher than [4, 99].
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    35
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    36
  Example Use Case:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    37
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    38
  Some number of people are participating in a programming contest.  Solving a
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    39
  problem gets points; contestants also get a tie-breaking "penalty time."  The
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    40
  higher the time, the worse the score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    41
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    42
  STEP 1:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    43
  # Creates the ranker when the contest is created:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    44
  rank = ranker.Ranker.Create([0, 10000, -999999, 1], 100)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    45
  # In our contest, people won't have more than 9999 points or 999999 penalty
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    46
  # seconds.  Since penalty time is bad, we store [score, -penalty].
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    47
  contest['ranker'] = rank.rootkey
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    48
  datastore.Put(contest)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    49
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    50
  STEP 2:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    51
  # Someone registers for the contest.  The default score is [0, 0], and for
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    52
  # efficiency we don't put them in the ranker; they won't be ahead of anyone
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    53
  # anyway.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    54
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    55
  STEP 3:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    56
  # Player "Jon" gets points for the first time!
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    57
  rank = ranker.Ranker(contest['ranker'])
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    58
  # Loads up the ranker.  This is the first step of all the STEPs below.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    59
  rank.SetScore("Jon", [5, -120])  # 5 points, 2 minutes
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    60
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    61
  STEP 4:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    62
  # Player "Jon" gets points for the second time!
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    63
  rank.SetScore("Jon", [10, -300])  # 10 points, 5 minutes
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    64
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    65
  STEP 5:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    66
  # What is the rank of the person with score [10, -300]?
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    67
  position = rank.FindRank([10, 300])
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    68
  # What are the ranks for the people with scores a, b, c?
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    69
  positions = rank.FindRanks([a, b, c])
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    70
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    71
  STEP 6:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    72
  # What is the score of the person ranked 20th?
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    73
  score = rank.FindScore(19)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    74
  # This is particularly useful for seeing multiple pages of ranked people.  If
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    75
  # the scores are separately tracked in an entity called 'scores', the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    76
  # datastore can efficiently answer:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    77
  # q = datastore.Query('scores')
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    78
  # q['score <='] = rank.FindScore(1000)[0]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    79
  # next_twenty_scores = q.Get(20)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    80
  # This is a simplified case, where scores are a single integer.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    81
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    82
  STEP 7:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    83
  # How many people have points?
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    84
  num_pointy_people = rank.TotalRankedScores()
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    85
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    86
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    87
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    88
  Implementation Details:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    89
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    90
  The Ranker is a rooted tree of 'ranker_node' entities.  It is an
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    91
  N-ary tree, where N = self.branching_factor, which is specified by the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    92
  constructor.  Each node represents some range of scores, and is assigned a
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    93
  unique node_id.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    94
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    95
  Take for example a 3-ary tree with point range [0, 10000, -36000, 1].  This
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    96
  could represent a contest where contestants can have between 0 and 9999
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    97
  points, with ties being broken by (negative) penalty seconds that can be
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    98
  between 0 and 10 hours.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
    99
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   100
  The root represents the score range [0, 10000, -36000, 1].  It has node_id 0.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   101
  Its first child has node_id 1 and score range [0, 3333, -36000, 1].
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   102
  The root's second child, node_id 2, has score range [3333, 6666, -36000, 1],
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   103
  and its third child, node_id 3, has score range [6666, 10000, -36000, 1].
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   104
  Node 1's first child, node_id 4, has range [0, 1111, -36000, 1], and so on.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   105
  See __WhichChild for details of how children are assigned score ranges.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   106
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   107
  The point of a node is to track how many stored scores are in the score range
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   108
  of each of its children.  The root in the above example would start off with
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   109
  child_node_counts = [0, 0, 0]; adding score [4000, 0] would change the root's
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   110
  child_node_counts to [0, 1, 0] and node 5's child_node_counts to [1, 0, 0],
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   111
  and so forth.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   112
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   113
  Ranker also has a "ranker_score" entity for every score stored in the ranker.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   114
  These entities are part of the same entity group as the ranker_node
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   115
  entities. This allows for atomic, idempotent calls to SetScores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   116
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   117
  Ranker supports the following operations, which can be read about in detail
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   118
  in their docstrings:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   119
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   120
  SetScores(scores): Set scores for multiple players.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   121
  FindRank(score): Finds the 0-based rank of the provided score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   122
  FindScore(rank): Finds the score with the provided 0-based rank.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   123
  FindScoreApproximate(rank): Finds a score >= the score of the provided 0-based
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   124
    rank, < the score of rank-1 (unless rank and rank-1 are tied, in which case
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   125
    it returns their mutual score).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   126
  TotalRankedScores: The total number of scores in the Ranker.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   127
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   128
  See __FindNodeIDs for more notes on structure.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   129
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   130
  """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   131
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   132
  def __init__(self, rootkey):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   133
    """Pulls a ranker out of the datastore, given the key of the root node.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   134
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   135
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   136
      rootkey: The datastore key of the ranker.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   137
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   138
    # Get the root from the datastore:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   139
    assert rootkey.kind() == "ranker"
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   140
    root = datastore.Get(rootkey)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   141
    # Initialize some class variables:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   142
    self.rootkey = rootkey
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   143
    self.score_range = root["score_range"]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   144
    self.branching_factor = root["branching_factor"]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   145
    # Sanity checking:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   146
    assert len(self.score_range) > 1
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   147
    assert len(self.score_range) % 2 == 0
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   148
    for i in xrange(0, len(self.score_range), 2):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   149
      assert self.score_range[i + 1] > self.score_range[i]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   150
    assert self.branching_factor > 1
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   151
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   152
  @classmethod
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   153
  def Create(cls, score_range, branching_factor):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   154
    """Constructs a new Ranker and returns it.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   155
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   156
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   157
      score_range: A list showing the range of valid scores, in the form:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   158
        [most_significant_score_min, most_significant_score_max,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   159
         less_significant_score_min, less_significant_score_max, ...]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   160
        Ranges are [inclusive, exclusive)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   161
      branching_factor: The branching factor of the tree.  The number of
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   162
        datastore Gets is Theta(1/log(branching_factor)), and the amount of data
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   163
        returned by each Get is Theta(branching_factor).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   164
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   165
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   166
      A new Ranker.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   167
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   168
    # Put the root in the datastore:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   169
    root = datastore.Entity("ranker")
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   170
    root["score_range"] = score_range
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   171
    root["branching_factor"] = branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   172
    datastore.Put(root)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   173
    myrank = Ranker(root.key())
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   174
    return myrank
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   175
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   176
  def __FindNodeIDs(self, score):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   177
    """Finds the nodes along the path from the root to a certain score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   178
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   179
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   180
      score: The score we're finding the path for.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   181
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   182
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   183
      A sorted list of (node_id, child) tuples, indicating that node_id is the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   184
      node id of a node on the path, and child is which child of that node is
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   185
      next.  Note that the lowest child node (which would be a leaf node) does
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   186
      not actually exist, since all its relevant information (number of times
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   187
      that score was inserted) is stored in its parent.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   188
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   189
    Nodes are numbered row-by-row: the root is 0, its children are in the range
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   190
    [1, self.branching_factor + 1), its grandchildren are in the range
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   191
    [self.branching_factor + 1,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   192
     self.branching_factor**2 + self.branching_factor + 1), etc.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   193
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   194
    Score ranges are lists of the form: [min_0, max_0, min_1, max_1, ...]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   195
    A node representing a score range will be divided up by the first index
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   196
    where max_i != min_i + 1 (score ranges are [inclusive, exclusive)).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   197
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   198
    Child x (0-indexed) of a node [a,b) will get the range:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   199
    [a+x*(b-a)/branching_factor, a+(x+1)*(b-a)/branching_factor);
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   200
    Thus not all nodes will have nonzero ranges.  Nodes with zero range will
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   201
    never be visited, but they and their descendants will be counted in the node
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   202
    numbering scheme, so row x still has self.branching_factor**x nodes.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   203
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   204
    nodes = []
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   205
    node = 0
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   206
    cur_range = list(self.score_range)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   207
    # The current range of scores.  This will be narrowed as we move down the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   208
    # tree; 'index' keeps track of the score type we're currently changing.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   209
    for index in xrange(0, len(cur_range), 2):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   210
      while cur_range[index + 1] - cur_range[index] > 1:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   211
        # Subdivide cur_range[index]..cur_range[index + 1]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   212
        which_child = self.__WhichChild(cur_range[index],
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   213
                                        cur_range[index + 1],
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   214
                                        score[index // 2],
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   215
                                        self.branching_factor)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   216
        child = which_child[0]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   217
        cur_range[index] = which_child[1][0]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   218
        cur_range[index + 1] = which_child[1][1]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   219
        assert 0 <= child < self.branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   220
        nodes.append((node, child))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   221
        node = self.__ChildNodeId(node, child)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   222
    return nodes
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   223
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   224
  def __WhichChild(self, low, high, want, branching_factor):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   225
    """Determines which child of the range [low, high) 'want' belongs to.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   226
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   227
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   228
      low: An int, the low end of the range.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   229
      high: An int, the high end of the range.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   230
      want: An int, the score we're trying to determine a child for.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   231
      branching_factor: The branching factor of the tree being used.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   232
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   233
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   234
      A tuple, (child, [child's score range]).  Note that in general a score
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   235
      has multiple sub-scores, written in order of decreasing significance; this
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   236
      function divides up a single sub-score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   237
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   238
    Raises:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   239
      An AssertionError if things go horribly wrong.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   240
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   241
    assert low <= want < high
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   242
    # Need to find x such that (using integer division):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   243
    #     x  *(high-low)/branching_factor <= want - low <
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   244
    #   (x+1)*(high-low)/branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   245
    # Which is the least x such that (using integer division):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   246
    #   want - low < (x+1)*(high-low)/branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   247
    # Which is the ceiling of x such that (using floating point division):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   248
    #   want - low + 1 == (x+1)*(high-low)/branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   249
    #   x = -1 + math.ceil((want-low+1) * branching_factor / (high - low))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   250
    # We get ceil by adding high - low - 1 to the numerator.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   251
    x = -1 + (((want - low + 1) * branching_factor + high - low - 1) //
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   252
              (high - low))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   253
    assert (x * (high - low) // branching_factor <=
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   254
            want - low < (x + 1) * (high - low) // branching_factor)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   255
    return (x, self.__ChildScoreRange([low, high], x, branching_factor))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   256
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   257
  def __ChildScoreRange(self, score_range, child, branching_factor):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   258
    """Calculates the score_range for a node's child.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   259
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   260
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   261
      score_range: A score range [min0, max0, min1, max1, ...]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   262
      child: Which child of the node with score range score_range we're
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   263
        calculating the score range of.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   264
      branching_factor: The branching factor of the tree in question.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   265
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   266
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   267
      A score range [min0', max0', min1', max1', ...] for that child.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   268
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   269
    for i in xrange(1, len(score_range), 2):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   270
      if score_range[i] > score_range[i - 1] + 1:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   271
        child_score_range = list(score_range)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   272
        low, high = score_range[i - 1], score_range[i]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   273
        child_score_range[i - 1], child_score_range[i] = (
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   274
            low + child * (high - low) // branching_factor,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   275
            low + (child + 1) * (high - low) // branching_factor)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   276
        return child_score_range
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   277
    raise AssertionError("Node with score range %s has no children." %
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   278
                         score_range)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   279
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   280
  def __ChildNodeId(self, node_id, child):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   281
    """Calculates the node id for a known node id's child.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   282
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   283
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   284
      node_id: The parent node's node_id
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   285
      child: Which child of the parent node we're finding the id for
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   286
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   287
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   288
      The node_id for the child'th child of node_id.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   289
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   290
    return node_id * self.branching_factor + 1 + child
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   291
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   292
  def __GetMultipleNodes(self, node_ids):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   293
    """Gets multiple nodes from the datastore.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   294
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   295
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   296
      node_ids: A list of node ids we want to get.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   297
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   298
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   299
      A dict of the nodes that were found, indexed by the node ids found
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   300
      in node_ids.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   301
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   302
    if len(node_ids) == 0:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   303
      return []
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   304
    node_ids = set(node_ids)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   305
    keys = [self.__KeyFromNodeId(node_id) for node_id in node_ids]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   306
    nodes = datastore.Get(keys)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   307
    return dict((node_id, node) for (node_id, node) in zip(node_ids, nodes)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   308
                if node)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   309
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   310
  # Although, this method is currently not needed, we'll keep this
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   311
  # since we might need it and some point and it's an interesting
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   312
  # relationship
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   313
  def __ParentNode(self, node_id):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   314
    """Returns the node id of the parameter node id's parent.  Returns None if
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   315
    the parameter is 0."""
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   316
    if node_id == 0:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   317
      return None
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   318
    return (node_id - 1) // self.branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   319
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   320
  def __KeyFromNodeId(self, node_id):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   321
    """Creates a (named) key for the node with a given id.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   322
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   323
    The key will have the ranker as a parent element to guarantee
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   324
    uniqueness (in the presence of multiple rankers) and to put all
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   325
    nodes in a single entity group.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   326
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   327
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   328
      node_id: The node's id as an integer.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   329
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   330
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   331
      A (named) key for the node with the id 'node_id'.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   332
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   333
    name = "node_%x" % node_id
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   334
    return datastore_types.Key.from_path("ranker_node", name,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   335
                                         parent=self.rootkey)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   336
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   337
  def __KeyForScore(self, name):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   338
    """Returns a (named) key for a ranker_score entity.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   339
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   340
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   341
      name: Name of the score to create a key for.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   342
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   343
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   344
      A (named) key for the entity storing the score of 'name'.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   345
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   346
    return datastore_types.Key.from_path("ranker_score", name,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   347
                                         parent=self.rootkey)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   348
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   349
  def __Increment(self, nodes_with_children, score_entities,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   350
                  score_entities_to_delete):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   351
    """Changes child counts for given nodes.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   352
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   353
    This method will create nodes as needed.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   354
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   355
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   356
      nodes_with_children: A dict of (node_key, child) tuples to deltas
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   357
      score_entities: Additional score entities to persist as part of
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   358
        this transaction
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   359
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   360
      None
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   361
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   362
    keys = list(set(key for ((key, _), delta) in nodes_with_children.iteritems()
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   363
                    if delta != 0))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   364
    if not keys:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   365
      return  # Nothing to do
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   366
    nodes = datastore.Get(keys)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   367
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   368
    node_dict = {}
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   369
    for (key, node) in zip(keys, nodes):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   370
      if not node:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   371
        node = datastore.Entity("ranker_node", parent=self.rootkey,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   372
                                name=key.name())
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   373
        node["child_counts"] = [0] * self.branching_factor
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   374
      node_dict[key] = node
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   375
    for ((key, child), amount) in nodes_with_children.iteritems():
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   376
      if amount != 0:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   377
        node = node_dict[key]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   378
        node["child_counts"][child] += amount
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   379
        assert node["child_counts"][child] >= 0
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   380
    datastore.Put(node_dict.values() + score_entities)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   381
    if score_entities_to_delete:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   382
      datastore.Delete(score_entities_to_delete)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   383
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   384
  def SetScore(self, name, score):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   385
    """Sets a single score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   386
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   387
    This is equivalent to calling 'SetScores({name: score})'
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   388
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   389
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   390
      name: the name of the score as a string
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   391
      score: the score to set name to
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   392
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   393
    return self.SetScores({name: score})
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   394
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   395
  @transactional
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   396
  def SetScores(self, scores):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   397
    """Changes multiple scores atomically.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   398
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   399
    Sets the scores of the named entities in scores to new values. For
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   400
    named entities that have not been registered with a score before,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   401
    a new score is created. For named entities that already had a score,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   402
    the score is changed to reflect the new score. If a score is None,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   403
    the named entity's score will be removed from the ranker.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   404
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   405
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   406
      scores: A dict mapping entity names (strings) to scores (integer lists)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   407
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   408
    score_deltas, score_ents, score_ents_del = self.__ComputeScoreDeltas(scores)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   409
    node_ids_to_deltas = self.__ComputeNodeModifications(score_deltas)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   410
    self.__Increment(node_ids_to_deltas, score_ents, score_ents_del)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   411
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   412
  def __ComputeScoreDeltas(self, scores):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   413
    """Compute which scores have to be incremented and decremented.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   414
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   415
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   416
      scores: A dict mapping entity names to scores
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   417
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   418
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   419
      A tuple (score_deltas, score_entities, score_entities_to_delete).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   420
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   421
      'score_deltas' is a dict, mapping scores (represented as tuples)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   422
      to integers. 'score_deltas[s]' represents how many times the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   423
      score 's' has to be incremented (or decremented).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   424
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   425
      'score_entities' is a list of 'ranker_score' entities that have
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   426
      to be updated in the same transaction as modifying the ranker
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   427
      nodes. The entities already contain the updated score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   428
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   429
      Similarly, 'score_entities_to_delete' is a list of entities that
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   430
      have to be deleted in the same transaction as modifying the ranker
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   431
      nodes.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   432
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   433
    score_keys = [self.__KeyForScore(score) for score in scores]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   434
    old_scores = {}
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   435
    for old_score in datastore.Get(score_keys):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   436
      if old_score:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   437
        old_scores[old_score.key().name()] = old_score
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   438
    score_deltas = {}
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   439
    # Score entities to update
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   440
    score_ents = []
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   441
    score_ents_del = []
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   442
    for score_name, score_value in scores.iteritems():
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   443
      if score_name in old_scores:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   444
        score_ent = old_scores[score_name]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   445
        if score_ent["value"] == score_value:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   446
          continue  # No change in score => nothing to do
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   447
        old_score_key = tuple(score_ent["value"])
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   448
        score_deltas.setdefault(old_score_key, 0)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   449
        score_deltas[old_score_key] -= 1
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   450
      else:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   451
        score_ent = datastore.Entity("ranker_score", parent=self.rootkey,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   452
                                     name=score_name)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   453
      if score_value:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   454
        score_key = tuple(score_value)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   455
        score_deltas.setdefault(score_key, 0)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   456
        score_deltas[score_key] += 1
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   457
        score_ent["value"] = score_value
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   458
        score_ents.append(score_ent)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   459
      else:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   460
        # Do we have to delete an old score entity?
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   461
        if score_name in old_scores:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   462
          score_ents_del.append(old_scores[score_name])
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   463
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   464
    return (score_deltas, score_ents, score_ents_del)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   465
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   466
  def __ComputeNodeModifications(self, score_deltas):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   467
    """Computes modifications to ranker nodes.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   468
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   469
    Given score deltas, computes which nodes need to be modified and by
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   470
    how much their child count has to be incremented / decremented.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   471
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   472
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   473
      score_deltas: A dict of scores to integers, as returned by
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   474
        _ComputeScoreDeltas.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   475
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   476
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   477
      A dict of nodes (represented as node_key, child tuples) to integers.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   478
      'result[(node_key, i)]' represents the amount that needs to be added to
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   479
      the i-th child of node node_key.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   480
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   481
    nodes_to_deltas = {}
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   482
    for score, delta in score_deltas.iteritems():
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   483
      for (node_id, child) in self.__FindNodeIDs(score):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   484
        node = (self.__KeyFromNodeId(node_id), child)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   485
        nodes_to_deltas[node] = nodes_to_deltas.get(node, 0) + delta
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   486
    return nodes_to_deltas
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   487
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   488
  def __FindRank(self, node_ids_with_children, nodes):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   489
    """Utility function.  Finds the rank of a score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   490
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   491
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   492
      node_ids_with_children: A list of node ids down to that score,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   493
        paired with which child links to follow.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   494
      nodes: A dict mapping node id to node entity.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   495
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   496
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   497
      The score's rank.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   498
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   499
    tot = 0  # Counts the number of higher scores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   500
    for (node_id, child) in node_ids_with_children:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   501
      if node_id in nodes:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   502
        node = nodes[node_id]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   503
        for i in xrange(child + 1, self.branching_factor):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   504
          tot += node["child_counts"][i]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   505
      else:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   506
        # If the node isn't in the dict, the node simply doesn't exist.  We
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   507
        # are probably finding the rank for a score that doesn't appear in the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   508
        # ranker, but that's perfectly fine.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   509
        pass
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   510
    return tot
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   511
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   512
  def FindRank(self, score):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   513
    """Finds the 0-based rank of a particular score; more precisely, returns the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   514
    number of strictly higher scores stored.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   515
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   516
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   517
      score: The score whose rank we wish to find.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   518
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   519
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   520
      The number of tracked scores that are higher.  Does not check whether
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   521
      anyone actually has the requested score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   522
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   523
    return self.FindRanks([score])[0]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   524
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   525
  def FindRanks(self, scores):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   526
    """Finds the 0-based ranks of a number of particular scores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   527
    Like FindRank, but more efficient for multiple scores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   528
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   529
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   530
      scores: A list of scores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   531
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   532
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   533
      A list of ranks.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   534
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   535
    for score in scores:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   536
      assert len(score) * 2 == len(self.score_range)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   537
    # Find the nodes we'll need to query to find information about these scores:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   538
    node_ids_with_children_list = [self.__FindNodeIDs(score)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   539
                                   for score in scores]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   540
    node_ids = []
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   541
    for node_ids_with_children in node_ids_with_children_list:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   542
      node_ids += [node_id for (node_id, _) in node_ids_with_children]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   543
    # Query the needed nodes:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   544
    nodes_dict = self.__GetMultipleNodes(node_ids)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   545
    # Call __FindRank, which does the math, for each score:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   546
    return [self.__FindRank(node_ids_with_children, nodes_dict) for
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   547
            node_ids_with_children in node_ids_with_children_list]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   548
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   549
  def __FindScore(self, node_id, rank, score_range, approximate):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   550
    """To be run in a transaction.  Finds the score ranked 'rank' in the subtree
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   551
    defined by node 'nodekey.'
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   552
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   553
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   554
      node_id: The id of the node whose subtree we wish to find the
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   555
        score of rank 'rank' in.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   556
      rank: The rank (within this subtree) of the score we wish to find.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   557
      score_range: The score range for this particular node, as a list.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   558
        Derivable from the node's node_id, but included for convenience.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   559
      approximate: Do we have to return an approximate result, or an exact one?
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   560
        See the docstrings for FindScore and FindScoreApproximate.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   561
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   562
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   563
      A tuple, (score, rank_of_tie), indicating the score's rank within
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   564
      node_id's subtree.  The way it indicates rank is defined in the dosctrings
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   565
      of FindScore and FindScoreApproximate, depending on the value of
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   566
      'approximate'.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   567
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   568
    # If we're approximating and thus allowed to do so, early-out if we just
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   569
    # need to return the highest available score.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   570
    if approximate and rank == 0:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   571
      return ([score - 1 for score in score_range[1::2]], 0)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   572
    # Find the current node.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   573
    node = datastore.Get(self.__KeyFromNodeId(node_id))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   574
    child_counts = node["child_counts"]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   575
    initial_rank = rank
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   576
    for i in xrange(self.branching_factor - 1, -1, -1):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   577
      # If this child has enough scores that rank 'rank' is in
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   578
      # there, recurse.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   579
      if rank - child_counts[i] < 0:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   580
        child_score_range = self.__ChildScoreRange(score_range, i,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   581
                                                   self.branching_factor)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   582
        if self.__IsSingletonRange(child_score_range):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   583
          # Base case; child_score_range refers to a single score. We don't
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   584
          # store leaf nodes so we can return right here.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   585
          return (child_score_range[0::2], initial_rank - rank)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   586
        # Not a base case.  Keep descending into children.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   587
        ans = self.__FindScore(self.__ChildNodeId(node_id, i), rank,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   588
                               child_score_range,
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   589
                               approximate)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   590
        # Note the 'initial_rank - rank': we've asked the child for a score of
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   591
        # some rank among *its* children, so we have to add back in the scores
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   592
        # discarded on the way to that child.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   593
        return (ans[0], ans[1] + (initial_rank - rank))
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   594
      else:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   595
        rank -= child_counts[i]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   596
    return None
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   597
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   598
  def __IsSingletonRange(self, scorerange):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   599
    """Returns whether a range contains exactly one score."""
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   600
    return [score + 1 for score in scorerange[0::2]] == scorerange[1::2]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   601
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   602
  @transactional
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   603
  def FindScore(self, rank):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   604
    """Finds the score ranked at 'rank'.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   605
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   606
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   607
      rank: The rank of the score we wish to find.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   608
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   609
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   610
      A tuple, (score, rank_of_tie).  'score' is the score ranked at 'rank',
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   611
      'rank_of_tie' is the rank of that score (which may be different from
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   612
      'rank' in the case of ties).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   613
      e.g. if there are two scores tied at 5th and rank == 6, returns
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   614
      (score, 5).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   615
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   616
    return self.__FindScore(0, rank, self.score_range, False)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   617
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   618
  @transactional
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   619
  def FindScoreApproximate(self, rank):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   620
    """Finds a score that >= the score ranked at 'rank'.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   621
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   622
    This method could be preferred to FindScore because it is more efficient.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   623
    For example, if the objective is to find the top 50 scores of rank X or
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   624
    less, and those scores are stored in entities called scoreboard_row:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   625
      score, rank = myrank.FindScoreApproximate(X)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   626
      query = datastore.Query('scoreboard_row')
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   627
      query['score <='] = score
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   628
      result = query.Get(50 + X - rank)[X-rank:])  # Takes care of ties.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   629
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   630
    Args:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   631
      rank: The rank of the score we wish to find.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   632
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   633
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   634
      A tuple, (score, rank_of_tie).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   635
      If there is a tie at rank 'rank-1':
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   636
        rank's score <= score < rank-1's score, rank_of_tie == rank
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   637
      else:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   638
        score == rank's score, rank_of_tie == the tied rank of everyone
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   639
        in the tie.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   640
        e.g. if two scores are tied at 5th and rank == 6, returns (score, 5).
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   641
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   642
    return self.__FindScore(0, rank, self.score_range, True)
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   643
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   644
  def TotalRankedScores(self):
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   645
    """Returns the total number of ranked scores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   646
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   647
    Returns:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   648
      The total number of ranked scores.
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   649
    """
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   650
    root = datastore.Get([self.__KeyFromNodeId(0)])[0]
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   651
    if root:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   652
      return sum(root["child_counts"])
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   653
    else:
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   654
      # Ranker doesn't have any ranked scores, yet
e7b7ea113a3b Add google-app-engine-ranklist project to ranklist folder in app.
Pawel Solyga <Pawel.Solyga@gmail.com>
parents:
diff changeset
   655
      return 0