Order Statistic Tree implementation with DynamoDB

lambda-order-statistic-tree.js

const AWS = require('aws-sdk')
const db = new AWS.DynamoDB({apiVersion: '2012-08-10', region: 'ap-southeast-1'})

exports.handler = function (event, context, callback) {
  const TABLE = (event.stageVariables && event.stageVariables.env === 'production')
              ? 'find-wally-ranking-tree'
              : 'find-wally-ranking-tree-dev'

  const q = event.queryStringParameters
  const score = +q.score
  const time = +q.time

  const root = {
    score: {N: '0'},
    time: {N: '0'}
  }

  let players

  visitChild(null, root)

  function returnRank (rank) {
    const response = {
      statusCode: 200,
      headers: {'Access-Control-Allow-Origin': '*'},
      body: JSON.stringify({score, time, rank, players}),
      isBase64Encoded: false
    }
    callback(null, response)
  }

  function visitChild (parent, child, subtree = 'left', rank = 1) {
    if (!child) {
      child = {
        score: {N: score.toFixed()},
        time: {N: time.toFixed()}
      }
      return addChild(parent, child, subtree, rank)
    }

    db.updateItem({
      TableName: TABLE,
      Key: child,
      UpdateExpression: 'SET size = size + :inc',
      ConditionExpression: 'attribute_not_exists(locked)',
      ExpressionAttributeValues: {
        ':inc': {N: '1'}
      },
      ReturnValues: 'ALL_OLD'
    }, function (err, data) {
      if (err) return callback(err)

      const currentScore = +child.score.N
      const currentTime = +child.time.N
      const size = +data.Attributes.size.N

      players = players || size + 1

      if (subtree === 'right') rank -= size

      const nextSubtree = score > currentScore ? 'left'
                        : score < currentScore ? 'right'
                        : time < currentTime ? 'left'
                        : time > currentTime ? 'right'
                        : null

      if (nextSubtree) {
        parent = child
        child = data.Attributes[nextSubtree] && data.Attributes[nextSubtree].M
        subtree = nextSubtree
        rank = subtree === 'right' ? rank + size : rank
        visitChild(parent, child, subtree, rank)
      } else {
        if (data.Attributes.left) {
          db.getItem({
            TableName: TABLE,
            Key: data.Attributes.left.M
          }, function (err, data) {
            if (err) return callback(err)
            returnRank(rank + +data.Item.size.N)
          })
        } else {
          returnRank(rank)
        }
      }
    })
  }

  function addChild (parent, child, subtree, rank) {
    db.putItem({
      TableName: TABLE,
      Item: Object.assign({}, child, {size: {N: '1'}})
    }, function (err, data) {
      if (err) return callback(err)
      db.updateItem({
        TableName: TABLE,
        Key: parent,
        UpdateExpression: 'SET #subtree = :child',
        ExpressionAttributeNames: {
          '#subtree': subtree
        },
        ExpressionAttributeValues: {
          ':child': {M: child}
        }
      }, function (err, data) {
        if (err) return callback(err)
        returnRank(rank)
      })
    })
  }
}