IndexedArray.h#
Implementation of a special kind of map that stores the data in a linear, contiguous store (std::vector interface), but additionally contains an Index to them (std::map interface). Supports custom association of names with values, and retrieval of indices by name or values by index.
Detailed Description#
PowerVR by Imagination, Developer Technology Team.
Copyright (c) Imagination Technologies Limited.
Includes#
algorithmlistmapvector
Included By#
Namespaces#
Classes#
Source Code#
#pragma once
#include <vector>
#include <map>
#include <list>
#include <algorithm>
namespace pvr {
template<typename ValueType_, typename IndexType_ = std::string>
class IndexedArray
{
private:
struct DictionaryEntry
{
ValueType_ value;
IndexType_ key;
DictionaryEntry() {}
DictionaryEntry(const IndexType_& key, const ValueType_& value) : key(key), value(value) {}
};
struct StorageItem_ : DictionaryEntry
{
bool isUnused;
StorageItem_() : isUnused(false) {}
StorageItem_(const IndexType_& key, const ValueType_& value) : DictionaryEntry(key, value), isUnused(false) {}
};
typedef std::vector<StorageItem_> vectortype_;
typedef typename std::map<IndexType_, size_t> maptype_;
typedef std::list<size_t> deleteditemlisttype_;
vectortype_ mystorage;
maptype_ myindex;
deleteditemlisttype_ myDeletedItems;
public:
class iterator
{
friend class IndexedArray<ValueType_, IndexType_>;
class const_iterator;
StorageItem_* start;
size_t current;
size_t size; // required for out-of-bounds checks when skipping empty...
iterator(StorageItem_* start, size_t size, size_t current = 0) : start(start), current(current), size(size) {}
public:
iterator(const const_iterator& rhs) : start(rhs.start), size(rhs.size), current(rhs.current) {}
DictionaryEntry& operator*() { return *(start + current); }
DictionaryEntry* operator->() { return (start + current); }
size_t getItemIndex() { return current; }
iterator& operator++()
{
while ((start + (++current))->isUnused && current != size) {} // skip empty values
return *this;
}
iterator operator++(int)
{
iterator ret = *this;
while ((start + (++current))->isUnused && current != size) {} // skip empty values
++(*this);
return ret;
}
iterator& operator--()
{
while ((start + (--current))->isUnused && current != static_cast<size_t>(-1)) {} // CAREFUL! this is a size_t, which means it WILL eventually overflow.
return *this;
}
iterator operator--(int)
{
iterator ret = *this;
--(*this);
return ret;
}
bool operator!=(const iterator& rhs) { return this->current != rhs.current; }
bool operator==(const iterator& rhs) { return !((*this) != rhs); }
};
class const_iterator
{
friend class IndexedArray<ValueType_, IndexType_>;
const StorageItem_* start;
size_t current;
size_t size; // required for out-of-bounds checks when skipping empty...
const_iterator(const StorageItem_* start, size_t size, size_t current = 0) : start(start), size(size), current(current) {}
public:
const DictionaryEntry& operator*() { return *(start + current); }
const DictionaryEntry* operator->() { return (start + current); }
size_t getItemIndex() { return current; }
const_iterator& operator++()
{
while (++current < size && (start + current)->isUnused) {} // skip empty values
return *this;
}
const_iterator operator++(int)
{
const_iterator ret = *this;
++(*this);
return ret;
}
const_iterator& operator--()
{
while (--current != static_cast<size_t>(-1) && (start + current)->isUnused) {} // CAREFUL! this is a size_t, which means it WILL eventually overflow.
return *this;
}
const_iterator operator--(int)
{
iterator ret = *this;
--(*this);
return ret;
}
bool operator!=(const const_iterator& rhs) { return this->current != rhs.current; }
bool operator==(const const_iterator& rhs) { return !((*this) != rhs); }
};
typedef typename maptype_::iterator index_iterator;
typedef typename maptype_::const_iterator const_index_iterator;
iterator begin()
{
if (!mystorage.empty())
{
iterator ret(&mystorage.front(), mystorage.size());
while ((ret.start + ret.current)->isUnused && (ret.current != ret.size)) { ++ret.current; } // skip empty values
return ret;
}
else
{
return iterator(NULL, 0);
}
}
const_iterator begin() const
{
if (!mystorage.empty())
{
const_iterator ret(&mystorage.front(), mystorage.size());
while ((ret.start + ret.current)->isUnused && ret.current != ret.size) { ++ret.current; } // skip empty values
return ret;
}
else
{
return const_iterator(NULL, 0);
}
}
typename maptype_::iterator indexed_find(const IndexType_& key) { return myindex.find(key); }
typename maptype_::const_iterator indexed_find(const IndexType_& key) const { return myindex.find(key); }
typename maptype_::iterator indexed_begin() { return myindex.begin(); }
typename maptype_::const_iterator indexed_begin() const { return myindex.begin(); }
typename maptype_::iterator indexed_end() { return myindex.end(); }
typename maptype_::const_iterator indexed_end() const { return myindex.end(); }
iterator end() { return mystorage.empty() ? iterator(NULL, 0) : iterator(&mystorage.front(), mystorage.size(), mystorage.size()); }
const_iterator end() const { return mystorage.empty() ? const_iterator(NULL, 0) : const_iterator(&mystorage.front(), mystorage.size(), mystorage.size()); }
void insertAt(size_t where, const IndexType_& key, const ValueType_& val)
{
if (insert(key, val) != where) { relocate(key, where); }
}
size_t insert(const IndexType_& key, const ValueType_& val)
{
std::pair<typename maptype_::iterator, bool> found = myindex.insert(std::make_pair(key, 0));
if (!found.second) // Element already existed!
{ mystorage[found.first->second].value = val; } else
{
found.first->second = insertinvector(key, val);
}
return found.first->second;
}
size_t getIndex(const IndexType_& key) const
{
typename maptype_::const_iterator found = myindex.find(key);
if (found != myindex.end()) // Element already existed!
{ return found->second; } return static_cast<size_t>(-1);
}
void erase(const IndexType_& key)
{
typename maptype_::iterator where = myindex.find(key);
if (where != myindex.end())
{
removefromvector(where->second);
myindex.erase(where);
// SPECIAL CASE: If no more items are left, there is absolutely no point in NOT compacting, as no iterators or indices exist to be invalidated, so we can clean up
// even though "deferred" was asked. Additionally, this is essentially free, except maybe for the list...
if (myindex.empty())
{
mystorage.clear();
myDeletedItems.clear();
}
}
}
ValueType_& operator[](size_t idx) { return mystorage[idx].value; }
const ValueType_& operator[](size_t idx) const { return mystorage[idx].value; }
ValueType_& operator[](const IndexType_& key) { return mystorage[myindex.find(key)->second].value; }
const ValueType_& operator[](const IndexType_& key) const { return mystorage[myindex.find(key)->second].value; }
void compact()
{
// We can do that because the last remove() tears down all datastructures used.
if (!myindex.size()) { return; }
// First, make sure there is something to compact...
deleteditemlisttype_::iterator unused_spot = myDeletedItems.begin();
while (myDeletedItems.size() && unused_spot != myDeletedItems.end())
{
// Last item in the storage vector.
size_t last = mystorage.size();
// 1) Trim the end of the vector...
while (last-- && mystorage[last].isUnused)
{
mystorage.pop_back();
// Rinse, repeat. If size is zero, there is nothing to do.
}
// Either the storage is empty
if (mystorage.empty())
{
myDeletedItems.clear();
// the rest should already be cleared...
// the loop will exit naturally
}
else // Or we can have find its last item!
{
// 2)Trim any items from the end of the unused spots list that may have been trimmed off by the vector...
while (unused_spot != myDeletedItems.end() && *unused_spot >= last) { myDeletedItems.erase(unused_spot++); }
// Any spots left?
if (unused_spot != myDeletedItems.end())
{
// Do the actual data movement. After all we've been through, we know that
// i. The last item of the vector is a valid item (guaranteed by 1)
// ii. The unused spot is not out of bounds of the vector
// iii.
// Copy by hand(as we have not defined a move assignment operator for compatibility reasons.
// Also, since the std::string does not throw, this makes easier to reason about exceptions.
mystorage[*unused_spot].value = std::move(mystorage[last].value);
mystorage[*unused_spot].key = std::move(mystorage[last].key);
mystorage[*unused_spot].isUnused = false;
myindex[mystorage[*unused_spot].key] = *unused_spot;
mystorage.pop_back();
myDeletedItems.erase(unused_spot++);
} // else : No action needed - unused spots has been trimmed off completely, so no movement is possible, or necessary...
}
}
}
void clear()
{
myindex.clear();
mystorage.clear();
myDeletedItems.clear();
}
size_t size() const { return myindex.size(); }
size_t sizeWithDeleted() const { return mystorage.size(); }
size_t capacity() const { return mystorage.size(); }
size_t deletedItemsCount() const { return myDeletedItems.size(); }
bool relocate(const IndexType_& key, size_t index)
{
typename maptype_::iterator found = myindex.find(key);
if (found == myindex.end()) { return false; }
size_t old_index = myindex[key];
if (index == old_index) { return true; } // No-op
if (index + 1 > mystorage.size()) // Storage not big enough.
{
// Grow, and mark unused all required items. Need to add all spots (But the last) to unusedspots.
size_t oldsize = mystorage.size();
mystorage.resize(index + 1);
for (size_t i = oldsize; i < index; ++i)
{
myDeletedItems.push_front(i);
mystorage[i].isUnused = 1;
}
mystorage.back() = mystorage[old_index];
removefromvector(old_index);
}
else if (mystorage[index].isUnused) // Lucky! Storage is big enough, and the item is not used!
{
deleteditemlisttype_::iterator place = std::find(myDeletedItems.begin(), myDeletedItems.end(), index);
assert(place != myDeletedItems.end()); // Shouldn't happen! Ever!
myDeletedItems.erase(place);
mystorage[index] = mystorage[old_index];
removefromvector(old_index);
}
else // Whoops! Space is already occupied. Swap with the old item!
{
myindex[mystorage[index].key] = old_index;
std::swap(mystorage[index], mystorage[old_index]);
}
myindex[key] = index;
return true;
}
private:
size_t insertinvector(const IndexType_& key, const ValueType_& val)
{
size_t retval;
if (myDeletedItems.empty())
{
retval = mystorage.size();
mystorage.emplace_back(StorageItem_());
mystorage.back().isUnused = false;
mystorage.back().key = key;
mystorage.back().value = val;
}
else
{
retval = myDeletedItems.back();
myDeletedItems.pop_back();
mystorage[retval].value = val;
mystorage[retval].key = key;
mystorage[retval].isUnused = false;
}
return retval;
}
void removefromvector(size_t index)
{
if (index == (mystorage.size() - 1))
{
// Removing the last item from the vector -- just pop it.
mystorage.pop_back();
}
else
{
// NOT the last item, so we just destruct it (to free any potential expensive resources),
// and then default-construct it (to have the spot destructible). We keep the reference to
// the key as we will need it.
myDeletedItems.push_front(index);
mystorage[index].isUnused = true;
mystorage[index].value.ValueType_::~ValueType_();
new (&mystorage[index].value) ValueType_;
}
}
};
} // namespace pvr