#ifndef __LONG_BITS_H__
#define __LONG_BITS_H__

#include <algorithm>
#include <iostream>
#include <iomanip>

#ifdef min
#define already_defined_min min
#undef min
#endif
#ifdef max
#define already_defined_max max
#undef max
#endif

template <class Storage>
struct BitmaskGenerator {
  static Storage rzeros(const int zero_bits = 0){
    return (Storage(~0) << zero_bits);
  }
  static Storage lzeros(const int zero_bits = 0){
    return ~rzeros((sizeof(Storage) * 8) - zero_bits);
  }
};

#define MAKE_SPECIALIZED(type) \
template <> \
type BitmaskGenerator<type >::lzeros( \
    const int zero_bits){ \
  return ((type)(~0) >> zero_bits); \
}

MAKE_SPECIALIZED(unsigned char);
MAKE_SPECIALIZED(unsigned short);
MAKE_SPECIALIZED(unsigned int);
MAKE_SPECIALIZED(unsigned long);
#undef MAKE_SPECIALIZED


/**
 * 
 * 可変長ビット列
 * 
 * storage中の下位ビットから使用していくことに注意
 * 
 */
template <typename Storage = unsigned char, bool bit_order_LSB_first = true>
class LongBits : public BitmaskGenerator<Storage> {
  public:
    typedef Storage storage_t;
    static const int bits_per_byte = 8;
    static const int bits_per_storage = sizeof(storage_t) * bits_per_byte;
    
  protected:
    int bits;
    int margin_bits_in_last_storage;
    int last_index_of_storage;
    int capacity_of_storage;
    storage_t *storage;
    
    void truncate_last(){
      if(bit_order_LSB_first){
        storage[last_index_of_storage] 
            &= lzeros(margin_bits_in_last_storage);
      }else{
        storage[last_index_of_storage] 
            &= rzeros(margin_bits_in_last_storage);
      }
    }
  
  public:
    LongBits(const int initial_capacity = 128) 
        : bits(0), 
          margin_bits_in_last_storage(bits_per_storage), 
          last_index_of_storage(0),
          capacity_of_storage(initial_capacity),
          storage(new storage_t[initial_capacity]){
      
    }
    LongBits(const storage_t *content, int num_of_bits, const int initial_capacity = 128) 
        : bits(num_of_bits), 
          margin_bits_in_last_storage(bits_per_storage - (num_of_bits % bits_per_storage)), 
          last_index_of_storage(num_of_bits / bits_per_storage),
          capacity_of_storage(std::max(initial_capacity, (last_index_of_storage + 1))),
          storage(new storage_t[capacity_of_storage]){
      std::copy(content, 
          content + last_index_of_storage + 1,
          storage);
      truncate_last();
    }
    /**
     * コピーコンストラクタ
     * 完全なコピーを作成する
     * 
     */
    LongBits(const LongBits &orig) 
        : bits(orig.bits), 
          margin_bits_in_last_storage(orig.margin_bits_in_last_storage), 
          last_index_of_storage(orig.last_index_of_storage),
          storage(new storage_t[orig.capacity_of_storage]),
          capacity_of_storage(orig.capacity_of_storage) {
      std::copy(orig.storage, 
          orig.storage + orig.last_index_of_storage + 1,
          storage);
    }
    
    /**
     * コピーコンストラクタ
     * 完全なコピーを作成する
     * 
     */
    template <class TransformFunc>
    LongBits(const LongBits &orig, const TransformFunc &func) 
        : bits(orig.bits), 
          margin_bits_in_last_storage(orig.margin_bits_in_last_storage), 
          last_index_of_storage(orig.last_index_of_storage),
          storage(new storage_t[orig.capacity_of_storage]),
          capacity_of_storage(orig.capacity_of_storage) {
      std::transform(orig.storage, 
          orig.storage + orig.last_index_of_storage + 1,
          storage,
          func);
      truncate_last();
    }
    
    
    ~LongBits() {
      delete storage;
    }
    int size() const {return bits;}
    int size_in_bytes() const {return (bits + (bits_per_byte - 1)) / bits_per_byte;}
    void clear() {
      bits = 0; 
      margin_bits_in_last_storage = bits_per_storage;
      last_index_of_storage = 0;
      truncate_last();
    }
  
  protected:
    void auto_expand(const int require_min_capacity = last_index_of_storage) {
      int require_capacity(capacity_of_storage);
      while(require_capacity < (require_min_capacity << 1)){
        require_capacity <<= 1;
      }
      if(require_capacity <= capacity_of_storage){return;}
      storage_t *old_storage(storage);
      storage = new storage_t[require_capacity];
      capacity_of_storage = require_capacity;
      std::copy(old_storage, old_storage + last_index_of_storage + 1, storage); 
      delete [] old_storage;
    }
  
  
    static storage_t extract_1unit(
        const storage_t front, const storage_t next, 
        const int start_index){
      if(start_index){
        if(bit_order_LSB_first){
          storage_t mask1(lzeros(start_index));
          storage_t mask2(~mask1);
          return (((front >> start_index) & mask1)) 
              | (((next << (bits_per_storage - start_index)) & mask2));
        }else{
          storage_t mask1(rzeros(start_index));
          storage_t mask2(~mask1);
          return (((front << start_index) & mask1)) 
              | (((next >> (bits_per_storage - start_index)) & mask2));
        }
      }else{
        return front;
      }
    }
  
  public:
    const storage_t *data() const {
      return storage;
    }
    
    LongBits &append(const storage_t *content, int num_of_bits){
      
      if(num_of_bits <= 0){return *this;}
      
      bits += num_of_bits;
      int require_min_capacity((bits + (bits_per_storage - 1)) / bits_per_storage);
      auto_expand(require_min_capacity);
      
      const int index_shift(margin_bits_in_last_storage % bits_per_storage);
      int content_index(0);
      
      if(margin_bits_in_last_storage < bits_per_storage){
        storage[last_index_of_storage]
            |= extract_1unit(0, content[content_index], index_shift);
        //printf("%d %02X \n", index_shift, storage[last_index_of_storage]);
        if(margin_bits_in_last_storage > num_of_bits){
          margin_bits_in_last_storage -= num_of_bits;
          truncate_last();
          return *this;
        }else if(margin_bits_in_last_storage == num_of_bits){
          margin_bits_in_last_storage = bits_per_storage;
          last_index_of_storage++;
          return *this;
        }else{
          last_index_of_storage++;
          num_of_bits -= margin_bits_in_last_storage;
        }
      }
      
      int copy_units(num_of_bits / bits_per_storage);
      if(index_shift){
        for(; content_index < copy_units;
            content_index++, last_index_of_storage++){
          storage[last_index_of_storage] 
              = extract_1unit(content[content_index], content[content_index + 1], index_shift);
        }
      }else{
        std::copy(content, 
            content + copy_units, 
            storage + last_index_of_storage);
        content_index += copy_units;
        last_index_of_storage += copy_units;
      }
      num_of_bits %= bits_per_storage;
      margin_bits_in_last_storage = bits_per_storage - num_of_bits;
      
      if(num_of_bits){
        storage[last_index_of_storage] 
            = extract_1unit(content[content_index], 
                (index_shift > margin_bits_in_last_storage ? content[content_index + 1] : 0), 
                index_shift);
        truncate_last();
        //printf("%02X %02X \n", mask, storage[last_index_of_storage]);
      }
     
      return *this;
    }
    
    LongBits &append(const LongBits &target){
      return append(target.data(), target.size());
    }
    
    static LongBits convert(const storage_t *content, int num_of_bits){
      return LongBits(content, num_of_bits);
    }
    
    friend std::ostream &operator<<(std::ostream &out, const LongBits &target) {
      std::ostream::fmtflags orig_flags(out.flags());
      // Hexだった場合
      if(orig_flags & std::ios_base::hex){
        for(int i(0); i < target.size_in_bytes(); i++){
          out 
            << std::setfill('0') 
            << std::setw(2)
            << (unsigned int)(target.data()[i]) << ' ';
        }
      }else{
        // それ以外はバイナリ出力
        int bits(target.size());
        for(int i(0); i < target.size_in_bytes(); i++){
          storage_t copy(target.data()[i]);
          if(bit_order_LSB_first){
            for(int j(0); 
                bits && (j < LongBits::bits_per_storage); 
                j++, bits--, copy >>= 1){
              out << ((copy & 0x1) ? '1' : '0');
            }
          }else{
            storage_t mask(rzeros(LongBits::bits_per_storage - 1));
            for(int j(0); 
                bits && (j < LongBits::bits_per_storage); 
                j++, bits--, copy <<= 1){
              out << ((copy & mask) ? '1' : '0');
            }
          }
          out << ' ';
        }
      }
      out.flags(orig_flags);
      return out;
    }
    
    /**
     * 左シフト、破壊的
     * (前から追い出していく)
     * 
     */
    LongBits &operator<<=(int shifts){
      shifts = std::min(shifts, bits);
      if(!shifts){return *this;}
      
      int src_index(shifts / bits_per_storage);
      int src_aligned_shift(shifts % bits_per_storage);
      
      bits -= shifts;
      int dist_last_index(bits / bits_per_storage);
      
      if(src_aligned_shift){
        for(int dist_index(0); 
            dist_index < dist_last_index; 
            dist_index++, src_index++){
          storage[dist_index] 
              = extract_1unit(storage[src_index], 
                  storage[src_index + 1], 
                  src_aligned_shift);
        }
        storage[dist_last_index] 
            = extract_1unit(storage[src_index], 
                (src_index < last_index_of_storage ? storage[src_index + 1] : 0), 
                src_aligned_shift);
      }else{
        std::copy(storage + src_index, 
            storage + last_index_of_storage + 1, 
            storage);
      }
      
      last_index_of_storage = dist_last_index;
      margin_bits_in_last_storage = bits_per_storage - (bits % bits_per_storage);
      truncate_last();
       
      return *this;
    }
    
    /**
     * 左シフト、非破壊的
     * 
     */
    LongBits operator<<(int shifts) const {
      LongBits res(*this);
      return res <<= shifts;
    }
    
    /**
     * 右シフト、破壊的
     * (後ろから追い出していく)
     * 
     */
    LongBits &operator>>=(int shifts){
      shifts = std::min(shifts, bits);
      if(!shifts){return *this;}
      
      bits -= shifts;
      last_index_of_storage = bits / bits_per_storage;
      margin_bits_in_last_storage = bits_per_storage - (bits % bits_per_storage);
      truncate_last();
      
      return *this;
    }
    
    /**
     * 右シフト、非破壊的
     * 
     */
    LongBits operator>>(int shifts) const {
      LongBits res(*this);
      return res >>= shifts;
    }
  
  protected:
    struct invert_t {
      template <class T>
      void operator()(T &t){return t = ~t;}
    };
    struct invert2_t {
      template <class T>
      T operator()(const T &t){return ~t;}
    };
    
  public:
    /**
     * ビット反転、破壊的
     * 
     */
    LongBits &invert() {
      std::for_each(storage,
          storage + last_index_of_storage + 1,
          invert_t());
      truncate_last();
    }
    /**
     * ビット反転
     * 
     */
    LongBits operator~() const {
      return LongBits(*this, invert2_t());
    }
  
  protected:
    struct mask_t {
      const LongBits &_mask;
      int index_of_mask_storage;
      mask_t(const LongBits &mask) : _mask(mask), index_of_mask_storage(0){
        
      }
      typename LongBits::storage_t next_mask(){
        return (index_of_mask_storage <= _mask.last_index_of_storage 
            ? _mask.data()[index_of_mask_storage++]
            : LongBits::storage_t(0));
      }
    };
    struct and_t : public mask_t {
      and_t(const LongBits &mask) : mask_t(mask){}
      template <class T>
      void operator()(T &t){t &= next_mask();}
    };
    struct and2_t : public mask_t {
      and2_t(const LongBits &mask) : mask_t(mask){}
      template <class T>
      T operator()(const T &t){return t & next_mask();}
    };
    struct or_t : public mask_t {
      or_t(const LongBits &mask) : mask_t(mask){}
      template <class T>
      void operator()(T &t){t |= next_mask();}
    };
    struct or2_t : public mask_t {
      or2_t(const LongBits &mask) : mask_t(mask){}
      template <class T>
      T operator()(const T &t){return t | next_mask();}
    };
    struct xor_t : public mask_t {
      xor_t(const LongBits &mask) : mask_t(mask){}
      template <class T>
      void operator()(T &t){t ^= next_mask();}
    };
    struct xor2_t : public mask_t {
      xor2_t(const LongBits &mask) : mask_t(mask){}
      template <class T>
      T operator()(const T &t){return t ^ next_mask();}
    };
    
  public:
    /**
     * ビット AND、破壊的
     * 
     */
    LongBits &operator&=(const LongBits &mask) {
      std::for_each(storage,
          storage + last_index_of_storage + 1,
          and_t(mask));
      truncate_last();
    }
    /**
     * ビット AND、非破壊的
     * 
     */
    LongBits operator&(const LongBits &mask) const {
      return LongBits(*this, and2_t(mask));
    }
    /**
     * ビット OR、破壊的
     * 
     */
    LongBits &operator|=(const LongBits &mask) {
      std::for_each(storage,
          storage + last_index_of_storage + 1,
          or_t(mask));
      truncate_last();
    }
    /**
     * ビット OR、非破壊的
     * 
     */
    LongBits operator|(const LongBits &mask) const {
      return LongBits(*this, or2_t(mask));
    }
    /**
     * ビット XOR、破壊的
     * 
     */
    LongBits &operator^=(const LongBits &mask) {
      std::for_each(storage,
          storage + last_index_of_storage + 1,
          xor_t(mask));
      truncate_last();
    }
    /**
     * ビット XOR、非破壊的
     * 
     */
    LongBits operator^(const LongBits &mask) const {
      return LongBits(*this, xor2_t(mask));
    }
    
  protected:
    struct reverse_in_storage_t {
      template <class T, int mask_bits>
      struct loop {
        static void exec(T &t){
          T mask(0);
          for(int i(0); i < (((sizeof(T) * 8) >> 1) / mask_bits); i++){
            for(int j(0); j < mask_bits; j++){
              mask <<= 1;
              mask |= 0x1;
            }
            mask <<= mask_bits;
          }
          t = ((t << mask_bits) & mask) | ((t >> mask_bits) & (~mask));
          loop<T, (mask_bits >> 1)>::exec(t);
        }
      };
      template <class T>
      struct loop<T, 1> {
        static void exec(T &t){
          T mask(0);
          for(int i(0); i < ((sizeof(T) * 8) >> 1); i++){
            mask <<= 1;
            mask |= 0x1;
            mask <<= 1;
          }
          t = ((t << 1) & mask) | ((t >> 1) & (~mask));
        }
      };
      template <class T>
      void operator()(T &t){
        loop<T, ((sizeof(T) * 8) >> 1)>::exec(t);
      }
    };
  public:
    /**
     * ビット逆転(storage単位)、破壊的
     * 
     */
    LongBits &reverse_in_storage() {
      std::for_each(storage,
          storage + last_index_of_storage + 1,
          reverse_in_storage_t());
      
      // 最後の部分については詰め方が逆になっている
      if(bit_order_LSB_first){
        storage[last_index_of_storage] <<= margin_bits_in_last_storage;
      }else{
        storage[last_index_of_storage] >>= margin_bits_in_last_storage;
      }
      
      truncate_last();
      return *this;
    }
};

#ifdef already_defined_min
#define min already_defined_min
#undef already_defined_min
#endif
#ifdef already_defined_max
#define max already_defined_max
#undef already_defined_max
#endif

#endif /* __LONG_BITS_H__ */