kernel.h

//
//  Deformabel Simplicial Complex (DSC) method
//  Copyright (C) 2013  Technical University of Denmark
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  See licence.txt for a copy of the GNU General Public License.

#pragma once

#include <cassert>
#include <iostream>
#include <vector>
#include <set>

#include "kernel_iterator.h"

namespace is_mesh
{

    class ISMesh;

    namespace util
    {
        
        template< typename key_t_, typename value_t_ >
        struct kernel_element
        {
            using value_type = value_t_;

            enum state_type { VALID, MARKED, EMPTY, EXCLUDED };
            
            kernel_element() : value(nullptr), state{kernel_element::EMPTY} { }
            
            kernel_element(const kernel_element& ke) = delete;

            kernel_element(kernel_element&& ke) : value{std::move(ke.value)}, state{ke.state} {
            }

            kernel_element&& operator=(kernel_element&& other) {
                if (this != &other) {
                    value = std::move(other.value);
                    state = other.state;
                }
                return *this;
            }
            
            value_type              value;
            state_type              state;
        };
    }
    
    template<typename key_type, typename value_type>
    class kernel
    {
    public:
        using kernel_type = kernel<key_type, value_type>;
        using kernel_key_type = key_type;
        using kernel_element = util::kernel_element<key_type, value_type>;
        using iterator = kernel_iterator<kernel_type>;
        using const_iterator = iterator const;

        friend class kernel_iterator<kernel_type>;

        bool readonly = false;

    private:
        std::vector<kernel_element> m_data;
        std::vector<key_type> m_data_freelist;
        std::vector<key_type> m_data_marked_for_deletion;
    private:
        kernel_element& lookup(key_type k)
        {
//          assume key_type is integer type
            assert(k >= 0 || !"looked up with negative element");
            assert((int)k < m_data.size() || !"k out of range");
            return m_data[k];
        }

        kernel_element& get_next_free_cell(unsigned int &key)
        {
            if (m_data_freelist.size()==0){
                key = (unsigned int)m_data.size();
                m_data.emplace_back();
                return m_data.back();
            } else {
                key = (unsigned int)m_data_freelist.back();
                m_data_freelist.pop_back();
                return m_data[key];
            }
        }
    public:
        
        kernel(size_t reservedSize =64)
        {
            m_data.reserve(reservedSize);
        }
        
        ~kernel()
        {
        }
        
        size_t size() const     { return m_data.size() - m_data_freelist.size(); }


        size_t capacity() const     { return m_data.size(); }

        bool      empty()    { return size() == 0; }

        template<typename... Values>
        const_iterator create(ISMesh* isMesh, Values... values)
        {
            assert(!readonly);
            unsigned int key;
            kernel_element& cur = get_next_free_cell(key);

            assert(cur.state != kernel_element::VALID || !"Cannot create new element, duplicate key.");
            assert(cur.state != kernel_element::MARKED || !"Attempted to overwrite a marked element.");
            assert(cur.state != kernel_element::EXCLUDED || !"Attempted to overwrite an excluded element.");

            cur.value = value_type{isMesh, values...};
            cur.state = kernel_element::VALID;
            return iterator(this, key);
        }
        
        const_iterator end() const
        {
            return iterator(this, key_type{(unsigned int)m_data.size()});
        }
        
        const_iterator begin() const
        {
            unsigned int i = 0;
            // find first valid element (if any)
            for (;i<m_data.size();i++){
                if (m_data[i].state == kernel_element::VALID){
                    break;
                }
            }
            return iterator(this, key_type{i});
        }
        
        void erase(key_type const & k)
        {
            assert(!readonly);
            kernel_element& p = lookup(k);
            assert (p.state == kernel_element::VALID || p.state == kernel_element::EXCLUDED || !"Attempted to remove a non-valid element!");
            if (p.state != kernel_element::VALID && p.state != kernel_element::EXCLUDED )
            {
                //No element with that key.
                return;
            }
            p.state = kernel_element::MARKED;
            m_data_marked_for_deletion.push_back(k);
        }
        
        void erase(const iterator& it)
        {
            assert(!readonly);
            erase(it.key());
        }
        
        void clear()
        {
            assert(!readonly);
            m_data.clear();
            m_data_freelist.clear();
            m_data_marked_for_deletion.clear();
        }
        
        iterator find_iterator(key_type k)
        {
            if (is_valid(k))
                return iterator(this, k);
            else
                return end();
        }

        iterator find_valid_iterator(key_type k)
        {
            if (k>=m_data.size()){
                return end();
            }
            iterator res(this, k);
            if (!is_valid(k) || is_excluded(k)){
                res++;
            }
            assert(res == end() || is_valid(res.key()));
            return res;
        }

        value_type & get(key_type k)
        {
            kernel_element& tmp = lookup(k);
            assert(tmp.state == kernel_element::VALID || tmp.state == kernel_element::EXCLUDED);
            return tmp.value;
        }

        const value_type &get(key_type k) const
        {
            return const_cast<kernel_type *>(this)->get(k);
        }

        char * data(){
            return (char*)m_data.data();
        }

        bool is_valid(key_type k)
        {
            kernel_element& tmp = lookup(k);
            if (tmp.state == kernel_element::VALID || tmp.state == kernel_element::EXCLUDED ) return true;
            return false;
        }

        bool is_excluded(key_type k){
            kernel_element& tmp = lookup(k);
            if (tmp.state == kernel_element::EXCLUDED ) return true;
            return false;
        }

        std::vector<key_type> commit_all()
        {
            assert(!readonly);
            std::vector<key_type> deletedKeys = m_data_marked_for_deletion;
            for (auto key : m_data_marked_for_deletion){
                auto & p = m_data[key];

                //m_alloc.destroy(&p);  // needed?
                p.state = kernel_element::EMPTY;
                m_data_freelist.push_back(key);
            }
            m_data_marked_for_deletion.clear();
            return deletedKeys;
        }

        void revert_excluded(){
            assert(!readonly);
            for (auto &e : m_data){
                if (e.state == kernel_element::state_type::EXCLUDED){
                    e.state = kernel_element::state_type::VALID;
                }
            }
        }

        void exclude_using_include_set(std::set<key_type> include_set){
            assert(!readonly);
            for (unsigned int i=0;i<m_data.size();i++){
                auto& e= m_data[i];
                key_type k{i};
                if (e.state == kernel_element::state_type::VALID){
                    if (include_set.find(k) == include_set.end()) {
                        e.state = kernel_element::state_type::EXCLUDED;
                    }
                }
            };
        }
        
        std::vector<key_type> garbage_collect()
        {
            assert(!readonly);
            return commit_all();
        }
    };
}