p2pool/util/skiplist.py

   1 from p2pool.util import math
   2
   3 class Base(object):
   4     def finalize(self, sol):
   5         return sol
   6
   7 class SkipList(Base):
   8     P = .5
   9
  10     def __init__(self):
  11         self.skips = {}
  12
  13     def forget_item(self, item):
  14         self.skips.pop(item, None)
  15
  16     def __call__(self, start, *args, **kwargs):
  17         updates = {}
  18         pos = start
  19         sol = self.initial_solution(start, args)
  20         if self.judge(sol, args) == 0:
  21             return self.finalize(sol)
  22         while True:
  23             if pos not in self.skips:
  24                 self.skips[pos] = math.geometric(self.P), [(self.previous(pos), self.get_delta(pos))]
  25             skip_length, skip = self.skips[pos]
  26
  27             # fill previous updates
  28             for i in xrange(skip_length):
  29                 if i in updates:
  30                     that_hash, delta = updates.pop(i)
  31                     x, y = self.skips[that_hash]
  32                     assert len(y) == i
  33                     y.append((pos, delta))
  34
  35             # put desired skip nodes in updates
  36             for i in xrange(len(skip), skip_length):
  37                 updates[i] = pos, None
  38
  39             #if skip_length + 1 in updates:
  40             #    updates[skip_length + 1] = self.combine(updates[skip_length + 1], updates[skip_length])
  41
  42             for jump, delta in reversed(skip):
  43                 sol_if = self.apply_delta(sol, delta, args)
  44                 decision = self.judge(sol_if, args)
  45                 #print pos, sol, jump, delta, sol_if, decision
  46                 if decision == 0:
  47                     return self.finalize(sol_if)
  48                 elif decision < 0:
  49                     sol = sol_if
  50                     break
  51             else:
  52                 raise AssertionError()
  53
  54             sol = sol_if
  55             pos = jump
  56
  57             # XXX could be better by combining updates
  58             for x in updates:
  59                 updates[x] = updates[x][0], self.combine_deltas(updates[x][1], delta) if updates[x][1] is not None else delta
  60
  61
  62         return item_hash
  63
  64 class NotSkipList(Base):
  65     def __call__(self, start, *args):
  66         pos = start
  67         sol = self.initial_solution(start, args)
  68         while True:
  69             decision = self.judge(sol, args)
  70             if decision > 0:
  71                 raise AssertionError()
  72             elif decision == 0:
  73                 return self.finalize(sol)
  74
  75             delta = self.get_delta(pos)
  76             sol = self.apply_delta(sol, delta, args)
  77
  78             pos = self.previous(pos)