"""
1. Закодируйте любую строку из трех слов по алгоритму Хаффмана.
"""
import queue


class HuffmanNode(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def __eq__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True


def getTree(frequencies):
    p = queue.PriorityQueue()
    for item in frequencies:
        p.put(item)

    while p.qsize() > 1:
        left, right = p.get(), p.get()
        node = HuffmanNode(left, right)
        p.put((left[0] + right[0], node))
    return p.get()


def walk_tree(tree, path="", tbl={}):
    if isinstance(tree[1].left[1], HuffmanNode):
        walk_tree(tree[1].left, path + "0", tbl)
    else:
        tbl[tree[1].left[1]] = path + "0"
    if isinstance(tree[1].right[1], HuffmanNode):
        walk_tree(tree[1].right, path + "1", tbl)
    else:
        tbl[tree[1].right[1]] = path + "1"
    return tbl


def getFreq(in_str):
    all_freq = {}
    result = []
    for i in in_str:
        if i in all_freq:
            all_freq[i] += 1
        else:
            all_freq[i] = 1
    for key, value in all_freq.items():
        temp = (value, key)
        result.append(temp)
    return result

def getEncoded(tbl,in_str):
    result = ""
    for ch in in_str:
        result += tbl[ch]
    return result

def getDecoded(tree,in_str):
    result = ""
    node = tree[1]
    for ch in in_str:
        if ch =="0":
            node = node.left[1]
        else:
            node = node.right[1]
        if not isinstance(node, HuffmanNode):
            result += node
            node = tree[1]
    return result

in_str = "beep boop beer!"
freq = getFreq(in_str)

print(freq)
tree = getTree(freq)
tbl = {}
walk_tree(tree, "", tbl)
print(tbl)
coded = getEncoded(tbl,in_str)
print(coded)
print(getDecoded(tree, coded))

ce634bc4ceb1b8a3d30ecc377b285a2ce7325b3b
<mask token>


class HuffmanNode(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def __eq__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True


<mask token>


def walk_tree(tree, path='', tbl={}):
    if isinstance(tree[1].left[1], HuffmanNode):
        walk_tree(tree[1].left, path + '0', tbl)
    else:
        tbl[tree[1].left[1]] = path + '0'
    if isinstance(tree[1].right[1], HuffmanNode):
        walk_tree(tree[1].right, path + '1', tbl)
    else:
        tbl[tree[1].right[1]] = path + '1'
    return tbl


<mask token>


def getEncoded(tbl, in_str):
    result = ''
    for ch in in_str:
        result += tbl[ch]
    return result


<mask token>

<mask token>


class HuffmanNode(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def __eq__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True


def getTree(frequencies):
    p = queue.PriorityQueue()
    for item in frequencies:
        p.put(item)
    while p.qsize() > 1:
        left, right = p.get(), p.get()
        node = HuffmanNode(left, right)
        p.put((left[0] + right[0], node))
    return p.get()


def walk_tree(tree, path='', tbl={}):
    if isinstance(tree[1].left[1], HuffmanNode):
        walk_tree(tree[1].left, path + '0', tbl)
    else:
        tbl[tree[1].left[1]] = path + '0'
    if isinstance(tree[1].right[1], HuffmanNode):
        walk_tree(tree[1].right, path + '1', tbl)
    else:
        tbl[tree[1].right[1]] = path + '1'
    return tbl


def getFreq(in_str):
    all_freq = {}
    result = []
    for i in in_str:
        if i in all_freq:
            all_freq[i] += 1
        else:
            all_freq[i] = 1
    for key, value in all_freq.items():
        temp = value, key
        result.append(temp)
    return result


def getEncoded(tbl, in_str):
    result = ''
    for ch in in_str:
        result += tbl[ch]
    return result


<mask token>

<mask token>


class HuffmanNode(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def __eq__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True


def getTree(frequencies):
    p = queue.PriorityQueue()
    for item in frequencies:
        p.put(item)
    while p.qsize() > 1:
        left, right = p.get(), p.get()
        node = HuffmanNode(left, right)
        p.put((left[0] + right[0], node))
    return p.get()


def walk_tree(tree, path='', tbl={}):
    if isinstance(tree[1].left[1], HuffmanNode):
        walk_tree(tree[1].left, path + '0', tbl)
    else:
        tbl[tree[1].left[1]] = path + '0'
    if isinstance(tree[1].right[1], HuffmanNode):
        walk_tree(tree[1].right, path + '1', tbl)
    else:
        tbl[tree[1].right[1]] = path + '1'
    return tbl


def getFreq(in_str):
    all_freq = {}
    result = []
    for i in in_str:
        if i in all_freq:
            all_freq[i] += 1
        else:
            all_freq[i] = 1
    for key, value in all_freq.items():
        temp = value, key
        result.append(temp)
    return result


def getEncoded(tbl, in_str):
    result = ''
    for ch in in_str:
        result += tbl[ch]
    return result


def getDecoded(tree, in_str):
    result = ''
    node = tree[1]
    for ch in in_str:
        if ch == '0':
            node = node.left[1]
        else:
            node = node.right[1]
        if not isinstance(node, HuffmanNode):
            result += node
            node = tree[1]
    return result


<mask token>
print(freq)
<mask token>
walk_tree(tree, '', tbl)
print(tbl)
<mask token>
print(coded)
print(getDecoded(tree, coded))

<mask token>


class HuffmanNode(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def __eq__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True


def getTree(frequencies):
    p = queue.PriorityQueue()
    for item in frequencies:
        p.put(item)
    while p.qsize() > 1:
        left, right = p.get(), p.get()
        node = HuffmanNode(left, right)
        p.put((left[0] + right[0], node))
    return p.get()


def walk_tree(tree, path='', tbl={}):
    if isinstance(tree[1].left[1], HuffmanNode):
        walk_tree(tree[1].left, path + '0', tbl)
    else:
        tbl[tree[1].left[1]] = path + '0'
    if isinstance(tree[1].right[1], HuffmanNode):
        walk_tree(tree[1].right, path + '1', tbl)
    else:
        tbl[tree[1].right[1]] = path + '1'
    return tbl


def getFreq(in_str):
    all_freq = {}
    result = []
    for i in in_str:
        if i in all_freq:
            all_freq[i] += 1
        else:
            all_freq[i] = 1
    for key, value in all_freq.items():
        temp = value, key
        result.append(temp)
    return result


def getEncoded(tbl, in_str):
    result = ''
    for ch in in_str:
        result += tbl[ch]
    return result


def getDecoded(tree, in_str):
    result = ''
    node = tree[1]
    for ch in in_str:
        if ch == '0':
            node = node.left[1]
        else:
            node = node.right[1]
        if not isinstance(node, HuffmanNode):
            result += node
            node = tree[1]
    return result


in_str = 'beep boop beer!'
freq = getFreq(in_str)
print(freq)
tree = getTree(freq)
tbl = {}
walk_tree(tree, '', tbl)
print(tbl)
coded = getEncoded(tbl, in_str)
print(coded)
print(getDecoded(tree, coded))

"""
1. Закодируйте любую строку из трех слов по алгоритму Хаффмана.
"""
import queue


class HuffmanNode(object):

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def __eq__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True

    def __lt__(self, other):
        if isinstance(other, HuffmanNode):
            return False
        else:
            return True


def getTree(frequencies):
    p = queue.PriorityQueue()
    for item in frequencies:
        p.put(item)

    while p.qsize() > 1:
        left, right = p.get(), p.get()
        node = HuffmanNode(left, right)
        p.put((left[0] + right[0], node))
    return p.get()


def walk_tree(tree, path="", tbl={}):
    if isinstance(tree[1].left[1], HuffmanNode):
        walk_tree(tree[1].left, path + "0", tbl)
    else:
        tbl[tree[1].left[1]] = path + "0"
    if isinstance(tree[1].right[1], HuffmanNode):
        walk_tree(tree[1].right, path + "1", tbl)
    else:
        tbl[tree[1].right[1]] = path + "1"
    return tbl


def getFreq(in_str):
    all_freq = {}
    result = []
    for i in in_str:
        if i in all_freq:
            all_freq[i] += 1
        else:
            all_freq[i] = 1
    for key, value in all_freq.items():
        temp = (value, key)
        result.append(temp)
    return result

def getEncoded(tbl,in_str):
    result = ""
    for ch in in_str:
        result += tbl[ch]
    return result

def getDecoded(tree,in_str):
    result = ""
    node = tree[1]
    for ch in in_str:
        if ch =="0":
            node = node.left[1]
        else:
            node = node.right[1]
        if not isinstance(node, HuffmanNode):
            result += node
            node = tree[1]
    return result

in_str = "beep boop beer!"
freq = getFreq(in_str)

print(freq)
tree = getTree(freq)
tbl = {}
walk_tree(tree, "", tbl)
print(tbl)
coded = getEncoded(tbl,in_str)
print(coded)
print(getDecoded(tree, coded))
