"""This module defines the PCP solver."""

from pcpsolver.util.workingqueue import WorkingQueueType
from pcpsolver.util.workingdeque import WorkingDeque
from pcpsolver.util.workingpriorityqueue import WorkingPriorityQueue


class Node:
    """This class describes a node in the search space."""

    def __init__(self, index=-1, parent=None):
        """Arguments:
           index -- The index of the node, -1 for a root node.
           parent -- The parent node, None for a root node.
        """
        self._index = index
        self._parent = parent

    @property
    def index(self):
        return self._index

    @property
    def parent(self):
        return self._parent

    def path(self):
        n = self
        while n.index >= 0:
            yield n.index
            n = n.parent


class Job:
    """This class describes a job to be done to populate the search space."""

    def __init__(self, node, word, first):
        """Arguments:
           node -- The node to be processed.
           word -- The non-empty word in the word pair associated to the node.
           first -- `True` iff the word stored in the word field is the first
                    component of the word pair associated to the node.
        """
        self._node = node
        self._word = word
        self._first = first

    @property
    def node(self):
        return self._node

    @property
    def word(self):
        return self._word

    @property
    def first(self):
        return self._first

    def __lt__(self, other):
        return len(self.word) < len(other.word)


class PCPSolver:
    """This class describes the PCP solver."""

    def __init__(self, instance, queue_type):
        self._instance = instance

        if queue_type is WorkingQueueType.deque:
            self._working_queue = WorkingDeque()
        elif queue_type is WorkingQueueType.priority_queue:
            self._working_queue = WorkingPriorityQueue()

        self._solution = None

    def run(self):
        while not self._working_queue.closed:
            job = self._working_queue.take()

            if job:
                for i in range(len(self._instance.index_names)):
                    wordpair = self._instance.word_pairs[i]
                    first_word = (
                        job.word + wordpair[0] if job.first else wordpair[0])
                    second_word = (
                        wordpair[1] if job.first else job.word + wordpair[1])

                    suffix = get_suffix(first_word, second_word)
                    if suffix is not None:
                        if not suffix:
                            # We have found a solution.
                            self._solution = Node(i, job.node)
                            self._working_queue.close()
                            break

                        self._working_queue.enqueue(
                            Job(Node(i, job.node),
                                suffix,
                                len(first_word) > len(second_word)))

    def solve(self):
        """This method solves the given PCP instance.

           Note that the function does not necessarily return if there is not
           solution.

           If a solution is found, it returns it as list of index names.
           Otherwise, it returns an empty list.
        """

        # Initialise the working queue with the starting job.
        self._working_queue.enqueue(Job(Node(), "", True))

        # Process the working queue until it is empty or a solution is found.
        self.run()

        if self._solution:
            s = [self._instance.index_names[i] for i in self._solution.path()]
            s.reverse()
            return s
        else:
            return []


def get_suffix(first_word, second_word):
    """This function the (possibly empty) suffix of the longer word, if the
       shorter word is a prefix of it.  Otherwise it returns `None`.
    """
    if len(first_word) <= len(second_word):
        if second_word.startswith(first_word):
            return second_word[len(first_word):]
        return None

    return get_suffix(second_word, first_word)
