class Executor(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def execute(self, y_toks, old_denotation=None):
        """Return the intermediate denotation of the formula.

        Args:
            y_toks (list[Predicate]): the formula fragment to be executed
            old_denotation (Denotation): If specified, continue execution
                from this intermediate denotation.
        Returns:
            Denotation
            The denotation is not finalized.
        Throws:
            Exception if the formula is malformed.
        """
        raise NotImplementedError

    def execute_predicate(self, predicate, old_denotation=None):
        """Return the denotation of the formula.

        This method takes only a single Predicate object as the argument.
        This allows more optimization to be performed.

        Args:
            predicate (Predicate): the next predicate
            old_denotation (Denotation): If specified, continue execution
                from this intermediate denotation.
        Returns:
            Denotation
            The denotation is not finalized.
        Throws:
            Exception if the formula is malformed.
        """
        # Default: call execute
        return self.execute([predicate], old_denotation)

    @abstractmethod
    def finalize(self, denotation):
        """Given a Denotation, return its finalized form as list[Value].

        Args:
            denotation (Denotation)
        Returns:
            list[Value] or None
        Raises:
            ValueError if the denotation cannot be finalized
        """
        raise NotImplementedError class Denotation(object):
    """Intermediate denotation."""
    __metaclass__ = ABCMeta

    @abstractproperty
    def utterance_idx(self):
        """Current the utterance index (int).

        Should be incremented every time an end-of-utterance predicate
        or its equivalence is executed.
        """
        raise NotImplementedError class Predicate(ComparableMixin):
    """Represents a step in the logical form (i.e., an output token)."""

    __slots__ = ['_name', '_original_string', '_types']

    def __init__(self, name, original_string=None, types=None):
        """Create Predicate.

        Args:
            name (unicode)
            original_string (unicode)
            types (tuple[unicode])
        """
        self._name = name
        self._original_string = original_string
        self._types = types or tuple()

    def __eq__(self, other):
        return (isinstance(other, Predicate)
                and self._name == other._name)

    def __hash__(self):
        return hash(self._name)

    @property
    def _cmpkey(self):
        return self._name

    def __str__(self):
        return self._name
    __repr__ = __str__

    @property
    def name(self):
        """Name of the predicate.
        Should be unique among the predicates in the same context.

        Returns:
            unicode
        """
        return self._name

    @property
    def original_string(self):
        """Original string of the predicate. Can be None.

        Returns:
            unicode or None
        """
        return self._original_string

    @property
    def types(self):
        """A collection of types.

        Returns:
            tuple[unicode]
        """
        return self._types

    @property
    def delexicalized_name(self):
        """A placeholder used in a delexicalized utterance.
        Can be None if the predicate should not be used for delexicalization.

        A subclass can customize this method to return different placeholders
        for different predicate types.

        Returns:
            unicode or None
        """
        return 'PRED' EOU = '<EOU>' class Value(object):
    """A value represents an item in either a denotation (gold or predicted)"""
    __metaclass__ = ABCMeta

    @abstractmethod
    def match(self, other):
        """Return True if the value matches the other value based on the
        official criteria.

        Args:
            other (Value)
        Returns:
            a boolean
        """
        pass

    def train_match(self, other):
        """Return a boolean of whether self and other are considered
        equal at train time. This can be used to encourage the model to
        predict values with the right type.

        The default is to use match.

        Args:
            other: Value
        """
        return self.match(other) def parse_number(x):
    """Parse a number from a string."""
    return round(float(x), 6) def parse_date(x):
    """Parse a date from a string with format yy-mm-dd."""
    x = x.split('-')
    assert len(x) == 3, 'Not a valid date: {}'.format(x)
    year = -1 if x[0][0].lower() == 'x' else int(x[0])
    month = -1 if x[1][0].lower() == 'x' else int(x[1])
    day = -1 if x[2][0].lower() == 'x' else int(x[2])
    return Date(year, month, day) class Date(object):
    """A date consisting of a year, a month, and a day.
    Some but not all fields can be absent (using placeholder -1)
    """

    def __init__(self, year, month, day):
        if year == -1 and month == -1 and day == -1:
            raise ValueError('Invalid date (-1 -1 -1)')
        self.year = year
        self.month = month
        self.day = day
        assert month == -1 or 1 <= month <= 12, 'Invalid month: {}'.format(month)
        assert day == -1 or 1 <= day <= 31, 'Invalid day: {}'.format(day)
        self._hash = hash((self.year, self.month, self.day))

    def __str__(self):
        return 'Date({}, {}, {})'.format(self.year, self.month, self.day)
    __repr__ = __str__

    def __eq__(self, other):
        if not isinstance(other, Date):
            return False
        return (self.year == other.year
                and self.month == other.month
                and self.day == other.day)

    def __hash__(self):
        return self._hash

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

    def __cmp__(self, other):
        if not isinstance(other, Date):
            raise ValueError('Cannot compare Date to {}'.format(type(other)))
        if self.year == other.year or self.year == -1 or other.year == -1:
            if self.month == other.month or self.month == -1 or other.month == -1:
                if self.day == other.day or self.day == -1 or other.day == -1:
                    return 0
                return cmp(self.day, other.day)
            return cmp(self.month, other.month)
        return cmp(self.year, other.year) def ensure_same_type(collection, allowed_types=None):
    """Ensure that all values in the collection have the same type.
    Return the agreed type. Throw an error if the type is not agreed.

    Args:
        collection: A set or a dict where values are sets.
        allowed_types: Restriction on the agreed type.
            Can be a string, a collection of strings, or None (= allow all).
    Returns:
        The agreed type
    Throws:
        ValueError if one of the following happens:
        - The collection is not a set or a set-valued dict
        - The collection is empty
        - Some two items have different types
        - Some item does not agree with the allowed types (if specified)
    """
    if isinstance(collection, set):
        itr = iter(collection)
    elif isinstance(collection, dict):
        # Iterate over all items in values
        itr = (x for v in collection.itervalues() for x in v)
    else:
        raise ValueError('Bad data type: {}'.format(type(collection)))
    if allowed_types and isinstance(allowed_types, basestring):
        allowed_types = [allowed_types]
    agreed_type = None
    for value in itr:
        if agreed_type is None:
            agreed_type = get_type(value)
            if allowed_types is not None and agreed_type not in allowed_types:
                raise ValueError('Type {} is not in allowed types {}'\
                        .format(agreed_type, allowed_types))
        else:
            t = get_type(value)
            if t != agreed_type:
                raise ValueError('Value {} does not have agreed type {}'\
                        .format(value, agreed_type))
    if agreed_type is None:
        raise ValueError('The collection is empty: {}'.format(collection))
    return agreed_type class InfiniteSet(ContainerABC):
    """An abstract class representing an infinite set of items."""

    def __and__(self, stuff):
        if isinstance(stuff, set):
            return {x for x in stuff if x in self}
        raise NotImplementedError

    def __rand__(self, stuff):
        return self & stuff class NeqInfiniteSet(InfiniteSet):
    """Represent (!= xxx).

    Note that the semantics of (!= xxx) is
    "things that are not xxx but have the same type as xxx"
    """

    def __init__(self, value):
        assert isinstance(value, THINGS), 'Invalid value for !=: {}'.format(value)
        self.value = value
        self.value_type = get_type(value)

    def __eq__(self, other):
        return (isinstance(other, NeqInfiniteSet)
                and self.value == other.value)

    def __hash__(self):
        return 12345 + hash(self.value)

    def __repr__(self):
        return '{{ != {} }}'.format(self.value)

    def __contains__(self, x):
        # Need to type check
        return x != self.value and get_type(x) == self.value_type class RangeInfiniteSet(InfiniteSet):
    """Represent ranges like (> xxx) or (and (> xxx) (< yyy)).

    xxx, yyy can be numbers or dates, but the types must agree.
    """

    def __init__(self, sign, value, sign2=None, value2=None):
        self.left_sign = self.left_value = None
        self.right_sign = self.right_value = None
        assert isinstance(value, COMPARABLES), \
                'Invalid value for comparison: {}'.format(value)
        self.value_type = get_type(value)
        if sign in ('>', '>='):
            self.left_sign = sign
            self.left_value = value
        elif sign in ('<', '<='):
            self.right_sign = sign
            self.right_value = value
        else:
            raise NotImplementedError(sign)
        if sign2 is not None:
            assert self.value_type == get_type(value2), \
                    'Invalid value for comparison: {}'.format(value2)
            if sign2 in ('>', '>='):
                assert self.left_sign is None
                self.left_sign = sign2
                self.left_value = value2
            elif sign2 in ('<', '<='):
                assert self.right_sign is None
                self.right_sign = sign2
                self.right_value = value2
            else:
                raise NotImplementedError(sign2)

    def __eq__(self, other):
        return (isinstance(other, RangeInfiniteSet)
                and self.left_sign == other.left_sign
                and self.right_sign == other.right_sign
                and self.left_value == other.left_value
                and self.right_value == other.right_value)

    def __hash__(self):
        return hash((self.left_sign, self.right_sign, self.left_value, self.right_value))

    def __repr__(self):
        if self.left_sign is None:
            return '{{ {} {} }}'.format(self.right_sign, self.right_value)
        if self.left_sign is None:
            return '{{ {} {} }}'.format(self.left_sign, self.left_value)
        else:
            return '{{ {} {} ; {} {} }}'.format(
                    self.left_sign, self.left_value,
                    self.right_sign, self.right_value)

    def __contains__(self, x):
        if self.value_type != get_type(x):
            return False
        if self.left_sign:
            if ((self.left_sign == '>' and x <= self.left_value)
                    or (self.left_sign == '>=' and x < self.left_value)):
                return False
        if self.right_sign:
            if ((self.right_sign == '<' and x >= self.right_value)
                    or (self.right_sign == '<=' and x > self.right_value)):
                return False
        return True

    def __and__(self, stuff):
        try:
            return super(RangeInfiniteSet, self).__and__(stuff)
        except NotImplementedError:
            if isinstance(stuff, RangeInfiniteSet):
                # ULTIMATE RANGE MERGE!!!
                assert self.value_type == stuff.value_type,\
                        'Incompatible types: {} and {}'.format(self.value_type, stuff.value_type)
                # Left
                if (not self.left_sign
                        or (stuff.left_sign and (
                            stuff.left_value > self.left_value
                            or (stuff.left_value == self.left_value
                                and stuff.left_sign == '>')))):
                    new_left_sign = stuff.left_sign
                    new_left_value = stuff.left_value
                else:
                    new_left_sign = self.left_sign
                    new_left_value = self.left_value
                # Right
                if (not self.right_sign
                        or (stuff.right_sign and (
                            stuff.right_value < self.right_value
                            or (stuff.right_value == self.right_value
                                and stuff.right_sign == '<')))):
                    new_right_sign = stuff.right_sign
                    new_right_value = stuff.right_value
                else:
                    new_right_sign = self.right_sign
                    new_right_value = self.right_value
                # Return value
                if not new_left_sign:
                    if not new_right_sign:
                        return set()
                    return RangeInfiniteSet(new_right_sign, new_right_value)
                elif not new_right_sign:
                    return RangeInfiniteSet(new_left_sign, new_left_value)
                if new_left_value > new_right_value:
                    return set()
                elif new_left_value == new_right_value:
                    if new_left_sign == '>' or new_right_sign == '<':
                        return set()
                    return {new_left_value}
                else:
                    return RangeInfiniteSet(new_left_sign, new_left_value,
                            new_right_sign, new_right_value) class GenericDateInfiniteSet(InfiniteSet):
    """Represent a generic date where a year, month, or day is left unspecified.

    For example, (-1 7 -1) represents the set of all dates with month = 7,
    and (1990 7 -1) is the set of dates with year = 1990 and month = 7.
    """

    def __init__(self, date):
        self.year = date.year
        self.month = date.month
        self.day = date.day

    def __eq__(self, other):
        return (isinstance(other, GenericDateInfiniteSet)
                and self.year == other.year
                and self.month == other.month
                and self.day == other.day)

    def __hash__(self):
        return hash((self.year, self.month, self.day))

    def __repr__(self):
        return '{{ {} {} {} }}'.format(self.year, self.month, self.day)

    def __contains__(self, x):
        if not isinstance(x, Date):
            return False
        return (self.year in (-1, x.year)
                and self.month in (-1, x.month)
                and self.day in (-1, x.day))

    def min_(self):
        # Note that the returned value might not be a valid date.
        # The value is nevertheless ok for comparison.
        if self.day != -1:      # ....-..-07
            return Date(self.year, self.month, self.day)
        if self.month != -1:    # ....-07-xx
            return Date(self.year, self.month, 1)
        if self.year != -1:     # 1907-xx-xx
            return Date(self.year, 1, 1)

    def max_(self):
        if self.day != -1:      # ....-..-07
            return Date(self.year, self.month, self.day)
        if self.month != -1:    # ....-07-xx
            if self.month == 2:
                if self.year % 4 == 0 and self.year % 400 != 0:
                    num_days = 29
                else:
                    num_days = 28
            elif self.month in (1, 3, 5, 7, 8, 10, 12):
                num_days = 31
            else:
                num_days = 30
            return Date(self.year, self.month, num_days)
        if self.year != -1:     # 1907-xx-xx
            return Date(self.year, 12, 31) class TablesKnowledgeGraph(object):
    """A knowledge graph constructed from a table."""

    # Whether to start the row indices from 1 (default) or 0 (legacy).
    FIRST_ROW_INDEX = 1

    def __init__(self, fin, name=None):
        """Construct a TablesKnowledgeGraph from a CoreNLP-tagged table TSV file.
        Each line in the TSV file describe a cell in the context table.

        The following fields must be present:
        - row: Row index (-1 = header row, body row index starts from 0)
        - col: Column index (starts from 0)
        - id: ID of the cell
        - content: Original string content of the cell

        The following fields are optional:
        - number: Possible number normalization ("40 cakes" --> 40)
        - date: Possible date normalization ("Jan 5" --> xx-01-05)
        - num2: Possible second-number normalization ("3-1" --> 1)
        - list and listID: Possible list normalization
            ("Apple, Banana, Orange" --> Apple|Banana|Orange)
            listID contains the ID of the list items,
            while list contains the original strings

        Args:
            fin: A filename string or a file object.
            name: Unique identifier
        """
        if isinstance(fin, basestring):
            with open(fin) as fin_file:
                self.__init__(fin_file, name=(name or fin))
            return
        self._name = name or (fin.name if hasattr(fin, 'name') else str(fin))
        # Map from relation -> [{first -> seconds}, {second -> firsts}]
        self._relations = {}
        # Map from id -> original string
        self._original_strings = {}
        # Set of all row IDs
        self._rows = set()
        # List of column IDs
        self._columns = []
        # _grid[i][j] = cell id at row i column j
        self._grid = []
        # Now fin is a file object
        current_row, current_row_id = None, None
        header = fin.readline().rstrip('\n').split('\t')
        for line in fin:
            line = line.rstrip('\n').split('\t')
            if len(line) < len(header):
                line.extend([''] * (len(header) - len(line)))
            record = dict(zip(header, line))
            if record['row'] == '-1':
                # column headers
                self._columns.append(record['id'])
                self._original_strings[record['id']] = tsv_unescape(record['content'])
                self._original_strings['!' + record['id']] = tsv_unescape(record['content'])
            else:
                # normal cell
                # Define a bunch of knowledge graph edges.
                row, col = int(record['row']), int(record['col'])
                if current_row != row:
                    current_row = row
                    actual_row_index = current_row + self.FIRST_ROW_INDEX
                    previous_row_id = current_row_id
                    current_row_id = 'fb:row.r{}'.format(actual_row_index)
                    if previous_row_id is not None:
                        # Row --> Next Row relation
                        self._add_relation(REL_NEXT, previous_row_id, current_row_id)
                    # Row --> Index relation
                    self._add_relation(REL_INDEX, current_row_id, float(actual_row_index))
                    self._rows.add(current_row_id)
                    self._grid.append([])
                # Assume that the cells are listed in the correct order
                assert len(self._grid[row]) == col
                self._grid[row].append(record['id'])
                self._original_strings[record['id']] = tsv_unescape(record['content'])
                # Row --> Cell relation
                self._add_relation(self._columns[col], current_row_id, record['id'])
                # Normalization relations
                if record.get('number'):
                    for second in (parse_number(x) for x in record['number'].split('|')):
                        self._add_relation(REL_NUMBER, record['id'], second)
                if record.get('date'):
                    for second in (parse_date(x) for x in record['date'].split('|')):
                        self._add_relation(REL_DATE, record['id'], second)
                if record.get('num2'):
                    for second in (parse_number(x) for x in record['num2'].split('|')):
                        self._add_relation(REL_NUM2, record['id'], second)
                if record.get('listId'):
                    list_ids = record['listId'].split('|')
                    for second in list_ids:
                        self._add_relation(REL_PART, record['id'], second)
                    # Original strings for listIds
                    list_strings = tsv_unescape_list(record['list'])
                    for list_id, list_string in zip(list_ids, list_strings):
                        self._original_strings[list_id] = list_string

    def _add_relation(self, relation, first, second):
        """Internal function for adding a knowledge graph edge (x, r, y).

        Args:
            relation: Relation r (string)
            first: Entity x (string, number, or date)
            second: Entity y (string, number, or date)
        """
        mapping = self._relations.setdefault(relation, [{}, {}])
        mapping[0].setdefault(first, set()).add(second)
        mapping[1].setdefault(second, set()).add(first)

    ################################
    # Queries

    @property
    def name(self):
        return self._name

    def __str__(self):
        return '<TablesKnowledgeGraph {}>'.format(self._name.encode('utf8', 'ignore'))
    __repr__ = __str__

    @property
    def executor(self):
        try:
            return self._executor
        except AttributeError:
            # Import here to prevent recursive import
            from strongsup.tables.executor import TablesPostfixExecutor
            self._executor = TablesPostfixExecutor(self)
            return self._executor

    def join(self, relation, seconds):
        """Return the set of all x such that for some y in seconds,
        (x, relation, y) is in the graph.

        Note that the shorthand reversed relations (e.g., !fb:row.row.name) does not work.

        Args:
            relation (basestring): relation r
            seconds (set, InfiniteSet, or list): the set of y's
        Returns:
            the set of x's
        """
        second_to_firsts = self._relations.get(relation, [{}, {}])[1]
        if isinstance(seconds, (list, set)):
            return set(chain.from_iterable(second_to_firsts.get(y, []) for y in seconds))
        elif isinstance(seconds, InfiniteSet):
            return set(chain.from_iterable(xs for (y, xs) in second_to_firsts.iteritems() if y in seconds))
        else:
            raise NotImplementedError, '? . {} . {}'.format(relation, seconds)

    def reversed_join(self, relation, firsts):
        """Return the collection of all y such that for some x in firsts,
        (x, relation, y) is in the graph.

        Note that the shorthand reversed relations (e.g., !fb:row.row.name) does not work.

        Args:
            relation (basestring): Relation r (string)
            firsts (set, InfiniteSet, or list): the set of x's
        Returns:
            the set of y's
        """
        first_to_seconds = self._relations.get(relation, [{}, {}])[0]
        if isinstance(firsts, (list, set)):
            return set(chain.from_iterable(first_to_seconds.get(x, []) for x in firsts))
        elif isinstance(firsts, InfiniteSet):
            return set(chain.from_iterable(ys for (x, ys) in first_to_seconds.iteritems() if x in firsts))
        else:
            raise NotImplementedError, '{} . {} . ?'.format(firsts, relation)

    @property
    def all_rows(self):
        """Return the set of all rows fb:row.r0, ..., fb:row.r(M-1)"""
        return self._rows

    @property
    def all_columns(self):
        """Return the set of all column IDs"""
        return set(self._columns)

    def has_id(self, id_):
        return id_ in self._original_strings

    def original_string(self, id_):
        """Return the original string (e.g., fb:cell.obama --> "Obama")"""
        return self._original_strings[id_] class StringValue(Value):

    def __init__(self, content):
        assert isinstance(content, basestring)
        self._normalized = normalize(content)
        self._hash = hash(self._normalized)

    def __eq__(self, other):
        return (isinstance(other, StringValue)
                and self._normalized == other._normalized)

    def __hash__(self):
        return self._hash

    def __str__(self):
        return 'S' +  str([self._normalized])
    __repr__ = __str__

    def match(self, other):
        assert isinstance(other, Value)
        return self._normalized == other._normalized class NumberValue(Value):

    def __init__(self, amount, original_string=None):
        assert isinstance(amount, (int, long, float))
        if abs(amount - round(amount)) < 1e-6:
            self._amount = int(amount)
        else:
            self._amount = float(amount)
        if not original_string:
            self._normalized = unicode(self._amount)
        else:
            self._normalized = normalize(original_string)
        self._hash = hash(self._amount)

    def __eq__(self, other):
        return (isinstance(other, NumberValue)
                and self._amount == other._amount)

    def __hash__(self):
        return self._hash

    def match(self, other):
        assert isinstance(other, Value)
        if self._normalized == other._normalized:
            return True
        if isinstance(other, NumberValue):
            return abs(self._amount - other._amount) < 1e-6
        return False

    def __str__(self):
        return ('N(%f)' % self._amount) + str([self._normalized])
    __repr__ = __str__

    @staticmethod
    def parse(text):
        """Try to parse into a number.

        Return:
            the number (int or float) if successful; otherwise None.
        """
        try:
            return int(text)
        except:
            try:
                amount = float(text)
                assert not isnan(amount) and not isinf(amount)
                return amount
            except:
                return None class DateValue(Value):

    def __init__(self, year, month, day, original_string=None):
        """Create a new DateValue. Placeholders are marked as -1."""
        assert isinstance(year, int)
        assert isinstance(month, int) and (month == -1 or 1 <= month <= 12)
        assert isinstance(day, int) and (day == -1 or 1 <= day <= 31)
        assert not (year == month == day == -1)
        self._year = year
        self._month = month
        self._day = day
        if not original_string:
            self._normalized = '{}-{}-{}'.format(
                year if year != -1 else 'xx',
                month if month != -1 else 'xx',
                day if day != '-1' else 'xx')
        else:
            self._normalized = normalize(original_string)
        self._hash = hash((self._year, self._month, self._day))

    def __eq__(self, other):
        return (isinstance(other, DateValue)
                and self._year == other._year
                and self._month == other._month
                and self._day == other._day)

    def __hash__(self):
        return self._hash

    def __str__(self):
        return (('D(%d,%d,%d)' % (self._year, self._month, self._day))
                + str([self._normalized]))
    __repr__ = __str__

    def match(self, other):
        assert isinstance(other, Value)
        if self._normalized == other._normalized:
            return True
        if isinstance(other, DateValue):
            return (self._year == other._year
                    and self._month == other._month
                    and self._day == other._day)
        return False

    @staticmethod
    def parse(text):
        """Try to parse into a date.

        Return:
            tuple (year, month, date) if successful; otherwise None.
        """
        try:
            ymd = text.lower().split('-')
            assert len(ymd) == 3
            year = -1 if ymd[0] in ('xx', 'xxxx') else int(ymd[0])
            month = -1 if ymd[1] == 'xx' else int(ymd[1])
            day = -1 if ymd[2] == 'xx' else int(ymd[2])
            assert not (year == month == day == -1)
            assert month == -1 or 1 <= month <= 12
            assert day == -1 or 1 <= day <= 31
            return (year, month, day)
        except:
            return None
from gtd.utils import cached_property
from strongsup.executor import Executor, Denotation
from strongsup.predicate import Predicate
from strongsup.utils import EOU
from strongsup.value import Value
from strongsup.tables.structure import (
        parse_number,
        parse_date,
        Date,
        ensure_same_type,
        InfiniteSet,
        NeqInfiniteSet,
        RangeInfiniteSet,
        GenericDateInfiniteSet,
        )
from strongsup.tables.graph import TablesKnowledgeGraph
from strongsup.tables.value import StringValue, NumberValue, DateValue
                denotation._utterance_idx = old_utterance_idx
        return denotation

    INVALID_FINAL_DENOTATION = ValueError('Invalid final denotation')

    def finalize(self, denotation):
        """Return the finalized denotation as list[Value]."""
        if (len(denotation) != 1
                or not isinstance(denotation[0], set)
                or not denotation[0]):
            raise TablesPostfixExecutor.INVALID_FINAL_DENOTATION
        values = []
        for item in denotation[0]:
            if isinstance(item, basestring):
                if not self.graph.has_id(item):
                    raise TablesPostfixExecutor.INVALID_FINAL_DENOTATION
                values.append(StringValue(self.graph.original_string(item)))
            elif isinstance(item, float):
                values.append(NumberValue(item))
            elif isinstance(item, Date):
                values.append(DateValue(item.year, item.month, item.day))
            else:
                # This should not happen.
                assert False, "Unknown item type: {}".format(item)
        return values

    ################################
    # Internal methods

    def apply(self, predicate, stack):
        """Apply the predicate to the stack. The stack is modified in-place.

        Args:
            predicate (basestring): The next predicate to apply.
            stack (TablesDenotation): The current execution stack
        """
        # Predefined operations
        if predicate in AGGREGATES:
            arg = stack.pop()
            stack.append(self.apply_aggregate(predicate, arg))
        elif predicate in MERGES:
            arg2 = stack.pop()
            arg1 = stack.pop()
            stack.append(self.apply_merge_arith(predicate, arg1, arg2))
        elif predicate in BEGIN_GROWS:
            arg = stack.pop()
            stack.append(self.apply_begin_grow(predicate, arg))
        elif predicate in END_GROWS:
            arg = stack.pop()
            stack.append(self.apply_end_grow(predicate, arg))
        # Assert
        elif predicate.startswith(ASSERT_PREFIX):
            unary = predicate[len(ASSERT_PREFIX):]
            assert is_unary(unary)
            self.apply_assert(unary, stack[-1])
        # Unary or Binary
        elif predicate == TYPE_ROW:
            stack.append(self.apply_type_row(predicate))
        elif is_unary(predicate):
            stack.append(self.apply_unary(predicate))
        elif is_binary(predicate):
            arg = stack.pop()
            stack.append(self.apply_join_fast(predicate, arg))
        else:
            raise ValueError('Unknown predicate {}'.format(predicate))
        # Optional: Check if the partial denotation is empty.
        if self.forbid_partial_empty:
            if (not stack[-1] or (isinstance(stack[-1], dict) and
                all(not x for x in stack[-1].itervalues()))):
                raise self.EMPTY_EXCEPTION

    EMPTY_EXCEPTION = ValueError('Denotation is empty!')

    ################################
    # Operators

    def apply_unary(self, predicate):
        unary = parse_unary(predicate)
        if (isinstance(unary, Date) and
                (unary.year == -1 or unary.month == -1 or unary.day == -1)):
            return GenericDateInfiniteSet(unary)
        else:
            return {unary}

    def apply_type_row(self, predicate):
        return self.graph.all_rows

    @handle_dict_1arg
    def apply_join(self, predicate, arg):
        assert isinstance(predicate, basestring), unicode(predicate)
        assert isinstance(arg, (set, InfiniteSet)), unicode(arg)
        if predicate in SPECIAL_BINARIES:
            if predicate == '!=':
                assert len(arg) == 1, '{} takes exactly 1 object; got {}'.format(predicate, arg)
                thing = next(iter(arg))
                return NeqInfiniteSet(thing)
            elif predicate in ('<', '<=', '>', '>='):
                if isinstance(arg, GenericDateInfiniteSet):
                    arg = [arg.min_()] if predicate in ('<', '>=') else [arg.max_()]
                assert len(arg) == 1, '{} takes exactly 1 object; got {}'.format(predicate, arg)
                thing = next(iter(arg))
                return RangeInfiniteSet(predicate, thing)
            else:
                raise NotImplementedError(predicate)
        elif is_binary_name(predicate):
            return self.graph.join(predicate, arg)
        elif is_reversed_binary_name(predicate):
            return self.graph.reversed_join(predicate[1:], arg)
        else:
            raise NotImplementedError(predicate)

    JOIN_EXCEPTION = ValueError('Join Exception!')

    def apply_join_fast(self, predicate, arg):
        if predicate == '!=':
            if isinstance(arg, dict):
                answer = {}
                for key, thing in arg.iteritems():
                    if len(thing) != 1:
                        raise self.JOIN_EXCEPTION

                    answer[key] = NeqInfiniteSet(next(iter(thing)))