text: /**
   * Binary tree to hold Huffman codes.
   * 
   * Leaves hold code values. Non-leaves cannot hold values.
   * 
   * Values are added in level-order traversal, with a maximum of (2^i - 1)
   * values at each level (except for the last level, which could have 2^i).
   * 
   * Each branch represents a '0' or a '1' in the bit string:
   *      Left: 0
   *      Right: 1
   * 
   * We can construct the bitstream for a given value by keeping track
   * of the branches as we descend the tree, appending the value of the
   * branch in order of descent.
   * 
   */
  class HuffTree {
  
      /**
       * Create a new node in the Huffman tree
       * 
       * @param {Number} level Optional level of the tree. Defaults to 0 (for the root)
       */
      constructor(level = 0) {
          this.level = level;
      }
      
      /**
       * Initialize the decoder with the 'BITS' array containing the number of huffman codes
       * of each length.
       * 
       * @param {Array} bits List of the number of Huffman codes of each length (0-NUM_HUFFMAN_LENGTHS)
       */
      initDecoder(bits) {
          // NOOP, since this implementation supports arbitrary tree sizes
      }
  
      /**
       * Insert a value into the tree at the given depth. Uses a level-order
       * traversal to fill the tree from left to right at a given level.
       * 
       * Returns 'true' if inserting the value was successful, otherwise false
       * 
       * @param {*} codeLength Depth of the tree at which to insert (length of huffman code)
       * @param {*} value Value to insert into the tree
       */
      insertCode(codeLength, value) {
          if (this.data != undefined) {
              return false;   // Invariant: leaf nodes can't have children
          }
          if (codeLength === this.level) {
              if (this.data === undefined) {
                  this.data = value;
                  return true;
              } else {
                  return false;   // We're full, try the node to the right
              }
          } else {
              if (this.left === undefined) {
                  // Invariant: nodes always created in pairs.
                  // Saves us from lots of checking for 'undefined' elsewhere
                  this.left = new HuffTree(this.level + 1);
                  this.right = new HuffTree(this.level + 1);
                  return this.left.insertCode(codeLength, value);
              } else {
                  if (this.left.insertCode(codeLength, value)) {
                      return true;
                  } else {
                      return this.right.insertCode(codeLength, value);
                  }
              }
          }
      }
  
  
      /**
       * Read the next huffman code from the data source and return the
       * value represented by the code.
       * 
       * F.2.2.3
       * 
       * @param {DataViewReader} reader Data source
       * @param {*} img Struct containing information about the image
       */
      decodeHuffman(reader, img) {
          let bitString = "";     // For debugging
          let node = this;
          while (true) {
              let bit = reader.nextBit(img);
              // bitString += bit;
              node = node.descendNode(bit);
              if (node === undefined) {
                  console.error("Error: Couldn't find huffman value for huffman code " + bitString);
                  break;
              } else if (node.data != undefined) {
                  // Found a value, so we're done!
                  // console.log("Found value " + node.data + " for huffman code " + bitString);
                  return node.data;
              }
          }
          return undefined;
      }
  
      /**
       * Print the entire tree to the console. Not recommended for large trees
       */
      dumpTree() {
          let str = "";
          for (let i = 0; i < this.level; i++) {
              str += " ";
          }
          str += this.level + ":";
          if (this.data != undefined) {
              str += this.data;
          }
          console.log(str);
          if (this.left != undefined) {
              this.left.dumpTree();
              this.right.dumpTree();
          }
      }
  
      /**
       * Return the next node in the tree for the given bit.
       * Returns the left node for '0' and the right node for '1'.
       * All other inputs are invalid.
       * 
       * @param {*} bit 
       */
      descendNode(bit) {
          if (bit === 0) {
              return this.left;
          } else if (bit === 1) {
              return this.right;
          } else {
              console.error("Error: invalid bit string (expected 0 or 1, got " + bit + ")");
          }
          return undefined;
      }
  
      /**
       * Return the value in the node represented by the given bitstring,
       * or undefined if the sequence is not found in the tree.
       * 
       * @param {String} bitString String representation of a sequence of bits
       */
      getValue(bitString) {
          if (bitString === "") {
              return this.data;
          }
          let c = bitString[0];
          if (c === '0') {    // '0' is left
              return this.left.getValue(bitString.slice(1));
          } else if (c === '1') { // '1' is right
              return this.right.getValue(bitString.slice(1));
          } else {
              console.error("Invalid character in bit string: " + c);
          }
      }
  
      /**
       * Additional tests for HuffTree's getValue(). getValue() isn't currently used by the
       * JPEG decoder, but it's a good way to experiement with the tree.
       */
      static testGetValue() {
          let tree = new HuffTree(0);
          let testCnt = 0;
          let errCnt = 0;
  
          function runInsertTest(level, value, expected) {
              let val = tree.insertCode(level, value);
              testCnt++;
              if (val != expected) {
                  console.error("Test " + testCnt + " Failed (expected " + expected + ", got " + val + ")");
                  errCnt++;
              }
          }
  
          runInsertTest(3, 4, true);
          runInsertTest(3, 5, true);
          runInsertTest(3, 3, true);
          runInsertTest(3, 2, true);
          runInsertTest(3, 6, true);
          runInsertTest(3, 1, true);
          runInsertTest(3, 0, true);
          // We shouldn't be able to insert an 8th node at L3, 
          // but the tree currently has no way of knowing this
          // since nodes don't know the state of other nodes.
          // For this to be a problem in practice, the JPEG
          // file would have to be out-of-spec/corrupt
          //runInsertTest(3, 12, false);    // Too many nodes in tree
          runInsertTest(4, 7, true);
          runInsertTest(5, 8, true);
          runInsertTest(6, 9, true);
          runInsertTest(7, 10, true);
          runInsertTest(8, 11, true);
          
          function runGetTest(input, expected) {
              let val = tree.getValue(input);
              testCnt++;
              if (val != expected) {
                  console.error("Test " + testCnt + " Failed (expected " + expected + ", got " + val + ")");
                  errCnt++;
              }
          }
  
          runGetTest("000", 4);
          runGetTest("001", 5);
          runGetTest("010", 3);
          runGetTest("011", 2);
          runGetTest("100", 6);
          runGetTest("101", 1);
          runGetTest("110", 0);
          runGetTest("1110", 7);
          runGetTest("11110", 8);
          runGetTest("111110", 9);
          runGetTest("1111110", 10);
          runGetTest("11111110", 11);
  
          // Sequence not in the table
          runGetTest("11111111", undefined);
  
          const testName = "HuffTree.getValue";
          if (errCnt === 0) {
              console.log(testName + "tests passed!");
          } else {
              console.error(testName + "tests failed: " + errCnt + " errors");
          }
      }
  }
  
  HuffTree.testGetValue();
  