none
how does this function recall RRS feed

  • Question

  • hi there

    I am tracing the implemented  compress text using  half man algorithm, my problem is with this function how does it recall Traverse function

    i am not familiar with second parameter !!!

    List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>());

    and this is the full code:

    public class Node
        {
                public char Symbol { get; set; }
                public int Frequency { get; set; }
                public Node Right { get; set; }
                public Node Left { get; set; }
                public List<bool> Traverse(char symbol, List<bool> data)
                {
                        // Leaf
                        if (Right == null && Left == null)
                        {
                                if (symbol.Equals(this.Symbol))
                                {
                                        return data;
                                }
                                else
                                {
                                        return null;
                                }
                        }
                        else
                        {
                                List<bool> left = null;
                                List<bool> right = null;
                                if (Left != null)
                                {
                                        List<bool> leftPath = new List<bool>();
                                        leftPath.AddRange(data);
                                        leftPath.Add(false);
                                        left = Left.Traverse(symbol, leftPath);
                                }
                                if (Right != null)
                                {
                                        List<bool> rightPath = new List<bool>();
                                        rightPath.AddRange(data);
                                        rightPath.Add(true);
                                        right = Right.Traverse(symbol, rightPath);
                                }
                                if (left != null)
                                {
                                        return left;
                                }
                                else
                                {
                                        return right;
                                }
                        }
                }
        }
    using System;
        using System.Collections.Generic;
        using System.Linq;
        using System.Text;
        using System.Collections;
        namespace HuffmanTest
        {
        public class HuffmanTree
        {
                private List<Node> nodes = new List<Node>();
                public Node Root { get; set; }
                public Dictionary<char, int> Frequencies = new Dictionary<char, int>();
                public void Build(string source)
                {
                        for (int i = 0; i < source.Length; i++)
                        {
                                if (!Frequencies.ContainsKey(source[i]))
                                {
                                        Frequencies.Add(source[i], 0);
                                }
                                Frequencies[source[i]]++;
                        }
                        foreach (KeyValuePair<char, int> symbol in Frequencies)
                        {
                                nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value });
                        }
                        while (nodes.Count > 1)
                        {
                                List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>();
                                if (orderedNodes.Count >= 2)
                                {
                                        // Take first two items
                                        List<Node> taken = orderedNodes.Take(2).ToList<Node>();
                                        // Create a parent node by combining the frequencies
                                        Node parent = new Node()
                                        {
                                                Symbol = '*',
                                                Frequency = taken[0].Frequency + taken[1].Frequency,
                                                Left = taken[0],
                                                Right = taken[1]
                                        };
                                        nodes.Remove(taken[0]);
                                        nodes.Remove(taken[1]);
                                        nodes.Add(parent);
                                }
                                this.Root = nodes.FirstOrDefault();
                        }
                }
                public BitArray Encode(string source)
                {
                        List<bool> encodedSource = new List<bool>();
                        for (int i = 0; i < source.Length; i++)
                        {
                                List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>());
                                encodedSource.AddRange(encodedSymbol);
                        }
                        BitArray bits = new BitArray(encodedSource.ToArray());
                        return bits;
                }
                public string Decode(BitArray bits)
                {
                        Node current = this.Root;
                        string decoded = "";
                        foreach (bool bit in bits)
                        {
                                if (bit)
                                {
                                        if (current.Right != null)
                                        {
                                                current = current.Right;
                                        }
                                }
                                else
                                {
                                        if (current.Left != null)
                                        {
                                                current = current.Left;
                                        }
                                }
                                if (IsLeaf(current))
                                {
                                        decoded += current.Symbol;
                                        current = this.Root;
                                }
                        }
                        return decoded;
                }
                public bool IsLeaf(Node node)
                {
                        return (node.Left == null && node.Right == null);
                }
        }

    Tuesday, June 5, 2012 8:42 AM

Answers

  • Consider the simple case: left node (ln) - top node (tn) - right node (rn).

    tn.Traverse starts at top level, goes to the left node. Comes back, left is not null. Goes to the right node. Comes back, right is not null. Now your if only returns the values collected from the left run.

    So the question is what should this function do? And what should it return?

    Wednesday, June 6, 2012 3:48 PM

All replies

  • The second parameter is a strongly typed list of Boolean values. List<T> is part of the Generics feature of C#.
    Tuesday, June 5, 2012 1:25 PM
  • i know it but my problem is that why its make an instance of list by new keyword and pass it. when we want to recall a function we use to do like this function (a,b);

    but it's use it like function(a,new b);

    what does it mean

    Tuesday, June 5, 2012 3:32 PM
  • i know it but my problem is that why its make an instance of list by new keyword and pass it. when we want to recall a function we use to do like this function (a,b);

    but it's use it like function(a,new b);

    what does it mean

    It just means that rather than creating an instance, storing that instance in a variable, and then passing that variable to a method, you can create a new instance an pass it directly into the new method.  There's no need to store it in an intermediate variable (unless you want to).  It's not really a special syntax or anything.  'new List<int>()' is just creating a new list and passing it in.
    Tuesday, June 5, 2012 3:37 PM
  • I think we do it because we want to use it as a recursive function Am i right!
    Tuesday, June 5, 2012 5:37 PM
  • Basically yes, but after reviewing your function, what should it do?  You travers first your left nodes, then your right node, but you only return the left values?

    btw, the List<bool> parameter is basically your result.

    Wednesday, June 6, 2012 10:14 AM
  • Are you sure its return both left and right here:

                                if (left != null)
                                {
                                        return left;
                                }
                                else
                                {
                                        return right;
                                }

    do you find any error into my code?!!



    Wednesday, June 6, 2012 1:58 PM
  • Consider the simple case: left node (ln) - top node (tn) - right node (rn).

    tn.Traverse starts at top level, goes to the left node. Comes back, left is not null. Goes to the right node. Comes back, right is not null. Now your if only returns the values collected from the left run.

    So the question is what should this function do? And what should it return?

    Wednesday, June 6, 2012 3:48 PM
  • it is the half man compress algorithm 

    at the first time we building a half man tree (sum  the two minimum elements and making a parent node) base on the input that we have got. then we encoding the code. we start from the parent the left is false and the right is true. our data are on the leaf. the traverse method traverse the tree to catch the data and record the way that reaching to leaf(i mean true and false) and finally the true and false convert to zero and one on the screen here is the main function

      class Program
        {
            static void Main(string[] args)
            {
                string input = "Hussein";
                HuffmanTree huffmanTree = new HuffmanTree();
    
                // Build the Huffman tree
                huffmanTree.Build(input);
    
                // Encode
                BitArray encoded = huffmanTree.Encode(input);
    
                Console.Write("Encoded: ");
                foreach (bool bit in encoded)
                {
                    Console.Write((bit ? 1 : 0) + "");
                }
                Console.WriteLine();
    
                // Decode
                string decoded = huffmanTree.Decode(encoded);
    
                Console.WriteLine("Decoded: " + decoded);
    
                Console.ReadLine();
            }
        }

    Wednesday, June 6, 2012 4:55 PM