elt_int.h

Go to the documentation of this file.

/**********************************************************//**
 **
 ** @file data/compress/elt_int.h
 **
 ** Copyright (C) 2012  Xpace, LLC.  All rights reserved
 **
 ** www.xpace.net
 **
 **************************************************************/

#ifndef XPACE_ELT_INT_H
#define XPACE_ELT_INT_H

#include "QtCore/QHash"    // TODO Xpace Hash

#include "util/bitstream.h"

namespace Xpace
{
  // ================================ INFO ====================

  template<typename N>
  class eltIntInfo
  {
  public:
    void set
      (const std::vector<N>& vals);
    
    uint getTermCount
      ()
      const
    {
      return term_count;
    }

    N getNormMax
      ()
      const
    {
      return norm_max_val;
    }

    QHash<N, uint>* getNormHash
      ()
    {
      return &norm_hash;
    }

    QHash<N, uint>* getRunsHash
      ()
    {
      return &runs_hash;
    }

  private:
    QHash<N, uint> norm_hash;
    QHash<N, uint> runs_hash;

    uint term_count;
    N norm_max_val;
  };

  // ================================ FIXED ===================

  template<typename N>
  class eltIntFixed
  {
  public:
    void set
      (const std::vector<N>* v,
       const N& maxValue);         

    size_t getLen
      ()
      const;

    void startEncode
      (MemBitStream* n)
      const;

   void encode
      (const N& n,
       MemBitStream* b)
      const;

    void startDecode
      (MemBitStream* b,
       BytePool*);

    N decode
      (MemBitStream* b)
      const
    {
      return N::getBits(b, bits);
    }

  private:
    const std::vector<N>* vals;
    size_t bits;
  };

  template<typename N>
  class eltIntVar
  {
  public:
    void set
      (const std::vector<N>* v)
    {
      vals = v;
    }

    void startEncode
      (MemBitStream*)
      const
    {
    }

    size_t getLen
      ()
      const
    {
      size_t ret(0);
      for (typename std::vector<N>::const_iterator n(vals->begin()); n != vals->end(); ++n)
        ret += n->lenVar();
      return ret;
    }

    void encode
      (const N& n,
       MemBitStream* b)
      const
    {
      n.addVar(b);
    }

    void startDecode
      (MemBitStream*,
       BytePool* p)
    {
      pool = p;
    }

    N decode
      (MemBitStream* b)
      const
    {
      return N::getVar(b, pool);
    }

  private:
    const std::vector<N>* vals;
    BytePool* pool;
  };

  // ================================ CODED ===================

  template<typename N>
  class eltIntCoded 
  {
  public:
    void set
      (eltIntInfo<N>* h,
       bool isRun);

    size_t getLen
      ()
      const;

    void startEncode
      (MemBitStream* b)
      const;

    void encode
      (const N& norm,         
       MemBitStream* b)
      const;

    void startDecode
      (MemBitStream* b,
       BytePool*);

    N decode
      (MemBitStream* b)
      const;

  private:
    eltIntInfo<N>* hash;
    QHash<N, uint>* qh;

    size_t code_bits;
    size_t fixed_size;
    size_t table_size;
    std::vector<N> codes;   
  };

  // ================================ VAR CODED ===============

  template<typename N>
  class eltIntVarCoded
  {
  public:
    void set
      (eltIntInfo<N>* h,
       bool isRun);

    size_t getLen
      ()
      const;

    void startEncode
      (MemBitStream* b)
      const;

    void encode
      (const N& n,
       MemBitStream* b)
      const;

    void startDecode
      (MemBitStream* b,
       BytePool* pool);

    N decode
      (MemBitStream* b)
      const;

  private:
    eltIntInfo<N>* hash;
    QHash<N, uint>* qh;
    QHash<N, uint> freq_hash;

    size_t fixed_size;
    size_t table_size;
    std::vector<N> codes;

    struct freq_elt
    {
      freq_elt
        (N k, 
         uint f) :
          key(k), 
          freq(f)
      {
      }

      bool operator<
        (const freq_elt& rhs)
        const
      {
        return freq > rhs.freq;
      }

      N key;
      uint freq;
    };
    std::vector<freq_elt> freq_list;
  };

  // ==========================================================
  // ==========================================================
  // ==========================================================

  #define SHOW_STATS !NDEBUG

  #if SHOW_STATS
  extern uint _counts[16];
  extern size_t _sizes[16]; 
  extern bool _is_delta;
  extern uint _max_ht_size, _max_ht_pct;
  #endif

  // ================================ INFO ====================

  template<typename N>
  inline
  void eltIntInfo<N>::set
    (const std::vector<N>& vals)
  {
    term_count = narrow_to<uint>(vals.size());

    norm_hash.clear();
    runs_hash.clear();

    norm_max_val = N::min();

    N prev_val(N::max());  // as long as it's different from val[0]
    for (typename std::vector<N>::const_iterator v(vals.begin()); v != vals.end(); ++v)
    {
      typename QHash<N, uint>::iterator it(norm_hash.find(*v));
      if (it == norm_hash.end())
        norm_hash.insert(*v, 0); 
      else
        ++*it;
   
      if (*v != prev_val)
      {
        typename QHash<N, uint>::iterator it(runs_hash.find(*v));
        if (it == runs_hash.end())
          runs_hash.insert(*v, 0); 
        else
          ++*it;
        prev_val = *v;

        if (*v > norm_max_val)
          norm_max_val = *v;
      }
    }
  }

  // ================================ FIXED ===================

  template<typename N>
  inline
  void eltIntFixed<N>::set
    (const std::vector<N>* n,
     const N& maxValue)
  {
    vals = n;
    bits = std::max(size_t(1), maxValue.bitsNeeded());
  }

  template<typename N>
  inline
  size_t eltIntFixed<N>::getLen
    ()
    const
  {
    return MemBitStream::lenVar(bits) + vals->size() * bits;
  }

  template<typename N>
  inline
  void eltIntFixed<N>::startEncode
    (MemBitStream* b)
    const
  {
    b->addVar(bits - 1);
  }

  template<typename N>
  inline
  void eltIntFixed<N>::encode
    (const N& n,
     MemBitStream* b)
    const
  {
    n.addBits(bits, b);
  }

  template<typename N>
  inline
  void eltIntFixed<N>::startDecode
    (MemBitStream* b,
     BytePool*)
  {
    bits = 1 + b->getVar<size_t>();
  }

  // ================================ CODED ===================

  template<typename N>
  inline
  void eltIntCoded<N>::set
    (eltIntInfo<N>* h,
     bool isRun) 
  {
    hash = h;
    qh = (isRun ? hash->getRunsHash() : hash->getNormHash());
    assert(qh->size());
    code_bits = bitsNeeded(qh->size() - 1);

    // calculate table size for fixed-size elts
    fixed_size = hash->getNormMax().bitsNeeded();
    table_size = MemBitStream::lenVar(fixed_size) + fixed_size * qh->size();

    // see if variable is smaller
    size_t var_table_size(2);  // place for fixed_size = 0
    for (typename QHash<N, uint>::const_iterator it(qh->begin()); var_table_size < table_size; )
    {
      var_table_size += it.key().lenVar();     
      if (++it == qh->end())
      {
        fixed_size = 0;
        table_size = var_table_size;
        break;
      }
    }

    // add space for the number of terms in the table and code bits
    table_size += MemBitStream::lenVar(size_t(qh->size() - 1)) 
                + MemBitStream::lenVar(code_bits - 1);

    // add space for the actual terms
    table_size += hash->getTermCount() * code_bits;
  }

  template<typename N>
  inline
  size_t eltIntCoded<N>::getLen
    ()
    const
  {
    return table_size;
  }

  template<typename N>
  inline
  void eltIntCoded<N>::startEncode
    (MemBitStream* b)
    const
  {
    #if SHOW_STATS
    if (uint(qh->size()) > _max_ht_size)
      _max_ht_size = qh->size();
    uint pct((qh->size() * 100) /  hash->getTermCount());
    if (pct > _max_ht_pct)
      _max_ht_pct = pct;
    #endif

    // some info about the hash table
    b->addVar(uint(qh->size() - 1));
    b->addVar(code_bits - 1);
    b->addVar(fixed_size);

    // write the hash table
    uint i(0);
    if (fixed_size)
    {
      for (typename QHash<N, uint>::iterator it(qh->begin()); it != qh->end(); ++it)
      {
        N n(it.key());
        *it = i++;         
        n.addBits(fixed_size, b);
      }
    }
    else
      for (typename QHash<N, uint>::iterator it(qh->begin()); it != qh->end(); ++it)
      {
        N n(it.key());
        *it = i++;
        n.addVar(b);
      }
  }

  template<typename N>
  inline
  void eltIntCoded<N>::encode
    (const N& n,
     MemBitStream* b)
    const
  {
    b->addBits(code_bits, (*qh)[n]);
  }

  template<typename N>
  inline
  void eltIntCoded<N>::startDecode
    (MemBitStream* b,
     BytePool* pool)
  {
    uint num_codes(b->getVar<uint>() + 1);
    codes.reserve(num_codes);
    codes.clear();
    code_bits = b->getVar<uint>() + 1;
    if ((fixed_size = b->getVar<size_t>()))
    {
      while (num_codes--)
        codes.push_back(N::getBits(b, fixed_size));
    }
    else
      while (num_codes--)
        codes.push_back(N::getVar(b, pool));
  }

  template<typename N>
  inline
  N eltIntCoded<N>::decode
    (MemBitStream* b)
    const
  {
    return codes[b->getBits<uint>(code_bits)];
  }

  // ================================ VAR CODED ===============

  template<typename N>
  inline
  void eltIntVarCoded<N>::set
    (eltIntInfo<N>* h,
     bool isRun) 
  {
    hash = h;
    qh = isRun ? hash->getRunsHash() : hash->getNormHash();
    assert(qh->size());

    // calculate table size for fixed-size elts
    fixed_size = hash->getNormMax().bitsNeeded();
    table_size = MemBitStream::lenVar(fixed_size) + fixed_size * qh->size();

    // see if variable is smaller
    size_t var_table_size(2);  // place for fixed_size = 0
    for (typename QHash<N, uint>::const_iterator it(qh->begin()); var_table_size < table_size; )
    {
      var_table_size += it.key().lenVar();      
      if (++it == qh->end())
      {
        fixed_size = 0;
        table_size = var_table_size;
        break;
      }
    }

    // add space for the number of terms in the table
    table_size += MemBitStream::lenVar(size_t(qh->size() - 1));

    uint i(0);
    freq_list.clear();
    freq_list.reserve(qh->size());

    for (typename QHash<N, uint>::const_iterator it(qh->begin()); it != qh->end(); ++it)
      freq_list.push_back(freq_elt(it.key(), it.value()));

    std::sort(freq_list.begin(), freq_list.end());
    freq_hash.clear();
    freq_hash.reserve(qh->size());
    i = 0;
    for (typename std::vector<freq_elt>::const_iterator it(freq_list.begin()); it != freq_list.end(); ++it)
    {
      table_size += MemBitStream::lenVar(i) * (1 + it->freq);
      freq_hash.insert(it->key, i++);
    }
  }

  template<typename N>
  inline
  size_t eltIntVarCoded<N>::getLen
    ()
    const
  {
    return table_size;
  }

  template<typename N>
  inline
  void eltIntVarCoded<N>::startEncode
    (MemBitStream* b)
    const
  {
    #if SHOW_STATS
    if (uint(freq_hash.size()) > _max_ht_size)
      _max_ht_size = freq_hash.size();
    uint pct(uint(freq_hash.size() * 100) / hash->getTermCount());
    if (pct > _max_ht_pct)
      _max_ht_pct = pct;
    #endif

    b->addVar(uint(freq_hash.size() - 1));
    b->addVar(fixed_size);

    if (fixed_size)
      for (typename std::vector<freq_elt>::const_iterator it(freq_list.begin()); it != freq_list.end(); ++it)
        it->key.addBits(fixed_size, b);
    else
      for (typename std::vector<freq_elt>::const_iterator it(freq_list.begin()); it != freq_list.end(); ++it)
        it->key.addVar(b);
  }

  template<typename N>
  inline
  void eltIntVarCoded<N>::encode
    (const N& n,
     MemBitStream* b)
    const
  {
    b->addVar(freq_hash[n]);
  }

  template<typename N>
  inline
  void eltIntVarCoded<N>::startDecode
    (MemBitStream* b,
     BytePool* pool)
  {
    uint num_codes(b->getVar<uint>() + 1);
    codes.reserve(num_codes);
    codes.clear();
    if ((fixed_size = b->getVar<size_t>()))
    {
      while (num_codes--)
        codes.push_back(N::getBits(b, fixed_size));  
    }
    else
      while (num_codes--)
        codes.push_back(N::getVar(b, pool));
  }

  template<typename N>
  inline
  N eltIntVarCoded<N>::decode
    (MemBitStream* b)
    const
  {
    uint i(b->getVar<uint>());
    if (i >= codes.size())
      throw MemBitStream::Corrupt(b->getBitPos());
    return codes[i];
  }
}
#endif