/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu

in C#: Michael Gärtner
************************************************/

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Logofatu
{
    class P05HuffmanCode
    {
        private static String FileInputName = "huffman.in";
        private static String FileOutputName = "huffman.out";

        static void Main(string[] args)
        {
            StreamReader sr = null;
            StreamWriter sw = null;
            try
            {
                sr = new StreamReader(FileInputName);
                SortedList<int, List<Node>> map = new SortedList<int, List<Node>>();

                // Daten einlesen
                while ( !sr.EndOfStream )
                {
                    string[] sArray = sr.ReadLine().Split(' ');
                    int cost = int.Parse(sArray[1]);                   
                    List<Node> list = null;
                    if ( !map.TryGetValue(cost, out list) )
                    {
                        list = new List<Node>();
                        map.Add(cost, list);
                    }
                    list.Add(new Node(cost, sArray[0][0]));
                }

                // Algorithmus
                if ( map.Count == 0 )
                    return;
                while ( map.Count > 1 )
                {
                    SortedListIterator it = new SortedListIterator(map);
                    KeyValuePair<int, List<Node>> entry = it.Next();

                    ListIterator listIt = new ListIterator(entry.Value);

                    Node first = listIt.Next();
                    listIt.Remove();
                    if ( !listIt.hasNext() && !listIt.hasPrevious() )
                    {
                        it.Remove();
                        entry = it.Next();
                        listIt = new ListIterator(entry.Value);
                    }

                    Node second = listIt.Next();
                    listIt.Remove();
                    if ( !listIt.hasNext() && !listIt.hasPrevious() )
                    {
                        it.Remove();
                    }

                    Node newNode = new Node(first, second);
                    List<Node> list = null;
                    if ( !map.TryGetValue(newNode.Cost, out list) )
                    {
                        list = new List<Node>();
                        map.Add(newNode.Cost, list);
                    }
                    list.Add(newNode);
                }

                // Daten ausgeben
                sw = new StreamWriter(FileOutputName);

                IEnumerator<KeyValuePair<int, List<Node>>> mapEn = map.GetEnumerator();
                mapEn.MoveNext();           // auf 1. Element von map positionieren
                KeyValuePair<int, List<Node>> entry1 = mapEn.Current;

                List<Node>.Enumerator listEn = entry1.Value.GetEnumerator();
                listEn.MoveNext();          // auf 1. Element der akt. Node-Liste positionieren
                Node node1 = listEn.Current;

                node1.writeCosts(sw, new List<bool>());
            }

            catch ( IOException ex )
            {
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n\n" + ex);
            }

            finally
            {
                if ( sr != null )
                {
                    sr.Close();
                }
                if ( sw != null )
                {
                    sw.Close();
                }
            }
        }
    }

    class Node : IComparable<Node>
    {
        private int cost;
        private char ch;
        private Node left, right;

        public Node(int cost, char ch)
        {
            this.cost = cost;
            this.ch = ch;
        }

        public Node(Node left, Node right)
        {
            this.left = left;
            this.right = right;
            this.cost = left.cost + right.cost;
        }

        public int Cost
        {
            get { return cost; }
        }

        public int CompareTo(Node o)
        {
            return this.cost - o.cost;
        }

        public void writeCosts(StreamWriter sw, List<bool> pathPrefix)
        {
            if ( left == null || right == null )
            {
                sw.Write(this.ch);
                sw.Write("\t");
                foreach ( var b in pathPrefix )
                {
                    sw.Write(b ? 1 : 0);
                }
                sw.WriteLine();
            }
            else
            {
                pathPrefix.Add(false);
                left.writeCosts(sw, pathPrefix);
                pathPrefix[pathPrefix.Count - 1] = true;
                right.writeCosts(sw, pathPrefix);
                pathPrefix.RemoveAt(pathPrefix.Count - 1);
            }
        }
    }


    // Eigene Iterator-Klassen "ListIterator" und "SortedListIterator" zur Nachbildung der Java-Interator Klasse Iterator
    // (C# Enumeratoren können hier nicht verwendet werden, da diese ein Zurückgehen (z.B Previous)
    // und Strukturänderungen (z.B. Remove) nicht unterstützen.)
    
    class ListIterator
    {
        private int currPos;
        private List<Node> list;

        public ListIterator(List<Node> list)
        {
            currPos = -1;
            this.list = list;
        }

        public int CurrPos
        { 
            get { return currPos; }
            set { currPos = value; }
        }

        public bool hasNext()
        {
            return currPos < list.Count - 1 ? true : false;
        }

        public bool hasPrevious()
        {
            return currPos > 0 ? true : false;
        }

        public Node Next()
        {
            currPos++;
            return list[currPos];
        }

        public Node Previous()
        {
            currPos--;
            return list[currPos];
        }

        public Node Current
        {
            get { return list[currPos]; }
            set { list[currPos] = value; }
        }

        public void Remove()
        {
            list.RemoveAt(currPos);
            currPos = -1;
        }
    }

    class SortedListIterator
    {
        private int currPos;
        private int currKey;
        private List<Node> currValue;
        private SortedList<int, List<Node>> sortedList;

        public SortedListIterator(SortedList<int, List<Node>> sortedList)
        {
            currPos = -1;
            this.sortedList = sortedList;
        }

        public KeyValuePair<int, List<Node>> Next()
        {
            currPos++;
            currKey = sortedList.Keys[currPos];
            currValue = sortedList.Values[currPos];
            return new KeyValuePair<int, List<Node>>(currKey, currValue);

        }

        public KeyValuePair<int, List<Node>> Previous()
        {
            currPos--;
            currKey = sortedList.Keys[currPos];
            currValue = sortedList.Values[currPos];
            return new KeyValuePair<int, List<Node>>(currKey, currValue);
        }

        public KeyValuePair<int, List<Node>> Current
        {
            get { return new KeyValuePair<int, List<Node>>(currKey, currValue); }
        }

        public void Remove()
        {
            sortedList.Remove(currKey);
            currPos = -1;
        }
    }   
}