| # Licensed to the Apache Software Foundation (ASF) under one |
| # or more contributor license agreements. See the NOTICE file |
| # distributed with this work for additional information |
| # regarding copyright ownership. The ASF licenses this file |
| # to you under the Apache License, Version 2.0 (the |
| # "License"); you may not use this file except in compliance |
| # with the License. You may obtain a copy of the License at |
| # |
| # http://www.apache.org/licenses/LICENSE-2.0 |
| # |
| # Unless required by applicable law or agreed to in writing, |
| # software distributed under the License is distributed on an |
| # "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| # KIND, either express or implied. See the License for the |
| # specific language governing permissions and limitations |
| # under the License. |
| |
| |
| class PackingIterator: |
| def __init__(self, items, target_weight, lookback, weight_func, largest_bin_first=False): |
| self.items = iter(items) |
| self.target_weight = target_weight |
| self.lookback = lookback |
| self.weight_func = weight_func |
| self.largest_bin_first = largest_bin_first |
| self.bins = [] |
| |
| def __iter__(self): |
| return self |
| |
| def __next__(self): |
| while True: |
| try: |
| item = next(self.items) |
| weight = self.weight_func(item) |
| bin_ = self.find_bin(weight) |
| if bin_ is not None: |
| bin_.add(item, weight) |
| else: |
| bin_ = self.Bin(self.target_weight) |
| bin_.add(item, weight) |
| self.bins.append(bin_) |
| |
| if len(self.bins) > self.lookback: |
| return list(self.remove_bin().items) |
| except StopIteration: |
| break |
| |
| if len(self.bins) == 0: |
| raise StopIteration() |
| |
| return list(self.remove_bin().items) |
| |
| def find_bin(self, weight): |
| for bin_ in self.bins: |
| if bin_.can_add(weight): |
| return bin_ |
| return None |
| |
| def remove_bin(self): |
| if self.largest_bin_first: |
| bin_ = max(self.bins, key=lambda b: b.weight()) |
| self.bins.remove(bin_) |
| return bin_ |
| else: |
| return self.bins.pop(0) |
| |
| class Bin: |
| def __init__(self, target_weight: int): |
| self.bin_weight = 0 |
| self.target_weight = target_weight |
| self.items: list = [] |
| |
| def weight(self) -> int: |
| return self.bin_weight |
| |
| def can_add(self, weight) -> bool: |
| return self.bin_weight + weight <= self.target_weight |
| |
| def add(self, item, weight): |
| self.bin_weight += weight |
| self.items.append(item) |
