# CodeQ: an online programming tutor.
# Copyright (C) 2015 UL FRI
#
# This program is free software: you can redistribute it and/or modify it under
# the terms of the GNU Affero General Public License as published by the Free
# Software Foundation, either version 3 of the License, or (at your option) any
# later version.
#
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
# details.
#
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.

from heapq import heappush, heappop
from itertools import chain, count
import math

# A simple priority queue based on the heapq class.
class PQueue(object):
    REMOVED = '<removed-task>'      # placeholder for a removed task

    def __init__(self):
        self.pq = []                         # list of entries arranged in a heap
        self.entry_finder = {}               # mapping of tasks to entries
        self.counter = count()               # unique sequence count
        self.size = 0

    def push(self, task, priority=0):
        'Add a new task or update the priority of an existing task'
        if task in self.entry_finder:
            self.remove(task)
        entry = [priority, next(self.counter), task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)
        self.size += 1

    def remove(self, task):
        'Mark an existing task as REMOVED.  Raise KeyError if not found.'
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED
        self.size -= 1

    def pop(self):
        'Remove and return the lowest priority task. Raise KeyError if empty.'
        while self.pq:
            priority, count, task = heappop(self.pq)
            if task is not self.REMOVED:
                del self.entry_finder[task]
                self.size -= 1
                return task
        return None

    def __len__(self):
        return self.size

# Return [n]th line in [text].
def get_line(text, n):
    lines = text.split('\n')
    if n >= 0 and n < len(lines):
        return lines[n]
    return None

# Does sequence [a] begin with sequence [b]?
def startswith(a, b):
    if len(a) < len(b):
        return False
    return all(x == y for x, y in zip(a, b))

# Does sequence [a] end with sequence [b]?
def endswith(a, b):
    if len(a) < len(b):
        return False
    return all(x == y for x, y in zip(reversed(a), reversed(b)))

# Indent each line in [text] by [indent] spaces.
def indent(text, indent=2):
    return '\n'.join([' '*indent+line for line in text.split('\n')])

# Average in a list.
def avg(l):
    return sum(l)/len(l)

# Logistic function.
def logistic(x, L=1, k=1, x_0=0):
    return L/(1+math.exp(-k*(x-x_0)))

# Damerau-Levenshtein distance between sequences [a] and [b]. Based on
# https://thetaiko.wordpress.com/2011/01/21/damerau-levenshtein-distance-in-python/
def damerau_levenshtein(a, b):
    # Construct an alphabet out of characters in [a] and [b] with a sequential
    # identifier for each word.
    alphabet = {}
    for char in chain(a, b):
        if char not in alphabet:
            alphabet[char] = len(alphabet)

    # Initialize distance matrix.
    inf = len(a) + len(b) + 1
    h = [[0]*(len(b)+2) for i in range(len(a)+2)]
    h[0][0] = inf
    for i in range(0, len(a)+1):
        h[i+1][1] = i
        h[i+1][0] = inf
    for j in range(0, len(b)+1):
        h[1][j+1] = j
        h[0][j+1] = inf

    # Do the magic.
    da = [0 for x in range(0, len(alphabet))]
    for i in range(1, len(a)+1):
        db = 0
        for j in range(1, len(b)+1):
            i1 = da[alphabet[b[j-1]]]
            j1 = db
            d = 1
            if (a[i-1] == b[j-1]):
                d = 0
                db = j
            h[i+1][j+1] = min(
                h[i][j] + d,                      # substitution
                h[i+1][j] + 1,                    # insertion
                h[i][j+1] + 1,                    # deletion
                h[i1][j1] + (i-i1-1)+1+(j-j1-1))  # transposition
        da[alphabet[a[i-1]]] = i

    return h[len(a)+1][len(b)+1]