#!/usr/bin/env python3
"""Provisional node-level recoding of observed Linux Huff_addRef/increment semantics."""
class Node:
    __slots__=('index','left','right','parent','next','previous','head','weight','symbol')
    def __init__(self,index,symbol=0,weight=0):
        self.index=index;self.symbol=symbol;self.weight=weight
        self.left=self.right=self.parent=self.next=self.previous=self.head=None


class Huffman:
    def __init__(self,second=False):
        self.nodes=[Node(0,256)];self.root=self.nyt=self.nodes[0];self.lookup={256:self.nyt};self.cells=[];self.free=None;self.second=second;self.events={}
    def event(self,name):self.events[name]=self.events.get(name,0)+1
    def allocate_cell(self,node):
        if self.free is None:i=len(self.cells);self.cells.append(node);self.event('cell_allocate')
        else:i=self.free;self.free=self.cells[i];self.cells[i]=node;self.event('cell_reuse')
        return i
    def free_cell(self,i):self.cells[i]=self.free;self.free=i;self.event('cell_free')
    def swap_tree(self,a,b):
        pa,pb=a.parent,b.parent
        if pa:
            if pa.left is a:pa.left=b
            else:pa.right=b
        else:self.root=b
        if pb:
            if pb.left is b:pb.left=a
            else:pb.right=a
        else:self.root=a
        a.parent,b.parent=pb,pa;self.event('tree_swap')
    def swap_list(self,a,b):
        a.next,b.next=b.next,a.next;a.previous,b.previous=b.previous,a.previous
        if a.next is a:a.next=b
        if b.next is b:b.next=a
        for n in [a,b]:
            if n.next:n.next.previous=n
            if n.previous:n.previous.next=n
        self.event('list_swap')
    def increment(self,node):
        if node is None:self.event('null_increment');return
        if node.next and node.next.weight==node.weight:
            self.event('equal_next');leader=self.cells[node.head]
            if leader is not node.parent:self.swap_tree(leader,node)
            else:self.event('leader_is_parent')
            self.swap_list(leader,node)
        if node.previous and node.previous.weight==node.weight:self.cells[node.head]=node.previous;self.event('old_head_previous')
        else:self.free_cell(node.head)
        node.weight=(node.weight+1)&0xffffffff
        if node.next and node.next.weight==node.weight:node.head=node.next.head;self.event('new_head_shared')
        else:node.head=self.allocate_cell(node)
        if node.parent:
            self.increment(node.parent)
            if node.previous is node.parent:
                self.event('post_parent_adjacent');parent=node.parent;self.swap_list(node,parent)
                if self.cells[node.head] is node:self.cells[node.head]=parent;self.event('post_parent_head')
    def add(self,symbol):
        symbol&=255
        if symbol in self.lookup:self.event('existing');self.increment(self.lookup[symbol]);return
        self.event('new');leaf=Node(len(self.nodes),symbol,1);internal=Node(len(self.nodes)+1,257,1);self.nodes.extend([leaf,internal]);nyt=self.nyt
        internal.next=nyt.next
        if internal.next:
            internal.next.previous=internal
            if internal.next.weight==1:internal.head=internal.next.head
            else:internal.head=self.allocate_cell(internal)
        else:internal.head=self.allocate_cell(internal)
        nyt.next=internal;internal.previous=nyt
        leaf.next=nyt.next;leaf.next.previous=leaf;leaf.head=leaf.next.head;nyt.next=leaf;leaf.previous=nyt
        parent=nyt.parent
        if parent:
            if parent.left is nyt:parent.left=internal
            else:parent.right=internal
        else:self.root=internal
        internal.left=nyt;internal.right=leaf;internal.parent=parent;leaf.parent=nyt.parent=internal;self.lookup[symbol]=leaf;self.increment(parent)
    def codewords(self):
        out={}
        def walk(n,bits):
            if n.symbol!=257:out[n.symbol]=bits;return
            walk(n.left,bits+[0]);walk(n.right,bits+[1])
        walk(self.root,[]);return out
    def state(self,base=0x10000):
        def addr(n):return 0 if n is None else base+0x830+56*n.index
        def cell(i):return 0 if i is None else base+0xb030+8*i
        nodes=[{'index':n.index,'address':addr(n),'left':addr(n.left),'right':addr(n.right),'parent':addr(n.parent),'next':addr(n.next),'previous':addr(n.previous),'head_cell':cell(n.head),'weight':n.weight,'symbol':n.symbol} for n in self.nodes]
        heads=sorted({n.head for n in self.nodes if n.head is not None})
        values=[addr(v) if isinstance(v,Node) else cell(v) for v in self.cells]
        return {'node_count':len(nodes),'pointer_cell_count':len(self.cells),'root':addr(self.root),'list_start':addr(self.nyt),'tail_slot':addr(self.nyt) if self.second else 0,'free_head':cell(self.free),'nodes':nodes,'heads':[[cell(i),addr(self.cells[i])] for i in heads],'pointer_cells':values,'lookup':[[s,addr(n)] for s,n in sorted(self.lookup.items())]}