Container.cpp

Go to the documentation of this file.

/*
 * This file is a part of the Biology project by eons LLC.
 * Biology (aka Develop Biology) is a framework for approaching software
 * development from a natural sciences perspective.
 *
 * Copyright (C) 2022 Séon O'Shannon & eons LLC
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero 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 Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#include "bio/common/container/Container.h"
#include "bio/common/container/Iterator.h"
#include <limits>
#include <algorithm>
 
namespace bio {
 
Container::Container(
    const Index expectedSize,
    std::size_t stepSize
)
    :
    m_firstFree(1),
    m_size(expectedSize + 1),
    m_tempItt(NULL)
{
    m_store = (unsigned char*)std::malloc(m_size * stepSize);
    BIO_ASSERT(m_store)
}
 
Container::Container(const Container& other)
    :
    m_firstFree(other.m_firstFree),
    m_size(other.m_size),
    m_tempItt(NULL)
{
    m_store = (unsigned char*)std::malloc(m_size * other.GetStepSize());
    BIO_ASSERT(m_store)
    Import(&other); // <- NOT VIRTUAL (in ctor).
}
 
Container::~Container()
{
    Clear(); // <- NOT VIRTUAL (in dtor).
    if (m_tempItt)
    {
        delete m_tempItt;
        m_tempItt = NULL;
    }
    std::free(m_store);
}
 
Index Container::GetBeginIndex() const
{
    return 1;
}
 
Index Container::GetEndIndex() const
{
    return GetAllocatedSize();
}
 
Index Container::GetCapacity() const
{
    return m_size;
}
 
Index Container::GetAllocatedSize() const
{
    return m_firstFree;
}
 
Index Container::GetNumberOfElements() const
{
    return GetAllocatedSize() - m_deallocated.size();
}
 
bool Container::IsInRange(const Index index) const
{
    return index && index < m_size;
}
 
bool Container::IsFree(Index index) const
{
    if (index >= m_firstFree)
    {
        return true;
    }
    return std::find(
        m_deallocated.begin(),
        m_deallocated.end(),
        index
    ) != m_deallocated.end();
}
 
bool Container::IsAllocated(const Index index) const
{
    return IsInRange(index) && !IsFree(index);
}
 
void Container::Expand()
{
    BIO_SANITIZE(m_size < std::numeric_limits< Index >::max(), ,
        return)
    Index targetSize = m_size * m_size; //squared.
    if (targetSize < m_size)
    {
        targetSize = std::numeric_limits< Index >::max();
    }
    m_store = (unsigned char*)std::realloc(
        m_store,
        targetSize * GetStepSize());
    BIO_SANITIZE(m_store, ,
        return)
    m_size = targetSize;
}
 
Index Container::Add(const ByteStream content)
{
    Index ret = GetNextAvailableIndex();
    BIO_SANITIZE(ret, ,
        return ret)
    std::memcpy(
        &m_store[ret * sizeof(ByteStream)],
        content,
        sizeof(ByteStream));
    return ret;
}
 
Index Container::Insert(
    const ByteStream content,
    const Index index
)
{
    BIO_SANITIZE(index, ,
        return InvalidIndex())
 
    if (index == m_firstFree)
    {
        //no adjustment necessary.
        Add(content);
    }
 
    if (GetAllocatedSize() == GetCapacity())
    {
        Expand();
    }
 
    //move all memory down 1.
    std::memcpy(
        &m_store[index * GetStepSize()],
        &m_store[(index + 1) * GetStepSize()],
        (m_firstFree - index) * GetStepSize());
 
    //adjust all deallocated positions.
    std::deque< Index > adjustedDeallocations;
    for (
        std::deque< Index >::iterator dlc = m_deallocated.begin();
        dlc != m_deallocated.end();
        ++dlc
        )
    {
        adjustedDeallocations.push_front(*dlc + 1);
    }
    m_deallocated = adjustedDeallocations;
 
    //make sure we add to the desired index.
    m_deallocated.push_front(index);
 
    //add the content.
    return Add(content);
}
 
ByteStream Container::Access(const Index index)
{
    BIO_SANITIZE(IsAllocated(index), ,
        return NULL)
    ByteStream* ret;
    std::memcpy(
        ret,
        &m_store[index * sizeof(ByteStream)],
        sizeof(ByteStream));
    return *ret;
}
 
const ByteStream Container::Access(const Index index) const
{
    BIO_SANITIZE(IsAllocated(index), ,
        return NULL)
    ByteStream* ret;
    std::memcpy(
        ret,
        &m_store[index * sizeof(ByteStream)],
        sizeof(ByteStream));
    return *ret;
}
 
Index Container::SeekTo(const ByteStream content) const
{
    if (!m_tempItt)
    {
        m_tempItt = ConstructClassIterator();
    }
    m_tempItt->MoveTo(GetEndIndex());
    for (
        ; !m_tempItt->IsAtBeginning();
        --m_tempItt
        )
    {
        if (AreEqual(
            m_tempItt->GetIndex(),
            content
        ))
        {
            return m_tempItt->GetIndex();
        }
    }
    return InvalidIndex();
}
 
bool Container::Has(const ByteStream content) const
{
    return SeekTo(content); //implicit cast to bool should work.
}
 
bool Container::Erase(const Index index)
{
    BIO_SANITIZE(IsAllocated(index), ,
        return false)
    ByteStream* toDelete;
    std::memcpy(
        toDelete,
        &m_store[index * sizeof(ByteStream)],
        sizeof(ByteStream));
    delete toDelete;
    m_deallocated.push_back(index);
    return true;
}
 
void Container::Import(const Container* other)
{
    BIO_SANITIZE(other, ,
        return)
    Iterator* otr = other->End();
    for (
        ; !otr->IsAtBeginning();
        --otr
        )
    {
        Add(**otr);
    }
}
 
void Container::Clear()
{
    //Call destructors before clearing the array.
    if (!m_tempItt)
    {
        m_tempItt = ConstructClassIterator();
    }
    m_tempItt->MoveTo(GetEndIndex());
    for (
        ; !m_tempItt->IsAtBeginning();
        --m_tempItt
        )
    {
        Erase(m_tempItt->GetIndex());
    }
 
    m_firstFree = 1;
    m_deallocated.clear();
}
 
Iterator* Container::ConstructClassIterator(const Index index) const
{
    BIO_SANITIZE(IsAllocated(index), ,
        return NULL)
    return new Iterator(
        this,
        index
    );
}
 
SmartIterator Container::Begin() const
{
    return SmartIterator(
        this,
        GetBeginIndex());
}
 
SmartIterator Container::End() const
{
    return SmartIterator(
        this,
        GetEndIndex());
}
 
ByteStream Container::operator[](const Index index)
{
    return Access(index);
}
 
const ByteStream Container::operator[](const Index index) const
{
    return Access(index);
}
 
ByteStream Container::operator[](const SmartIterator itt)
{
    return Access(itt);
}
 
const ByteStream Container::operator[](const SmartIterator itt) const
{
    return Access(itt);
}
 
Index Container::GetNextAvailableIndex()
{
    Index ret = InvalidIndex();
    if (!m_deallocated.empty())
    {
        ret = m_deallocated.front();
        m_deallocated.pop_front();
    }
    else if (m_firstFree == m_size)
    {
        Expand();
        ret = m_firstFree++;
    }
    return ret;
}
 
bool Container::AreEqual(
    Index internal,
    const ByteStream external
) const
{
    return Access(internal) == external;
}
 
const std::size_t Container::GetStepSize() const
{
    return sizeof(ByteStream);
}
 
} //bio namespace