/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
#ifndef PackedIntVector_h
#define PackedIntVector_h

#include <wtf/BitVector.h>

namespace WTF {

// This class allows you to create an array of integers, where those
// integers have only a handful of bits each. It is not meant to be
// efficient in time, but only in space. (Though making it efficient
// in time for power-of-2 values of bitCount would not be difficult.)
// Note that this does not work as expected for signed types, if you
// are relying on the sign being preserved.

template<typename T, unsigned bitCount>
class PackedIntVector {
public:
    static_assert(bitCount, "bitCount must not be zero!");
    static_assert(bitCount < sizeof(void*) * 8, "bitCount must not exceed the address space limit!");

    PackedIntVector()
    {
    }
    
    PackedIntVector(const PackedIntVector& other)
        : m_bits(other.m_bits)
    {
    }
    
    PackedIntVector& operator=(const PackedIntVector& other)
    {
        m_bits = other.m_bits;
        return *this;
    }
    
    size_t size() const
    {
        return m_bits.size() / bitCount;
    }
    
    void ensureSize(size_t numInts)
    {
        m_bits.ensureSize(numInts * bitCount);
    }
    
    void resize(size_t numInts)
    {
        m_bits.resize(numInts * bitCount);
    }
    
    void clearAll()
    {
        m_bits.clearAll();
    }
    
    T get(size_t index) const
    {
        uintptr_t result = 0;
        for (unsigned subIndex = 0; subIndex < bitCount; ++subIndex) {
            result <<= 1;
            result |= (m_bits.quickGet(index * bitCount + subIndex) ? 1 : 0);
        }
        return static_cast<T>(result);
    }
    
    void set(size_t index, T value)
    {
        // Do arithmetic using uintptr_t, because (1) we know what it is
        // (T might be an enum) and (2) it's the largest integer type that
        // is likely to perform decently well.
        uintptr_t myValue = static_cast<uintptr_t>(value);
        
        // Preliminary sanity check that the value is not out of range.
        ASSERT((myValue & mask()) == myValue);
        
        for (unsigned subIndex = bitCount; subIndex-- > 0;) {
            m_bits.quickSet(index * bitCount + subIndex, !!(myValue & 1));
            myValue >>= 1;
        }
        
        // Final sanity check that we stored what the user thought we
        // stored.
        ASSERT(get(index) == value);
    }
private:
    // This returns the mask, and is careful to not step on the wrap-around
    // semantics of the shift amount (1 << 32 is 1 since 32 wraps to 0). There
    // is the separate question of why you would ever use this to store 32-bit
    // or 64-bit values, but it's probably better to have this work as expected
    // in such situations regardless.
    static uintptr_t mask() { return (static_cast<uintptr_t>(2) << (bitCount - 1)) - 1; }
               
    // Stores integers bit by bit in big endian.
    BitVector m_bits;
};

} // namespace WTF

using WTF::PackedIntVector;

#endif // PackedIntVector_h