Java Implementation

[John]

I made a java implementation to the ranker and to my knowledge it
works perfectly fine. I thought I would share it with the rest of
you. I made a few slight modifications to creating it and calling it
that you all should know:

To create a ranker, you do:
String rankerKey = new Ranker().Create("MyRanker", scoreRange,
branchingFactor).getKeyString(); where scoreRange is an Integer
ArrayList of four elements.

To call a ranker, you do:
new Ranker(rankerKey);

To set a score, you do:
new Ranker(rankerKey).SetScore(someId, new Score_Tuple(score,
penalty));

Enjoy! (If you want some more info on it, I made a quick little post
about it here: http://goo.gl/cTN5u )

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import org.mortbay.log.Log;

import com.google.appengine.api.datastore.DatastoreService;
import com.google.appengine.api.datastore.DatastoreServiceFactory;
import com.google.appengine.api.datastore.Entity;
import com.google.appengine.api.datastore.EntityNotFoundException;
import com.google.appengine.api.datastore.Key;
import com.google.appengine.api.datastore.KeyFactory;

@SuppressWarnings("unchecked")
public class Ranker
{

// Class variables
private DatastoreService datastore =
DatastoreServiceFactory.getDatastoreService();
private Key rootkey;
private ArrayList<Long> score_range = new ArrayList<Long>();
private long branching_factor;

// 0-argument constructor for Java
public Ranker()
{

}

/**
* Pulls a ranker out of the datastore, given the key of the root
node.
*
* @throws EntityNotFoundException
*
* @param rootkey
* The datastore key of the ranker.
*/
// @SuppressWarnings("unchecked")
public Ranker(String rootkey) throws EntityNotFoundException
{
Entity root;
root = datastore.get(KeyFactory.stringToKey(rootkey));
// Initialize some class variables
this.rootkey = KeyFactory.stringToKey(rootkey);
// Need to convert arrayList of Longs to Integers
this.score_range = (ArrayList<Long>)
root.getProperty("score_range");
this.branching_factor = (Long) root.getProperty("branching_factor");
// Sanity checking
assert this.score_range.size() > 1;
assert this.score_range.size() % 2 == 0;
for (int i = 0; i < this.score_range.size(); i = i + 2)
assert this.score_range.get(i + 1) > this.score_range.get(i);
assert this.branching_factor > 1;
}

/**
* Constructs a new Ranker and returns it.
*
* @param score_range
* A list showing the range of valid scores, in the form:
* [most_significant_score_min,
most_significant_score_max,
* less_significant_score_min,
less_significant_score_max, ...]
* Ranges are [inclusive, exclusive)
* @param branching_factor
* The branching factor of the tree. The number of
datastore Gets
* is Theta(1/log(branching_factor)), and the amount of
data
* returned by each Get is Theta(branching_factor).
* @return
* @throws EntityNotFoundException
*/
public Ranker Create(String rankerName, ArrayList<Integer>
score_range, int branching_factor) throws EntityNotFoundException
{
Entity root = new Entity(rankerName);
root.setProperty("score_range", score_range);
root.setProperty("branching_factor", branching_factor);
datastore.put(root);
return new Ranker(KeyFactory.keyToString(root.getKey()));
}

public String getKeyString()
{
return KeyFactory.keyToString(this.rootkey);
}


/**
* Finds the nodes along the path from the root to a certain score.
*
* Nodes are numbered row-by-row: the root is 0, its children are in
the
* range [1, self.branching_factor + 1), its grandchildren are in the
range
* [self.branching_factor + 1, self.branching_factor**2 +
* self.branching_factor + 1), etc.
*
* Score ranges are lists of the form: [min_0, max_0, min_1,
max_1, ...] A
* node representing a score range will be divided up by the first
index
* where max_i != min_i + 1 (score ranges are [inclusive,
exclusive)).
*
* Child x (0-indexed) of a node [a,b) will get the range:
* [a+x*(b-a)/branching_factor, a+(x+1)*(b-a)/branching_factor); Thus
not
* all nodes will have nonzero ranges. Nodes with zero range will
never be
* visited, but they and their descendants will be counted in the
node
* numbering scheme, so row x still has self.branching_factor**x
nodes.
*
* @param score
* The score we're finding the path for.
* @return A sorted list of (node_id, child) tuples, indicating that
node_id
* is the node id of a node on the path, and child is which
child of
* that node is next. Note that the lowest child node (which
would
* be a leaf node) does not actually exist, since all its
relevant
* information (number of times that score was inserted) is
stored
* in its parent.
*/
public ArrayList<NodeID_Child_Tuple> FindNodeIDs(Score_Tuple score)
throws Exception
{
ArrayList<NodeID_Child_Tuple> nodes = new
ArrayList<NodeID_Child_Tuple>();
long node = 0;

ArrayList<Long> cur_range = new ArrayList<Long>();
for (Iterator<Long> iter = this.score_range.iterator();
iter.hasNext();)
{
cur_range.add(iter.next());
}

Child_ChildScoreRange_Tuple which_child;
long child;

// The current range of scores. This will be narrowed as we move
down
// the tree; 'index' keeps track of the score type we're currently
// changing.
for (int i = 0; i < cur_range.size(); i += 2)
{
while (cur_range.get(i + 1) - cur_range.get(i) > 1)
{
// Subdivide cur_range[index]..cur_range[index + 1]
which_child = WhichChild(cur_range.get(i), cur_range.get(i + 1),
score.getByIndex(i / 2), this.branching_factor);
child = which_child.getChild();
cur_range.set(i, which_child.getChildScoreRange().get(0));
cur_range.set(i + 1, which_child.getChildScoreRange().get(1));
assert 0 <= child;
assert child < this.branching_factor;
nodes.add(new NodeID_Child_Tuple(node, child));
node = ChildNodeId(node, child);
}
}

return nodes;
}

/**
* Determines which child of the range [low, high) 'want' belongs to.
*
* @param loow
* An int, the low end of the range.
* @param high
* An int, the high end of the range.
* @param want
* An int, the score we're trying to determine a child
for.
* @param branching_factor
* The branching factor of the tree being used.
*
* @return A tuple, (child, [child's score range]). Note that in
general a
* score has multiple sub-scores, written in order of
decreasing
* significance; this function divides up a single sub-score.
* @throws Exception
*/
private Child_ChildScoreRange_Tuple WhichChild(Long low, Long high,
int want, Long branching_factor) throws Exception
{
long x;

assert low <= want;
assert want < high;

/*
* Need to find x such that (using integer division): x
* *(high-low)/branching_factor <= want - low <
* (x+1)*(high-low)/branching_factor Which is the least x such that
* (using integer division): want - low <
* (x+1)*(high-low)/branching_factor Which is the ceiling of x such
that
* (using floating point division): want - low + 1 ==
* (x+1)*(high-low)/branching_factor x = -1 + math.ceil((want-low+1)
*
* branching_factor / (high - low)) We get ceil by adding high - low
- 1
* to the numerator.
*/

x = -1 + (((want - low + 1) * branching_factor + high - low - 1) /
(high - low));

assert (x * (high - low) / branching_factor <= want - low);
assert (want - low < (x + 1) * (high - low) / branching_factor);

ArrayList<Long> score_range = new ArrayList<Long>();
score_range.add(low);
score_range.add(high);
return new Child_ChildScoreRange_Tuple(x,
ChildScoreRange(score_range, x, branching_factor));
}

/**
* Calculates the score_range for a node's child.
*
* @param score_range
* A score range [min0, max0, min1, max1, ...]
* @param x
* Which child of the node with score range score_range
we're
* calculating the score range of.
* @param branching_factor2
* The branching factor of the tree in question.
* @return A score range [min0', max0', min1', max1', ...] for that
child.
* @throws Exception
*/
private ArrayList<Long> ChildScoreRange(ArrayList<Long> score_range,
long child, long branching_factor) throws Exception
{
ArrayList<Long> child_score_range = new ArrayList<Long>();
long low;
long high;

for (int i = 1; i < score_range.size(); i = i + 2)
{
if (score_range.get(i) > score_range.get(i - 1) + 1)
{
// child_score_range = score_range.clone();
for (Iterator<Long> iter = score_range.iterator();
iter.hasNext();)
child_score_range.add(iter.next());
low = score_range.get(i - 1);
high = score_range.get(i);
child_score_range.set(i - 1, (low + child * (high - low) /
branching_factor));
child_score_range.set(i, (low + (child + 1) * (high - low) /
branching_factor));
return child_score_range;
}
}
throw new Exception("Node with score range " + score_range + " has
no children.");
}

/**
* Calculates the node id for a known node id's child.
*
* @param node
* The parent node's node_id
* @param child
* Which child of the parent node we're finding the id for
* @return The node_id for the child'th child of node_id.
*/
private long ChildNodeId(long node, long child)
{
return node * this.branching_factor + 1 + child;
}

public Map<Long, Entity> GetMultipleNodes(ArrayList<Long> node_ids)
{
ArrayList<Key> keys = new ArrayList<Key>();
Map<Key, Entity> nodes;

Map<Long, Entity> dict = new HashMap<Long, Entity>();

if (node_ids.size() == 0)
return new HashMap<Long, Entity>();

// Remove dupes, preserve insertion order
Set<Long> set = new LinkedHashSet<Long>(node_ids);
for (Iterator<Long> iter = set.iterator(); iter.hasNext();)
keys.add(KeyFromNodeId(iter.next()));

nodes = datastore.get(keys);

int i = 0;
for (Iterator<Long> iter = set.iterator(); iter.hasNext();)
{
dict.put(iter.next(), nodes.get(keys.get(i)));
i++;
}
return dict;
}

// # Although, this method is currently not needed, we'll keep this
since we
// might need it and some point and it's an interesting relationship
/**
*
* @param node_id
* @return The node id of the parameter node id's parent. Returns -1
if the
* parameter is 0.
*/
@SuppressWarnings("unused")
private long ParentNode(int node_id)
{
if (node_id == 0)
return -1;
return (node_id - 1) / this.branching_factor;
}

/**
* Creates a (named) key for the node with a given id.
*
* The key will have the ranker as a parent element to guarantee
uniqueness
* (in the presence of multiple rankers) and to put all nodess in a
single
* entity group.
*
* @param node_id
* The node's id as an integer.
*
* @return A (named) key for the node with the id 'node_id'.
*/
private Key KeyFromNodeId(long node_id)
{
String name = "node_" + Long.toString(node_id);
return KeyFactory.createKey(this.rootkey, "ranker_node", name);
}

/**
* Returns a (named) key for a ranker_score entity.
*
* @param name
* Name of the score to create a key for.
* @return A (named) key for the entity storing the score of 'name'.
*/
private Key KeyForScore(String name)
{
return KeyFactory.createKey(this.rootkey, "ranker_score", name);
}

/**
* """Changes child counts for given nodes. This method will create
nodes as
* needed.
*
* @param node_ids_to_deltas
* A dict of (node_key, child) tuples to deltas
* @param score_entities
* Additional score entities to persist as part of this
* transaction
* @param score_entities_to_delete
* Additional score entities to delete as part of this
* transaction
*/
private void Increment(HashMap<Key_Child_Tuple, Integer>
node_ids_to_deltas, ArrayList<Entity> score_entities,
ArrayList<Entity> score_entities_to_delete)
{
ArrayList<Key> keys = new ArrayList<Key>();
Key_Child_Tuple tuple;
Map<Key, Entity> nodes;
Map<Key, Entity> node_dict = new HashMap<Key, Entity>();
Entity node;

for (Iterator<Key_Child_Tuple> iter =
node_ids_to_deltas.keySet().iterator(); iter.hasNext();)
{
tuple = iter.next();
if (node_ids_to_deltas.get(tuple) != 0)
{
keys.add((Key) tuple.getKey());
}
}

if (keys.isEmpty())
return;

nodes = datastore.get(keys);

for (int i = 0; i < keys.size(); i++)
{
if (!nodes.containsKey(keys.get(i)))
{
node = new Entity("ranker_node", keys.get(i).getName(),
this.rootkey);

ArrayList<Long> branchingList = new ArrayList<Long>();
for (int j = 0; j < this.branching_factor; j++)
branchingList.add((long) 0);
node.setProperty("child_counts", branchingList);
}

else
{
node = nodes.get(keys.get(i));
}

node_dict.put(keys.get(i), node);
}

for (Iterator<Key_Child_Tuple> iter =
node_ids_to_deltas.keySet().iterator(); iter.hasNext();)
{
tuple = iter.next();
int amount = node_ids_to_deltas.get(tuple);
if (amount != 0)
{
ArrayList<Long> child_counts = new ArrayList<Long>();
node = node_dict.get(tuple.getKey());

child_counts = ((ArrayList<Long>)
node.getProperty("child_counts"));
Long a = child_counts.get((int) tuple.getChild());
a += amount;
child_counts.set((int) tuple.getChild(), (long) a);
assert ((ArrayList<Long>)
node.getProperty("child_counts")).get((int) tuple.getChild()) >= 0;
}
}

ArrayList<Entity> entities = new ArrayList<Entity>();
for (Iterator<Entity> entityiter = node_dict.values().iterator();
entityiter.hasNext();)
entities.add(entityiter.next());

entities.addAll(score_entities);
datastore.put(entities);

ArrayList<Key> keyEntitiesToDelete = new ArrayList<Key>();
for (int i = 0; i < score_entities_to_delete.size(); i++)
keyEntitiesToDelete.add(score_entities_to_delete.get(i).getKey());

if (!score_entities_to_delete.isEmpty())
datastore.delete(keyEntitiesToDelete);
}

/**
* Sets a single score. This is equivalent to calling
'SetScores({name:
* score})'
*
* @param name
* the name of the score as a string
* @param score
* the score to set name to
* @return
* @throws Exception
*/
public void SetScore(String name, Score_Tuple score) throws Exception
{
HashMap<String, Score_Tuple> map = new HashMap<String,
Score_Tuple>();
map.put(name, score);
SetScores(map);
}

// Tuple<HashMap<Tuple<String, Integer>, Integer>, ArrayList<Entity>,
// ArrayList<Entity>>

/**
* Changes multiple scores atomically. Sets the scores of the named
entities
* in scores to new values. For named entities that have not been
registered
* with a score before, a new score is created. For named entities
that
* already had a score, the score is changed to reflect the new
score. If a
* score is None, the named entity's score will be removed from the
ranker.
*
* @param scores
* A dict mapping entity names (strings) to scores
(integer
* lists)
* @throws Exception
*/
public void SetScores(HashMap<String, Score_Tuple> scores) throws
Exception
{
ScoreDeltas_ScoreEnts_ScoreEntsDel_Tuple tuple;
Map<Score_Tuple, Integer> score_deltas;
ArrayList<Entity> score_ents;
ArrayList<Entity> score_ents_del;
HashMap<Key_Child_Tuple, Integer> node_ids_to_deltas;

tuple = ComputeScoreDeltas(scores);

score_deltas = (Map<Score_Tuple, Integer>) tuple.getScore_deltas();
score_ents = (ArrayList<Entity>) tuple.getScore_ents();
score_ents_del = (ArrayList<Entity>) tuple.getScore_ents_del();

node_ids_to_deltas = ComputeNodeModifications(score_deltas);

Increment(node_ids_to_deltas, score_ents, score_ents_del);
}

/**
* Compute which scores have to be incremented and decremented.
*
* @param scores
* A dict mapping entity names to scores
* @return ScoreDeltas_ScoreEnts_ScoreEntsDel_Tuple 'score_deltas' is
a
* dict, mapping scores (represented as tuples) to integers.
* 'score_deltas[s]' represents how many times the score 's'
has to
* be incremented (or decremented).
*
* 'score_entities' is a list of 'ranker_score' entities that
have
* to be updated in the same transaction as modifying the
ranker
* nodes. The entities already contain the updated score.
*
* Similarly, 'score_entities_to_delete' is a list of
entities that
* have to be deleted in the same transaction as modifying
the
* ranker nodes.
*/
private ScoreDeltas_ScoreEnts_ScoreEntsDel_Tuple
ComputeScoreDeltas(HashMap<String, Score_Tuple> scores)
{
ArrayList<Key> score_keys = new ArrayList<Key>();
for (Iterator<String> scoreiter = scores.keySet().iterator();
scoreiter.hasNext();)
score_keys.add(KeyForScore(scoreiter.next()));

Map<String, Entity> old_scores = new HashMap<String, Entity>();
for (Iterator<Entity> oldScoresFromDatastoreIter =
datastore.get(score_keys).values().iterator();
oldScoresFromDatastoreIter.hasNext();)
{
Entity old_score = oldScoresFromDatastoreIter.next();
old_scores.put(old_score.getKey().getName(), old_score);
}

HashMap<Score_Tuple, Integer> score_deltas = new
HashMap<Score_Tuple, Integer>();
// Score entities to update
ArrayList<Entity> score_ents = new ArrayList<Entity>();
ArrayList<Entity> score_ents_del = new ArrayList<Entity>();

for (Iterator<Entry<String, Score_Tuple>> scoreiter =
scores.entrySet().iterator(); scoreiter.hasNext();)
{
Entry<String, Score_Tuple> scoreEntry = scoreiter.next();
String score_name = scoreEntry.getKey();
Score_Tuple score_value = scoreEntry.getValue();

Entity score_ent;
Score_Tuple old_score_key;
Score_Tuple score_key;

if (old_scores.containsKey(score_name))
{
score_ent = old_scores.get(score_name);

if (new Score_Tuple((String)
score_ent.getProperty("value")).equals(score_value))
{
continue; // No change in score => nothing to do
}

old_score_key = new Score_Tuple(((String)
score_ent.getProperty("value")));

if (!score_deltas.containsKey(old_score_key))
score_deltas.put(old_score_key, 0);

score_deltas.put(old_score_key, score_deltas.get(old_score_key) -
1);

}

else
{
score_ent = new Entity("ranker_score", score_name, this.rootkey);
}

if (score_value != null) // WARNING: line 453????
{
score_key = new Score_Tuple(score_value.getScore(),
score_value.getScore_time());

if (!score_deltas.containsKey(score_key))
score_deltas.put(score_key, 0);

score_deltas.put(score_key, ((Integer)
score_deltas.get(score_key)) + 1);
score_ent.setProperty("value", score_value.toString());
score_ents.add(score_ent);
}

else
{
// Do we have to delete an old score entity?
if (old_scores.containsKey(score_name))
{
score_ents_del.add(old_scores.get(score_name));
}
}

}

return new ScoreDeltas_ScoreEnts_ScoreEntsDel_Tuple(score_deltas,
score_ents, score_ents_del);
}

/**
* Computes modifications to ranker nodes. Given score deltas,
computes
* which nodes need to be modified and by how much their child count
has to
* be incremented / decremented.
*
* @param score_deltas
* A dict of scores to integers, as returned by
* _ComputeScoreDeltas.
* @return A dict of nodes (represented as node_key, child tuples) to
* integers. 'result[(node_key, i)]' represents the amount
that
* needs to be added to the i-th child of node node_key.
* @throws Exception
*/
private HashMap<Key_Child_Tuple, Integer>
ComputeNodeModifications(Map<Score_Tuple, Integer> score_deltas)
throws Exception
{
HashMap<Key_Child_Tuple, Integer> node_to_deltas = new
HashMap<Key_Child_Tuple, Integer>();

for (Iterator<Entry<Score_Tuple, Integer>> iter =
score_deltas.entrySet().iterator(); iter.hasNext();)
{
Entry<Score_Tuple, Integer> entry = iter.next();
Score_Tuple score = entry.getKey();
int delta = entry.getValue();

ArrayList<NodeID_Child_Tuple> nodeIDs = FindNodeIDs(score);
for (Iterator<NodeID_Child_Tuple> iter2 = nodeIDs.iterator();
iter2.hasNext();)
{
NodeID_Child_Tuple nodeTuple = iter2.next();
long node_id = nodeTuple.getNode_id();
long child = nodeTuple.getChild();
Key_Child_Tuple node = new Key_Child_Tuple(KeyFromNodeId(node_id),
child);

try
{
node_to_deltas.put(node, node_to_deltas.get(node) + delta);
} catch (NullPointerException e)
{
node_to_deltas.put(node, delta);
}
}
}

return node_to_deltas;
}

/**
* Utility function. Finds the rank of a score.
*
* @param node_ids_with_children
* A list of node ids down to that score, paired with
which child
* links to follow.
* @param nodes_dict
* A dict mapping node id to node entity.
* @return The score's rank.
*/
private long FindRank(ArrayList<NodeID_Child_Tuple>
node_ids_with_children, Map<Long, Entity> nodes_dict)
{
long tot = 0; // Counts the number of higher scores

for (Iterator<NodeID_Child_Tuple> iter =
node_ids_with_children.iterator(); iter.hasNext();)
{
NodeID_Child_Tuple node_id_with_child = iter.next();
long node_id = node_id_with_child.getNode_id();
long child = node_id_with_child.getChild();

if (nodes_dict.containsKey(node_id))
{
Entity node = nodes_dict.get(node_id);
for (int i = (int) (child + 1); i < this.branching_factor; i++)
{
// tot += ((int[]) node.getProperty("child_counts"))[i];
tot += ((ArrayList<Long>)
node.getProperty("child_counts")).get(i);
}
}

else
{
// If the node isn't in the dict, the node simply doesn't exist.
// We are probably finding the rank for a score that doesn't
// appear in the ranker, but that's perfectly fine.
break;
}
}
return tot;
}

/**
* Finds the 0-based rank of a particular score; more precisely,
returns the
* number of strictly higher scores stored.
*
* @param score
* The score whose rank we wish to find.
* @return The number of tracked scores that are higher. Does not
check
* whether anyone actually has the requested score.
* @throws Exception
*/
public ArrayList<Long> FindRank(Score_Tuple score) throws Exception
{
ArrayList<Score_Tuple> scoreList = new ArrayList<Score_Tuple>();
scoreList.add(score);
return FindRanks(scoreList);
}

/**
* Finds the 0-based ranks of a number of particular scores. Like
FindRank,
* but more efficient for multiple scores.
*
* @param scores
* A list of scores.
* @return A list of ranks.
* @throws Exception
*/
public ArrayList<Long> FindRanks(ArrayList<Score_Tuple> scores)
throws Exception
{
ArrayList<ArrayList<NodeID_Child_Tuple>> node_ids_with_children_list
= new ArrayList<ArrayList<NodeID_Child_Tuple>>();
ArrayList<Long> node_ids = new ArrayList<Long>();
Map<Long, Entity> nodes_dict;
ArrayList<Long> ranks = new ArrayList<Long>();

// Find the nodes we'll need to query to find information about
these
// scores:
for (Iterator<Score_Tuple> iter = scores.iterator();
iter.hasNext();)
node_ids_with_children_list.add(FindNodeIDs(iter.next()));

for (Iterator<ArrayList<NodeID_Child_Tuple>> iter =
node_ids_with_children_list.iterator(); iter.hasNext();)
{
ArrayList<NodeID_Child_Tuple> node_ids_with_childern = new
ArrayList<NodeID_Child_Tuple>();
node_ids_with_childern = iter.next();
for (int i = 0; i < node_ids_with_childern.size(); i++)
{
node_ids.add(node_ids_with_childern.get(i).getNode_id());
}
}

// Query the needed nodes
nodes_dict = GetMultipleNodes(node_ids);

// # Call __FindRank, which does the math, for each score:
for (Iterator<ArrayList<NodeID_Child_Tuple>> iter =
node_ids_with_children_list.iterator(); iter.hasNext();)
{
ArrayList<NodeID_Child_Tuple> node_ids_with_childern = new
ArrayList<NodeID_Child_Tuple>();
node_ids_with_childern = iter.next();
ranks.add(FindRank(node_ids_with_childern, nodes_dict));
}
return ranks;
}

/**
* To be run in a transaction. Finds the score ranked 'rank' in the
subtree
* defined by node 'nodekey.'
*
* @param node_id
* The id of the node whose subtree we wish to find the
score of
* rank 'rank' in.
* @param rank
* The rank (within this subtree) of the score we wish to
find.
* @param score_range
* The score range for this particular node, as a list.
Derivable
* from the node's node_id, but included for convenience.
* @param approximateDo
* we have to return an approximate result, or an exact
one? See
* the docstrings for FindScore and FindScoreApproximate.
* @returnA tuple, (score, rank_of_tie), indicating the score's rank
within
* node_id's subtree. The way it indicates rank is defined
in the
* dosctrings of FindScore and FindScoreApproximate,
depending on
* the value of 'approximate'.
* @throws EntityNotFoundException
* @throws Exception
*/
private Score_RankOfTie_Tuple FindScore(long node_id, int rank,
ArrayList<Long> score_range, boolean approximate) throws
EntityNotFoundException,
Exception
{
// # If we're approximating and thus allowed to do so, early-out if
we
// just need to return the highest available score.
if (approximate && rank == 0)
{
ArrayList<Long> arr = new ArrayList<Long>();
for (int i = 1; i < score_range.size(); i += 2)
arr.add(score_range.get(i) - 1);

return new Score_RankOfTie_Tuple(arr, 0);
}

// Find the current node.
Entity node = datastore.get(KeyFromNodeId(node_id));
ArrayList<Long> child_counts = (ArrayList<Long>)
node.getProperty("child_counts");
int initial_rank = rank;
for (int i = ((int) this.branching_factor - 1); i > -1; i--)
{
// If this child has enough scores that rank 'rank' is in there,
// recurse.
ArrayList<Long> child_score_range = ChildScoreRange(score_range, i,
this.branching_factor);
if (rank - child_counts.get(i) < 0)
{
child_score_range = ChildScoreRange(score_range, i,
this.branching_factor);

if (IsSingletonRange(child_score_range))
{
// # Base case; child_score_range refers to a single score.
// We don't store leaf nodes so we can return right here.
ArrayList<Long> arr = new ArrayList<Long>();
for (int j = 0; j < child_score_range.size(); j += 2)
arr.add(child_score_range.get(j));

return new Score_RankOfTie_Tuple(arr, initial_rank - rank);
}

// Not a base case. Keep descending into children.
Score_RankOfTie_Tuple ans = FindScore(ChildNodeId(node_id, i),
rank, child_score_range, approximate);

// # Note the 'initial_rank - rank': we've asked the child for a
// score of some rank among *its* children, so we have to add
// back in the scores discarded on the way to that child.
return new Score_RankOfTie_Tuple(ans.getScore(),
ans.getRank_of_tie() - rank);
} else
{
rank -= child_counts.get(i);
}
}

Log.debug("FindScore(int node_id, int rank, ArrayList<Integer>
score_range, int approximate) returns null!");
return null;
}

/**
* Returns whether a range contains exactly one score.
*
* @param child_score_range
* @return
*/
private boolean IsSingletonRange(ArrayList<Long> child_score_range)
{
boolean var = true;
for (int i = 0; i < child_score_range.size(); i += 2)
{
if (child_score_range.get(i) + 1 != child_score_range.get(i +
1))
{
var = false;
}
}
return var;

}

/**
* Finds the score ranked at 'rank'.
*
* @param rank
* The rank of the score we wish to find.
* @return A tuple, (score, rank_of_tie). 'score' is the score ranked
at
* 'rank', 'rank_of_tie' is the rank of that score (which may
be
* different from 'rank' in the case of ties). e.g. if there
are two
* scores tied at 5th and rank == 6, returns (score, 5).
* @throws EntityNotFoundException
* @throws Exception
*/
public Score_RankOfTie_Tuple FindScore(int rank) throws
EntityNotFoundException, Exception
{
return FindScore(0, rank, this.score_range, false);

}

/**
* Finds a score that >= the score ranked at 'rank'. This method
could be
* preferred to FindScore because it is more efficient. For example,
if the
* objective is to find the top 50 scores of rank X or less, and
those
* scores are stored in entities called scoreboard_row: score, rank =
* myrank.FindScoreApproximate(X) query =
datastore.Query('scoreboard_row')
* query['score <='] = score result = query.Get(50 + X - rank)[X-
rank:]) #
* Takes care of ties.
*
* @param rank
* The rank of the score we wish to find.
* @return A tuple, (score, rank_of_tie). If there is a tie at rank
* 'rank-1': rank's score <= score < rank-1's score,
rank_of_tie ==
* rank else: score == rank's score, rank_of_tie == the tied
rank of
* everyone in the tie. e.g. if two scores are tied at 5th
and rank
* == 6, returns (score, 5).
* @throws EntityNotFoundException
* @throws Exception
*/
public Score_RankOfTie_Tuple FindScoreApproximate(int rank) throws
EntityNotFoundException, Exception
{
return FindScore(0, rank, this.score_range, true);
}

/**
* Returns the total number of ranked scores.
*
* @return The total number of ranked scores.
* @throws EntityNotFoundException
*/
public int TotalRankedScores() throws EntityNotFoundException
{
int sum = 0;
Entity root = datastore.get(KeyFromNodeId(0));
ArrayList<Long> root_counts = (ArrayList<Long>)
root.getProperty("child_counts");
for (int i = 0; i < root_counts.size(); i++)
sum += root_counts.get(i);

return sum;
}

// Custom Tuple Data Structures
protected final class NodeID_Child_Tuple
{
private long node_id;
private long child;

NodeID_Child_Tuple(long node, long child)
{
this.node_id = node;
this.child = child;
}

public long getNode_id()
{
return node_id;
}

public void setNode_id(long node_id)
{
this.node_id = node_id;
}

public long getChild()
{
return child;
}

public void setChild(long child)
{
this.child = child;
}

}

protected final class Child_ChildScoreRange_Tuple
{
private long child;
private ArrayList<Long> childScoreRange;

Child_ChildScoreRange_Tuple(long child, ArrayList<Long> arrayList)
{
this.child = child;
this.childScoreRange = arrayList;
}

public long getChild()
{
return child;
}

public void setChild(long child)
{
this.child = child;
}

public ArrayList<Long> getChildScoreRange()
{
return childScoreRange;
}

public void setChildScoreRange(ArrayList<Long> childScoreRange)
{
this.childScoreRange = childScoreRange;
}
}

public final static class Score_Tuple
{
private int score;
private int score_time;

private Score_Tuple(String s)
{
String[] arr = s.split(",");
this.score = Integer.parseInt(arr[0]);
this.score_time = Integer.parseInt(arr[1]);
}

public Score_Tuple(int score, int score_time)
{
this.score = score;
this.score_time = score_time;
}

public int getByIndex(int i)
{
if (i == 0)
{
return score;
}

else if (i == 1)
{
return score_time;
}

else
{
Log.debug("Score_Tuple: getByIndex() exception");
return -1;
}
}

public int getScore()
{
return score;
}

public void setScore(int score)
{
this.score = score;
}

public int getScore_time()
{
return score_time;
}

public void setScore_time(int score_time)
{
this.score_time = score_time;
}

@Override
public String toString()
{
return Integer.toString(score) + "," +
Integer.toString(score_time);
}
}

protected final class Key_Child_Tuple
{
private Key key;
private long child;

Key_Child_Tuple(Key key, long child)
{
this.key = key;
this.child = child;
}

public Key getKey()
{
return key;
}

public void setKey(Key key)
{
this.key = key;
}

public long getChild()
{
return child;
}

public void setChild(long child)
{
this.child = child;
}
}

protected final class ScoreDeltas_ScoreEnts_ScoreEntsDel_Tuple
{
private HashMap<Score_Tuple, Integer> score_deltas;
private ArrayList<Entity> score_ents;
private ArrayList<Entity> score_ents_del;

ScoreDeltas_ScoreEnts_ScoreEntsDel_Tuple(HashMap<Score_Tuple,
Integer> score_deltas, ArrayList<Entity> score_ents,
ArrayList<Entity> score_ents_del)
{
this.score_deltas = score_deltas;
this.score_ents = score_ents;
this.score_ents_del = score_ents_del;
}

public HashMap<Score_Tuple, Integer> getScore_deltas()
{
return score_deltas;
}

public void setScore_deltas(HashMap<Score_Tuple, Integer>
score_deltas)
{
this.score_deltas = score_deltas;
}

public ArrayList<Entity> getScore_ents()
{
return score_ents;
}

public void setScore_ents(ArrayList<Entity> score_ents)
{
this.score_ents = score_ents;
}

public ArrayList<Entity> getScore_ents_del()
{
return score_ents_del;
}

public void setScore_ents_del(ArrayList<Entity> score_ents_del)
{
this.score_ents_del = score_ents_del;
}
}

protected final class Score_RankOfTie_Tuple
{
ArrayList<Long> score;
int rank_of_tie;

Score_RankOfTie_Tuple(ArrayList<Long> arr, int rank_of_tie)
{
this.score = arr;
this.rank_of_tie = rank_of_tie;
}

public ArrayList<Long> getScore()
{
return score;
}

public void setScore(ArrayList<Long> score)
{
this.score = score;
}

public int getRank_of_tie()
{
return rank_of_tie;
}

public void setRank_of_tie(int rank_of_tie)
{
this.rank_of_tie = rank_of_tie;
}
}
}

[Bartholomew Furrow]

That's awesome, John!  Thanks so much for submitting that.  I know other people have been asking for that.

--
You received this message because you are subscribed to the Google Groups "Google App Engine Ranklist" group.
To post to this group, send email to google-app-en...@googlegroups.com.
To unsubscribe from this group, send email to google-app-engine-r...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/google-app-engine-ranklist?hl=en.

[John]

No problem! Here's the code on gist, not sure why I didn't do this to
begin with -> https://gist.github.com/2158846

> ...
>
> read more »

[Oliver Billing]

Thankyou :-)

I really needed that.

[Oliver Billing]

Could you give me some real value examples... I must be doing something wrong ;-)

Getting this all the time...

com.google.appengine.api.datastore.EntityNotFoundException: No entity was found matching the key: ranker(12010)/ranker_node("node_0")


My test code...
	Ranker rank = new Ranker();
	ArrayList<Integer> range = new ArrayList<Integer>();
	range.add(0);
	range.add(100);
	range.add(0);
	range.add(100);
	
	
	
	
	rank.Create(range, 5);
	Random rand = new Random();
	for(int i=0;i<50;i++){
		rank.SetScore("TEST_USER"+i, new Ranker.Score_Tuple(rand.nextInt(50),23));
	}	

On Monday, March 19, 2012 11:58:59 PM UTC+1, John wrote:

[Roberto Caldas]

How did you call `rank.Create` without passing the name as argument?

By the way, `Create` should be static and there shouldn't exist a public constructor for Ranker.

...

[Message clipped]  

[John]

I made a slight modification to the constructor - you can just pass in a name so that multiple instances of rankers with unique names can be saved into the datastore:

public class RankerSettings

{

    public static ArrayList<Integer> Score_Range()

    {

ArrayList<Integer> scoreRange = new ArrayList<Integer>();

scoreRange.add(0);

scoreRange.add(100000000);

scoreRange.add(-999999);

scoreRange.add(1);

return scoreRange;

    }

    public static Integer Branching_Factor()

    {

return 100;

    }

}

String key = new Ranker().Create("My Ranker Name", RankerSettings.Score_Range(), RankerSettings.Branching_Factor()).getKeyString();

new Ranker(key).SetScore(Long.toString(id), new Score_Tuple((int) (someAmount * 100), 0));

Hope this helps.

[Anders Mårtensson]

Hi, thanks for the Java version.

I have some problems with it though, or maybe I don't understand how to use it. Here's how I create the Ranker:

ArrayList<Integer> scoreRange = new ArrayList<Integer>();

scoreRange.add(new Integer(0)); // minimum score
scoreRange.add(new Integer(5000)); // max score
scoreRange.add(new Integer(-99999)); // not used
scoreRange.add(new Integer(1)); // not used

int branchingFactor = 101;

ranker = new Ranker().Create("ranker", scoreRange, branchingFactor);

And some data and the results

name=41 1811,0 rank 1

name=42 1604,0 rank 2

name=40 1590,0 rank 2

name=47 1490,0 rank 3

name=58 1475,0 rank 4

name=48 1409,0 rank 5

name=56 1294,0 rank 6

name=57 1242,0 rank 7

I'm curious why player 42 and 40 both get the same rank. They have different scores and I would expect that rank would be 2 and 3 respectively. My guess is the branching factor is the issue.

Any ideas?

Thanks in advance, 

Anders

[Bartholomew Furrow]

Can you post a short piece of code that reproduces those results? Whenever I file a bug like this, there's always a chance that I've screwed up the repro code, so it would be nice to rule that out. And if it's right, that'll make it easier to debug.

FYI in Python, it appears to work fine:

rank = ranker.Ranker.Create([0, 5000, -99999, 1], 101)

a = [1811, 0]

b = [1604, 0]

c = [1590, 0]

rank.SetScore("41", a)

rank.SetScore("42", b)

rank.SetScore("40", c)

print rank.FindRanks([a,b,c])

Prints: [0L, 1L, 2L]

--

You received this message because you are subscribed to the Google Groups "Google App Engine Ranklist" group.

To unsubscribe from this group and stop receiving emails from it, send an email to google-app-engine-r...@googlegroups.com.

To post to this group, send email to google-app-en...@googlegroups.com.

Visit this group at http://groups.google.com/group/google-app-engine-ranklist.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Anders Mårtensson]

Thanks for the idea, Bart. I did a small test as suggested:

ArrayList<Integer> scoreRange = new ArrayList<Integer>();

scoreRange.add(new Integer(0)); // minimum score

scoreRange.add(new Integer(5000)); // max score

scoreRange.add(new Integer(-99999)); // not used

scoreRange.add(new Integer(1)); // not used

int branchingFactor = 101;

try {

Ranker ranker = new Ranker().Create("test", scoreRange, branchingFactor);

ArrayList<Score_Tuple> scores = new ArrayList<Ranker.Score_Tuple>();

scores.add(new Score_Tuple(1811, 0));

scores.add(new Score_Tuple(1604, 0));

scores.add(new Score_Tuple(1590, 0));

scores.add(new Score_Tuple(1490, 0));

scores.add(new Score_Tuple(1475, 0));

scores.add(new Score_Tuple(1409, 0));

scores.add(new Score_Tuple(1294, 0));

scores.add(new Score_Tuple(1242, 0));

ranker.SetScore("41", scores.get(0));

ranker.SetScore("42", scores.get(1));

ranker.SetScore("40", scores.get(2));

ranker.SetScore("47", scores.get(3));

ranker.SetScore("58", scores.get(4));

ranker.SetScore("48", scores.get(5));

ranker.SetScore("56", scores.get(6));

ranker.SetScore("57", scores.get(7));

ArrayList<Long> results = ranker.FindRanks(scores);

for (Long rank : results) {

out.println(rank);

}

} catch (EntityNotFoundException e) {

e.printStackTrace();

} catch (Exception e) {

e.printStackTrace();

}

And it prints out as expected 0, 1, 2, 3, 4 and so on. So something was indeed wrong in my own code :) I had a little utility function that and there was the problem, a basic 123 code error:

try {

ArrayList<Long> result = Util.getRanker().FindRank(new Score_Tuple(player.getRating(), 0));

rank = 1 + result.get(0).intValue();

} catch (Exception e) {

updateRankForPlayer(player);

save(player);

try {

ArrayList<Long> result = Util.getRanker().FindRank(new Score_Tuple(player.getRating(), 0));

rank = 1 + result.get(0).intValue();

} catch (Exception e1) {

e1.printStackTrace();

}

}

If a rank was not found, I add it. Problem is that previous ranks that I have already fetched may be wrong, as in player who was #2 before might be #3 now. I looped through all players and updated their rank and now everything works as expected.

So thanks again for pointing me to the right direction :) 

To unsubscribe from this group and stop receiving emails from it, send an email to google-app-engine-ranklist+unsub...@googlegroups.com.

[Bartholomew Furrow]

Ahh, nice find! I'm glad it worked out for you.