#include "include/list.hpp"

using namespace qOS;

/*============================================================================*/
void node::init( void ) noexcept
{
    next = nullptr;
    prev = nullptr;
    container = nullptr;
}
/*============================================================================*/
list::list() noexcept
{
    clean();
}
/*============================================================================*/
bool list::isMember( const void * const xNode ) const noexcept
{
    bool retValue = false;

    if ( nullptr != xNode ) {
        /*cstat -CERT-EXP36-C_b*/
        const node * const Node = static_cast<const node*>( xNode );

        if ( this == Node->container ) {
            retValue = true;
        }
        /*cstat +CERT-EXP36-C_b*/
    }

    return retValue;
}
/*============================================================================*/
void list::insertAtFront( node * const xNode ) noexcept
{
    xNode->next = this->head;
    head->prev = xNode;
    head = xNode;
}
/*============================================================================*/
void list::insertAtBack( node * const xNode ) noexcept
{
    tail->next = xNode;
    xNode->prev = tail;
    tail = xNode;
}
/*============================================================================*/
node* list::removeFront( void ) noexcept
{
    node * const removed = head;

    head = removed->next;
    if ( nullptr == head ) {
        tail = head;
    }
    else {
        head->prev = nullptr;
    }

    return removed;
}
/*============================================================================*/
node* list::removeBack( void ) noexcept
{
    node * const removed = tail;

    tail = removed->prev;
    if ( nullptr == tail ) {
        head = tail;
    }
    else {
        tail->next = nullptr;
    }

    return removed;
}
/*============================================================================*/
node* list::getNodeAtIndex( const listPosition p ) const noexcept
{
    node *iNode;
    base_t iPos = 0;
    /*cstat -MISRAC++2008-0-1-2_b*/
    for ( iNode = head ; ( iPos < static_cast<base_t>( p )  ) && ( nullptr != iNode->next ) ; iNode = iNode->next ) {
        ++iPos;
    }
    /*cstat +MISRAC++2008-0-1-2_b*/
    return iNode;
}
/*============================================================================*/
bool list::insert( void * const xNode, const listPosition p ) noexcept
{
    bool retValue = false;

    if ( ( nullptr != xNode ) && ( p >= listPosition::AT_BACK ) ) {
        if ( !isMember( xNode ) ) {
            /*cstat -CERT-EXP36-C_b*/
            node * const newNode = static_cast<node*>( xNode );
            /*cstat +CERT-EXP36-C_b*/
            newNode->init();

            retValue = true;
            if ( nullptr == head ){
                head = newNode;
                tail = newNode;
            }
            else if ( listPosition::AT_FRONT == p ) {
                insertAtFront( newNode );
            }
            /*cstat -MISRAC++2008-0-1-2_a*/
            else if ( listPosition::AT_BACK == p ) {
                insertAtBack( newNode );
            }
            /*cstat +MISRAC++2008-0-1-2_a*/
            else {
                node *iNode;
                iNode = getNodeAtIndex( p );
                newNode->next = iNode->next;  /* NEW -> (i+1)NODE */
                newNode->prev = iNode;        /* iNODE <- NEW */
                iNode->next->prev = newNode;  /* NEW <- (i+1)NODE */
                iNode->next = newNode;        /* iNODE -> NEW */
            }
            ++size;
            newNode->container = this;
        }
    }

    return retValue;
}
/*============================================================================*/
bool list::remove( void * const xNode ) noexcept
{
    bool retValue = false;

    if ( nullptr != xNode ) {
        /*cstat -CERT-EXP36-C_b*/
        node * const toRemove = static_cast<node*>( xNode );
        /*cstat +CERT-EXP36-C_b*/

        if ( this == toRemove->container ) {
            if ( toRemove == head ) {
                (void)removeFront();
            }
            else if ( toRemove == tail ) {
                (void)removeBack();
            }
            else {
                toRemove->prev->next = toRemove->next;
                if ( nullptr != toRemove->next ) {
                    toRemove->next->prev = toRemove->prev;
                }
            }
            --size;
            toRemove->container = nullptr;
            retValue = true;
        }
    }

    return retValue;
}
/*============================================================================*/
void* list::remove( const listPosition p, void * const xNode ) noexcept
{
    node *removed = nullptr;

    if ( ( nullptr != head ) && ( p >= listPosition::AT_BACK ) ) {
        if ( isMember( xNode ) ) {
            if ( remove( xNode ) ) {
                /*cstat -CERT-EXP36-C_b*/
                removed = static_cast<node*>( xNode );
                /*cstat +CERT-EXP36-C_b*/
            }
        }
        else {
            if ( listPosition::AT_FRONT == p ) {
                removed = removeFront();
            }
            /*cstat -MISRAC++2008-0-1-2_a*/
            else if ( listPosition::AT_BACK  == p ) {
                removed = removeBack();
            }
            /*cstat +MISRAC++2008-0-1-2_a*/
            else {
                node *iNode;
                const base_t lastIndex = ( static_cast<base_t>( p ) - 1 );

                iNode = getNodeAtIndex( static_cast<listPosition>( lastIndex ) );
                removed = iNode->next; /* <-> (inode0) <-> inode1 <-> inode2 */
                iNode->next = removed->next;
                if ( nullptr != removed->next ) {
                    iNode->next->prev = iNode;
                }
            }
            removed->container = nullptr;
            --size;
        }
    }

    return removed;
}
/*============================================================================*/
void* list::getFront( void ) const noexcept
{
    return static_cast<void*>( head );
}
/*============================================================================*/
void* list::getBack( void ) const noexcept
{
    return static_cast<void*>( tail );
}
/*============================================================================*/
bool list::isEmpty( void ) const noexcept
{
    return ( nullptr == head );
}
/*============================================================================*/
size_t list::length( void ) const noexcept
{
    return size;
}
/*============================================================================*/
/*cstat -MISRAC++2008-7-1-2*/
bool list::sort( listCompareFcn_t f ) noexcept
{
/*cstat +MISRAC++2008-7-1-2*/
    bool retValue = false;

    if ( nullptr != f ) {
        const size_t count = size;

        if ( count >= 2U ) {
            node *current = nullptr;
            node *before;
            node *after;
            bool xRetCmp;

            for ( size_t i = 1U ; i < count ; ++i ) {
                const size_t n = count - i - 1U;
                current = head;
                for ( size_t j = 0U; j <= n; ++j ) {
                    xRetCmp = f( current, current->next );
                    if ( xRetCmp ) {
                        before = current->prev;
                        after = current->next;

                        if ( nullptr != before ) {
                            before->next = after;
                        }
                        else {
                            head = after;
                        }
                        current->next = after->next;
                        current->prev = after;

                        if ( nullptr != after->next ) {
                            after->next->prev = current;
                        }

                        after->next = current;
                        after->prev = before;
                        retValue = true;
                    }
                    else {
                        current = current->next;
                    }
                }
            }
            while ( nullptr != current->next ) {
                current = current->next;
            }
            tail = current;
        }
    }

    return retValue;
}
/*============================================================================*/
bool list::swap( void* node1, void* node2 ) noexcept
{
    bool retValue = false;

    if ( ( nullptr != node1 ) && ( nullptr != node2 ) && ( node1 != node2 ) ) {
        /*cstat -CERT-EXP36-C_b*/
        node *n1 = static_cast<node*>( node1 );
        node *n2 = static_cast<node*>( node2 );
        /*cstat +CERT-EXP36-C_b*/
        if ( ( this == n1->container ) && ( n1->container == n2->container ) ) {
            /*nodes are part of the same list*/
            node *tmp1;
            node *tmp2;

            if ( n2->next == n1 ) {
                /*cstat -CERT-EXP36-C_b*/
                n1 = static_cast<node*>( node2 );
                n2 = static_cast<node*>( node1 );
                /*cstat +CERT-EXP36-C_b*/
            }
            tmp1 = n1->prev;
            tmp2 = n2->next;
            givenNodeSwapBoundaries( n1, n2 );
            givenNodeSwapAdjacent( n1, n2 );
            n2->prev = tmp1;
            n1->next = tmp2;
            givenNodesUpdateOuterLinks( n1, n2 );
            retValue = true;
        }
    }

    return retValue;
}
/*============================================================================*/
void list::givenNodeSwapBoundaries( node *n1, node *n2 ) noexcept
{
    if ( head == n1 ) {
        head = n2;
    }
    else if ( head == n2 ) {
        head = n1;
    }
    else {
        /*nothing to do here*/
    }
    if ( tail == n1 ) {
        tail = n2;
    }
    else if ( tail == n2 ) {
        tail = n1;
    }
    else {
        /*nothing to do here*/
    }
}
/*============================================================================*/
void list::givenNodeSwapAdjacent( node *n1, node *n2 ) noexcept
{
    if ( ( ( n1->next == n2 ) && ( n2->prev == n1 ) ) || ( ( n1->prev == n2 ) && ( n2->next == n1 ) ) ) {
        n1->prev = n1->next;
        n2->next = n2->prev;
    }
    else {
        n1->prev = n2->prev;
        n2->next = n1->next;
    }
}
/*============================================================================*/
void list::givenNodesUpdateOuterLinks( node *n1, node *n2 ) noexcept
{
    if ( nullptr != n1->prev ) {
        n1->prev->next = n1;
    }
    if ( nullptr != n1->next ) {
        n1->next->prev = n1;
    }
    if ( nullptr != n2->prev ) {
        n2->prev->next = n2;
    }
    if ( nullptr != n2->next ) {
        n2->next->prev = n2;
    }
}
/*============================================================================*/
bool list::move( list& src, const listPosition p ) noexcept
{
    bool retValue = false;

    if ( ( nullptr != src.head) && ( p >= listPosition::AT_BACK ) ) {
        node *iNode;
        /* cppcheck-suppress postfixOperator */
        for ( listIterator i = src.begin() ; i.untilEnd() ; i++ ) {
            iNode = i.get<node*>();
            iNode->container = this;
        }
        if ( nullptr == head ) { /*destination is empty*/
            head = src.head;
            tail = src.tail;
        }
        else if ( AT_FRONT == p ) {
            src.tail->next = head;
            head->prev = src.tail;
            head = src.head;
        }
        /*cstat -MISRAC++2008-0-1-2_a*/
        else if ( AT_BACK == p ) {
            tail->next = src.head;
            src.head->prev = tail;
            tail = src.tail;
        }
        /*cstat +MISRAC++2008-0-1-2_a*/
        else {
            iNode = getNodeAtIndex( p );
            src.tail->next = iNode->next;
            src.head->prev = iNode;
            iNode->next = src.head;
        }
        size += src.size;
        src.clean();
        retValue = true;
    }

    return retValue;
}
/*============================================================================*/
void list::clean( void ) noexcept
{
    head = nullptr;
    tail = nullptr;
    size = 0U;
}
/*============================================================================*/
listIterator list::begin( void ) noexcept
{
    listIterator it( *this, listDirection::FORWARD, nullptr );
    return it;
}
/*============================================================================*/
listIterator list::end( void ) noexcept
{
    listIterator it( *this, listDirection::BACKWARD, nullptr );
    return it;
}
/*============================================================================*/
listIterator list::from( void *offset ) noexcept
{
    listIterator it( *this, listDirection::FORWARD, offset );
    return it;
}
/*============================================================================*/
listIterator::listIterator( list& xList, listDirection dir, void *nodeOffset ) noexcept
{
    node *ret;
    /*cstat -CERT-EXP36-C_b*/
    node * const offset = static_cast<node*>( nodeOffset );
    /*cstat +CERT-EXP36-C_b*/
    l = &xList;
    if ( listDirection::FORWARD == dir ) {
        ret = ( xList.isMember( nodeOffset ) ) ? offset : xList.head;
        iter = ( nullptr != ret ) ? ret->next : nullptr;
    }
    else {
        ret = ( xList.isMember( nodeOffset ) ) ? offset : xList.tail;
        iter = ( nullptr != ret ) ? ret->prev : nullptr;
    }
    current = static_cast<void*>( ret );
}
/*============================================================================*/
bool listIterator::untilEnd( void ) const noexcept
{
    return ( nullptr != current );
}
/*============================================================================*/
bool listIterator::untilEnd( void* node ) const noexcept
{
    return ( l->isMember( node ) ) && ( node != current );
}
/*============================================================================*/
listIterator& listIterator::operator++( int ) noexcept
{
    node * const ret = iter;
    iter = ( nullptr != iter ) ? iter->next : nullptr;
    current = static_cast<void*>( ret );
    return *this;
}
/*============================================================================*/
listIterator& listIterator::operator--( int ) noexcept
{
    node * const ret = iter;
    iter = ( nullptr != iter ) ? iter->prev : nullptr;
    current = static_cast<void*>( ret );
    return *this;
}
/*============================================================================*/
