experimental distributed hashtable implementations with 2D topology
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

69 lines
2.2 KiB

import json
from direction import Direction
FULL_KEYSPACE_LOWER = (0, 0)
FULL_KEYSPACE_UPPER = (1, 1)
# FULL_KEYSPACE_LOWER = (-180, -90) # FIXME: see constructor NOTE
# FULL_KEYSPACE_UPPER = (180, 90)
class Keyspace(object):
def __init__(self, lower=FULL_KEYSPACE_LOWER, upper=FULL_KEYSPACE_UPPER):
'''
2D keyspace: (minx,miny) (maxx,maxy) tuples.
NOTE: both dimensions should have same size, otherwise alternating
split direction is not guaranteed!
TODO: we should be able to translate a keyspace to geohash-ish representation
'''
self.lower = lower
self.upper = upper
def __str__(self):
return "(%s, %s)" % (self.lower, self.upper)
def __contains__(self, val):
return (
self.lower[0] <= val[0] < self.upper[0] and
self.lower[1] <= val[1] < self.upper[1]
)
def midpoint(self):
# returns the middle of the keyspace as (x,y) tuple
return (
(self.upper[0] - self.lower[0]) / 2.0 + self.lower[0],
(self.upper[1] - self.lower[1]) / 2.0 + self.lower[1]
)
def largestDimension(self):
keyrange = [
self.upper[0] - self.lower[0],
self.upper[1] - self.lower[1]
]
return keyrange.index(sorted(keyrange)[-1])
def subdivide(self):
# splits the keyspace in half, and returns a keyspace of the remaining half.
splitDirection = Direction.EAST if self.largestDimension() == 0 else Direction.NORTH
midpoint = self.midpoint()
if splitDirection == Direction.EAST:
newUpper = (midpoint[0], self.upper[1])
newLower = (midpoint[0], self.lower[1])
else:
newUpper = (self.upper[0], midpoint[1])
newLower = (self.lower[0], midpoint[1])
otherHalf = Keyspace(newLower, self.upper)
self.upper = newUpper
return otherHalf, splitDirection
def serialize(self):
# return "%s|%s" % (self.lower, self.upper)
return json.dumps((self.lower, self.upper))
@classmethod
def unserialize(self, keyspaceString):
lower, upper = json.loads(keyspaceString)
return Keyspace(lower, upper)