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