import math
import Queue
import copy

from BitStream.bitStream import BitStream
from FrequencyCounter.freqCounter import FreqCounter

def numToBytearray(num):
    result = bytearray()
    while num > 0:
        result.insert(0, num % 256)
        num /= 256
    
    return result

def BinaryToUnary(num):  
    return 2 ** num - 1 << 1

def UnaryToBinary(num):
    return int(math.log((num >> 1) + 1, 2))

def encodeNum(num):
    try:
        # num    output
        # 0      0
        # 1      1000
        # 2      1001
        # 3      1010
        # 4      1011
        # 5      1100000
        # 6      1100001
        # 7      1100010
        # 8      1100011
        
        try:
            tmp = 0
            for c in num:
                tmp <<= 8
                tmp += ord(c)
            num = tmp
        except TypeError:
            pass
        
        
        ''' try:
            num = ord(num)
        except TypeError:
            pass'''
        
        if num == 0:
            return BitStream(0, 1)
        
        bits = 0
        total = 0
        
        while total < num:
            # bits    =  0 1 2  3 
            # total   =  0 4 20 276
            # total+1 =  1 5 21 277
            bits += 1
            total += 2**(2**bits) # 4 16 256
            
        total -= 2**(2**bits) - 1

        
        result = BitStream(BinaryToUnary(bits))
        result.push(num - total, 2**bits)
        return result      
    except ValueError:
        return BitStream(0, 1)
    
def decodeNum(stream):
    count = 0
    while stream.pop() == 1:
        count += 1
    
    if count == 0:
        return 0
    
    num = 0
    total = 0
    for i in xrange(2**count):
        num <<= 1
        num += stream.pop()
    
    for i in xrange(count):
        total += 2**(2**i)
        
    return num + total - 1

class BinaryTree:
    def __init__(self, data = None, leftChild = None, rightChild = None):
        self.data = data
        self.left = leftChild
        self.right = rightChild
        
        try:
            length = 0
            for c in data:
                length += 8
            #self.dataLength = int(math.floor(math.log(length,2)) + 1)
            self.dataLength = length
        except (TypeError, ValueError):
            self.dataLength = 1
            
        try:
            leftDataLen = self.left.dataLength
            if leftDataLen > self.dataLength:
                self.dataLength = leftDataLen
        except AttributeError:
            pass
        
        try:
            rightDataLen = self.right.dataLength
            if rightDataLen > self.dataLength:
                self.dataLength = rightDataLen
        except AttributeError:
            pass
        
    def __hash__(self):
        return hash((self.data, self.left, self.right))
    
    def __str__(self):
        return '(%r %s %s)' % (self.data, self.left, self.right)
    
    def __lt__(self, other):
        return self.data < other