fork download
copy 
  1. ''' pure storage buddy system bitmap
  2.     Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold:
  3.     (1) a node's value is 1 if and only if all its subtree nodes' values are 1
  4.     (2) a leaf node can have value either 1 or 0
  5.     Implement the following 2 APIs:
  6.     set_bit(offset, length), set the bits at range from offset to offset+length-1
  7.     clear_bit(offset, length), clear the bits at range from offset to offset+length-1
  8.  
  9.     i.e. The tree is like:
  10.                  0
  11.               /     \
  12.              0        1
  13.            /  \      /  \
  14.           1    0    1    1
  15.          /\   / \   / 
  16.         1  1 1   0 1
  17.         Since it's complete binary tree, the nodes can be stored in an array:
  18.         [0,0,1,1,0,1,1,1,1,1,0,1] 
  19.  
  20. '''
  21.  
  22. def setbit_down(A, x, n):
  23.     if x>=n:
  24.         return
  25.     if 2*x+1<=n and A[2*x+1]==0:
  26.         A[2*x+1]=1
  27.         setbit_down(A,2*x+1,n)
  28.     if 2*x+2<=n and A[2*x+2]==0:
  29.         A[2*x+2]=1
  30.         setbit_down(A,2*x+2,n)
  31.  
  32.  
  33. def set_bit(A, pos, length):
  34.     if not A or pos<0 or length<=0:
  35.         return
  36.     n = len(A)-1    #last index of A
  37.     for x in range(pos, min(n+1,min(pos+length, 2*pos+1))):
  38.         # set self
  39.         if A[x] == 1:
  40.             continue
  41.         A[x]=1
  42.         # set descendants
  43.         setbit_down(A,x,n)
  44.         # set ancestors
  45.         while x>0:
  46.             # make sure its sibling is 1, if its sibling is 0, cannot set ancestors
  47.             if (x%2==0 and A[x-1]==1) or (x%2==1 and x<n and A[x+1]==1):
  48.                 A[(x-1)/2] = 1
  49.             x = (x-1)/2
  50.  
  51. def clear_bit(A, pos, length):
  52.     if not A or pos<0 or length<=0:
  53.         return
  54.     n = len(A)-1    #last index of A
  55.     for x in range(pos, min(n+1, pos+length)):
  56.         # clear self
  57.         if A[x]==0:
  58.             continue
  59.         A[x]=0
  60.         # clear descendants
  61.         while 2*x+1<=n:
  62.             A[2*x+1] = 0
  63.             x=2*x+1
  64.         # clear ancestors
  65.         while x>0:
  66.             if A[(x-1)/2]==0:
  67.                 break
  68.             A[(x-1)/2] = 0
  69.             x = (x-1)/2
  70.  
  71. if __name__=='__main__':
  72.     A=[0,0,1,1,0,1,1,1,1,1,0,1]
  73.     test_cases = [(2, 3)]
  74.  
  75.     for each_test_case in test_cases:
  76.         pos, length = each_test_case        
  77.         A=[0,0,1,1,0,1,1,1,1,1,0,1]
  78.         set_bit(A,pos, length)
  79.         print 'after setting bit from ', pos, 'for ', length,'A is: ', A
  80.         A=[0,0,1,1,0,1,1,1,1,1,0,1]
  81.         clear_bit(A,pos, length)
  82.         print 'after clearing bit from ', pos, 'for ', length,'A is: ', A
  83.  
Success #stdin #stdout 0.01s 7260KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
after setting bit from  2 for  3 A is:  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
after clearing bit from  2 for  3 A is:  [0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0]
https://ideone.com/m1xBg4
language:
Python (cpython 2.7.16)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!