packing.py

Go to the documentation of this file.

# Copyright (C) 2006,2016,2017,2020  Kipp Cannon
#
# This program is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation; either version 2 of the License, or (at your
# option) any later version.
#
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
# Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program; if not, write to the Free Software Foundation, Inc.,
# 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 
 
#
# =============================================================================
#
#                                   Preamble
#
# =============================================================================
#
 
 
"""
This module provides bin packing utilities.
"""
 
 
__author__ = "Kipp Cannon <kipp.cannon@ligo.org>"
from .git_version import date as __date__
from .git_version import version as __version__
 
 
#
# =============================================================================
#
#                                     Bins
#
# =============================================================================
#
 
 
# FIXME:  this should probably be a subclass of list, but no doubt that will
# break things so make this change some time it's convenient.
 
 
class Bin(object):
        """
        Bin object for use in packing algorithm implementations.  A Bin
        instance has two attributes:  size, which is the total "size" of
        the contents of the Bin, and objects, which is a list of the Bins
        contents.
 
        Example:
 
        >>> strings = Bin()
        >>> s = "hello"
        >>> strings.add(s, len(s))
        >>> s.objects
        ['hello']
        >>> s.size
        5
        """
        def __init__(self):
                """
                Initialize a new Bin instance.
                """
                self.objects = []
                self.size = 0
 
        def add(self, obj, size):
                """
                Add the object, whose size is as given, to the bin.
                """
                self.objects.append(obj)
                self.size += size
                return self
 
        def __iadd__(self, other):
                """
                Add the contents of another Bin object to this one.
                """
                self.objects.extend(other.objects)
                self.size += other.size
                return self
 
        #
        # Compare two Bin objects by their sizes.
        #
 
        def __lt__(self, other):
                return self.size < other.size
 
        def __le__(self, other):
                return self.size <= other.size
 
        def __eq__(self, other):
                return self.size == other.size
 
        def __ne__(self, other):
                return self.size != other.size
 
        def __ge__(self, other):
                return self.size >= other.size
 
        def __gt__(self, other):
                return self.size > other.size
 
        def __repr__(self):
                """
                A representation of the Bin object.
                """
                return "Bin(size=%s, %s)" % (str(self.size), str(self.objects))
 
        __str__ = __repr__
 
 
#
# =============================================================================
#
#                              Packing Algorithms
#
# =============================================================================
#
 
 
# FIXME:  this should probably also be a subclass of list.
 
class Packer(object):
        """
        Parent class for packing algorithms.  Specific packing algorithms
        should sub-class this, providing implementations of the pack() and
        packlist() methods.
        """
        def __init__(self, bins):
                """
                Set the list of bins on which we shall operate
                """
                self.bins = bins
 
        def pack(self, size, obj):
                """
                Pack an object of given size into the bins.
                """
                raise NotImplementedError
 
        def packlist(self, size_object_pairs):
                """
                Pack a list of (size, object) tuples into the bins.
 
                Default implementation invokes self.pack() on each pair in
                the the order given.
                """
                for size, obj in size_object_pairs:
                        self.pack(size, obj)
 
 
class BiggestIntoEmptiest(Packer):
        """
        Packs the biggest object into the emptiest bin.
        """
        def pack(self, size, obj):
                min(self.bins).add(obj, size)
 
        def packlist(self, size_object_pairs):
                for size, obj in sorted(size_object_pairs, reverse = True):
                        self.packpack(size, obj)