home *** CD-ROM | disk | FTP | other *** search
/ PC Welt 2006 November (DVD) / PCWELT_11_2006.ISO / casper / filesystem.squashfs / usr / lib / python2.4 / site-packages / BitTorrent / PiecePicker.pyc (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2006-08-31  |  5.9 KB  |  257 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.4)
  3.  
  4. from random import randrange, shuffle, choice
  5.  
  6. class PiecePicker:
  7.     
  8.     def __init__(self, numpieces, rarest_first_cutoff = 1):
  9.         self.rarest_first_cutoff = rarest_first_cutoff
  10.         self.numpieces = numpieces
  11.         self.interests = [
  12.             range(numpieces)]
  13.         self.pos_in_interests = range(numpieces)
  14.         self.numinterests = [
  15.             0] * numpieces
  16.         self.started = []
  17.         self.seedstarted = []
  18.         self.numgot = 0
  19.         self.scrambled = range(numpieces)
  20.         shuffle(self.scrambled)
  21.  
  22.     
  23.     def got_have(self, piece):
  24.         if self.numinterests[piece] is None:
  25.             return None
  26.         
  27.         numint = self.numinterests[piece]
  28.         if numint == len(self.interests) - 1:
  29.             self.interests.append([])
  30.         
  31.         self.numinterests[piece] += 1
  32.         self._shift_over(piece, self.interests[numint], self.interests[numint + 1])
  33.  
  34.     
  35.     def lost_have(self, piece):
  36.         if self.numinterests[piece] is None:
  37.             return None
  38.         
  39.         numint = self.numinterests[piece]
  40.         self.numinterests[piece] -= 1
  41.         self._shift_over(piece, self.interests[numint], self.interests[numint - 1])
  42.  
  43.     
  44.     def _shift_over(self, piece, l1, l2):
  45.         p = self.pos_in_interests[piece]
  46.         l1[p] = l1[-1]
  47.         self.pos_in_interests[l1[-1]] = p
  48.         del l1[-1]
  49.         newp = randrange(len(l2) + 1)
  50.         if newp == len(l2):
  51.             self.pos_in_interests[piece] = len(l2)
  52.             l2.append(piece)
  53.         else:
  54.             old = l2[newp]
  55.             self.pos_in_interests[old] = len(l2)
  56.             l2.append(old)
  57.             l2[newp] = piece
  58.             self.pos_in_interests[piece] = newp
  59.  
  60.     
  61.     def requested(self, piece, seed = False):
  62.         if piece not in self.started:
  63.             self.started.append(piece)
  64.         
  65.         if seed and piece not in self.seedstarted:
  66.             self.seedstarted.append(piece)
  67.         
  68.  
  69.     
  70.     def complete(self, piece):
  71.         if not self.numinterests[piece] is not None:
  72.             raise AssertionError
  73.         self.numgot += 1
  74.         l = self.interests[self.numinterests[piece]]
  75.         p = self.pos_in_interests[piece]
  76.         l[p] = l[-1]
  77.         self.pos_in_interests[l[-1]] = p
  78.         del l[-1]
  79.         self.numinterests[piece] = None
  80.         
  81.         try:
  82.             self.started.remove(piece)
  83.             self.seedstarted.remove(piece)
  84.         except ValueError:
  85.             self
  86.             self
  87.         except:
  88.             self
  89.  
  90.  
  91.     
  92.     def next(self, havefunc, seed = False):
  93.         bests = None
  94.         bestnum = 2 ** 30
  95.         if seed:
  96.             s = self.seedstarted
  97.         else:
  98.             s = self.started
  99.         for i in s:
  100.             if havefunc(i):
  101.                 if self.numinterests[i] < bestnum:
  102.                     bests = [
  103.                         i]
  104.                     bestnum = self.numinterests[i]
  105.                 elif self.numinterests[i] == bestnum:
  106.                     bests.append(i)
  107.                 
  108.             self.numinterests[i] < bestnum
  109.         
  110.         if bests:
  111.             return choice(bests)
  112.         
  113.         if self.numgot < self.rarest_first_cutoff:
  114.             for i in self.scrambled:
  115.                 if havefunc(i):
  116.                     return i
  117.                     continue
  118.             
  119.             return None
  120.         
  121.         for i in xrange(1, min(bestnum, len(self.interests))):
  122.             for j in self.interests[i]:
  123.                 if havefunc(j):
  124.                     return j
  125.                     continue
  126.             
  127.         
  128.  
  129.     
  130.     def am_I_complete(self):
  131.         return self.numgot == self.numpieces
  132.  
  133.     
  134.     def bump(self, piece):
  135.         l = self.interests[self.numinterests[piece]]
  136.         pos = self.pos_in_interests[piece]
  137.         del l[pos]
  138.         l.append(piece)
  139.         for i in range(pos, len(l)):
  140.             self.pos_in_interests[l[i]] = i
  141.         
  142.  
  143.  
  144.  
  145. def test_requested():
  146.     p = PiecePicker(9)
  147.     p.complete(8)
  148.     p.got_have(0)
  149.     p.got_have(2)
  150.     p.got_have(4)
  151.     p.got_have(6)
  152.     p.requested(1)
  153.     p.requested(1)
  154.     p.requested(3)
  155.     p.requested(0)
  156.     p.requested(6)
  157.     v = _pull(p)
  158.     if not v[:2] == [
  159.         1,
  160.         3] and v[:2] == [
  161.         3,
  162.         1]:
  163.         raise AssertionError
  164.     if not v[2:4] == [
  165.         0,
  166.         6] and v[2:4] == [
  167.         6,
  168.         0]:
  169.         raise AssertionError
  170.     if not v[4:] == [
  171.         2,
  172.         4] and v[4:] == [
  173.         4,
  174.         2]:
  175.         raise AssertionError
  176.  
  177.  
  178. def test_change_interest():
  179.     p = PiecePicker(9)
  180.     p.complete(8)
  181.     p.got_have(0)
  182.     p.got_have(2)
  183.     p.got_have(4)
  184.     p.got_have(6)
  185.     p.lost_have(2)
  186.     p.lost_have(6)
  187.     v = _pull(p)
  188.     if not v == [
  189.         0,
  190.         4] and v == [
  191.         4,
  192.         0]:
  193.         raise AssertionError
  194.  
  195.  
  196. def test_change_interest2():
  197.     p = PiecePicker(9)
  198.     p.complete(8)
  199.     p.got_have(0)
  200.     p.got_have(2)
  201.     p.got_have(4)
  202.     p.got_have(6)
  203.     p.lost_have(2)
  204.     p.lost_have(6)
  205.     v = _pull(p)
  206.     if not v == [
  207.         0,
  208.         4] and v == [
  209.         4,
  210.         0]:
  211.         raise AssertionError
  212.  
  213.  
  214. def test_complete():
  215.     p = PiecePicker(1)
  216.     p.got_have(0)
  217.     p.complete(0)
  218.     if not _pull(p) == []:
  219.         raise AssertionError
  220.     p.got_have(0)
  221.     p.lost_have(0)
  222.  
  223.  
  224. def test_rarer_in_started_takes_priority():
  225.     p = PiecePicker(3)
  226.     p.complete(2)
  227.     p.requested(0)
  228.     p.requested(1)
  229.     p.got_have(1)
  230.     p.got_have(0)
  231.     p.got_have(0)
  232.     if not _pull(p) == [
  233.         1,
  234.         0]:
  235.         raise AssertionError
  236.  
  237.  
  238. def test_zero():
  239.     if not _pull(PiecePicker(0)) == []:
  240.         raise AssertionError
  241.  
  242.  
  243. def _pull(pp):
  244.     r = []
  245.     
  246.     def want(p, r = r):
  247.         return p not in r
  248.  
  249.     while True:
  250.         n = pp.next(want)
  251.         if n is None:
  252.             break
  253.         
  254.         r.append(n)
  255.     return r
  256.  
  257.