#######################################################################
# Copyright (C) 2007-2011 by Carnegie Mellon University.
#
# @OPENSOURCE_HEADER_START@
#
# Use of the SILK system and related source code is subject to the terms
# of the following licenses:
#
# GNU Public License (GPL) Rights pursuant to Version 2, June 1991
# Government Purpose License Rights (GPLR) pursuant to DFARS 252.227.7013
#
# NO WARRANTY
#
# ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER
# PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY
# PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN
# "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY
# KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT
# LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE,
# MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE
# OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT,
# SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY
# TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF
# WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES.
# LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF
# CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON
# CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE
# DELIVERABLES UNDER THIS LICENSE.
#
# Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie
# Mellon University, its trustees, officers, employees, and agents from
# all claims or demands made against them (and any related losses,
# expenses, or attorney's fees) arising out of, or relating to Licensee's
# and/or its sub licensees' negligent use or willful misuse of or
# negligent conduct or willful misconduct regarding the Software,
# facilities, or other rights or assistance granted by Carnegie Mellon
# University under this License, including, but not limited to, any
# claims of product liability, personal injury, death, damage to
# property, or violation of any laws or regulations.
#
# Carnegie Mellon University Software Engineering Institute authored
# documents are sponsored by the U.S. Department of Defense under
# Contract FA8721-05-C-0003. Carnegie Mellon University retains
# copyrights in all material produced under this contract. The U.S.
# Government retains a non-exclusive, royalty-free license to publish or
# reproduce these documents, or allow others to do so, for U.S.
# Government purposes only pursuant to the copyright license under the
# contract clause at 252.227.7013.
#
# @OPENSOURCE_HEADER_END@
#
#######################################################################

#######################################################################
# $SiLK: __init__.py 16752 2011-02-24 17:41:51Z mthomas $
#######################################################################

# ALTERNATE LOADING SCHEME:
#import os,sys,traceback
#
#if hasattr(sys, "argv"):
#    # running in a Python interpreter.  load the PySiLK module that
#    # includes a copy of libsilk
#    from silk.pysilk import *
#else:
#    # running embedded, presumably from a SiLK application loading a
#    # plug-in.  Attempt to load the PySiLK module that is not linked
#    # against libsilk.
#    try:
#        from silk.pysilk_nl import *
#    except ImportError:
#        for e in ["SILK_PLUGIN_DEBUG", "SILK_PYTHON_TRACEBACK"]:
#            if os.getenv(e, "") != "":
#                print "Exception when importing silk.pysilk_nl:"
#                print '-'*60
#                traceback.print_exc()
#                print '-'*60
#                break
#        raise


# When using PySiLK as a plug-in from a SiLK application, we want to
# use the libsilk from the application.  When using PySiLK from a
# Python interpreter, the PySiLK module must include libsilk.  To
# handle these two cases, first attempt to load the PySiLK module that
# is not linked against libsilk.  If that fails, assume it failed due
# to missing symbols and attempt to load the PySiLK module that
# includes libsilk.
try:
    # try the version not linked against libsilk
    from silk.pysilk_nl import *
except ImportError:
    # use version that is linked against libsilk.
    from silk.pysilk import *

from silk.site import sensors, classes, classtypes
from silk.fglob import FGlob

__all__ = ['IPAddr', 'IPv4Addr', 'IPv6Addr',
           'IPWildcard', 'IPSet', 'RWRec', 'TCPFlags', 'SilkFile',
           'PrefixMap', 'Bag',
           'IGNORE', 'ASV4', 'MIX', 'FORCE', 'ONLY',
           'READ', 'WRITE', 'APPEND',
           'DEFAULT', 'NO_COMPRESSION', 'ZLIB', 'LZO1X',
           'FIN', 'SYN', 'RST', 'PSH', 'ACK', 'URG', 'ECE', 'CWR',
           'sensors', 'classes', 'classtypes',
           'init_site', 'have_site_config',
           'silk_version',
           'initial_tcpflags_enabled', 'ipv6_enabled',
           'init_country_codes', 'FGlob']


rwrec_kwds = set(["application", "bytes", "classtype", "dip",
                  "dport", "duration", "duration_secs",
                  "etime", "icmpcode", "icmptype",
                  "initflags", "input", "nhip", "output", "packets",
                  "protocol", "restflags", "sensor", "sip", "sport",
                  "stime", "tcpflags", "finnoack", "timeout_killed",
                  "timeout_started"])


class RWRec(RWRecBase):

    def __init__(self, rec=None, _clone=None, **kwds):
        """RWRec() -> empty RWRec
        RWRec(rec, **kwds) -> clone of rec, updated by given keywords
        RWRec(dict, **kwds) -> RWRec, updated by dict and keywords

        Examples:
          foo = RWRec()
          bar = RWRec(foo, dip="192.168.1.1", dport=2000)
          baz = RWRec(bar.as_dict(), application=1)
        """
        if _clone:
            RWRecBase.__init__(self, clone=_clone)
        else:
            if isinstance(rec, dict):
                rec.update(kwds)
                kwds = rec
                rec = None
            if rec:
                RWRecBase.__init__(self, copy=rec)
            else:
                RWRecBase.__init__(self)
        # ETime has to be set last
        etime = kwds.pop("etime", None)
        for key, val in kwds.iteritems():
            if key not in rwrec_kwds:
                raise TypeError, (("'%s' is an invalid keyword "
                                   "argument for this function") % key)
            setattr(self, key, val)
        if etime:
            self.etime = etime

    def as_dict(self):
        "Returns the rwrec as a dictionary."
        recdict = dict()
        for x in ['application', 'bytes', 'dip', 'duration', 'stime',
                  'input', 'nhip', 'output', 'packets', 'protocol', 'sip']:
            recdict[x] = getattr(self, x)
        if have_site_config():
            for x in ['classtype', 'sensor']:
                recdict[x] = getattr(self, x)
        protocol = self.protocol
        if protocol in [6, 17, 132]:
            for x in ['sport', 'dport']:
                recdict[x] = getattr(self, x)
        if protocol == 1:
            for x in ['icmptype', 'icmpcode']:
                recdict[x] = getattr(self, x)
        elif protocol == 6:
            recdict['tcpflags'] = self.tcpflags

        if self.finnoack != None:
            for x in ['finnoack', 'timeout_killed', 'timeout_started']:
                recdict[x] = getattr(self, x)
            if protocol == 6:
                for x in ['initflags', 'restflags']:
                    recdict[x] = getattr(self, x)
        return recdict

    def __str__(self):
        return self.as_dict().__str__()

    def __repr__(self):
        return ("silk.RWRec(%s)" % self)


class SilkFile(SilkFileBase):

    def __init__(self, *args, **kwds):
        SilkFileBase.__init__(self, *args, **kwds)

    def read(self):
        rawrec = SilkFileBase.read(self)
        if rawrec:
            rawrec = RWRec(_clone = rawrec)
        return rawrec

    def __iter__(self):
        return self

    def next(self):
        rec = self.read()
        if not rec:
            raise StopIteration
        return rec


class IPSet(IPSetBase):
    """IPSet() -> empty IPSet
    IPSet(iterable) -> IPSet with items from the iterable inserted
    """
    def __init__(self, arg=None, _filename=None):
        if _filename:
            IPSetBase.__init__(self, _filename)
        else:
            IPSetBase.__init__(self)
        if arg:
            self.update(arg)

    @classmethod
    def load(cls, fname):
        "IPSet.load(filename) -> IPSet -- Load an IPSet from a file"
        return cls(_filename=fname)

    def __nonzero__(self):
        "Return whether the IPSet is non-empty"
        try:
            iter(self).next()
        except StopIteration:
            return False
        return True

    def update(self, arg):
        "Update an IPSet with the union of itself and another."
        if isinstance(arg, IPSet):
            return IPSetBase.update(self, arg)
        if isinstance(arg, basestring):
            # We don't want to treat strings as iterables
            return IPSetBase.add(self, IPWildcard(arg))
        try:
            # Is this an iterable?
            iter(arg)
        except TypeError:
            # It is not an iterable.  Add as an address.
            return IPSetBase.add(self, arg)
        for item in arg:
            if isinstance(item, basestring):
                IPSetBase.add(self, IPWildcard(item))
            else:
                IPSetBase.add(self, item)
        return self

    def add(self, arg):
        "Add a single IP Address to the IPSet"
        if isinstance(arg, basestring):
            arg = IPv4Addr(arg)
        if not isinstance(arg, IPv4Addr):
            raise TypeError, "Must be an IPv4Addr or IP Address string"
        return IPSetBase.add(self, arg)

    def union(self, arg):
        """Return the union of two IPSets as a new IPSet.

        (i.e. all elements that are in either IPSet.)
        """
        return self.copy().update(arg)

    def intersection_update(self, arg):
        "Update an IPSet with the intersection of itself and another."
        if isinstance(arg, IPSet):
            return IPSetBase.intersection_update(self, arg)
        return self.intersection_update(IPSet(arg))

    def intersection(self, arg):
        """Return the intersection of two IPSets as a new IPSet.

        (i.e. all elements that are in both IPSets.)
        """
        return self.copy().intersection_update(arg)

    def difference_update(self, arg):
        "Remove all elements of another IPSet from this IPSet."
        if isinstance(arg, IPSet):
            return IPSetBase.difference_update(self, arg)
        return self.difference_update(IPSet(arg))

    def difference(self, arg):
        """Return the difference of two IPSets as a new IPSet.

        (i.e. all elements that are in this IPSet but not the other.)
        """
        return self.copy().difference_update(arg)

    def symmetric_difference(self, arg):
        """Return the symmetric difference of two IPSets as a new IPSet.

        (i.e. all elements that are in exactly one of the IPSets.)
        """
        intersect = self.intersection(arg)
        combine = self.union(arg)
        return combine.difference_update(intersect)

    def symmetric_difference_update(self, arg):
        "Update an IPSet with the symmetric difference of itself and another."
        intersect = self.intersection(arg)
        self.update(arg)
        return self.difference_update(intersect)

    def issubset(self, arg):
        "Report whether another IPSet contains this IPSet."
        return not self.difference(arg)

    def issuperset(self, arg):
        "Report whether this IPSet contains another IPSet."
        if isinstance(arg, IPSet):
            newarg = arg
        else:
            newarg = IPSet(arg)
        return not newarg.difference(self)

    def copy(self):
        "Return a copy of this IPSet."
        return IPSet().update(self)

    def __copy__(self):
        return self.copy()

    def discard(self, arg):
        """Remove an IP address from an IPSet if it is a member.

        If the IP address is not a member, do nothing.
        """
        if arg in self:
            self.difference_update(IPSet().add(arg))
        return self

    def remove(self, arg):
        """Remove an IP address from an IPSet; it must be a member.

        If the IP address is not a member, raise a KeyError.
        """
        if arg not in self:
            raise KeyError
        return self.difference_update(IPSet().add(arg))

    def __le__(self, arg):
        "ipset.issubset(ipset)"
        if not isinstance(arg, IPSet):
            raise TypeError, "can only compare to an IPSet"
        return self.issubset(arg)

    def __ge__(self, arg):
        "ipset.issuperset(ipset)"
        if not isinstance(arg, IPSet):
            raise TypeError, "can only compare to an IPSet"
        return self.issuperset(arg)

    def __or__(self, arg):
        "ipset.union(ipset)"
        if not isinstance(arg, IPSet):
            return NotImplemented
        return self.union(arg)

    def __and__(self, arg):
        "ipset.intersection(ipset)"
        if not isinstance(arg, IPSet):
            return NotImplemented
        return self.intersection(arg)

    def __sub__(self, arg):
        "ipset.difference(ipset)"
        if not isinstance(arg, IPSet):
            return NotImplemented
        return self.difference(arg)

    def __xor__(self, arg):
        "ipset.symmetric_difference(ipset)"
        if not isinstance(arg, IPSet):
            raise NotImplemented
        return self.symmetric_difference(arg)

    def __ior__(self, arg):
        "ipset.update(ipset)"
        if not isinstance(arg, IPSet):
            raise TypeError, "can only compare to an IPSet"
        return self.update(arg)

    def __iand__(self, arg):
        "ipset.intersection_update(ipset)"
        if not isinstance(arg, IPSet):
            raise TypeError, "can only compare to an IPSet"
        return self.intersection_update(arg)

    def __isub__(self, arg):
        "ipset.difference_update(ipset)"
        if not isinstance(arg, IPSet):
            raise TypeError, "can only compare to an IPSet"
        return self.difference_update(arg)

    def __ixor__(self, arg):
        "ipset.symmetric_difference_update(ipset)"
        if not isinstance(arg, IPSet):
            raise TypeError, "can only compare to an IPSet"
        return self.symmetric_difference_update(arg)

    def __eq__(self, arg):
        return self <= arg and self >= arg

    def __ne__(self, arg):
        return not (self == arg)


class PrefixMap(object):
    "PrefixMap(filename) -> Prefix map from prefix map file"

    def __new__(cls, filename):
        pmap = PMapBase(filename)
        if pmap.content == "address":
            obj = object.__new__(AddressPrefixMap)
        elif pmap.content == "proto-port":
            obj = object.__new__(ProtoPortPrefixMap)
        else:
            raise RuntimeError, ("Unknown pmap content type %s" % pmap.content)
        obj._filename = filename
        obj._pmap = pmap
        obj._valuedict = {}
        obj.name = pmap.name
        return obj

    def _value(self, v):
        try:
            return self._valuedict[v]
        except KeyError:
            rv = self._pmap.get_value_string(v)
            self._valuedict[v] = rv
            return rv

    def __getitem__(self, key):
        "pmap.__getitem__(x) <==> pmap[x]"
        return self._value(self._pmap[self._to_int(key)])

    def get(self, key, default = None):
        "pmap.get(k[,d]) -> pmap[k] if k in pmap, else d.  d defaults to None."
        try:
            return self[key]
        except (TypeError, ValueError):
            return default

    def iterranges(self):
        "pmap.iterranges() -> an iterator over (start, end, value) ranges"
        for (start, end, value) in self._pmap:
            yield (self._from_int(start), self._from_int(end),
                   self._value(value))

    def _itervalues(self):
        for i in range(0, self._pmap.num_values):
            value = self._value(i)
            if value:
                yield value;

    def values(self):
        "pmap.values() -> list of pmap's values"
        return tuple(self._itervalues())



class AddressPrefixMap(PrefixMap):

    @staticmethod
    def _to_int(value):
        if not isinstance(value, IPv4Addr):
            raise TypeError, "key must be an IPv4Addr"
        return int(value)

    @staticmethod
    def _from_int(value):
        return IPv4Addr(value)


class ProtoPortPrefixMap(PrefixMap):

    @staticmethod
    def _to_int(value):
        (proto, port) = value
        return (proto << 16) + port

    @staticmethod
    def _from_int(value):
        return (value >> 16, value & 0xFFFF)


import itertools
import copy

def _count(n=0, step=1):
    while True:
        yield n
        n += step

class Bag(BagBase):
    """Bag() -> empty bag
    Bag(mapping) -> bag with items from the mapping inserted
    Bag(seq) ->  bag with items from a sequence of pairs
    """

    def __init__(self, arg=None, key_type=IPv4Addr,
                 _copy=None, _filename=None):
        if _filename:
            BagBase.__init__(self, filename = _filename)
        elif _copy:
            BagBase.__init__(self, copy = _copy)
        else:
            BagBase.__init__(self)
        self.key_type = key_type
        if arg:
            self.update(arg)

    @classmethod
    def ipaddr(cls, arg=None):
        return cls(arg, key_type=IPv4Addr)

    @classmethod
    def integer(cls, arg=None):
        return cls(arg, key_type=long)

    @classmethod
    def load(cls, fname, key_type=IPv4Addr):
        "Bag.load(filename) -> Bag -- Load a bag from a file"
        return cls(_filename=fname, key_type=key_type)

    @classmethod
    def load_ipaddr(cls, fname):
        "Bag.load_ipaddr(filename) -> Bag -- Load an IP address bag from a file"
        return cls.load(fname, key_type=IPv4Addr)

    @classmethod
    def load_integer(cls, fname):
        "Bag.load_integer(filename) -> Bag -- Load a integer bag from a file"
        return cls.load(fname, key_type=long)

    def copy(self):
        return Bag(_copy=self, key_type = self.key_type)

    def __copy__(self):
        return self.copy()

    def _to_int(self, value):
        if self.key_type == long and isinstance(value, int):
            return long(value)
        return self.key_type.__int__(value)

    def _from_int(self, value):
        return self.key_type(value)

    def __getitem__(self, key):
        "x.__getitem__(y) <==> x[y]"
        if isinstance(key, (slice, IPSet, IPWildcard)):
            key = (key,)
        if isinstance(key, tuple):
            retval = Bag(key_type = self.key_type)
            for item in key:
                if isinstance(item, self.key_type):
                    indices = (self._to_int(item),)
                elif (issubclass(self.key_type, IPv4Addr) and
                      isinstance(item, (IPSet, IPWildcard))):
                    indices = (int(x) for x in item)
                elif isinstance(item, slice):
                    # slice
                    if item.step:
                        raise ValueError, "Bags do not support stepped slices"
                    if item.start == None:
                        start = 0
                    else:
                        start = self._to_int(item.start)
                    if item.stop == None:
                        stop = 0x100000000
                    else:
                        stop = self._to_int(item.stop)
                    indices = itertools.islice(itertools.count(start),
                                               stop - start)
                else:
                    indices = (item,)
                for i in indices:
                    BagBase.__setitem__(retval, i,
                                        BagBase.__getitem__(self, i))
            return retval
        return BagBase.__getitem__(self, self._to_int(key))

    def __delitem__(self, key):
        "x.__delitem__(y) <==> del x[y]"
        self[key] = 0

    def __setitem__(self, key, value):
        "x.__setitem__(i, y) <==> x[i]=y"
        return BagBase.__setitem__(self, self._to_int(key), value)

    def __iter__(self):
        "x.__iter__() <==> iter(x)"
        return self.iterkeys()

    def __contains__(self, key):
        "B.__contains__(k) -> True if B has a key k, else False"
        return self[key] != 0

    def get(self, key, default=None):
        "B.get(k[,d]) -> B[k] if k in B, else d.  d defaults to None."
        retval = self[key]
        if retval:
            return retval
        return default

    def items(self):
        "B.items() -> list of B's (key, value) pairs, as 2-tuples"
        return list(self.iteritems())

    def iteritems(self):
        "B.iteritems() -> an iterator over the (key, value) items of B"
        for (key, value) in BagBase.__iter__(self):
            yield (self._from_int(key), value)

    def iterkeys(self):
        "B.iterkeys() -> an iterator over the keys of B"
        for item in self.iteritems():
            yield item[0]

    def itervalues(self):
        "B.itervalues() -> an iterator over the values of B"
        for item in self.iteritems():
            yield item[1]

    def keys(self):
        "B.keys() -> list of B's keys"
        return list(self.iterkeys())

    def update(self, arg):
        """B.update(mapping) -> updates bag with items from the mapping
        B.update(seq) ->  updates bag with items from a sequence of pairs
        """
        try:
            for key in arg.keys():
                self[key] = arg[key]
        except AttributeError:
            for (key, value) in arg:
                self[key] = value

    def values(self):
        "B.values() -> list of B's values"
        return list(self.itervalues())

    def add(self, *items):
        """B.add(key[, key]...) -> increments B[key] by 1 for each key
        B.add(sequence) -> increments B[key] by 1 for each key in sequence
        """
        if len(items) == 1:
            try:
                self.incr(items[0])
            except TypeError:
                for key in items[0]:
                    self.incr(key)
        else:
            for key in items:
                self.incr(key)

    def remove(self, *items):
        """B.remove(key[, key]...) -> decrements B[key] by 1 for each key
        B.remove(sequence) -> decrements B[key] by 1 for each key in sequence
        """
        if len(items) == 1:
            try:
                self.decr(items[0])
            except TypeError:
                for key in items[0]:
                    self.decr(key)
        else:
            for key in items:
                self.decr(key)

    def incr(self, key, value = 1):
        """B.incr(key) -> increments B[key] by 1
        B.incr(key, value) -> increments B[key] by value
        """
        return BagBase.incr(self, self._to_int(key), value)

    def decr(self, key, value = 1):
        """B.decr(key) -> increments B[key] by 1
        B.decr(key, value) -> increments B[key] by value
        """
        return BagBase.decr(self, self._to_int(key), value)

    def __iadd__(self, other):
        "B.__iadd__(x) <==> B += x"
        if not isinstance(other, Bag):
            return NotImplemented
        for (key, value) in other.iteritems():
            self.incr(key, value)
        return self

    def __isub__(self, other):
        "B.__isub__(x) <==> B -= x"
        if not isinstance(other, Bag):
            return NotImplemented
        for (key, value) in other.iteritems():
            try:
                self.decr(key, value)
            except OverflowError:
                del self[key]
        return self

    def __add__(self, other):
        "B.__add__(x) <==> B + x"
        return self.copy().__iadd__(other)

    def __sub__(self, other):
        """B.__sub__(x) <==> B - x

        Will not underflow."""
        return self.copy().__isub__(other)

    def group_iterator(self, other):
        """B.group_iterator(bag) -> an iterator over (key, B-value, bag-value)
        Will iterator over every key in which one of the bags has a non-zero
        value.  If one of the bags has a zero value, the value returned for
        that bag will be None.

        >>> a = Bag.integer({1: 1, 2: 2})
        >>> b = Bag.integer({1: 3, 3: 4})
        >>> list(a.group_iterator(b))
        [(1L, 1L, 3L), (2L, 3L, None), (3L, None, 4L)]
        """
        if not isinstance(other, Bag):
            raise TypeError, "Expected a Bag"
        a = self.iteritems()
        b = other.iteritems()
        try:
            ak, av = a.next()
        except StopIteration:
            while True:
                bk, bv = b.next()
                yield (bk, None, bv)
        try:
            bk, bv = b.next()
        except StopIteration:
            yield (ak, av, None)
            while True:
                ak, av = a.next()
                yield (ak, av, None)
        while True:
            if ak < bk:
                yield (ak, av, None)
                try:
                    ak, av = a.next()
                except StopIteration:
                    yield (bk, None, bv)
                    while True:
                        bk, bv = b.next()
                        yield (bk, None, bv)
            elif bk < ak:
                yield (bk, None, bv)
                try:
                    bk, bv = b.next()
                except StopIteration:
                    yield (ak, av, None)
                    while True:
                        ak, av = a.next()
                        yield (ak, av, None)
            else:
                yield (ak, av, bv)
                try:
                    ak, av = a.next()
                except StopIteration:
                    while True:
                        bk, bv = b.next()
                        yield (bk, None, bv)
                try:
                    bk, bv = b.next()
                except StopIteration:
                    yield (ak, av, None)
                    while True:
                        ak, av = a.next()
                        yield (ak, av, None)

    def min(self, other):
        "B.min(bag) -> new bag with minimum value for each key in originals"
        retval = Bag(key_type = self.key_type)
        for key, a, b in self.group_iterator(other):
            if a != None and b != None:
                retval[key] = min(a, b)
        return retval

    def max(self, other):
        "B.max(bag) -> new bag with maximum value for each key in originals"
        retval = Bag(key_type = self.key_type)
        for key, a, b in self.group_iterator(other):
            retval[key] = max(a, b)
        return retval

    def __div__(self, other):
        "B.__div__(bag) -> new bag c where c[key] = B[key] / bag[key]"
        if not isinstance(other, Bag):
            return NotImplemented
        retval = Bag(key_type = self.key_type)
        for key, a, b in self.group_iterator(other):
            if a != None and b != None:
                v, r = divmod(a, b)
                if r * 2 >= b:
                    v += 1
                retval[key] = v
        return retval

    def __imul__(self, other):
        if not isinstance(other, (int, long)):
            return NotImplemented
        for key, value in self.iteritems():
            self[key] = value * other
        return self

    def __mul__(self, other):
        if not isinstance(other, (int, long)):
            return NotImplemented
        return self.copy().__imul__(other)

    def __rmul__(self, other):
        return self.__mul__(other)

    def intersect(self, other):
        retval = Bag(key_type = self.key_type)
        for key, value in self.iteritems():
            if key in other:
                retval[key] = value
        return retval

    def complement_intersect(self, other):
        retval = Bag(key_type = self.key_type)
        for key, value in self.iteritems():
            if key not in other:
                retval[key] = value
        return retval

    def ipset(self):
        return IPSet(self.iterkeys())

    def __eq__(self, other):
        for key, va, vb in self.group_iterator(other):
            if va != vb:
                return False
        return True

    def __ne__(self, other):
        return not self == other

    def constrain_values(self, min = None, max = None):
        if not (min or max):
            raise ValueError, "Must supply at least one of min, max"
        for key, value in self.iteritems():
            if (min and value < min) or (max and value > max):
                del self[key]

    def constrain_keys(self, min = None, max = None):
        if not (min or max):
            raise ValueError, "Must supply at least one of min, max"
        for key in self:
            if (min and key < min) or (max and key > max):
                del self[key]

    def inversion(self):
        retval = Bag.integer()
        retval.add((min(x, 0xFFFFFFFF) for x in self.itervalues()))
        return retval
