lzw

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class LZWTree
{
    protected class Node
    {
        private char letter;
        private Node leftZeroChild, rightOneChild;

        public Node(char b = '\\')
        {
            this.letter = b;
        }

        public char Letter
        {
            get { return this.letter; }
            private set { }
        }

        public Node LeftZeroChild
        {
            get { return this.leftZeroChild; }
            set { this.leftZeroChild = value; }
        }

        public Node RightOneChild
        {
            get { return this.rightOneChild;  }
            set { this.rightOneChild = value; }
        }
    }

    public LZWTree()
    {
        currentNode = root;
    }

    public void insert(char b)
    {
        if ('0' == b)
        {
            if (null == currentNode.LeftZeroChild)
            {
                currentNode.LeftZeroChild = new Node('0');
                currentNode = root;
            }
            else
                currentNode = currentNode.LeftZeroChild;
        }
        else
        {
            if (null == currentNode.RightOneChild)
            {
                currentNode.RightOneChild = new Node('1');
                currentNode = root;
            }
            else
                currentNode = currentNode.RightOneChild;
        }
    }

    public void print(System.IO.StreamWriter output)
    {
       depth = 0;
       print(root, output);
    }

    public int getDepth()
    {
        depth = maxDepth = 0;
        _getDepth(root);
        return maxDepth - 1;
    }

    public double getAverage()
    {
        depth = averageSum = averageCount = 0;
        _getAverage(root);
        average = ((double)averageSum) / averageCount;
        return average;
    }

    public double getVariance()
    {
        average = getAverage();
        varianceSum = 0.0;
        depth = averageCount = 0;

        _getVariance(root);

        if (averageCount - 1 > 0)
            variance = Math.Sqrt(varianceSum / (averageCount - 1));
        else
            variance = Math.Sqrt(varianceSum);
        return variance;
    }

    private void print(Node node, System.IO.StreamWriter output)
        {
                if (null != node)
                {
                        ++depth;
                        print(node.RightOneChild, output);

                        for(int i=0; i < depth; ++i)
                             output.Write("---");
                        output.WriteLine(node.Letter + "(" + (depth - 1) + ")");

                        print(node.LeftZeroChild, output);
                        --depth;
                }
        }

    protected void _getDepth(Node node)
    {
        if (null != node)
        {
            ++depth;

            if (depth > maxDepth)
                maxDepth = depth;

            _getDepth(node.RightOneChild);
            _getDepth(node.LeftZeroChild);
            --depth;
        }
    }

    protected void _getAverage(Node node)
    {
        if (null != node)
        {
            ++depth;
            _getAverage(node.RightOneChild);
            _getAverage(node.LeftZeroChild);
            --depth;
            if (null == node.RightOneChild && null == node.LeftZeroChild)
            {
                ++averageCount;
                averageSum += depth;
            }
        }
    }

    protected void _getVariance(Node node)
    {
        if (null != node)
        {
            ++depth;
            _getVariance(node.RightOneChild);
            _getVariance(node.LeftZeroChild);
            --depth;
            if (null == node.RightOneChild && null == node.LeftZeroChild)
            {
                ++averageCount;
                varianceSum += ((depth - average) * (depth - average));
            }
        }
    }

    private Node currentNode;
    private int depth, averageSum, averageCount;
    private double varianceSum;
    protected Node root = new Node();
    protected int maxDepth;
    protected double average, variance;
}

class Program
{
    static void Main(string[] args)
    {
       String usage = "Usage: lzwtree in_file -o out_file";

       if (args.Length < 3)
       {
           Console.WriteLine(usage);
           Environment.Exit(-1);
       }
       if (!"-o".Equals(args[1]))
       {
           Console.WriteLine(usage);
           Environment.Exit(-1);
       }

       System.IO.StreamReader input;
       System.IO.StreamWriter output = new System.IO.StreamWriter(args[2]);

       try
       {
          input = new System.IO.StreamReader(args[0]);
       }
       catch (Exception)
       {
          Console.WriteLine("cannot find input file...");
          Environment.Exit(-1);
       }
       input = new System.IO.StreamReader(args[0]);

       char ch;
       LZWTree lzw = new LZWTree();

       while (input.EndOfStream == false)
       {
           ch = (char)input.Read();
           if (0x0a == ch) break;
       }

       bool inComment = false;
       while (input.EndOfStream == false)
       {
           ch = (char)input.Read();

           if (0x3e == ch)
           {
               inComment = true;
               continue;
           }
           if (0x0a == ch)
           {
               inComment = false;
               continue;
           }
           if (inComment) continue;
           if (0x4e == ch) continue;

           for (int i = 0; i < 8; i++)
           {
               if ((ch & 0x80) != 0)
                   lzw.insert('1');
               else
                   lzw.insert('0');
               ch <<= 1;
           }
       }

       lzw.print(output);
       output.Write("depth = " + lzw.getDepth() + '\n');
       output.Write("mean = " + lzw.getAverage() + '\n');
       output.Write("var = " + lzw.getVariance() + '\n');

       input.Close();
       output.Close();
    }
}