indexed_list.cpp

#include <iostream>
#include <cstdint>
#include <vector>
#include <queue>
#include <list>

template <class SizeType, uint8_t MIN_LOG_INDEX, uint8_t BALANCE_LOG_RATIO, class Type>
struct TIndexedList
{
    using Iterator = typename std::list<Type>::iterator;

    struct Next
    {
        Iterator operator()(Iterator iterator) const
        {
            return std::next(iterator);
        }
    };

    struct Prev
    {
        Iterator operator()(Iterator iterator) const
        {
            return std::prev(iterator);
        }
    };

    struct IndexElement
    {
        typename std::list<Type>::iterator _iterator;
        SizeType _rangeLeft;
        SizeType _rangeRight;
    };

    static IndexElement splitRangeLeft(const IndexElement& indexElement)
    {
        auto iterator = indexElement._iterator;
        auto half     = indexElement._rangeLeft >> 1;
        
        for (SizeType i = 0; i < half; i++)
        {
            iterator = std::prev(iterator);
        }
        
        return IndexElement{iterator, indexElement._rangeLeft - half, half - 1}; 
    }

    static IndexElement splitRangeRight(const IndexElement& indexElement)
    { 
        auto iterator = indexElement._iterator;
        auto half     = indexElement._rangeRight >> 1;
        
        for (SizeType i = 0; i < half; i++)
        {
            iterator = std::next(iterator);
        }
        
        return IndexElement{iterator, half - 1, indexElement._rangeRight - half}; 
    }
    
    Iterator insert(const Type& value)
    {   
        auto size = _list.size();
        
        if ((size & (size - 1)) == 0 && size > (1 << MIN_LOG_INDEX))
        {
            addIndexLevel();    
        }
        
        std::queue<SizeType > branch;
        std::queue<int8_t   > rangeUpdate;
        
        SizeType i = 0;
        
        while (i < indexSize())
        {
            branch.push(i);

            auto iterator = _index[i]._iterator;

            if (value < *iterator)
            {
                rangeUpdate.push(-1);
                i = 1 + (i << 1) + 0;

                if (i >= indexSize())
                {
                    while (value < *iterator && iterator != _list.begin())
                    {
                        iterator = std::prev(iterator);
                    }

                    if (iterator != _list.end() && *iterator == value)
                    {
                        return iterator;
                    }

                    return insertAt(value < *iterator ? _list.begin() : std::next(iterator), value, branch, rangeUpdate);
                }
            }
            else if (value > *iterator)
            {
                rangeUpdate.push(1);
                i = 1 + (i << 1) + 1;

                if (i >= indexSize())
                {
                    while (iterator != _list.end() && value > *iterator)
                    {
                        iterator = std::next(iterator);
                    }

                    if (iterator != _list.end() && *iterator == value)
                    {
                        return iterator;
                    }

                    return insertAt(iterator, value, branch, rangeUpdate);
                }                 
            }
            else
            {
                return _index[i]._iterator;
            }
        }

        for (auto it = _list.begin(); it != _list.end(); it++)
        {
            if (value < *it)
            {
                return _list.insert(it, value);
            }

            if (*it == value)
            {
                return it;
            }
        }

        return _list.insert(_list.end(), value);
    }

    Iterator insertAt(Iterator iterator, const Type& value, std::queue<SizeType>& branch, std::queue<int8_t>& rangeUpdate)
    {
        auto newIterator = _list.insert(iterator, value);

        while (!branch.empty())
        {
            balanceNode(branch, rangeUpdate);

            branch      .pop();
            rangeUpdate .pop();
        }

        return newIterator;
    }
    
    void balanceNode(std::queue<SizeType>& branch, std::queue<int8_t>& rangeUpdate)
    {
        auto& node = branch.front();

        auto& rangeLeft  = _index[node]._rangeLeft;
        auto& rangeRight = _index[node]._rangeRight;

        if (rangeUpdate.front() < 0)
        {
            rangeLeft++;
        }

        if (rangeUpdate.front() > 0)
        {
            rangeRight++;
        }

        if (std::abs(rangeLeft - rangeRight) < 
                    (rangeLeft + rangeRight) >> BALANCE_LOG_RATIO)
        {
            return;
        }
        
        (rangeLeft > rangeRight) ? balanceRanges<Prev, -1>(branch, rangeUpdate)
                                 : balanceRanges<Next,  1>(branch, rangeUpdate);
    }

    template <class Iterater, int8_t DIRECTION>
    void balanceRanges(std::queue<SizeType>& branch, std::queue<int8_t>& rangeUpdate)
    {
        auto& node = branch.front();

        auto iterator   = _index[node]._iterator;
        auto rangeLeft  = _index[node]._rangeLeft;
        auto rangeRight = _index[node]._rangeRight;

        auto offset = std::abs(rangeLeft - rangeRight) >> 1;

        Iterater iterater;

        for (SizeType i = 0; i < offset; i++)
        {
            iterator = iterater(iterator);
        }
        
        _index[node]._iterator    = iterator;
        _index[node]._rangeLeft  += offset * DIRECTION; 
        _index[node]._rangeRight -= offset * DIRECTION;

        if (1 + (node << 1) < indexSize())
        {
            _index[1 + (node << 1) + 0]._rangeRight += offset * DIRECTION;
            _index[1 + (node << 1) + 1]._rangeLeft  -= offset * DIRECTION;

            branch.push(1 + (node << 1) + 0);
            branch.push(1 + (node << 1) + 1);

            rangeUpdate.push(0);
            rangeUpdate.push(0);
        }
    }
    
    void addIndexLevel()
    {
        if (_index.empty())
        {
            SizeType half = _list.size() >> 1;
            auto iterator = _list.begin();
            
            std::advance(iterator, half);
            
            _index.push_back(IndexElement{iterator, half, half - 1});

            return;
        }
        
        auto size = _index.size();

        for (auto i = size >> 1; i < size ; i++)
        {
            _index.push_back(splitRangeLeft  (_index[i]));
            _index.push_back(splitRangeRight (_index[i]));
        }
    }

    int64_t indexSize() const
    {
        return static_cast<int64_t>(_index.size());
    }
    
    std::list<Type>           _list;
    std::vector<IndexElement> _index;
};

int main()
{
    TIndexedList<int32_t, 2, 2, char> charIndexedList;
    
    charIndexedList.insert('q');
    charIndexedList.insert('a');
    charIndexedList.insert('z');
    charIndexedList.insert('x');
    charIndexedList.insert('s');
    charIndexedList.insert('w');
    charIndexedList.insert('e');
    charIndexedList.insert('d');
    charIndexedList.insert('c');
    charIndexedList.insert('v');
    charIndexedList.insert('f');
    charIndexedList.insert('r');
    charIndexedList.insert('t');
    charIndexedList.insert('g');
    charIndexedList.insert('b');
    charIndexedList.insert('n');
    charIndexedList.insert('h');
    charIndexedList.insert('y');
    charIndexedList.insert('_');
    charIndexedList.insert('t');
    charIndexedList.insert('h');
    charIndexedList.insert('i');
    charIndexedList.insert('s');
    charIndexedList.insert('_');
    charIndexedList.insert('t');
    charIndexedList.insert('o');
    charIndexedList.insert('_');
    charIndexedList.insert('g');
    charIndexedList.insert('e');
    charIndexedList.insert('t');
    charIndexedList.insert('_');
    charIndexedList.insert('t');
    charIndexedList.insert('o');
    charIndexedList.insert('_');
    charIndexedList.insert('1');
    charIndexedList.insert('6');
    
    for (auto e : charIndexedList._list)
    {
        std::cout << e;
    }

    std::cout << '\n';

    return 0;
}