p2pool/util/skiplist.py

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