C#•2y ago

❔ Huffman Coding Tree returning BaseNode

I have the following Huffman tree implementation: HuffTree.root() and HuffInternalNode both return BaseNode type. Is there a way to only return the specific type that it is? HuffLeafNode or HuffInternalNode? Trying to traverse the tree is a nightmare of explicit type casting. E.g. HuffLeafNode node = (HuffLeafNode)((HuffInternalNode)htree.root()).left()

using System;
using System.Collections.Generic;

public interface HuffBaseNode {
  bool isLeaf();
  int weight();
}

public class HuffLeafNode : HuffBaseNode {
  private char _element;
  private int _weight;

  // Constructor
  public HuffLeafNode(char el, int wt) {
    this._element = el; this._weight = wt;
  }

  public char value() { return this._element;}
  public int weight() { return this._weight;}
  public bool isLeaf() { return true; }
}

public class HuffInternalNode : HuffBaseNode {
  private int _weight;
  private HuffBaseNode _left;
  private HuffBaseNode _right;

  // Constructor
  public HuffInternalNode(HuffBaseNode l, HuffBaseNode r, int wt) {
    this._left = l;
    this._right = r;
    this._weight = wt;
  }

  public HuffBaseNode left() { return this._left;}
  public HuffBaseNode right() { return this._right;}
  public int weight() { return this._weight;}
  public bool isLeaf() { return false;}
}

class HuffTree : IComparable {
  private HuffBaseNode _root;

  // Constructors
  public HuffTree(char el, int wt) {
    this._root = new HuffLeafNode(el, wt);
  }
  public HuffTree(HuffBaseNode l, HuffBaseNode r, int wt) {
    this._root = new HuffInternalNode(l, r, wt);
  }

  public HuffBaseNode root() { return this._root;}
  public int weight() { return this._root.weight(); }
  public int CompareTo(Object t) {
    HuffTree that = (HuffTree) t;
    if(this._root.weight() < that.weight()) { return -1; }
    else if (this._root.weight() == that.weight()) { return 0; }
    else { return 1; }
  }  
  public static HuffTree BuildTree(PriorityQueue<HuffTree, int> Hheap) {
    HuffTree tmp1, tmp2, tmp3 = null;
    while(Hheap.Count > 1) {
      tmp1 = Hheap.Dequeue();
      tmp2 = Hheap.Dequeue();
      tmp3 = new HuffTree(tmp1.root(), tmp2.root(), tmp1.weight() + tmp2.weight());

      Hheap.Enqueue(tmp3, tmp3.weight());
    }
    return tmp3;
  }
}

using System;
using System.Collections.Generic;

public interface HuffBaseNode {
  bool isLeaf();
  int weight();
}

public class HuffLeafNode : HuffBaseNode {
  private char _element;
  private int _weight;

  // Constructor
  public HuffLeafNode(char el, int wt) {
    this._element = el; this._weight = wt;
  }

  public char value() { return this._element;}
  public int weight() { return this._weight;}
  public bool isLeaf() { return true; }
}

public class HuffInternalNode : HuffBaseNode {
  private int _weight;
  private HuffBaseNode _left;
  private HuffBaseNode _right;

  // Constructor
  public HuffInternalNode(HuffBaseNode l, HuffBaseNode r, int wt) {
    this._left = l;
    this._right = r;
    this._weight = wt;
  }

  public HuffBaseNode left() { return this._left;}
  public HuffBaseNode right() { return this._right;}
  public int weight() { return this._weight;}
  public bool isLeaf() { return false;}
}

class HuffTree : IComparable {
  private HuffBaseNode _root;

  // Constructors
  public HuffTree(char el, int wt) {
    this._root = new HuffLeafNode(el, wt);
  }
  public HuffTree(HuffBaseNode l, HuffBaseNode r, int wt) {
    this._root = new HuffInternalNode(l, r, wt);
  }

  public HuffBaseNode root() { return this._root;}
  public int weight() { return this._root.weight(); }
  public int CompareTo(Object t) {
    HuffTree that = (HuffTree) t;
    if(this._root.weight() < that.weight()) { return -1; }
    else if (this._root.weight() == that.weight()) { return 0; }
    else { return 1; }
  }  
  public static HuffTree BuildTree(PriorityQueue<HuffTree, int> Hheap) {
    HuffTree tmp1, tmp2, tmp3 = null;
    while(Hheap.Count > 1) {
      tmp1 = Hheap.Dequeue();
      tmp2 = Hheap.Dequeue();
      tmp3 = new HuffTree(tmp1.root(), tmp2.root(), tmp1.weight() + tmp2.weight());

      Hheap.Enqueue(tmp3, tmp3.weight());
    }
    return tmp3;
  }
}

11 Replies

Tvde1•2y ago

while traversing, you'll have to check whether it's a node or a value anyways, right? also a bit off topic, you can replace your methods with read-only properties so you don't need the () everywhere

L-I-V-E-2DAYOP•2y ago

So you're thinking something like:

if(node.left().isLeaf()) {
    HuffLeafNode NodeL = (HuffLeafNode)node.left()
} else {
    ....
}

if(node.left().isLeaf()) {
    HuffLeafNode NodeL = (HuffLeafNode)node.left()
} else {
    ....
}

That would make sense and wouldn't be as messy as I was thinking. I'll look into read only properties, pretty new to c# but i worked with c++ a long time ago. I'm assuming thats like setting a getter on the property without a setter? Something like: public int weight { get; }

Klarth•2y ago

As long as you're using HuffBaseNode and having separate nodes for branching and leaf nodes, you're going to be pushing polymorphic handling onto the caller. Which is fine if you're doing this to conserve space, but you could handle this via logic instead of the type system, too.

if (node.Left is HuffLeafNode leaf)
{
  // Do something with leaf
}
else if (node.Left is HuffInternalNode node)
{
  // Do something with node
}

if (node.Left is HuffLeafNode leaf)
{
  // Do something with leaf
}
else if (node.Left is HuffInternalNode node)
{
  // Do something with node
}

If you switch to properties, you can do that. No need for IsLeaf() as you're already hardcasting in the original. If you need multiple types of leaf nodes, then you can make a separate interface specifically for leaf nodes to implement. Partially rewritten

public interface IHuffNode
{
  int Weight { get; }
  bool IsLeaf { get; }
}

public class HuffInternalNode : IHuffNode {
  public int Weight { get; }
  public IHuffNode Left { get; }
  public IHuffNode Right { get; }
  public bool IsLeaf => false;

  public HuffInternalNode(IHuffNode left, IHuffNode right, int weight)
  {
    Left = left;
    Right = right;
    Weight = weight;
  }
}

public interface IHuffNode
{
  int Weight { get; }
  bool IsLeaf { get; }
}

public class HuffInternalNode : IHuffNode {
  public int Weight { get; }
  public IHuffNode Left { get; }
  public IHuffNode Right { get; }
  public bool IsLeaf => false;

  public HuffInternalNode(IHuffNode left, IHuffNode right, int weight)
  {
    Left = left;
    Right = right;
    Weight = weight;
  }
}

L-I-V-E-2DAYOP•2y ago

That looks good. I'll try it out. Thanks! Reformatted it using your changes + some more and its a lot cleaner. Prefix table generating and everything

using System;
using System.Collections.Generic;

public interface IHuffNode {
  bool IsLeaf { get; }
  int Weight { get; }
}

public class HuffLeafNode : IHuffNode {
  public char Value { get; }
  public int Weight { get; }
  public bool IsLeaf => true;

  // Constructor
  public HuffLeafNode(char el, int wt) {
    Value = el; 
    Weight = wt;
  }
}

public class HuffInternalNode : IHuffNode {
  public int Weight { get; }
  public IHuffNode Left { get; }
  public IHuffNode Right { get; }
  public bool IsLeaf => false;

  // Constructor
  public HuffInternalNode(IHuffNode l, IHuffNode r, int wt) {
    Left = l;
    Right = r;
    Weight = wt;
  }
}

class HuffTree : IComparable {
  private IHuffNode _root;

  // Constructors
  public HuffTree(char el, int wt) {
    this._root = new HuffLeafNode(el, wt);
  }
  public HuffTree(IHuffNode l, IHuffNode r, int wt) {
    this._root = new HuffInternalNode(l, r, wt);
  }

  public IHuffNode root() { return this._root;}
  public int Weight() { return this._root.Weight; }
  public int CompareTo(Object t) {
    HuffTree that = (HuffTree) t;
    if(this._root.Weight < that.Weight()) { return -1; }
    else if (this._root.Weight == that.Weight()) { return 0; }
    else { return 1; }
  }  
  public static HuffTree BuildTree(PriorityQueue<HuffTree, int> Hheap) {
    HuffTree tmp1, tmp2, tmp3 = null;
    while(Hheap.Count > 1) {
      tmp1 = Hheap.Dequeue();
      tmp2 = Hheap.Dequeue();
      tmp3 = new HuffTree(tmp1.root(), tmp2.root(), tmp1.Weight() + tmp2.Weight());

      Hheap.Enqueue(tmp3, tmp3.Weight());
    }
    return tmp3;
  }
  public Dictionary<char, string> GeneratePrefixTable() {
    Dictionary<char, string> prefixTable = new();
    Traverse((HuffInternalNode)this._root, "", prefixTable);
    return prefixTable;
  }
  public void Traverse(HuffInternalNode node, string prefix, Dictionary<char, string> table) {
    if(node.Left is HuffLeafNode leafL) {
        Console.WriteLine(leafL.Value + " " + prefix + "0");
        table[leafL.Value] = prefix + "0";
    } else if (node.Left is HuffInternalNode intNode) {
        Traverse(intNode, prefix + "0", table);
    }

    if(node.Right is HuffLeafNode leafR) {
        Console.WriteLine(leafR.Value + " " + prefix + "1");
        table[leafR.Value] = prefix + "1";
    } else if (node.Right is HuffInternalNode intNode) {
        Traverse(intNode, prefix + "1", table);
    }
  }
}

using System;
using System.Collections.Generic;

public interface IHuffNode {
  bool IsLeaf { get; }
  int Weight { get; }
}

public class HuffLeafNode : IHuffNode {
  public char Value { get; }
  public int Weight { get; }
  public bool IsLeaf => true;

  // Constructor
  public HuffLeafNode(char el, int wt) {
    Value = el; 
    Weight = wt;
  }
}

public class HuffInternalNode : IHuffNode {
  public int Weight { get; }
  public IHuffNode Left { get; }
  public IHuffNode Right { get; }
  public bool IsLeaf => false;

  // Constructor
  public HuffInternalNode(IHuffNode l, IHuffNode r, int wt) {
    Left = l;
    Right = r;
    Weight = wt;
  }
}

class HuffTree : IComparable {
  private IHuffNode _root;

  // Constructors
  public HuffTree(char el, int wt) {
    this._root = new HuffLeafNode(el, wt);
  }
  public HuffTree(IHuffNode l, IHuffNode r, int wt) {
    this._root = new HuffInternalNode(l, r, wt);
  }

  public IHuffNode root() { return this._root;}
  public int Weight() { return this._root.Weight; }
  public int CompareTo(Object t) {
    HuffTree that = (HuffTree) t;
    if(this._root.Weight < that.Weight()) { return -1; }
    else if (this._root.Weight == that.Weight()) { return 0; }
    else { return 1; }
  }  
  public static HuffTree BuildTree(PriorityQueue<HuffTree, int> Hheap) {
    HuffTree tmp1, tmp2, tmp3 = null;
    while(Hheap.Count > 1) {
      tmp1 = Hheap.Dequeue();
      tmp2 = Hheap.Dequeue();
      tmp3 = new HuffTree(tmp1.root(), tmp2.root(), tmp1.Weight() + tmp2.Weight());

      Hheap.Enqueue(tmp3, tmp3.Weight());
    }
    return tmp3;
  }
  public Dictionary<char, string> GeneratePrefixTable() {
    Dictionary<char, string> prefixTable = new();
    Traverse((HuffInternalNode)this._root, "", prefixTable);
    return prefixTable;
  }
  public void Traverse(HuffInternalNode node, string prefix, Dictionary<char, string> table) {
    if(node.Left is HuffLeafNode leafL) {
        Console.WriteLine(leafL.Value + " " + prefix + "0");
        table[leafL.Value] = prefix + "0";
    } else if (node.Left is HuffInternalNode intNode) {
        Traverse(intNode, prefix + "0", table);
    }

    if(node.Right is HuffLeafNode leafR) {
        Console.WriteLine(leafR.Value + " " + prefix + "1");
        table[leafR.Value] = prefix + "1";
    } else if (node.Right is HuffInternalNode intNode) {
        Traverse(intNode, prefix + "1", table);
    }
  }
}

Klarth•2y ago

I'd ditch the this., but it's personal preference.

this._root = new HuffInternalNode(l, r, wt);
// Into
_root = new HuffInternalNode(l, r, wt);

this._root = new HuffInternalNode(l, r, wt);
// Into
_root = new HuffInternalNode(l, r, wt);

_name is a popular convention for private fields and is sufficient to prevent naming conflicts.

L-I-V-E-2DAYOP•2y ago

so is this just not needed in c#, i'm used to js and python where its needed. i guess in python its self but same thing

Klarth•2y ago

It's rarely required.

L-I-V-E-2DAYOP•2y ago

like only if there is ambiguity? say there was a public Traverse function, then i'd have to call this.Traverse()

Klarth•2y ago

Only if you're trying to call an extension method on the current instance. Otherwise, smart use of capitalization conventions should supplant all other uses (some people do prefer this instead though). That shouldn't be ambiguous, but yes.

L-I-V-E-2DAYOP•2y ago

alright thanks a ton for your help. @Tvde1 SM PO LD PM , you too

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ Huffman Coding Tree returning BaseNode