home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pyth_os2.zip / python-1.0.2 / Demo / rsa / merge.py < prev    next >
Encoding:
Python Source  |  1992-12-09  |  1.8 KB  |  82 lines
  1.  
  2.  
  3. # merge src into dst.  Assumptions: src and dst are sorted
  4. def mergein(dst, src):
  5.     srclen, dstlen = len(src), len(dst)
  6.     srcidx, dstidx = 0, 0
  7.     for srcitem in src:
  8.         # while there are elements to insert
  9.         while dstidx < dstlen and dst[dstidx] < srcitem:
  10.             dstidx = dstidx + 1
  11.         dst.insert(dstidx, srcitem)
  12.         dstlen = dstlen + 1
  13.  
  14. # return the merge of s1 and s2.  Assumptions: s1 and s2 are sorted
  15. def merge(s1, s2):
  16.     # this could be made faster
  17.     result = s1[:]            # make a real copy of s1
  18.     mergein(result, s2)
  19.     return result
  20.  
  21. def binsortinsert(item, data, i, j):
  22.     diff = j - i
  23.     if diff == 0:
  24.         data.insert(data, item)
  25.     else:
  26.         diff = diff >> 1
  27.         if item < data[i + diff]:
  28.             binsortinsert(item, data, i, i+diff)
  29.         else:
  30.             binsortinsert(item, data, i+diff, j)
  31.     
  32.  
  33. # return a list of (listitem, count) pairs.  Assumptions: s is sorted contains
  34. # no None's
  35. def countitems(list):
  36.     result = []
  37.     lastitem, count = None, 0
  38.     for i in list:
  39.         if i != lastitem:
  40.             if count:
  41.                 result.append((lastitem, count))
  42.             lastitem, count = i, 1
  43.         else:
  44.             count = count + 1
  45.     if count:
  46.         result.append((lastitem, count))
  47.     return result
  48.  
  49. def gluetimes(times, df):
  50.     quot, rem = divmod(times, 2)
  51.     if times:
  52.         if times == 1:
  53.             return df()
  54.         else:
  55.             a = gluetimes(times/2, df)
  56.             b = gluetimes((times+1)/2, df)
  57.             return a + b
  58.     return ''
  59.  
  60. def gluerange(start, stop, df):
  61.     if start == stop:
  62.         raise ValueError, 'I don\'t know how to return a Null range'
  63.     halfway = (start + stop) / 2
  64.     gotleft, gotright = halfway - start, stop - halfway
  65.  
  66.     if gotleft:
  67.         if gotleft == 1:
  68.             left = df(start)
  69.         else:
  70.             left = gluerange(start, halfway, df)
  71.     if gotright:
  72.         if gotright == 1:
  73.             right = df(halfway)
  74.         else:
  75.             right = gluerange(halfway, stop, df)
  76.         if gotleft:
  77.             return left + right
  78.         else:
  79.             return right
  80.     else:
  81.         return left
  82.