UT_RLEArray.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        UT_RLEArray.h (GT Library, C++)
 *
 * COMMENTS:
 */

#ifndef __UT_RLEArray__
#define __UT_RLEArray__

#include "UT_API.h"
#include "UT_SmallArray.h"
#include "UT_Debug.h"
#include <algorithm>
#include <iterator>
#include <utility>

class UT_JSONWriter;

/// Appending elements to this array will build up a run-length encoded
/// compressed array.  Random access may not be fast.
template <typename T>
class UT_RLEArray
{
public:
    using value_type = T;

    struct Run
    {
        Run()
            : myArray()
            , myRepeat(0)
            , myStartIndex(0)
        {
        }
        Run(const T &item, exint repeat, exint start_index)
            : myArray()
            , mySingle(item)
            , myRepeat(repeat)
            , myStartIndex(start_index)
        {
        }

        SYS_FORCE_INLINE bool   isEmpty() const { return myRepeat == 0; }
        SYS_FORCE_INLINE bool   isRun() const   { return myRepeat >= 0; }
        SYS_FORCE_INLINE exint  runSize() const
        {
            UT_ASSERT(myRepeat >= 0);
            return myRepeat;
        }
        SYS_FORCE_INLINE exint  size() const
        {
            return myRepeat >= 0 ? myRepeat : myArray.size();
        }
        SYS_FORCE_INLINE exint  startIndex() const { return myStartIndex; }
        SYS_FORCE_INLINE exint  endIndex() const { return myStartIndex + size(); }
        SYS_FORCE_INLINE const T        &arrayItem(exint idx) const
        {
            return myRepeat >= 0 ? mySingle : myArray[idx];
        }
        SYS_FORCE_INLINE const T &operator[](exint idx) const
        {
            if (isRun())
            {
                UT_ASSERT_P(idx < myRepeat && myArray.size() == 0);
                return mySingle;
            }
            return myArray[idx];
        }

        SYS_FORCE_INLINE void   appendRun(exint num=1) { myRepeat += num; }
        SYS_FORCE_INLINE void   appendSequence(const T &item)
        {
            UT_ASSERT(!isRun());
            myArray.append(item);
        }

        SYS_FORCE_INLINE void   convertToSequence(const T &item)
        {
            UT_ASSERT(myRepeat > 0 && myArray.size() == 0);
            myArray.appendMultiple(mySingle, myRepeat);
            myArray.append(item);
            myRepeat = -1;
        }

        /// Return the number of items at the end of the sequence which match
        /// the item.
        SYS_FORCE_INLINE exint  matchesAtEnd(const T &item) const
        {
            UT_ASSERT(!isRun() && myArray.size() > 0);
            for (exint i = myArray.size(); i-- > 0; )
            {
                if (myArray[i] != item)
                    return (myArray.size() - 1) - i;
            }
            return myArray.size();
        }
        SYS_FORCE_INLINE void   removeItemsFromEnd(exint n)
        {
            UT_ASSERT(!isRun() && myArray.size() > n);
            myArray.setSize(myArray.size() - n);
            UT_ASSERT(myArray.size());
        }
        SYS_FORCE_INLINE void shiftStartIndex(exint n)
        {
            myStartIndex += n;
            UT_ASSERT_P(myStartIndex >= 0);
        }

        SYS_FORCE_INLINE exint  getMemoryUsage() const
        {
            return myArray.getMemoryUsage() + sizeof(exint) + sizeof(T);
        }

    private:
        // The small array is big enough to hold a single item
        UT_Array<T>     myArray;
        T               mySingle;
        exint           myRepeat;
        exint           myStartIndex;
    };

    UT_RLEArray()
        : myRuns()
        , mySize(0)
    {
    }
    UT_RLEArray(const T *data, exint size)
        : myRuns()
        , mySize(0)
    {
        for (exint i = 0; i < size; ++i)
            append(data[i]);
    }
    UT_RLEArray(const UT_Array<T> &arr)
        : myRuns()
        , mySize(0)
    {
        for (auto &&item : arr)
            append(item);
    }

    SYS_FORCE_INLINE bool        isEmpty() const { return mySize == 0; }
    SYS_FORCE_INLINE exint       size() const { return mySize; }
    SYS_FORCE_INLINE exint       numRuns() const { return myRuns.size(); }
    SYS_FORCE_INLINE const Run  &run(exint i) const { return myRuns(i); }
    SYS_FORCE_INLINE void        clear()
    {
        mySize = 0;
        myRuns.clear();
    }

    /// This is a slow way of computing the size of the array but can be used
    /// for debugging.
    SYS_FORCE_INLINE exint      countSize() const
    {
        exint   n = 0;
        for (auto &&run : myRuns)
            n += run.size();
        return n;
    }

    SYS_FORCE_INLINE exint      getMemoryUsage() const
    {
        exint   mem = 0;
        for (auto &&run : myRuns)
            mem += run.getMemoryUsage();
        return mem + myRuns.getMemoryUsage() + sizeof(exint);
    }

    // Test whether the array has a single value for the entire array
    SYS_FORCE_INLINE bool        isUniform() const
    {
        return myRuns.size() == 1 && myRuns[0].isRun();
    }
    SYS_FORCE_INLINE const T    &uniformItem() const
    {
        return myRuns[0].arrayItem(0);
    }

    /// Note that finding an item is O(log(N)) - where N is the number of runs
    SYS_FORCE_INLINE const T    &findItem(exint idx) const
    {
        UT_ASSERT_P(idx >= 0 && idx < mySize);
        auto &&it = std::lower_bound(myRuns.begin(), myRuns.end(), idx,
                            [](const Run &run, exint value)
                            {
                                // Return true if the run's end index is less
                                // than or equal to the value we're searching
                                // for (the run is earlier in the list than
                                // the one we're looking for).
                                return run.endIndex() <= value;
                            });
        return (*it)[idx - (*it).startIndex()];
    }

    SYS_FORCE_INLINE void       appendRun(const T &item, exint n)
    {
        if (n == 0)
            return;
        if (n < 3)
        {
            for (exint i = 0; i < n; ++i)
                append(item);
            return;
        }
        if (myRuns.size()
                && myRuns.last().isRun()
                && item == myRuns.last().arrayItem(0))
        {
            myRuns.last().appendRun(n);
        }
        else
        {
            newRun(item, n);
        }
        mySize += n;
    }

    /// Move and concatenate another UT_RLEArray at the end.
    SYS_FORCE_INLINE void concat(UT_RLEArray<T> &&src)
    {
        UT_ASSERT_P(this != &src);
        if (src.mySize == 0)
            return;

        // If this array was empty, just steal.
        if (mySize == 0)
        {
            myRuns = std::move(src.myRuns);
            mySize = src.mySize;
            src.mySize = 0;
            return;
        }

        // Shift the start index for the new runs.
        for (auto &&run : src.myRuns)
            run.shiftStartIndex(mySize);

        mySize += src.mySize;
        src.mySize = 0;

        // Merge with our last run if the new array starts with the same.
        const bool merge_runs = myRuns.last().isRun() && src.myRuns[0].isRun()
                                && myRuns.last().arrayItem(0)
                                           == src.myRuns[0].arrayItem(0);
        if (merge_runs)
        {
            myRuns.last().appendRun(src.myRuns[0].runSize());

            myRuns.bumpCapacity(myRuns.size() + src.myRuns.size() - 1);
            for (exint i = 1, n = src.myRuns.size(); i < n; ++i)
                myRuns.append(std::move(src.myRuns[i]));

            src.myRuns.clear();
        }
        else
        {
            myRuns.concat(std::move(src.myRuns));
        }
    }

    SYS_FORCE_INLINE void       append(const T &item)
    {
        if (mySize == 0)
        {
            // First item
            newRun(item, 1);
        }
        else
        {
            Run &last = myRuns.last();
            if (last.isRun())
            {
                if (item == last.arrayItem(0))
                    last.appendRun(1);
                else
                {
                    if (last.runSize() > 2)
                    {
                        // If we have a run that's over 2 items, we start a new run
                        newRun(item, 1);
                    }
                    else
                    {
                        // Convert the current run into a squence instead of a run
                        last.convertToSequence(item);
                    }
                }
            }
            else
            {
                exint   n = last.matchesAtEnd(item);
                if (n >= 3)
                {
                    last.removeItemsFromEnd(n);
                    newRun(item, n+1);
                    myRuns.last().shiftStartIndex(-n);
                }
                else
                {
                    last.appendSequence(item);
                }
            }
        }
        mySize++;
    }

    class iterator
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = exint;
        using difference_type = std::ptrdiff_t;
        using pointer = value_type*;
        using reference = value_type&;

        iterator()
            : myArray(nullptr)
            , myRunIndex(0)
            , myRunOffset(0)
        {
        }

        const T &item() const
        {
            return myArray->run(myRunIndex)[myRunOffset];
        }
        const T &operator*() const { return item(); }

        bool    operator==(const iterator &i) const
        {
            return myArray == i.myArray
                && myRunIndex == i.myRunIndex
                && myRunOffset == i.myRunOffset;
        }
        bool    operator!=(const iterator &i) const
        {
            return !(*this == i);
        }
        bool    atEnd() const
        {
            return myRunIndex >= myArray->numRuns();
        }
        iterator        &operator++() { advance(); return *this; }
        void             rewind()
        {
            if (myArray)
            {
                myRunIndex = 0;
                myRunOffset = 0;
            }
        }
        void    advance()
        {
            myRunOffset++;
            if (myRunOffset >= myArray->run(myRunIndex).size())
            {
                // Advance to the next run
                myRunIndex++;
                myRunOffset = 0;
            }
        }
    private:
        iterator(const UT_RLEArray<T> &array, bool end)
            : myArray(&array)
            , myRunIndex(end ? array.numRuns() : 0)
            , myRunOffset(0)
        {
        }
        const UT_RLEArray<T>    *myArray;
        exint                    myRunIndex;    // Index into array of runs
        exint                    myRunOffset;   // Index into run's items
        friend class UT_RLEArray<T>;
    };
    using const_iterator = iterator;

    SYS_FORCE_INLINE iterator   begin() const { return iterator(*this, false); }
    SYS_FORCE_INLINE iterator   end() const { return iterator(*this, true); }

private:
    SYS_FORCE_INLINE void       newRun(const T &item, exint size)
    {
        myRuns.emplace_back(item, size, mySize);
    }
    UT_SmallArray<Run, sizeof(Run)*4>   myRuns;
    exint                               mySize;
};

#endif