author | Lennard de Rijk <ljvderijk@gmail.com> |
Sat, 04 Jul 2009 14:19:39 +0200 | |
changeset 2528 | 9de8348890d8 |
parent 1597 | e7b7ea113a3b |
permissions | -rwxr-xr-x |
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 |