কেস স্টাডি: একটি মেমরি অ্যালোকেটর সিমুলেটর বানানো

class MemoryAllocator:
    def __init__(self, total_size, strategy):
        self.total_size = total_size
        self.strategy = strategy          # "first_fit" | "best_fit" | "worst_fit"
        self.free_holes = [(0, total_size)]   # (start, size), ঠিকানা-ক্রমে সাজানো
        self.occupied = {}                # name -> (start, size)

    def _choose_hole(self, size):
        candidates = [h for h in self.free_holes if h[1] >= size]
        if not candidates:
            return None
        if self.strategy == "first_fit":
            for h in self.free_holes:      # ঠিকানা-ক্রমে প্রথম যথেষ্ট বড় হোল
                if h[1] >= size:
                    return h
        elif self.strategy == "best_fit":
            return min(candidates, key=lambda h: (h[1], h[0]))   # সবচেয়ে ছোট, কিন্তু যথেষ্ট
        elif self.strategy == "worst_fit":
            return max(candidates, key=lambda h: (h[1], -h[0]))  # সবচেয়ে বড়
        raise ValueError("অজানা strategy")

    def allocate(self, name, size):
        hole = self._choose_hole(size)
        if hole is None:
            return None
        start, hole_size = hole
        self.free_holes.remove(hole)
        self.occupied[name] = (start, size)
        remainder = hole_size - size
        if remainder > 0:
            self.free_holes.append((start + size, remainder))
        self.free_holes.sort(key=lambda h: h[0])
        return start

    def free(self, name):
        start, size = self.occupied.pop(name)
        self.free_holes.append((start, size))
        self.free_holes.sort(key=lambda h: h[0])

    def total_free(self):
        return sum(size for _, size in self.free_holes)

    def largest_hole(self):
        return max((size for _, size in self.free_holes), default=0)

    def fragmentation_report(self):
        total = self.total_free()
        largest = self.largest_hole()
        return {
            "holes": sorted(self.free_holes),
            "hole_count": len(self.free_holes),
            "total_free": total,
            "largest_hole": largest,
            "wasted_fragmented": total - largest,   # ফ্রি, কিন্তু সবচেয়ে বড় একক অনুরোধের চেয়ে ছোট টুকরোয় ছড়ানো
        }

# একই allocate/free সিকোয়েন্স -- মাঝে ইচ্ছাকৃতভাবে "filler" ব্লক (F1, F2) রাখা হয়েছে
# যাতে A, B, C ফ্রি করার পর তিনটি পৃথক, ভিন্ন-সাইজের হোল তৈরি হয় (কোনো merge ছাড়াই)।
ops = [
    ("alloc", "A", 300), ("alloc", "F1", 50), ("alloc", "B", 500),
    ("alloc", "F2", 50), ("alloc", "C", 200),
    ("free", "A", None), ("free", "B", None), ("free", "C", None),
    ("alloc", "D", 150), ("alloc", "E", 80),
]

for strategy in ["first_fit", "best_fit", "worst_fit"]:
    allocator = MemoryAllocator(1200, strategy)
    print(f"\n=== স্ট্র্যাটেজি: {strategy} ===")
    for op, name, size in ops:
        if op == "alloc":
            start = allocator.allocate(name, size)
            if name in ("D", "E"):
                print(f"  {name}({size}) বরাদ্দ -> ঠিকানা {start}-তে শুরু হওয়া হোলে")
        else:
            allocator.free(name)
    report = allocator.fragmentation_report()
    print(f"  ফ্রি হোল লেআউট: {report['holes']}")
    print(f"  মোট ফ্রি: {report['total_free']}, সবচেয়ে বড় হোল: {report['largest_hole']}, "
          f"ফ্র্যাগমেন্টেড/অপচয়: {report['wasted_fragmented']}")