Trace.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.




#ifndef Sawyer_Trace_H
#define Sawyer_Trace_H

#include <Sawyer/Interval.h>
#include <Sawyer/Map.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Sawyer.h>
#include <Sawyer/Set.h>
#include <boost/foreach.hpp>
#include <boost/range.hpp>
#include <set>
#include <vector>

namespace Sawyer {
namespace Container {

class TraceMapIndexTag {};

class TraceVectorIndexTag {};

//                                      Implementation Details
namespace TraceDetail {

// Internal: An index where labels are keys for a tree-based map.
template<class K, class V>
class MapIndex {
    typedef K Label;
    typedef V Value;

    Sawyer::Container::Map<Label, Value> map_;

public:
    // Reset index to initial state
    void clear() {
        map_.clear();
    }

    // Return all labels, and possibly more (although this implementation is exact).  If any extra labels are returned, their
    // values are the default constructed.
    boost::iterator_range<typename Sawyer::Container::Map<Label, Value>::ConstKeyIterator> labels() const {
        return map_.keys();
    }

    // Return the value stored for a label. If the label has no value then return a default constructed value and do not modify
    // the index.
    const Value& operator[](const Label &label) const {
        return map_.getOrDefault(label);
    }

    // Return the value stored for a label. If the label has no value then first insert a default constructed value.
    Value& operator[](const Label &label) {
        return map_.insertMaybeDefault(label);
    }

    // If the index supports it, reserve space for the specified number of labels.
    void reserve(size_t /*n*/) {}
};

// Internal: An index where labels are indexes into a vector.  For member documentation see TraceMapIndex
template<class K, class V>
class VectorIndex {
    typedef K Label;
    typedef V Value;

    const Value dflt_;
    std::vector<Value> vector_;

public:
    VectorIndex() {}

    void clear() {
        vector_.clear(0);
    }

    boost::iterator_range<typename Sawyer::Container::Interval<Label>::ConstIterator> labels() const {
        return Sawyer::Container::Interval<Label>::baseSize(0, vector_.size()).values();
    }

    const Value& operator[](Label label) const {
        return (size_t)label < vector_.size() ? vector_[label] : dflt_;
    }

    Value& operator[](Label label) {
        if ((size_t)label >= vector_.size())
            vector_.resize(label+1, dflt_);
        return vector_[label];
    }

    void reserve(size_t n) {
        vector_.reserve(n);
    }
};

} // namespace


//                                      Traits

template<class Label, class Value, class IndexTypeTag>
struct TraceIndexTraits {
    typedef TraceDetail::MapIndex<Label, Value> Index;
};

template<class Label, class Value>
struct TraceIndexTraits<Label, Value, TraceVectorIndexTag> {
    typedef TraceDetail::VectorIndex<Label, Value> Index;
};


//                                      Trace

template<class T, class IndexTag = TraceMapIndexTag>
class Trace {
private:
    struct Decompression {
        size_t n;                                       // label visitation sequence number (starts at zero for each label)
        size_t succIdx;                                 // index into a Successors list;

        Decompression(): n(0), succIdx(0) {}
    };

public:
    typedef T Label;

    struct Successor {
        size_t end;                                     
        Label next;                                     
        Successor(): end(0) {}
        Successor(size_t end, const Label &next): end(end), next(next) {}
    };

    typedef std::vector<Successor> Successors;

    class ConstIterator: public boost::iterator_facade<ConstIterator, const Label, boost::forward_traversal_tag, Label> {
        friend class boost::iterator_core_access;
        const Trace *trace_;
        Sawyer::Optional<Label> label_;
        size_t position_;
        typename TraceIndexTraits<Label, Trace::Decompression, IndexTag>::Index decompressionState_;

    public:
        ConstIterator()
            : trace_(NULL), position_(0) {}

        explicit ConstIterator(const Trace &trace)
            : trace_(&trace), position_(0) {
            if (!trace_->isEmpty())
                label_ = trace_->front();
        }

        ConstIterator(const ConstIterator &other)
            : trace_(other.trace_), label_(other.label_), position_(other.position_),
              decompressionState_(other.decompressionState_) {}

        bool isEnd() const {
            return !label_;
        }

        size_t position() const {
            return position_;
        }

    private:
        // core operation from iterator_facade needed for readable iterator concept
        Label dereference() const {
            ASSERT_forbid(isEnd());
            return *label_;
        }

        // core operation from iterator_facade needed for single pass iterator concept
        bool equal(const ConstIterator &other) const {
            if (isEnd() || other.isEnd())
                return isEnd() == other.isEnd();
            return trace_ == other.trace_ && position() == other.position();
        }
            
        // core operation from iterator_facade needed for incrementable iterator concept
        void increment() {
            ASSERT_forbid(isEnd());
            const Successors &successors = trace_->index_[*label_];
            Decompression &dcomp = decompressionState_[*label_];
            if (dcomp.succIdx >= successors.size()) {
                label_ = Nothing();
            } else {
                const Successor &successor = successors[dcomp.succIdx];
                if (dcomp.n < successor.end) {
                    label_ = successor.next;
                    ++dcomp.n;
                } else {
                    ++dcomp.succIdx;
                    if (dcomp.succIdx >= successors.size()) {
                        label_ = Nothing();
                    } else {
                        label_ = successors[dcomp.succIdx].next;
                        ++dcomp.n;
                    }
                }
            }
            ++position_;
        }
    };
    
private:
    typedef typename TraceIndexTraits<Label, Successors, IndexTag>::Index Index;
    Index index_;                                       // encoded sequence of labels
    size_t size_;                                       // total length of sequence
    size_t nLabels_;                                    // number of distinct labels in sequence
    Optional<Label> front_, back_;                      // first and last labels in the sequence if size_ > 0

public:
    Trace(): size_(0), nLabels_(0) {}

    ConstIterator begin() const {
        return ConstIterator(*this);
    }

    ConstIterator end() const {
        return ConstIterator();
    }

    Label front() const {
        return *front_;
    }

    Label back() const {
        return *back_;
    }
    
    void clear() {
        index_.clear();
        size_ = nLabels_ = 0;
        front_ = back_ = Nothing();
    }

    void reserve(size_t n) {
        index_.reserve(n);
    }

    bool isEmpty() const {
        return front_ ? false : true;
    }

    bool exists(const Label &label) const {
        return isEmpty() ? false : (*front_ == label || *back_ == label || !index_[label].empty());
    }

    size_t size() const {
        return size_;
    }
    size_t size(const Label &label) const {
        const Successors &successors = index_[label];
        return successors.empty() ? 0 : successors.back().end;
    }
    size_t nLabels() const {
        return nLabels_;
    }

    Sawyer::Container::Set<Label> labels() const {
        Sawyer::Container::Set<Label> retval;
        BOOST_FOREACH (const Label &label, index_.labels())
            retval.insert(label);
        return retval;
    }

    void append(const Label &label) {
        if (isEmpty()) {
            front_ = label;
            ++nLabels_;
        } else {
            ASSERT_require(front_);
            if (!exists(label))
                ++nLabels_;
            Successors &successors = index_[*back_];
            if (successors.empty()) {
                successors.push_back(Successor(1, label));
            } else if (successors.back().next == label) {
                ++successors.back().end;
            } else {
                successors.push_back(Successor(successors.back().end+1, label));
            }
        }
        back_ = label;
        ++size_;
    }

    template<class Visitor>
    void traverse(Visitor &visitor) const {
        if (isEmpty())
            return;
        Label label = *front_;
        typename TraceIndexTraits<Label, Decompression, IndexTag>::Index decompressionState;
        while (1) {
            if (!visitor(label))
                return;
            const Successors &successors = index_[label];
            Decompression &dcomp = decompressionState[label];
            if (dcomp.succIdx >= successors.size()) {     // FIXME[Robb Matzke 2016-12-08]: simplify these nested "if"s
                return;
            } else {
                const Successor &successor = successors[dcomp.succIdx];
                if (dcomp.n < successor.end) {
                    label = successor.next;
                    ++dcomp.n;
                } else {
                    ++dcomp.succIdx;
                    if (dcomp.succIdx >= successors.size())
                        return;
                    label = successors[dcomp.succIdx].next;
                    ++dcomp.n;
                }
            }
        }
    }

private:
    // helper for the "print" method
    struct PrintHelper {
        std::ostream &out;
        const std::string &separator;
        size_t nPrinted;

        PrintHelper(std::ostream &out, const std::string &separator)
            : out(out), separator(separator), nPrinted(0) {}

        bool operator()(const Label &label) {
            if (1 != ++nPrinted)
                out <<separator;
            out <<label;
            return true;
        }
    };

public:
    void print(std::ostream &out, const std::string &separator = ", ") const {
        PrintHelper visitor(out, separator);
        traverse(visitor);
    }

    void dump(std::ostream &out) const {
        if (isEmpty()) {
            out <<"Trace(empty)";
        } else {
            out <<"Trace(size=" <<size_ <<", unique=" <<nLabels_ <<", front=" <<*front_ <<", back=" <<*back_;
            BOOST_FOREACH (const Label &label, index_.labels()) {
                const Successors &successors = index_[label];
                if (!successors.empty()) {
                    out <<"\n  " <<label <<" => [";
                    BOOST_FOREACH (const Successor &successor, successors)
                        out <<"\n    end index=" <<successor.end <<", next label=" <<successor.next;
                    out <<"]\n";
                }
            }
            out <<")";
        }
    }

private:
    // helper for the "toVector" method
    struct ToVector {
        std::vector<Label> vector;
        bool operator()(const Label &label) {
            vector.push_back(label);
            return true;
        }
    };

public:
    std::vector<Label> toVector() const {
        ToVector visitor;
        traverse(visitor);
        return visitor.vector;
    }

    std::set<Label> successorSet(const Label &label) const {
        std::set<Label> unique;
        BOOST_FOREACH (const Successor &successor, index_[label])
            unique.insert(successor.next);
        return unique;
    }

    double burstiness(const Label &label) const {
        if (size_t nUniqueLabels = successorSet(label).size())
            return (double)nUniqueLabels / index_[label].size();
        return 0.0;
    }
    double burstiness() const {
        size_t size = 0;
        double sum = 0.0;
        BOOST_FOREACH (const Label &label, index_.labels()) {
            if (double x = burstiness(label)) {
                sum += x;
                ++size;
            }
        }
        return size ? sum / size : 0.0;
    }

    const Successors& successors(const Label &label) const {
        return index_[label];
    }
};

template<class T, class IndexTag>
inline std::ostream&
operator<<(std::ostream &out, const Trace<T, IndexTag> &trace) {
    trace.print(out);
    return out;
}

} // namespace
} // namespace

#endif