File size: 1,723 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | # Check which free chain nodes are actually needed
L, R = 577837, 979141
lenL = L.bit_length()
lenR = R.bit_length()
# The recursive decomposition
needed_free = set()
range_nodes = {}
def gr(k, lo, hi):
if lo > hi:
return None
if k == 0:
return ('END',) if (lo == 0 and hi == 0) else None
if lo == 0 and hi == (1 << k) - 1:
needed_free.add(k)
return ('FREE', k)
key = (k, lo, hi)
if key in range_nodes:
return range_nodes[key]
mid = 1 << (k-1)
left = None
if lo <= min(hi, mid-1):
left = gr(k-1, lo, min(hi, mid-1))
right = None
if max(lo, mid) <= hi:
right = gr(k-1, max(lo, mid) - mid, hi - mid)
if left is None and right is None:
range_nodes[key] = None
return None
range_nodes[key] = ('RANGE', k, lo, hi, left, right)
return range_nodes[key]
for length in range(lenL, lenR+1):
rs = 1 << (length-1)
re = (1 << length) - 1
cL = max(L, rs)
cR = min(R, re)
if cL > cR:
continue
if length == 1:
pass # END
else:
gr(length-1, cL - rs, cR - rs)
print("Directly referenced free nodes:", sorted(needed_free))
print("Total needed free chain nodes (including intermediate):", end=" ")
# All free nodes needed: for each directly referenced F[k], we need F[1]..F[k]
all_free = set()
for k in needed_free:
for i in range(1, k+1):
all_free.add(i)
print(sorted(all_free))
print(f"Free chain size: {len(all_free)}")
# Count range nodes
rn = sum(1 for v in range_nodes.values() if v is not None)
print(f"Range nodes: {rn}")
print(f"Total: 2 (START+END) + {len(all_free)} (free) + {rn} (range) = {2 + len(all_free) + rn}")
|