From: Vivien Maisonneuve <v.maisonneuve@gmail.com>
Date: Thu, 22 May 2014 21:59:53 +0000 (+0200)
Subject: Initial commit
X-Git-Tag: 1.0~268
X-Git-Url: https://scm.cri.mines-paristech.fr/git/linpy.git/commitdiff_plain/841943174bb4d3b602e8e055592d8b54d1bb086d

Initial commit
---

841943174bb4d3b602e8e055592d8b54d1bb086d
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..bbe9588
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+/build/
+/dist/
+/MANIFEST
+__pycache__
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..4ab5d2a
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,18 @@
+PYTHON=python3
+RM=rm -rf
+
+.PHONY: default
+default:
+	@echo "pypol - A polyhedral library based on ISL"
+	@echo
+	@echo "Makefile usage:"
+	@echo "  make test             run the test suite"
+	@echo "  make clean            remove the generated files"
+
+.PHONY: test
+test:
+	$(PYTHON) -m unittest
+
+.PHONY: clean
+clean:
+	$(RM) build dist MANIFEST pypol/__pycache__ tests/__pycache__
diff --git a/pypol/__init__.py b/pypol/__init__.py
new file mode 100644
index 0000000..fde0347
--- /dev/null
+++ b/pypol/__init__.py
@@ -0,0 +1,15 @@
+
+"""
+A polyhedral library based on ISL.
+"""
+
+from .linear import constant, symbol, symbols
+from .linear import eq, le, lt, ge, gt
+from .linear import empty, universe
+
+
+__all__ = [
+    'constant', 'symbol', 'symbols',
+    'eq', 'le', 'lt', 'ge', 'gt',
+    'empty', 'universe'
+]
diff --git a/pypol/isl.py b/pypol/isl.py
new file mode 100644
index 0000000..758fb79
--- /dev/null
+++ b/pypol/isl.py
@@ -0,0 +1,267 @@
+
+import ctypes, ctypes.util
+import math
+import numbers
+import operator
+import re
+
+from decimal import Decimal
+from fractions import Fraction
+from functools import wraps
+
+
+libisl = ctypes.CDLL(ctypes.util.find_library('isl'))
+
+libisl.isl_printer_get_str.restype = ctypes.c_char_p
+
+
+class Context:
+
+    __slots__ = ('_ic')
+
+    def __init__(self):
+        self._ic = libisl.isl_ctx_alloc()
+
+    @property
+    def _as_parameter_(self):
+        return self._ic
+
+    def __del__(self):
+        libisl.isl_ctx_free(self)
+
+    def __eq__(self, other):
+        if not isinstance(other, Context):
+            return False
+        return self._ic == other._ic
+
+
+class Value:
+
+    class _ptr(int):
+        def __new__(cls, iv):
+            return super().__new__(cls, iv)
+        def __repr__(self):
+            return '{}({})'.format(self.__class__.__name__, self)
+
+    _RE_NONFINITE = re.compile(
+            r'^\s*(?P<sign>[-+])?((?P<inf>Inf(inity)?)|(?P<nan>NaN))\s*$',
+            re.IGNORECASE)
+
+    _RE_FRACTION = re.compile(r'^(?P<num>[-+]?\d+)(/(?P<den>\d+))?$')
+
+    __slots__ = ('context', '_iv', '_numerator', '_denominator')
+
+    def __new__(cls, context, numerator=0, denominator=None):
+        self = super().__new__(cls)
+        if not isinstance(context, Context):
+            raise TypeError('first argument should be a context')
+        self.context = context
+        if isinstance(numerator, cls._ptr):
+            assert denominator is None
+            self._iv = numerator
+            if libisl.isl_val_is_rat(self):
+                # retrieve numerator and denominator as strings to avoid integer
+                # overflows
+                ip = libisl.isl_printer_to_str(self.context)
+                ip = libisl.isl_printer_print_val(ip, self)
+                string = libisl.isl_printer_get_str(ip).decode()
+                libisl.isl_printer_free(ip)
+                m = self._RE_FRACTION.match(string)
+                assert m is not None
+                self._numerator = int(m.group('num'))
+                self._denominator = int(m.group('den')) if m.group('den') else 1
+            else:
+                self._numerator = None
+                self._denominator = None
+            return self
+        if isinstance(numerator, str) and denominator is None:
+            m = self._RE_NONFINITE.match(numerator)
+            if m is not None:
+                self._numerator = None
+                self._denominator = None
+                if m.group('inf'):
+                    if m.group('sign') == '-':
+                        self._iv = libisl.isl_val_neginfty(context)
+                    else:
+                        self._iv = libisl.isl_val_infty(context)
+                else:
+                    assert m.group('nan')
+                    self._iv = libisl.isl_val_nan(context)
+                return self
+        try:
+            frac = Fraction(numerator, denominator)
+        except ValueError:
+            raise ValueError('invalid literal for {}: {!r}'.format(
+                    cls.__name__, numerator))
+        self._numerator = frac.numerator
+        self._denominator = frac.denominator
+        # values passed as strings to avoid integer overflows
+        if frac.denominator == 1:
+            numerator = str(frac.numerator).encode()
+            self._iv = libisl.isl_val_read_from_str(context, numerator)
+        else:
+            numerator = str(frac.numerator).encode()
+            numerator = libisl.isl_val_read_from_str(context, numerator)
+            denominator = str(frac.denominator).encode()
+            denominator = libisl.isl_val_read_from_str(context, denominator)
+            self._iv = libisl.isl_val_div(numerator, denominator)
+        return self
+
+    @property
+    def _as_parameter_(self):
+        return self._iv
+
+    def __del__(self):
+        libisl.isl_val_free(self)
+        self.context # prevents context from being GC'ed before the value
+
+    @property
+    def numerator(self):
+        if self._numerator is None:
+            raise ValueError('not a rational number')
+        return self._numerator
+
+    @property
+    def denominator(self):
+        if self._denominator is None:
+            raise ValueError('not a rational number')
+        return self._denominator
+
+    def __bool__(self):
+        return not bool(libisl.isl_val_is_zero(self))
+
+    def _polymorphic(func):
+        @wraps(func)
+        def wrapper(self, other):
+            if isinstance(other, Value):
+                return func(self, other)
+            if isinstance(other, numbers.Rational):
+                other = Value(self.context, other)
+                return func(self, other)
+            raise TypeError('operand should be a Value or a Rational')
+        return wrapper
+
+    @_polymorphic
+    def __lt__(self, other):
+        return bool(libisl.isl_val_lt(self, other))
+
+    @_polymorphic
+    def __le__(self, other):
+        return bool(libisl.isl_val_le(self, other))
+
+    @_polymorphic
+    def __gt__(self, other):
+        return bool(libisl.isl_val_gt(self, other))
+
+    @_polymorphic
+    def __ge__(self, other):
+        return bool(libisl.isl_val_ge(self, other))
+
+    @_polymorphic
+    def __eq__(self, other):
+        return bool(libisl.isl_val_eq(self, other))
+
+    # __ne__ is not implemented, ISL semantics does not match Python's on
+    # nan != nan
+
+    def __abs__(self):
+        val = libisl.isl_val_copy(self)
+        val = libisl.isl_val_abs(val)
+        return self.__class__(self.context, self._ptr(val))
+
+    def __pos__(self):
+        return self
+
+    def __neg__(self):
+        val = libisl.isl_val_copy(self)
+        val = libisl.isl_val_neg(val)
+        return self.__class__(self.context, self._ptr(val))
+
+    def __floor__(self):
+        val = libisl.isl_val_copy(self)
+        val = libisl.isl_val_floor(val)
+        return self.__class__(self.context, self._ptr(val))
+
+    def __ceil__(self):
+        val = libisl.isl_val_copy(self)
+        val = libisl.isl_val_ceil(val)
+        return self.__class__(self.context, self._ptr(val))
+
+    def __trunc__(self):
+        val = libisl.isl_val_copy(self)
+        val = libisl.isl_val_trunc(val)
+        return self.__class__(self.context, self._ptr(val))
+
+    @_polymorphic
+    def __add__(self, other):
+        val1 = libisl.isl_val_copy(self)
+        val2 = libisl.isl_val_copy(other)
+        val = libisl.isl_val_add(val1, val2)
+        return self.__class__(self.context, self._ptr(val))
+
+    __radd__ = __add__
+
+    @_polymorphic
+    def __sub__(self, other):
+        val1 = libisl.isl_val_copy(self)
+        val2 = libisl.isl_val_copy(other)
+        val = libisl.isl_val_sub(val1, val2)
+        return self.__class__(self.context, self._ptr(val))
+
+    __rsub__ = __sub__
+
+    @_polymorphic
+    def __mul__(self, other):
+        val1 = libisl.isl_val_copy(self)
+        val2 = libisl.isl_val_copy(other)
+        val = libisl.isl_val_mul(val1, val2)
+        return self.__class__(self.context, self._ptr(val))
+
+    __rmul__ = __mul__
+
+    @_polymorphic
+    def __truediv__(self, other):
+        val1 = libisl.isl_val_copy(self)
+        val2 = libisl.isl_val_copy(other)
+        val = libisl.isl_val_div(val1, val2)
+        return self.__class__(self.context, self._ptr(val))
+
+    __rtruediv__ = __truediv__
+
+    def __float__(self):
+        if libisl.isl_val_is_rat(self):
+            return self.numerator / self.denominator
+        elif libisl.isl_val_is_infty(self):
+            return float('inf')
+        elif libisl.isl_val_is_neginfty(self):
+            return float('-inf')
+        else:
+            assert libisl.isl_val_is_nan(self)
+            return float('nan')
+
+    def is_finite(self):
+        return bool(libisl.isl_val_is_rat(self))
+
+    def is_infinite(self):
+        return bool(libisl.isl_val_is_infty(self) or
+                libisl.isl_val_is_neginfty(self))
+
+    def is_nan(self):
+        return bool(libisl.isl_val_is_nan(self))
+
+    def __str__(self):
+        if libisl.isl_val_is_rat(self):
+            if self.denominator == 1:
+                return '{}'.format(self.numerator)
+            else:
+                return '{}/{}'.format(self.numerator, self.denominator)
+        elif libisl.isl_val_is_infty(self):
+            return 'Infinity'
+        elif libisl.isl_val_is_neginfty(self):
+            return '-Infinity'
+        else:
+            assert libisl.isl_val_is_nan(self)
+            return 'NaN'
+
+    def __repr__(self):
+        return '{}({!r})'.format(self.__class__.__name__, str(self))
diff --git a/pypol/linear.py b/pypol/linear.py
new file mode 100644
index 0000000..5b5d8aa
--- /dev/null
+++ b/pypol/linear.py
@@ -0,0 +1,458 @@
+
+import functools
+import numbers
+
+from fractions import Fraction, gcd
+
+
+__all__ = [
+    'Expression',
+    'constant', 'symbol', 'symbols',
+    'eq', 'le', 'lt', 'ge', 'gt',
+    'Polyhedron',
+    'empty', 'universe'
+]
+
+
+class Expression:
+    """
+    This class implements linear expressions.
+    """
+
+    def __new__(cls, coefficients=None, constant=0):
+        if isinstance(coefficients, str):
+            if constant:
+                raise TypeError('too many arguments')
+            return cls.fromstring(coefficients)
+        self = super().__new__(cls)
+        self._coefficients = {}
+        if isinstance(coefficients, dict):
+            coefficients = coefficients.items()
+        if coefficients is not None:
+            for symbol, coefficient in coefficients:
+                if isinstance(symbol, Expression) and symbol.issymbol():
+                    symbol = str(symbol)
+                elif not isinstance(symbol, str):
+                    raise TypeError('symbols must be strings')
+                if not isinstance(coefficient, numbers.Rational):
+                    raise TypeError('coefficients must be rational numbers')
+                if coefficient != 0:
+                    self._coefficients[symbol] = coefficient
+        if not isinstance(constant, numbers.Rational):
+            raise TypeError('constant must be a rational number')
+        self._constant = constant
+        return self
+
+    def symbols(self):
+        yield from sorted(self._coefficients)
+
+    @property
+    def dimension(self):
+        return len(list(self.symbols()))
+
+    def coefficient(self, symbol):
+        if isinstance(symbol, Expression) and symbol.issymbol():
+            symbol = str(symbol)
+        elif not isinstance(symbol, str):
+            raise TypeError('symbol must be a string')
+        try:
+            return self._coefficients[symbol]
+        except KeyError:
+            return 0
+
+    __getitem__ = coefficient
+
+    def coefficients(self):
+        for symbol in self.symbols():
+            yield symbol, self.coefficient(symbol)
+
+    @property
+    def constant(self):
+        return self._constant
+
+    def isconstant(self):
+        return len(self._coefficients) == 0
+
+    def values(self):
+        for symbol in self.symbols():
+            yield self.coefficient(symbol)
+        yield self.constant
+
+    def symbol(self):
+        if not self.issymbol():
+            raise ValueError('not a symbol: {}'.format(self))
+        for symbol in self.symbols():
+            return symbol
+
+    def issymbol(self):
+        return len(self._coefficients) == 1 and self._constant == 0
+
+    def __bool__(self):
+        return (not self.isconstant()) or bool(self.constant)
+
+    def __pos__(self):
+        return self
+
+    def __neg__(self):
+        return self * -1
+
+    def _polymorphic(func):
+        @functools.wraps(func)
+        def wrapper(self, other):
+            if isinstance(other, Expression):
+                return func(self, other)
+            if isinstance(other, numbers.Rational):
+                other = Expression(constant=other)
+                return func(self, other)
+            return NotImplemented
+        return wrapper
+
+    @_polymorphic
+    def __add__(self, other):
+        coefficients = dict(self.coefficients())
+        for symbol, coefficient in other.coefficients():
+            if symbol in coefficients:
+                coefficients[symbol] += coefficient
+            else:
+                coefficients[symbol] = coefficient
+        constant = self.constant + other.constant
+        return Expression(coefficients, constant)
+
+    __radd__ = __add__
+
+    @_polymorphic
+    def __sub__(self, other):
+        coefficients = dict(self.coefficients())
+        for symbol, coefficient in other.coefficients():
+            if symbol in coefficients:
+                coefficients[symbol] -= coefficient
+            else:
+                coefficients[symbol] = -coefficient
+        constant = self.constant - other.constant
+        return Expression(coefficients, constant)
+
+    __rsub__ = __sub__
+
+    @_polymorphic
+    def __mul__(self, other):
+        if other.isconstant():
+            coefficients = dict(self.coefficients())
+            for symbol in coefficients:
+                coefficients[symbol] *= other.constant
+            constant = self.constant * other.constant
+            return Expression(coefficients, constant)
+        if isinstance(other, Expression) and not self.isconstant():
+            raise ValueError('non-linear expression: '
+                    '{} * {}'.format(self._parenstr(), other._parenstr()))
+        return NotImplemented
+
+    __rmul__ = __mul__
+
+    @_polymorphic
+    def __truediv__(self, other):
+        if other.isconstant():
+            coefficients = dict(self.coefficients())
+            for symbol in coefficients:
+                coefficients[symbol] = \
+                        Fraction(coefficients[symbol], other.constant)
+            constant = Fraction(self.constant, other.constant)
+            return Expression(coefficients, constant)
+        if isinstance(other, Expression):
+            raise ValueError('non-linear expression: '
+                '{} / {}'.format(self._parenstr(), other._parenstr()))
+        return NotImplemented
+
+    def __rtruediv__(self, other):
+        if isinstance(other, Rational):
+            if self.isconstant():
+                constant = Fraction(other, self.constant)
+                return Expression(constant=constant)
+            else:
+                raise ValueError('non-linear expression: '
+                        '{} / {}'.format(other._parenstr(), self._parenstr()))
+        return NotImplemented
+
+    def __str__(self):
+        string = ''
+        symbols = sorted(self.symbols())
+        i = 0
+        for symbol in symbols:
+            coefficient = self[symbol]
+            if coefficient == 1:
+                if i == 0:
+                    string += symbol
+                else:
+                    string += ' + {}'.format(symbol)
+            elif coefficient == -1:
+                if i == 0:
+                    string += '-{}'.format(symbol)
+                else:
+                    string += ' - {}'.format(symbol)
+            else:
+                if i == 0:
+                    string += '{}*{}'.format(coefficient, symbol)
+                elif coefficient > 0:
+                    string += ' + {}*{}'.format(coefficient, symbol)
+                else:
+                    assert coefficient < 0
+                    coefficient *= -1
+                    string += ' - {}*{}'.format(coefficient, symbol)
+            i += 1
+        constant = self.constant
+        if constant != 0 and i == 0:
+            string += '{}'.format(constant)
+        elif constant > 0:
+            string += ' + {}'.format(constant)
+        elif constant < 0:
+            constant *= -1
+            string += ' - {}'.format(constant)
+        return string
+
+    def _parenstr(self, always=False):
+        string = str(self)
+        if not always and (self.isconstant() or self.issymbol()):
+            return string
+        else:
+            return '({})'.format(string)
+
+    def __repr__(self):
+        string = '{}({{'.format(self.__class__.__name__)
+        for i, (symbol, coefficient) in enumerate(self.coefficients()):
+            if i != 0:
+                string += ', '
+            string += '{!r}: {!r}'.format(symbol, coefficient)
+        string += '}}, {!r})'.format(self.constant)
+        return string
+
+    @classmethod
+    def fromstring(cls, string):
+        raise NotImplementedError
+
+    @_polymorphic
+    def __eq__(self, other):
+        # "normal" equality
+        # see http://docs.sympy.org/dev/tutorial/gotchas.html#equals-signs
+        return isinstance(other, Expression) and \
+                self._coefficients == other._coefficients and \
+                self.constant == other.constant
+
+    def __hash__(self):
+        return hash((self._coefficients, self._constant))
+
+    def _canonify(self):
+        lcm = functools.reduce(lambda a, b: a*b // gcd(a, b),
+                [value.denominator for value in self.values()])
+        return self * lcm
+
+    @_polymorphic
+    def _eq(self, other):
+        return Polyhedron(equalities=[(self - other)._canonify()])
+
+    @_polymorphic
+    def __le__(self, other):
+        return Polyhedron(inequalities=[(self - other)._canonify()])
+
+    @_polymorphic
+    def __lt__(self, other):
+        return Polyhedron(inequalities=[(self - other)._canonify() + 1])
+
+    @_polymorphic
+    def __ge__(self, other):
+        return Polyhedron(inequalities=[(other - self)._canonify()])
+
+    @_polymorphic
+    def __gt__(self, other):
+        return Polyhedron(inequalities=[(other - self)._canonify() + 1])
+
+
+def constant(numerator=0, denominator=None):
+    return Expression(constant=Fraction(numerator, denominator))
+
+def symbol(name):
+    if not isinstance(name, str):
+        raise TypeError('name must be a string')
+    return Expression(coefficients={name: 1})
+
+def symbols(names):
+    if isinstance(names, str):
+        names = names.replace(',', ' ').split()
+    return (symbol(name) for name in names)
+
+
+def _operator(func):
+    @functools.wraps(func)
+    def wrapper(a, b):
+        if isinstance(a, numbers.Rational):
+            a = constant(a)
+        if isinstance(b, numbers.Rational):
+            b = constant(b)
+        if isinstance(a, Expression) and isinstance(b, Expression):
+            return func(a, b)
+        raise TypeError('arguments must be linear expressions')
+    return wrapper
+
+@_operator
+def eq(a, b):
+    return a._eq(b)
+
+@_operator
+def le(a, b):
+    return a <= b
+
+@_operator
+def lt(a, b):
+    return a < b
+
+@_operator
+def ge(a, b):
+    return a >= b
+
+@_operator
+def gt(a, b):
+    return a > b
+
+
+class Polyhedron:
+    """
+    This class implements polyhedrons.
+    """
+
+    def __new__(cls, equalities=None, inequalities=None):
+        if isinstance(equalities, str):
+            if inequalities is not None:
+                raise TypeError('too many arguments')
+            return cls.fromstring(equalities)
+        self = super().__new__(cls)
+        self._equalities = []
+        if equalities is not None:
+            for constraint in equalities:
+                for value in constraint.values():
+                    if value.denominator != 1:
+                        raise TypeError('non-integer constraint: '
+                                '{} == 0'.format(constraint))
+                self._equalities.append(constraint)
+        self._inequalities = []
+        if inequalities is not None:
+            for constraint in inequalities:
+                for value in constraint.values():
+                    if value.denominator != 1:
+                        raise TypeError('non-integer constraint: '
+                                '{} <= 0'.format(constraint))
+                self._inequalities.append(constraint)
+        return self
+
+    @property
+    def equalities(self):
+        yield from self._equalities
+
+    @property
+    def inequalities(self):
+        yield from self._inequalities
+
+    def constraints(self):
+        yield from self.equalities
+        yield from self.inequalities
+
+    def symbols(self):
+        s = set()
+        for constraint in self.constraints():
+            s.update(constraint.symbols)
+        yield from sorted(s)
+
+    @property
+    def dimension(self):
+        return len(self.symbols())
+
+    def __bool__(self):
+        # return false if the polyhedron is empty, true otherwise
+        raise NotImplementedError
+
+    def __contains__(self, value):
+        # is the value in the polyhedron?
+        raise NotImplementedError
+
+    def __eq__(self, other):
+        raise NotImplementedError
+
+    def isempty(self):
+        return self == empty
+
+    def isuniverse(self):
+        return self == universe
+
+    def isdisjoint(self, other):
+        # return true if the polyhedron has no elements in common with other
+        raise NotImplementedError
+
+    def issubset(self, other):
+        raise NotImplementedError
+
+    def __le__(self, other):
+        return self.issubset(other)
+
+    def __lt__(self, other):
+        raise NotImplementedError
+
+    def issuperset(self, other):
+        # test whether every element in other is in the polyhedron
+        raise NotImplementedError
+
+    def __ge__(self, other):
+        return self.issuperset(other)
+
+    def __gt__(self, other):
+        raise NotImplementedError
+
+    def union(self, *others):
+        # return a new polyhedron with elements from the polyhedron and all
+        # others (convex union)
+        raise NotImplementedError
+
+    def __or__(self, other):
+        return self.union(other)
+
+    def intersection(self, *others):
+        # return a new polyhedron with elements common to the polyhedron and all
+        # others
+        # a poor man's implementation could be:
+        # equalities = list(self.equalities)
+        # inequalities = list(self.inequalities)
+        # for other in others:
+        #     equalities.extend(other.equalities)
+        #     inequalities.extend(other.inequalities)
+        # return self.__class__(equalities, inequalities)
+        raise NotImplementedError
+
+    def __and__(self, other):
+        return self.intersection(other)
+
+    def difference(self, *others):
+        # return a new polyhedron with elements in the polyhedron that are not
+        # in the others
+        raise NotImplementedError
+
+    def __sub__(self, other):
+        return self.difference(other)
+
+    def __str__(self):
+        constraints = []
+        for constraint in self.equalities:
+            constraints.append('{} == 0'.format(constraint))
+        for constraint in self.inequalities:
+            constraints.append('{} <= 0'.format(constraint))
+        return '{{{}}}'.format(', '.join(constraints))
+
+    def __repr__(self):
+        equalities = list(self.equalities)
+        inequalities = list(self.inequalities)
+        return '{}(equalities={!r}, inequalities={!r})' \
+                ''.format(self.__class__.__name__, equalities, inequalities)
+
+    @classmethod
+    def fromstring(cls, string):
+        raise NotImplementedError
+
+
+empty = le(1, 0)
+
+universe = Polyhedron()
diff --git a/setup.py b/setup.py
new file mode 100755
index 0000000..a0dfb8a
--- /dev/null
+++ b/setup.py
@@ -0,0 +1,10 @@
+#!/usr/bin/env python3
+
+from distutils.core import setup
+
+setup(
+    name='pypol',
+    description='A polyhedral library based on ISL',
+    author='MINES ParisTech',
+    packages=['pypol']
+)
diff --git a/tests/__init__.py b/tests/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/tests/test_isl.py b/tests/test_isl.py
new file mode 100644
index 0000000..7186dad
--- /dev/null
+++ b/tests/test_isl.py
@@ -0,0 +1,199 @@
+
+import unittest
+
+from math import floor, ceil, trunc
+
+from pypol.isl import *
+
+
+class TestContext(unittest.TestCase):
+
+    def test_eq(self):
+        ctx1, ctx2 = Context(), Context()
+        self.assertEqual(ctx1, ctx1)
+        self.assertNotEqual(ctx1, ctx2)
+
+
+class TestValue(unittest.TestCase):
+
+    def setUp(self):
+        self.context = Context()
+        self.zero = Value(self.context)
+        self.nan = Value(self.context, 'NaN')
+        self.inf = Value(self.context, 'Inf')
+        self.neginf = Value(self.context, '-Inf')
+        self.answer = Value(self.context, 42)
+        self.pi = Value(self.context, 22, 7)
+
+    def test_init(self):
+        self.assertEqual(Value(self.context, 42), self.answer)
+        self.assertEqual(Value(self.context, '42'), self.answer)
+        self.assertEqual(Value(self.context, 22, 7), self.pi)
+        self.assertEqual(Value(self.context, '-22/7'), -self.pi)
+        self.assertTrue(Value(self.context, 'nan').is_nan())
+        self.assertTrue(Value(self.context, '-nan').is_nan())
+        self.assertTrue(Value(self.context, 'NaN').is_nan())
+        self.assertEqual(Value(self.context, '-inf'), self.neginf)
+        self.assertEqual(Value(self.context, '-Infinity'), self.neginf)
+
+    def test_numerator(self):
+        self.assertEqual(self.zero.numerator, 0)
+        self.assertEqual(self.answer.numerator, 42)
+        self.assertEqual(self.pi.numerator, 22)
+        with self.assertRaises(ValueError):
+            self.nan.numerator
+        with self.assertRaises(ValueError):
+            self.inf.numerator
+
+    def test_denominator(self):
+        self.assertEqual(self.zero.denominator, 1)
+        self.assertEqual(self.answer.denominator, 1)
+        self.assertEqual(self.pi.denominator, 7)
+        with self.assertRaises(ValueError):
+            self.nan.denominator
+        with self.assertRaises(ValueError):
+            self.inf.denominator
+
+    def test_bool(self):
+        self.assertFalse(self.zero)
+        self.assertTrue(self.answer)
+        self.assertTrue(self.pi)
+        self.assertEqual(bool(self.nan), bool(float('nan')))
+        self.assertEqual(bool(self.inf), bool(float('inf')))
+
+    def test_lt(self):
+        self.assertTrue(self.neginf < self.zero)
+        self.assertTrue(self.zero < self.pi)
+        self.assertTrue(self.pi < self.answer)
+        self.assertTrue(self.answer < self.inf)
+        self.assertFalse(self.nan < self.answer)
+        self.assertFalse(self.nan < self.inf)
+        self.assertFalse(self.nan < self.neginf)
+        self.assertTrue(self.neginf < self.inf)
+
+    def test_le(self):
+        self.assertTrue(self.pi <= self.pi)
+        self.assertTrue(self.pi <= self.answer)
+        self.assertFalse(self.answer <= self.pi)
+
+    def test_gt(self):
+        self.assertFalse(self.pi > self.pi)
+        self.assertTrue(self.answer > self.pi)
+        self.assertFalse(self.pi > self.answer)
+
+    def test_ge(self):
+        self.assertTrue(self.pi >= self.pi)
+        self.assertTrue(self.answer >= self.pi)
+        self.assertFalse(self.pi >= self.answer)
+
+    def test_eq(self):
+        self.assertEqual(self.pi, self.pi)
+        self.assertEqual(self.inf, self.inf)
+        self.assertNotEqual(self.neginf, self.inf)
+        self.assertNotEqual(self.nan, self.nan)
+        self.assertEqual(self.zero, 0)
+        self.assertEqual(0, self.zero)
+        self.assertEqual(self.pi, Fraction(22, 7))
+        self.assertEqual(Fraction(22, 7), self.pi)
+        with self.assertRaises(TypeError):
+            self.zero == 0.
+
+    def test_ne(self):
+        self.assertTrue(self.pi != self.answer)
+        self.assertFalse(self.pi != self.pi)
+        self.assertTrue(self.neginf != self.inf)
+        self.assertTrue(self.nan != self.nan)
+
+    def test_abs(self):
+        self.assertEqual(abs(self.pi), self.pi)
+        self.assertEqual(abs(self.neginf), self.inf)
+        self.assertEqual(abs(-self.pi), self.pi)
+        self.assertTrue(abs(self.nan).is_nan())
+
+    def test_pos(self):
+        self.assertEqual(+self.pi, self.pi)
+
+    def test_neg(self):
+        self.assertEqual(-self.neginf, self.inf)
+        self.assertEqual(-(-self.pi), self.pi)
+
+    def test_floor(self):
+        self.assertEqual(floor(self.pi), Value(self.context, 3))
+        self.assertEqual(floor(-self.pi), Value(self.context, -4))
+        # not float behavior, but makes sense
+        self.assertEqual(floor(self.inf), self.inf)
+        self.assertTrue(floor(self.nan).is_nan())
+
+    def test_ceil(self):
+        self.assertEqual(ceil(self.pi), Value(self.context, 4))
+        self.assertRaises(ceil(-self.pi) == Value(self.context, -3))
+
+    def test_trunc(self):
+        self.assertEqual(trunc(self.pi), Value(self.context, 3))
+        self.assertEqual(trunc(-self.pi), Value(self.context, -3))
+
+    def test_add(self):
+        self.assertEqual(self.answer + self.answer, Value(self.context, 84))
+        self.assertEqual(self.answer + self.pi, Value(self.context, 316, 7))
+        self.assertEqual(self.pi + self.pi, Value(self.context, 44, 7))
+        self.assertEqual(self.pi + self.neginf, self.neginf)
+        self.assertEqual(self.pi + self.inf, self.inf)
+        self.assertTrue((self.pi + self.nan).is_nan())
+        self.assertTrue((self.inf + self.nan).is_nan())
+        self.assertTrue((self.inf + self.neginf).is_nan())
+        self.assertEqual(self.pi + 42, Value(self.context, 316, 7))
+        self.assertEqual(42 + self.pi, Value(self.context, 316, 7))
+        self.assertEqual(self.pi + Fraction(22, 7), Value(self.context, 44, 7))
+        with self.assertRaises(TypeError):
+            self.pi + float(42)
+
+    def test_sub(self):
+        self.assertEqual(self.answer - self.pi, Value(self.context, 272, 7))
+
+    def test_mul(self):
+        self.assertEqual(Value(self.context, 6) * Value(self.context, 7), self.answer)
+        self.assertNotEqual(Value(self.context, 6) * Value(self.context, 9), self.answer)
+        self.assertEqual(self.inf * Value(self.context, 2), self.inf)
+        self.assertEqual(self.inf * Value(self.context, -2), self.neginf)
+        self.assertTrue((self.nan * Value(self.context, 2)).is_nan())
+        self.assertTrue((self.nan * self.inf).is_nan())
+
+    def test_div(self):
+        self.assertEqual(Value(self.context, 22) / Value(self.context, 7), self.pi)
+        self.assertEqual(self.pi / self.pi, Value(self.context, 1))
+        # not float behavior, but makes sense
+        self.assertTrue((self.pi / self.zero).is_nan())
+
+    def test_float(self):
+        self.assertAlmostEqual(float(Value(self.context, 1, 2)), 0.5)
+        self.assertTrue(math.isnan(float(Value(self.context, 'NaN'))))
+        self.assertAlmostEqual(float(Value(self.context, 'Inf')), float('inf'))
+
+    def test_is_finite(self):
+        self.assertTrue(self.pi.is_finite())
+        self.assertFalse(self.inf.is_finite())
+        self.assertFalse(self.nan.is_finite())
+
+    def test_is_infinite(self):
+        self.assertFalse(self.pi.is_infinite())
+        self.assertTrue(self.inf.is_infinite())
+        self.assertFalse(self.nan.is_infinite())
+
+    def test_is_nan(self):
+        self.assertFalse(self.pi.is_nan())
+        self.assertFalse(self.inf.is_nan())
+        self.assertTrue(self.nan.is_nan())
+
+    def test_str(self):
+        self.assertEqual(str(self.answer), '42')
+        self.assertEqual(str(self.pi), '22/7')
+        self.assertEqual(str(self.nan), 'NaN')
+        self.assertEqual(str(self.inf), 'Infinity')
+        self.assertEqual(str(self.neginf), '-Infinity')
+
+    def test_repr(self):
+        self.assertEqual(repr(self.answer), "Value('42')")
+        self.assertEqual(repr(self.pi), "Value('22/7')")
+        self.assertEqual(repr(self.nan), "Value('NaN')")
+        self.assertEqual(repr(self.inf), "Value('Infinity')")
+        self.assertEqual(repr(self.neginf), "Value('-Infinity')")
diff --git a/tests/test_linear.py b/tests/test_linear.py
new file mode 100644
index 0000000..3912fd3
--- /dev/null
+++ b/tests/test_linear.py
@@ -0,0 +1,176 @@
+
+import unittest
+
+from fractions import Fraction
+
+from pypol.linear import *
+
+
+class TestExpression(unittest.TestCase):
+
+    def setUp(self):
+        self.x = symbol('x')
+        self.y = symbol('y')
+        self.z = symbol('z')
+        self.zero = constant(0)
+        self.pi = constant(Fraction(22, 7))
+        self.e = self.x - 2*self.y + 3
+
+    def test_new(self):
+        pass
+
+    def test_symbols(self):
+        self.assertCountEqual(self.x.symbols(), ['x'])
+        self.assertCountEqual(self.pi.symbols(), [])
+        self.assertCountEqual(self.e.symbols(), ['x', 'y'])
+
+    def test_dimension(self):
+        self.assertEqual(self.x.dimension, 1)
+        self.assertEqual(self.pi.dimension, 0)
+        self.assertEqual(self.e.dimension, 2)
+
+    def test_coefficient(self):
+        self.assertEqual(self.e.coefficient('x'), 1)
+        self.assertEqual(self.e.coefficient('y'), -2)
+        self.assertEqual(self.e.coefficient(self.y), -2)
+        self.assertEqual(self.e.coefficient('z'), 0)
+        with self.assertRaises(TypeError):
+            self.e.coefficient(0)
+        with self.assertRaises(TypeError):
+            self.e.coefficient(self.e)
+
+    def test_getitem(self):
+        self.assertEqual(self.e['x'], 1)
+        self.assertEqual(self.e['y'], -2)
+        self.assertEqual(self.e[self.y], -2)
+        self.assertEqual(self.e['z'], 0)
+        with self.assertRaises(TypeError):
+            self.e[0]
+        with self.assertRaises(TypeError):
+            self.e[self.e]
+
+    def test_coefficients(self):
+        self.assertCountEqual(self.e.coefficients(), [('x', 1), ('y', -2)])
+
+    def test_constant(self):
+        self.assertEqual(self.x.constant, 0)
+        self.assertEqual(self.pi.constant, Fraction(22, 7))
+        self.assertEqual(self.e.constant, 3)
+
+    def test_isconstant(self):
+        self.assertFalse(self.x.isconstant())
+        self.assertTrue(self.pi.isconstant())
+        self.assertFalse(self.e.isconstant())
+
+    def test_values(self):
+        self.assertCountEqual(self.e.values(), [1, -2, 3])
+
+    def test_symbol(self):
+        self.assertEqual(self.x.symbol(), 'x')
+        with self.assertRaises(ValueError):
+            self.pi.symbol()
+        with self.assertRaises(ValueError):
+            self.e.symbol()
+
+    def test_issymbol(self):
+        self.assertTrue(self.x.issymbol())
+        self.assertFalse(self.pi.issymbol())
+        self.assertFalse(self.e.issymbol())
+
+    def test_bool(self):
+        self.assertTrue(self.x)
+        self.assertFalse(self.zero)
+        self.assertTrue(self.pi)
+        self.assertTrue(self.e)
+
+    def test_pos(self):
+        self.assertEqual(+self.e, self.e)
+
+    def test_neg(self):
+        self.assertEqual(-self.e, -self.x + 2*self.y - 3)
+
+    def test_add(self):
+        self.assertEqual(self.x + Fraction(22, 7), self.x + self.pi)
+        self.assertEqual(Fraction(22, 7) + self.x, self.x + self.pi)
+        self.assertEqual(self.x + self.x, 2 * self.x)
+        self.assertEqual(self.e + 2*self.y, self.x + 3)
+
+    def test_sub(self):
+        self.assertEqual(self.x - self.x, 0)
+        self.assertEqual(self.e - 3, self.x - 2*self.y)
+
+    def test_mul(self):
+        self.assertEqual(self.pi * 7, 22)
+        self.assertEqual(self.e * 0, 0)
+        self.assertEqual(self.e * 2, 2*self.x - 4*self.y + 6)
+
+    def test_div(self):
+        with self.assertRaises(ZeroDivisionError):
+            self.e / 0
+        self.assertEqual(self.e / 2, self.x / 2 - self.y + Fraction(3, 2))
+
+    def test_str(self):
+        self.assertEqual(str(self.x), 'x')
+        self.assertEqual(str(-self.x), '-x')
+        self.assertEqual(str(self.pi), '22/7')
+        self.assertEqual(str(self.e), 'x - 2*y + 3')
+
+    def test_repr(self):
+        self.assertEqual(repr(self.e), "Expression({'x': 1, 'y': -2}, 3)")
+
+    @unittest.expectedFailure
+    def test_fromstring(self):
+        self.assertEqual(Expression.fromstring('x'), self.x)
+        self.assertEqual(Expression.fromstring('-x'), -self.x)
+        self.assertEqual(Expression.fromstring('22/7'), self.pi)
+        self.assertEqual(Expression.fromstring('x - 2y + 3'), self.e)
+        self.assertEqual(Expression.fromstring('x - (3-1)y + 3'), self.e)
+        self.assertEqual(Expression.fromstring('x - 2*y + 3'), self.e)
+
+    def test_eq(self):
+        self.assertEqual(self.e, self.e)
+        self.assertNotEqual(self.x, self.y)
+        self.assertEqual(self.zero, 0)
+
+    def test_canonify(self):
+        self.assertEqual((self.x + self.y/2 + self.z/3)._canonify(),
+                6*self.x + 3*self.y + 2*self.z)
+
+
+class TestHelpers(unittest.TestCase):
+
+    def setUp(self):
+        self.x = symbol('x')
+        self.y = symbol('y')
+
+    def test_constant(self):
+        self.assertEqual(constant(3), 3)
+        self.assertEqual(constant('3'), 3)
+        self.assertEqual(constant(Fraction(3, 4)), Fraction(3, 4))
+        self.assertEqual(constant('3/4'), Fraction(3, 4))
+        with self.assertRaises(ValueError):
+            constant('a')
+        with self.assertRaises(TypeError):
+            constant([])
+
+    def test_symbol(self):
+        self.assertEqual(symbol('x'), self.x)
+        self.assertNotEqual(symbol('y'), self.x)
+        with self.assertRaises(TypeError):
+            symbol(0)
+
+    def test_symbols(self):
+        self.assertListEqual(list(symbols('x y')), [self.x, self.y])
+        self.assertListEqual(list(symbols('x,y')), [self.x, self.y])
+        self.assertListEqual(list(symbols(['x', 'y'])), [self.x, self.y])
+
+
+class TestOperators(unittest.TestCase):
+
+    pass
+
+
+class TestPolyhedron(unittest.TestCase):
+
+    pass
+