array.h

Go to the documentation of this file.

// This file is part of Hermes2D.
//
// Hermes2D 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 2 of the License, or
// (at your option) any later version.
//
// Hermes2D 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.
//
// You should have received a copy of the GNU General Public License
// along with Hermes2D.  If not, see <http://www.gnu.org/licenses/>.
#ifndef __HERMES_COMMON_ARRAY_H
#define __HERMES_COMMON_ARRAY_H

#include <vector>
#include <limits.h>

#ifndef INVALID_IDX
#define INVALID_IDX      INT_MAX
#endif
namespace Hermes
{
  namespace Hermes2D
  {
    template<class TYPE>
    class Array
    {
    protected:
      Hermes::vector<TYPE*> pages; 
      Hermes::vector<int> unused;
      int  size, nitems;
      bool append_only;

      static const int HERMES_PAGE_BITS = 10;
      static const int HERMES_PAGE_SIZE = 1 << HERMES_PAGE_BITS;
      static const int HERMES_PAGE_MASK = HERMES_PAGE_SIZE-1;

    public:

      Array()
      {
        size = nitems = 0;
        append_only = false;
      }

      Array(Array& array) { copy(array); }

      ~Array() { free(); }

      void copy(const Array& array)
      {
        free();

        pages = array.pages;
        unused = array.unused;
        size = array.size;
        nitems = array.nitems;
        append_only = array.append_only;

        for (unsigned i = 0; i < pages.size(); i++)
        {
          TYPE* new_page = new TYPE[HERMES_PAGE_SIZE];
          memcpy(new_page, pages[i], sizeof(TYPE) * HERMES_PAGE_SIZE);
          pages[i] = new_page;
        }
      }

      void free()
      {
        for (unsigned i = 0; i < pages.size(); i++) delete [] pages[i];
        pages.clear();
        unused.clear();
        size = nitems = 0;
      }

      void set_append_only(bool append_only)
      {
        this->append_only = append_only;
      }

      int add(TYPE item)
      {
        TYPE* ptr = this->add();
        *ptr = item;
        return ptr->id;
      }

      TYPE* add()
      {
        TYPE* item;
        if (unused.empty() || append_only)
        {
          if (!(size & HERMES_PAGE_MASK))
          {
            TYPE* new_page = new TYPE[HERMES_PAGE_SIZE];
            pages.push_back(new_page);
          }
          item = pages[size >> HERMES_PAGE_BITS] + (size & HERMES_PAGE_MASK);
          item->id = size++;
          item->used = 1;
        }
        else
        {
          int id = unused.back();
          unused.pop_back();
          item = pages[id >> HERMES_PAGE_BITS] + (id & HERMES_PAGE_MASK);
          item->used = 1;
        }
        nitems++;
        return item;
      }

      void remove(int id)
      {
        assert(id >= 0 && id < size);
        TYPE* item = pages[id >> HERMES_PAGE_BITS] + (id & HERMES_PAGE_MASK);
        assert(item->used);
        item->used = 0;
        unused.push_back(id);
        nitems--;
      }

      // Iterators

      int first(int idx = 0)
      {
        int index = idx;
        while (get(index).used == false)
        {
          index++;
          if (index >= nitems) return INVALID_IDX;
        }
        return index;
      }

      int next(int idx = 0)
      {
        int index = idx + 1;
        while (get(index).used == false)
        {
          index++;
          if (index >= nitems) return INVALID_IDX;
        }
        return index;
      }

      int last(int idx = INT_MAX)
      {
        int index = idx;
        if (index > nitems - 1) index = nitems - 1;
        while (get(index).used == false)
        {
          index--;
          if (index < 0) return INVALID_IDX;
        }
        return index;
      }

      int prev(int idx = INT_MAX)
      {
        int index = idx - 1;
        if (index > nitems - 1) index = nitems - 1;
        while (get(index).used == false)
        {
          index--;
          if (index < 0) return INVALID_IDX;
        }
        return index;
      }

      bool exists(int idx)
      {
        if (get(idx).used == true) return true;
        else return false;
      }

      void force_size(int size)
      {
        free();
        while (size > 0)
        {
          TYPE* new_page = new TYPE[HERMES_PAGE_SIZE];
          memset(new_page, 0, sizeof(TYPE) * HERMES_PAGE_SIZE);
          pages.push_back(new_page);
          size -= HERMES_PAGE_SIZE;
        }
        this->size = pages.size() * HERMES_PAGE_SIZE;
      }

      void post_load_scan(int start = 0)
      {
        nitems = 0;
        for (int i = start; i < size; i++)
          if (get(i).used) nitems++;
          else unused.push_back(i);
      }

      void skip_slot()
      {
        if (!(size & HERMES_PAGE_MASK))
        {
          TYPE* new_page = new TYPE[HERMES_PAGE_SIZE];
          pages.push_back(new_page);
        }
        TYPE* item = pages[size >> HERMES_PAGE_BITS] + (size & HERMES_PAGE_MASK);
        item->id = size++;
        item->used = 0;
        nitems++;
      }

      int get_size() const { return size; }
      int get_num_items() const { return nitems; }

      TYPE& get(int id) const { return pages[id >> HERMES_PAGE_BITS][id & HERMES_PAGE_MASK]; }
      TYPE& operator[] (int id) const { return get(id); }

    };

    template<class TYPE>
    class LightArray
    {
    protected:
      Hermes::vector<TYPE*> pages; //\todo standard array for maximum access speed
      Hermes::vector<bool*> presence; //\todo standard array for maximum access speed
      unsigned int size;

      const unsigned int page_bits;
      const unsigned int page_size;
      const unsigned int page_mask;

    public:

      LightArray(unsigned int page_bits = 9) : page_bits(page_bits), page_size(1 << page_bits), page_mask((1 << page_bits) - 1)
      {
        size = 0;
      }

      ~LightArray()
      {
        for(unsigned int i = 0; i < pages.size(); i++)
        {
          delete [] pages[i];
          delete [] presence[i];
        }
        pages.clear();
        presence.clear();
      }

      void add(TYPE item, unsigned int id)
      {
        TYPE* temp;
        while(id >= pages.size() * page_size)
        {
          TYPE* new_page = new TYPE[page_size];
          pages.push_back(new_page);

          bool* new_page_presence = new bool[page_size];
          memset(new_page_presence, 0, page_size * sizeof(bool));
          presence.push_back(new_page_presence);
        }

        temp = pages[id >> page_bits] + (id & page_mask);
        *temp = item;

        presence[id >> page_bits][id & page_mask] = true;

        if(id >= size)
          size = id + 1;
        return;
      }

      unsigned int get_size() const
      {
        return size;
      }

      bool present(unsigned int id) const
      {
        if(id >= size)
          return false;
        return presence[id >> page_bits][id & page_mask];
      }

      TYPE& get(unsigned int id) const
      {
        assert(id < size);
        return pages[id >> page_bits][id & page_mask];
      }

    };
  }
}
#endif