/* Last edited on 2023-02-06 07:26:23 by stolfi */

void tcot_check_tree(codetree_node_t *root, uint32_t nv, uint64_t freq[])
  { 
    bool_t tick[nv]; /* {tick[val]} is true iff {val} occurs in the tree. */
    for (uint32_t iv = 0; iv < nv; iv++) { tick[iv] = FALSE; }
  
    uint32_t nbug = 0;

    auto void checkit(codetree_node_t *nd, uint64_t *weight_P, uint32_t *leaves_P, uint32_t *minval_P);
      /* Checks the tree rooted at {nd}. Returns in {*weight_P} the
        total leaf weight, in {*leaves_P}, the number of leaves, and in
        {*minval_P} the min {value} field among all leaves. Also sets
        {tick[val]} for all leaf values, complaining if duplicate.
        Increments {nbug} and prints a message every time it finds a bug. */
        
    uint64_t tree_weight = 0;
    uint32_t tree_leaves = 0;
    uint32_t tree_minval = 0;
    if (root != NULL) { checkit(root, &tree_weight, &tree_leaves, &tree_minval);  }
    fprintf(stderr, "tree has %u leaves (min value = %u)\n", tree_leaves, tree_minval);
    fprintf(stderr, "total weight = %lu\n", tree_weight);
      
    /* Check consistency of {tick} with {freq}: */
    uint64_t tot_weight = 0;
    uint32_t tot_leaves = 0;
    for (uint32_t iv = 0; iv < nv; iv++) 
      { if (freq[iv] == 0)
          { fprintf(stderr, "** tree has leaf with {val} = %u and {freq[val]} = 0\n", iv); nbug++; }
        else
          { fprintf(stderr, "** value {val} = %u with {freq[val]} = %lu is not in tree\n", iv, freq[iv]); nbug++; 
            tot_weight += freq[iv];
            tot_leaves++;
          }
      }
    if (nbug == 0) 
      { assert(tree_weight == tot_weight); 
        assert(tree_leaves == tot_leaves);
      }
    else
      { demand(FALSE, "bad tree"); }
      
    return;
    
    /* INTERBAL IMPS */
    
    void checkit(codetree_node_t *nd, uint64_t *weight_P, uint32_t *leaves_P, uint32_t *minval_P)
      { if (nd == NULL)
          { /* Should not happen: */
            fprintf(stderr, "** child pointer is null\n"); nbug++;
          }
        else if (nd->value == NO_VALUE)
          { /* Internal node: */
            uint64_t wt_ch[2]; /* Total leaf weight of each subtree. */
            uint32_t lf_ch[2]; /* Number of leaves in each subtree. */
            uint32_t mv_ch[2]; /* Min {value} in each subtree. */
            for (uint32_t ich = 0; ich < 2; ich++)
              { checkit(nd->child[ich], &(wt_ch[ich]), &(lf_ch[ich]), &(mv_ch[ich])); }
            (*weight_P) = wt_ch[0] + wt_ch[1];
            (*leaves_P) = lf_ch[0] + lf_ch[1];
            (*minval_P) = (mv_ch[0] < mv_ch[1] ? mv_ch[0] : mv_ch[1]);
            /* The {tick} logic will detect if {mv_ch[0] == mv_ch[1]}. */
            /* Child order property: */
            if (wt_ch[0] > wt_ch[1]) 
              { fprintf(stderr, "** node has children in wrong order, weights = %lu %lu\n", wt_ch[0], wt_ch[1]); nbug++; }
            else if ((wt_ch[0] == wt_ch[1]) && (mv_ch[0] > mv_ch[1]))
              { fprintf(stderr, "** wrong children tie-breaking, minvals = %u %u\n", mv_ch[0], mv_ch[1]); nbug++; }
          }
        else
          { /* Leaf node: */
            uint32_t iv = nd->value;
            if (iv >= nv) 
              { fprintf(stderr, "** leaf value = %u out of range 0..%u\n", iv, nv-1); nbug++; }
            else if (tick[iv])
              { fprintf(stderr, "** leaf value = %u occurs twice in tree\n", iv); nbug++; }
            else 
              { /* The positive freq property is checked later. */
                (*weight_P) = freq[iv];
                (*leaves_P) = 1;
                (*minval_P) = iv;
              }
          }
      }
  }