+
−#!/usr/bin/python
+
−#
+
−# Copyright 2008 Google Inc.
+
−#
+
−# Licensed under the Apache License, Version 2.0 (the "License");
+
−# you may not use this file except in compliance with the License.
+
−# You may obtain a copy of the License at
+
−#
+
−#      http://www.apache.org/licenses/LICENSE-2.0
+
−#
+
−# Unless required by applicable law or agreed to in writing, software
+
−# distributed under the License is distributed on an "AS IS" BASIS,
+
−# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+
−# See the License for the specific language governing permissions and
+
−# limitations under the License.
+
−
+
−from google.appengine.api import datastore
+
−from google.appengine.api import datastore_types
+
−
+
−from common import transactional
+
−
+
−
+
−class Ranker(object):
+
−  """A data structure for storing integer scores and quickly retrieving their
+
−  relative ranks.
+
−
+
−  Scores are stored as "name: score" mapping. A score is inserted by
+
−  calling SetScore with a new name. The score can later be updated by
+
−  calling SetScore again with the same name.
+
−
+
−  The scores are actually lists of integers with the same number of elements,
+
−  and their ordering is lexicographic.  That is to say that score A is higher
+
−  than score B if they are different, and the first element that differs between
+
−  the two is higher in A.  Thus [5, 3] is ranked higher than [4, 99].
+
−
+
−  Example Use Case:
+
−
+
−  Some number of people are participating in a programming contest.  Solving a
+
−  problem gets points; contestants also get a tie-breaking "penalty time."  The
+
−  higher the time, the worse the score.
+
−
+
−  STEP 1:
+
−  # Creates the ranker when the contest is created:
+
−  rank = ranker.Ranker.Create([0, 10000, -999999, 1], 100)
+
−  # In our contest, people won't have more than 9999 points or 999999 penalty
+
−  # seconds.  Since penalty time is bad, we store [score, -penalty].
+
−  contest['ranker'] = rank.rootkey
+
−  datastore.Put(contest)
+
−
+
−  STEP 2:
+
−  # Someone registers for the contest.  The default score is [0, 0], and for
+
−  # efficiency we don't put them in the ranker; they won't be ahead of anyone
+
−  # anyway.
+
−
+
−  STEP 3:
+
−  # Player "Jon" gets points for the first time!
+
−  rank = ranker.Ranker(contest['ranker'])
+
−  # Loads up the ranker.  This is the first step of all the STEPs below.
+
−  rank.SetScore("Jon", [5, -120])  # 5 points, 2 minutes
+
−
+
−  STEP 4:
+
−  # Player "Jon" gets points for the second time!
+
−  rank.SetScore("Jon", [10, -300])  # 10 points, 5 minutes
+
−
+
−  STEP 5:
+
−  # What is the rank of the person with score [10, -300]?
+
−  position = rank.FindRank([10, 300])
+
−  # What are the ranks for the people with scores a, b, c?
+
−  positions = rank.FindRanks([a, b, c])
+
−
+
−  STEP 6:
+
−  # What is the score of the person ranked 20th?
+
−  score = rank.FindScore(19)
+
−  # This is particularly useful for seeing multiple pages of ranked people.  If
+
−  # the scores are separately tracked in an entity called 'scores', the
+
−  # datastore can efficiently answer:
+
−  # q = datastore.Query('scores')
+
−  # q['score <='] = rank.FindScore(1000)[0]
+
−  # next_twenty_scores = q.Get(20)
+
−  # This is a simplified case, where scores are a single integer.
+
−
+
−  STEP 7:
+
−  # How many people have points?
+
−  num_pointy_people = rank.TotalRankedScores()
+
−
+
−
+
−
+
−  Implementation Details:
+
−
+
−  The Ranker is a rooted tree of 'ranker_node' entities.  It is an
+
−  N-ary tree, where N = self.branching_factor, which is specified by the
+
−  constructor.  Each node represents some range of scores, and is assigned a
+
−  unique node_id.
+
−
+
−  Take for example a 3-ary tree with point range [0, 10000, -36000, 1].  This
+
−  could represent a contest where contestants can have between 0 and 9999
+
−  points, with ties being broken by (negative) penalty seconds that can be
+
−  between 0 and 10 hours.
+
−
+
−  The root represents the score range [0, 10000, -36000, 1].  It has node_id 0.
+
−  Its first child has node_id 1 and score range [0, 3333, -36000, 1].
+
−  The root's second child, node_id 2, has score range [3333, 6666, -36000, 1],
+
−  and its third child, node_id 3, has score range [6666, 10000, -36000, 1].
+
−  Node 1's first child, node_id 4, has range [0, 1111, -36000, 1], and so on.
+
−  See __WhichChild for details of how children are assigned score ranges.
+
−
+
−  The point of a node is to track how many stored scores are in the score range
+
−  of each of its children.  The root in the above example would start off with
+
−  child_node_counts = [0, 0, 0]; adding score [4000, 0] would change the root's
+
−  child_node_counts to [0, 1, 0] and node 5's child_node_counts to [1, 0, 0],
+
−  and so forth.
+
−
+
−  Ranker also has a "ranker_score" entity for every score stored in the ranker.
+
−  These entities are part of the same entity group as the ranker_node
+
−  entities. This allows for atomic, idempotent calls to SetScores.
+
−
+
−  Ranker supports the following operations, which can be read about in detail
+
−  in their docstrings:
+
−
+
−  SetScores(scores): Set scores for multiple players.
+
−  FindRank(score): Finds the 0-based rank of the provided score.
+
−  FindScore(rank): Finds the score with the provided 0-based rank.
+
−  FindScoreApproximate(rank): Finds a score >= the score of the provided 0-based
+
−    rank, < the score of rank-1 (unless rank and rank-1 are tied, in which case
+
−    it returns their mutual score).
+
−  TotalRankedScores: The total number of scores in the Ranker.
+
−
+
−  See __FindNodeIDs for more notes on structure.
+
−
+
−  """
+
−
+
−  def __init__(self, rootkey):
+
−    """Pulls a ranker out of the datastore, given the key of the root node.
+
−
+
−    Args:
+
−      rootkey: The datastore key of the ranker.
+
−    """
+
−    # Get the root from the datastore:
+
−    assert rootkey.kind() == "ranker"
+
−    root = datastore.Get(rootkey)
+
−    # Initialize some class variables:
+
−    self.rootkey = rootkey
+
−    self.score_range = root["score_range"]
+
−    self.branching_factor = root["branching_factor"]
+
−    # Sanity checking:
+
−    assert len(self.score_range) > 1
+
−    assert len(self.score_range) % 2 == 0
+
−    for i in xrange(0, len(self.score_range), 2):
+
−      assert self.score_range[i + 1] > self.score_range[i]
+
−    assert self.branching_factor > 1
+
−
+
−  @classmethod
+
−  def Create(cls, score_range, branching_factor):
+
−    """Constructs a new Ranker and returns it.
+
−
+
−    Args:
+
−      score_range: A list showing the range of valid scores, in the form:
+
−        [most_significant_score_min, most_significant_score_max,
+
−         less_significant_score_min, less_significant_score_max, ...]
+
−        Ranges are [inclusive, exclusive)
+
−      branching_factor: The branching factor of the tree.  The number of
+
−        datastore Gets is Theta(1/log(branching_factor)), and the amount of data
+
−        returned by each Get is Theta(branching_factor).
+
−
+
−    Returns:
+
−      A new Ranker.
+
−    """
+
−    # Put the root in the datastore:
+
−    root = datastore.Entity("ranker")
+
−    root["score_range"] = score_range
+
−    root["branching_factor"] = branching_factor
+
−    datastore.Put(root)
+
−    myrank = Ranker(root.key())
+
−    return myrank
+
−
+
−  def __FindNodeIDs(self, score):
+
−    """Finds the nodes along the path from the root to a certain score.
+
−
+
−    Args:
+
−      score: The score we're finding the path for.
+
−
+
−    Returns:
+
−      A sorted list of (node_id, child) tuples, indicating that node_id is the
+
−      node id of a node on the path, and child is which child of that node is
+
−      next.  Note that the lowest child node (which would be a leaf node) does
+
−      not actually exist, since all its relevant information (number of times
+
−      that score was inserted) is stored in its parent.
+
−
+
−    Nodes are numbered row-by-row: the root is 0, its children are in the range
+
−    [1, self.branching_factor + 1), its grandchildren are in the range
+
−    [self.branching_factor + 1,
+
−     self.branching_factor**2 + self.branching_factor + 1), etc.
+
−
+
−    Score ranges are lists of the form: [min_0, max_0, min_1, max_1, ...]
+
−    A node representing a score range will be divided up by the first index
+
−    where max_i != min_i + 1 (score ranges are [inclusive, exclusive)).
+
−
+
−    Child x (0-indexed) of a node [a,b) will get the range:
+
−    [a+x*(b-a)/branching_factor, a+(x+1)*(b-a)/branching_factor);
+
−    Thus not all nodes will have nonzero ranges.  Nodes with zero range will
+
−    never be visited, but they and their descendants will be counted in the node
+
−    numbering scheme, so row x still has self.branching_factor**x nodes.
+
−    """
+
−    nodes = []
+
−    node = 0
+
−    cur_range = list(self.score_range)
+
−    # The current range of scores.  This will be narrowed as we move down the
+
−    # tree; 'index' keeps track of the score type we're currently changing.
+
−    for index in xrange(0, len(cur_range), 2):
+
−      while cur_range[index + 1] - cur_range[index] > 1:
+
−        # Subdivide cur_range[index]..cur_range[index + 1]
+
−        which_child = self.__WhichChild(cur_range[index],
+
−                                        cur_range[index + 1],
+
−                                        score[index // 2],
+
−                                        self.branching_factor)
+
−        child = which_child[0]
+
−        cur_range[index] = which_child[1][0]
+
−        cur_range[index + 1] = which_child[1][1]
+
−        assert 0 <= child < self.branching_factor
+
−        nodes.append((node, child))
+
−        node = self.__ChildNodeId(node, child)
+
−    return nodes
+
−
+
−  def __WhichChild(self, low, high, want, branching_factor):
+
−    """Determines which child of the range [low, high) 'want' belongs to.
+
−
+
−    Args:
+
−      low: An int, the low end of the range.
+
−      high: An int, the high end of the range.
+
−      want: An int, the score we're trying to determine a child for.
+
−      branching_factor: The branching factor of the tree being used.
+
−
+
−    Returns:
+
−      A tuple, (child, [child's score range]).  Note that in general a score
+
−      has multiple sub-scores, written in order of decreasing significance; this
+
−      function divides up a single sub-score.
+
−
+
−    Raises:
+
−      An AssertionError if things go horribly wrong.
+
−    """
+
−    assert low <= want < high
+
−    # Need to find x such that (using integer division):
+
−    #     x  *(high-low)/branching_factor <= want - low <
+
−    #   (x+1)*(high-low)/branching_factor
+
−    # Which is the least x such that (using integer division):
+
−    #   want - low < (x+1)*(high-low)/branching_factor
+
−    # Which is the ceiling of x such that (using floating point division):
+
−    #   want - low + 1 == (x+1)*(high-low)/branching_factor
+
−    #   x = -1 + math.ceil((want-low+1) * branching_factor / (high - low))
+
−    # We get ceil by adding high - low - 1 to the numerator.
+
−    x = -1 + (((want - low + 1) * branching_factor + high - low - 1) //
+
−              (high - low))
+
−    assert (x * (high - low) // branching_factor <=
+
−            want - low < (x + 1) * (high - low) // branching_factor)
+
−    return (x, self.__ChildScoreRange([low, high], x, branching_factor))
+
−
+
−  def __ChildScoreRange(self, score_range, child, branching_factor):
+
−    """Calculates the score_range for a node's child.
+
−
+
−    Args:
+
−      score_range: A score range [min0, max0, min1, max1, ...]
+
−      child: Which child of the node with score range score_range we're
+
−        calculating the score range of.
+
−      branching_factor: The branching factor of the tree in question.
+
−
+
−    Returns:
+
−      A score range [min0', max0', min1', max1', ...] for that child.
+
−    """
+
−    for i in xrange(1, len(score_range), 2):
+
−      if score_range[i] > score_range[i - 1] + 1:
+
−        child_score_range = list(score_range)
+
−        low, high = score_range[i - 1], score_range[i]
+
−        child_score_range[i - 1], child_score_range[i] = (
+
−            low + child * (high - low) // branching_factor,
+
−            low + (child + 1) * (high - low) // branching_factor)
+
−        return child_score_range
+
−    raise AssertionError("Node with score range %s has no children." %
+
−                         score_range)
+
−
+
−  def __ChildNodeId(self, node_id, child):
+
−    """Calculates the node id for a known node id's child.
+
−
+
−    Args:
+
−      node_id: The parent node's node_id
+
−      child: Which child of the parent node we're finding the id for
+
−
+
−    Returns:
+
−      The node_id for the child'th child of node_id.
+
−    """
+
−    return node_id * self.branching_factor + 1 + child
+
−
+
−  def __GetMultipleNodes(self, node_ids):
+
−    """Gets multiple nodes from the datastore.
+
−
+
−    Args:
+
−      node_ids: A list of node ids we want to get.
+
−
+
−    Returns:
+
−      A dict of the nodes that were found, indexed by the node ids found
+
−      in node_ids.
+
−    """
+
−    if len(node_ids) == 0:
+
−      return []
+
−    node_ids = set(node_ids)
+
−    keys = [self.__KeyFromNodeId(node_id) for node_id in node_ids]
+
−    nodes = datastore.Get(keys)
+
−    return dict((node_id, node) for (node_id, node) in zip(node_ids, nodes)
+
−                if node)
+
−
+
−  # Although, this method is currently not needed, we'll keep this
+
−  # since we might need it and some point and it's an interesting
+
−  # relationship
+
−  def __ParentNode(self, node_id):
+
−    """Returns the node id of the parameter node id's parent.  Returns None if
+
−    the parameter is 0."""
+
−    if node_id == 0:
+
−      return None
+
−    return (node_id - 1) // self.branching_factor
+
−
+
−  def __KeyFromNodeId(self, node_id):
+
−    """Creates a (named) key for the node with a given id.
+
−
+
−    The key will have the ranker as a parent element to guarantee
+
−    uniqueness (in the presence of multiple rankers) and to put all
+
−    nodes in a single entity group.
+
−
+
−    Args:
+
−      node_id: The node's id as an integer.
+
−
+
−    Returns:
+
−      A (named) key for the node with the id 'node_id'.
+
−    """
+
−    name = "node_%x" % node_id
+
−    return datastore_types.Key.from_path("ranker_node", name,
+
−                                         parent=self.rootkey)
+
−
+
−  def __KeyForScore(self, name):
+
−    """Returns a (named) key for a ranker_score entity.
+
−
+
−    Args:
+
−      name: Name of the score to create a key for.
+
−
+
−    Returns:
+
−      A (named) key for the entity storing the score of 'name'.
+
−    """
+
−    return datastore_types.Key.from_path("ranker_score", name,
+
−                                         parent=self.rootkey)
+
−
+
−  def __Increment(self, nodes_with_children, score_entities,
+
−                  score_entities_to_delete):
+
−    """Changes child counts for given nodes.
+
−
+
−    This method will create nodes as needed.
+
−
+
−    Args:
+
−      nodes_with_children: A dict of (node_key, child) tuples to deltas
+
−      score_entities: Additional score entities to persist as part of
+
−        this transaction
+
−    Returns:
+
−      None
+
−    """
+
−    keys = list(set(key for ((key, _), delta) in nodes_with_children.iteritems()
+
−                    if delta != 0))
+
−    if not keys:
+
−      return  # Nothing to do
+
−    nodes = datastore.Get(keys)
+
−
+
−    node_dict = {}
+
−    for (key, node) in zip(keys, nodes):
+
−      if not node:
+
−        node = datastore.Entity("ranker_node", parent=self.rootkey,
+
−                                name=key.name())
+
−        node["child_counts"] = [0] * self.branching_factor
+
−      node_dict[key] = node
+
−    for ((key, child), amount) in nodes_with_children.iteritems():
+
−      if amount != 0:
+
−        node = node_dict[key]
+
−        node["child_counts"][child] += amount
+
−        assert node["child_counts"][child] >= 0
+
−    datastore.Put(node_dict.values() + score_entities)
+
−    if score_entities_to_delete:
+
−      datastore.Delete(score_entities_to_delete)
+
−
+
−  def SetScore(self, name, score):
+
−    """Sets a single score.
+
−
+
−    This is equivalent to calling 'SetScores({name: score})'
+
−
+
−    Args:
+
−      name: the name of the score as a string
+
−      score: the score to set name to
+
−    """
+
−    return self.SetScores({name: score})
+
−
+
−  @transactional
+
−  def SetScores(self, scores):
+
−    """Changes multiple scores atomically.
+
−
+
−    Sets the scores of the named entities in scores to new values. For
+
−    named entities that have not been registered with a score before,
+
−    a new score is created. For named entities that already had a score,
+
−    the score is changed to reflect the new score. If a score is None,
+
−    the named entity's score will be removed from the ranker.
+
−
+
−    Args:
+
−      scores: A dict mapping entity names (strings) to scores (integer lists)
+
−    """
+
−    score_deltas, score_ents, score_ents_del = self.__ComputeScoreDeltas(scores)
+
−    node_ids_to_deltas = self.__ComputeNodeModifications(score_deltas)
+
−    self.__Increment(node_ids_to_deltas, score_ents, score_ents_del)
+
−
+
−  def __ComputeScoreDeltas(self, scores):
+
−    """Compute which scores have to be incremented and decremented.
+
−
+
−    Args:
+
−      scores: A dict mapping entity names to scores
+
−
+
−    Returns:
+
−      A tuple (score_deltas, score_entities, score_entities_to_delete).
+
−
+
−      'score_deltas' is a dict, mapping scores (represented as tuples)
+
−      to integers. 'score_deltas[s]' represents how many times the
+
−      score 's' has to be incremented (or decremented).
+
−
+
−      'score_entities' is a list of 'ranker_score' entities that have
+
−      to be updated in the same transaction as modifying the ranker
+
−      nodes. The entities already contain the updated score.
+
−
+
−      Similarly, 'score_entities_to_delete' is a list of entities that
+
−      have to be deleted in the same transaction as modifying the ranker
+
−      nodes.
+
−    """
+
−    score_keys = [self.__KeyForScore(score) for score in scores]
+
−    old_scores = {}
+
−    for old_score in datastore.Get(score_keys):
+
−      if old_score:
+
−        old_scores[old_score.key().name()] = old_score
+
−    score_deltas = {}
+
−    # Score entities to update
+
−    score_ents = []
+
−    score_ents_del = []
+
−    for score_name, score_value in scores.iteritems():
+
−      if score_name in old_scores:
+
−        score_ent = old_scores[score_name]
+
−        if score_ent["value"] == score_value:
+
−          continue  # No change in score => nothing to do
+
−        old_score_key = tuple(score_ent["value"])
+
−        score_deltas.setdefault(old_score_key, 0)
+
−        score_deltas[old_score_key] -= 1
+
−      else:
+
−        score_ent = datastore.Entity("ranker_score", parent=self.rootkey,
+
−                                     name=score_name)
+
−      if score_value:
+
−        score_key = tuple(score_value)
+
−        score_deltas.setdefault(score_key, 0)
+
−        score_deltas[score_key] += 1
+
−        score_ent["value"] = score_value
+
−        score_ents.append(score_ent)
+
−      else:
+
−        # Do we have to delete an old score entity?
+
−        if score_name in old_scores:
+
−          score_ents_del.append(old_scores[score_name])
+
−
+
−    return (score_deltas, score_ents, score_ents_del)
+
−
+
−  def __ComputeNodeModifications(self, score_deltas):
+
−    """Computes modifications to ranker nodes.
+
−
+
−    Given score deltas, computes which nodes need to be modified and by
+
−    how much their child count has to be incremented / decremented.
+
−
+
−    Args:
+
−      score_deltas: A dict of scores to integers, as returned by
+
−        _ComputeScoreDeltas.
+
−
+
−    Returns:
+
−      A dict of nodes (represented as node_key, child tuples) to integers.
+
−      'result[(node_key, i)]' represents the amount that needs to be added to
+
−      the i-th child of node node_key.
+
−    """
+
−    nodes_to_deltas = {}
+
−    for score, delta in score_deltas.iteritems():
+
−      for (node_id, child) in self.__FindNodeIDs(score):
+
−        node = (self.__KeyFromNodeId(node_id), child)
+
−        nodes_to_deltas[node] = nodes_to_deltas.get(node, 0) + delta
+
−    return nodes_to_deltas
+
−
+
−  def __FindRank(self, node_ids_with_children, nodes):
+
−    """Utility function.  Finds the rank of a score.
+
−
+
−    Args:
+
−      node_ids_with_children: A list of node ids down to that score,
+
−        paired with which child links to follow.
+
−      nodes: A dict mapping node id to node entity.
+
−
+
−    Returns:
+
−      The score's rank.
+
−    """
+
−    tot = 0  # Counts the number of higher scores.
+
−    for (node_id, child) in node_ids_with_children:
+
−      if node_id in nodes:
+
−        node = nodes[node_id]
+
−        for i in xrange(child + 1, self.branching_factor):
+
−          tot += node["child_counts"][i]
+
−      else:
+
−        # If the node isn't in the dict, the node simply doesn't exist.  We
+
−        # are probably finding the rank for a score that doesn't appear in the
+
−        # ranker, but that's perfectly fine.
+
−        pass
+
−    return tot
+
−
+
−  def FindRank(self, score):
+
−    """Finds the 0-based rank of a particular score; more precisely, returns the
+
−    number of strictly higher scores stored.
+
−
+
−    Args:
+
−      score: The score whose rank we wish to find.
+
−
+
−    Returns:
+
−      The number of tracked scores that are higher.  Does not check whether
+
−      anyone actually has the requested score.
+
−    """
+
−    return self.FindRanks([score])[0]
+
−
+
−  def FindRanks(self, scores):
+
−    """Finds the 0-based ranks of a number of particular scores.
+
−    Like FindRank, but more efficient for multiple scores.
+
−
+
−    Args:
+
−      scores: A list of scores.
+
−
+
−    Returns:
+
−      A list of ranks.
+
−    """
+
−    for score in scores:
+
−      assert len(score) * 2 == len(self.score_range)
+
−    # Find the nodes we'll need to query to find information about these scores:
+
−    node_ids_with_children_list = [self.__FindNodeIDs(score)
+
−                                   for score in scores]
+
−    node_ids = []
+
−    for node_ids_with_children in node_ids_with_children_list:
+
−      node_ids += [node_id for (node_id, _) in node_ids_with_children]
+
−    # Query the needed nodes:
+
−    nodes_dict = self.__GetMultipleNodes(node_ids)
+
−    # Call __FindRank, which does the math, for each score:
+
−    return [self.__FindRank(node_ids_with_children, nodes_dict) for
+
−            node_ids_with_children in node_ids_with_children_list]
+
−
+
−  def __FindScore(self, node_id, rank, score_range, approximate):
+
−    """To be run in a transaction.  Finds the score ranked 'rank' in the subtree
+
−    defined by node 'nodekey.'
+
−
+
−    Args:
+
−      node_id: The id of the node whose subtree we wish to find the
+
−        score of rank 'rank' in.
+
−      rank: The rank (within this subtree) of the score we wish to find.
+
−      score_range: The score range for this particular node, as a list.
+
−        Derivable from the node's node_id, but included for convenience.
+
−      approximate: Do we have to return an approximate result, or an exact one?
+
−        See the docstrings for FindScore and FindScoreApproximate.
+
−
+
−    Returns:
+
−      A tuple, (score, rank_of_tie), indicating the score's rank within
+
−      node_id's subtree.  The way it indicates rank is defined in the dosctrings
+
−      of FindScore and FindScoreApproximate, depending on the value of
+
−      'approximate'.
+
−    """
+
−    # If we're approximating and thus allowed to do so, early-out if we just
+
−    # need to return the highest available score.
+
−    if approximate and rank == 0:
+
−      return ([score - 1 for score in score_range[1::2]], 0)
+
−    # Find the current node.
+
−    node = datastore.Get(self.__KeyFromNodeId(node_id))
+
−    child_counts = node["child_counts"]
+
−    initial_rank = rank
+
−    for i in xrange(self.branching_factor - 1, -1, -1):
+
−      # If this child has enough scores that rank 'rank' is in
+
−      # there, recurse.
+
−      if rank - child_counts[i] < 0:
+
−        child_score_range = self.__ChildScoreRange(score_range, i,
+
−                                                   self.branching_factor)
+
−        if self.__IsSingletonRange(child_score_range):
+
−          # Base case; child_score_range refers to a single score. We don't
+
−          # store leaf nodes so we can return right here.
+
−          return (child_score_range[0::2], initial_rank - rank)
+
−        # Not a base case.  Keep descending into children.
+
−        ans = self.__FindScore(self.__ChildNodeId(node_id, i), rank,
+
−                               child_score_range,
+
−                               approximate)
+
−        # Note the 'initial_rank - rank': we've asked the child for a score of
+
−        # some rank among *its* children, so we have to add back in the scores
+
−        # discarded on the way to that child.
+
−        return (ans[0], ans[1] + (initial_rank - rank))
+
−      else:
+
−        rank -= child_counts[i]
+
−    return None
+
−
+
−  def __IsSingletonRange(self, scorerange):
+
−    """Returns whether a range contains exactly one score."""
+
−    return [score + 1 for score in scorerange[0::2]] == scorerange[1::2]
+
−
+
−  @transactional
+
−  def FindScore(self, rank):
+
−    """Finds the score ranked at 'rank'.
+
−
+
−    Args:
+
−      rank: The rank of the score we wish to find.
+
−
+
−    Returns:
+
−      A tuple, (score, rank_of_tie).  'score' is the score ranked at 'rank',
+
−      'rank_of_tie' is the rank of that score (which may be different from
+
−      'rank' in the case of ties).
+
−      e.g. if there are two scores tied at 5th and rank == 6, returns
+
−      (score, 5).
+
−    """
+
−    return self.__FindScore(0, rank, self.score_range, False)
+
−
+
−  @transactional
+
−  def FindScoreApproximate(self, rank):
+
−    """Finds a score that >= the score ranked at 'rank'.
+
−
+
−    This method could be preferred to FindScore because it is more efficient.
+
−    For example, if the objective is to find the top 50 scores of rank X or
+
−    less, and those scores are stored in entities called scoreboard_row:
+
−      score, rank = myrank.FindScoreApproximate(X)
+
−      query = datastore.Query('scoreboard_row')
+
−      query['score <='] = score
+
−      result = query.Get(50 + X - rank)[X-rank:])  # Takes care of ties.
+
−
+
−    Args:
+
−      rank: The rank of the score we wish to find.
+
−
+
−    Returns:
+
−      A tuple, (score, rank_of_tie).
+
−      If there is a tie at rank 'rank-1':
+
−        rank's score <= score < rank-1's score, rank_of_tie == rank
+
−      else:
+
−        score == rank's score, rank_of_tie == the tied rank of everyone
+
−        in the tie.
+
−        e.g. if two scores are tied at 5th and rank == 6, returns (score, 5).
+
−    """
+
−    return self.__FindScore(0, rank, self.score_range, True)
+
−
+
−  def TotalRankedScores(self):
+
−    """Returns the total number of ranked scores.
+
−
+
−    Returns:
+
−      The total number of ranked scores.
+
−    """
+
−    root = datastore.Get([self.__KeyFromNodeId(0)])[0]
+
−    if root:
+
−      return sum(root["child_counts"])
+
−    else:
+
−      # Ranker doesn't have any ranked scores, yet
+
−      return 0