/*
 * table.h
 *
 *  Created on: Jun 5, 2010
 *      Author: Peter Goodman
 *     Version: $Id$
 */

#ifndef TABLE_H_
#define TABLE_H_

#include <cassert>

namespace peg {

    /// base type representing some contiguous memory and those operations
    /// on that memory
    ///
    /// this class imposes the following restrictions on parameterized
    /// types:
    ///     - they must have an assignment operator defined
    ///     - they must have a zero-argument constructor defined, or a
    ///       constructor with all arguments having default values.
    ///
    template <typename T>
    class table {
    public:
        typedef T &reference;
        typedef T *pointer;
        typedef T value;

    private:
        pointer slots;
        size_t num_slots;
        mutable size_t num_used_slots;

    public:

        table(void) throw()
         : slots(0)
         , num_slots(0)
         , num_used_slots(0) { }

        /// basic constructor
        table(const size_t len) throw()
         : slots(0)
         , num_slots(0)
         , num_used_slots(0) {
            reserve(len, false);
        }

        /// copy constructor
        table(const table<T> &other) throw()
         : slots(0)
         , num_slots(0)
         , num_used_slots(0) {
            extend(other);
        }

        ~table(void) {
            if(0 != slots) {
                delete [] slots;
                slots = 0;
            }
            num_slots = 0;
            num_used_slots = 0;
        }

        /// access an element in a slot of the table
        inline reference get(const size_t offset) const throw() {
            assert(offset < num_slots);
            assert(0 != slots);

            if(offset > num_used_slots) {
                num_used_slots = offset + 1;
            }

            return slots[offset];
        }

        inline reference operator[](const size_t offset) const throw() {
            return get(offset);
        }

        /// get the element at the back
        inline reference back(void) const throw() {
            return get(num_used_slots - 1);
        }

        /// update an element in a slot
        inline void set(const size_t offset, const reference item) throw() {
            assert(offset < num_used_slots);
            assert(0 != slots);

            slots[offset] = item;
        }

        /// swap two elements in the table
        inline void swap(const size_t i, const size_t j) throw() {
            assert(0 != slots);
            assert(i < num_used_slots);
            assert(j < num_used_slots);

            reference old_i(slots[i]);
            slots[i] = slots[j];
            slots[j] = old_i;
        }

        /// get the length of the table
        inline size_t size(void) const throw() {
            return num_used_slots;
        }

        /// extend this table with another table
        void extend(const table<T> &other) throw() {

            if(0 == other.num_used_slots) {
                return;
            }

            const size_t old_len(num_used_slots);
            reserve(old_len + other.num_used_slots, true);
            set_size(old_len + other.num_used_slots);

            for(size_t i(0); i < other.num_used_slots; ++i) {
                slots[i + old_len] = other.slots[i];
            }
        }

        /// push_back an item to this table
        inline void push_back(const reference item) throw() {
            const size_t old_len(num_used_slots);
            reserve(old_len + 1, true);
            set_size(old_len + 1);
            slots[old_len] = item;
        }

        inline void push_back(value item_val) throw() {
            const reference item(item_val);
            const size_t old_len(num_used_slots);
            reserve(old_len + 1, true);
            set_size(old_len + 1);
            slots[old_len] = item;
        }

        inline reference pop_back(void) throw() {
            assert(0 < num_used_slots);
            reference ref(back());
            --num_used_slots;
            return ref;
        }

        /// reverse the order of items in this table
        inline void reverse(void) throw() {
            const size_t mid = num_used_slots / 2;
            for (size_t j(0); j < mid; ++j) {
                swap(j, num_used_slots - j - 1);
            }
        }

        /// clear out the table, this actually just changes the length of
        /// the table
        inline void clear(void) throw() {
            num_used_slots = 0;
        }

        /// remove an element from the table and slide all elements that
        /// follow it back into its position
        void remove(const size_t i) {
            // is j in range?
            if (i >= num_used_slots) {
                return;
            }

            // remove T at index j
            --num_used_slots;
            for (size_t j(i) ; j < num_used_slots; ++j) {
                slots[j] = slots[j + 1];
            }
        }

        /// guarantee that this table can scale up to a minimum length
        void reserve(
            const size_t min_slots,
            const bool copy_old=true
        ) {

            if(num_slots >= min_slots) {
                return;
            }

            const size_t old_num_slots(num_slots);
            size_t new_num_slots(num_slots);

            if(!(new_num_slots & 1)) {
                ++new_num_slots;
            }

            for(; new_num_slots < min_slots; new_num_slots *= 2) {
                // do do la la de do
            }

            pointer new_slots(0);
            try {
                new_slots = new value[new_num_slots];
            } catch(...) {
                new_slots = 0;
            }

            assert(0 != new_slots);

            if(0 != slots) {
                if(copy_old) {
                    for(size_t i(0); i < old_num_slots; ++i) {
                        new_slots[i] = slots[i];
                    }
                }

                delete [] slots;
            }

            num_slots = new_num_slots;
            slots = new_slots;
        }

        /// change the current length of the table
        inline void set_size(const size_t new_len) throw() {
            assert(new_len <= num_slots);
            num_used_slots = new_len;
        }

        inline bool is_empty(void) const throw() {
            return 0 == num_used_slots;
        }
    };
}

#endif /* TABLE_H_ */