11#include <Sawyer/Interval.h>
12#include <Sawyer/Map.h>
13#include <Sawyer/Optional.h>
14#include <Sawyer/Sawyer.h>
15#include <Sawyer/Set.h>
16#include <boost/foreach.hpp>
17#include <boost/range.hpp>
33namespace TraceDetail {
36template<
class K,
class V>
51 boost::iterator_range<typename Sawyer::Container::Map<Label, Value>::ConstKeyIterator> labels()
const {
57 const Value& operator[](
const Label &label)
const {
62 Value& operator[](
const Label &label) {
67 void reserve(
size_t ) {}
71template<
class K,
class V>
77 std::vector<Value> vector_;
86 boost::iterator_range<typename Sawyer::Container::Interval<Label>::ConstIterator> labels()
const {
90 const Value& operator[](Label label)
const {
91 return (
size_t)label < vector_.size() ? vector_[label] : dflt_;
94 Value& operator[](Label label) {
95 if ((
size_t)label >= vector_.size())
96 vector_.resize(label+1, dflt_);
97 return vector_[label];
100 void reserve(
size_t n) {
166template<
class Label,
class Value,
class IndexTypeTag>
171template<
class Label,
class Value>
261template<
class T,
class IndexTag = TraceMapIndexTag>
264 struct Decompression {
268 Decompression(): n(0), succIdx(0) {}
294 class ConstIterator:
public boost::iterator_facade<ConstIterator, const Label, boost::forward_traversal_tag, Label> {
295 friend class boost::iterator_core_access;
304 : trace_(NULL), position_(0) {}
308 : trace_(&trace), position_(0) {
310 label_ = trace_->
front();
315 : trace_(other.trace_), label_(other.label_), position_(other.position_),
316 decompressionState_(other.decompressionState_) {}
332 Label dereference()
const {
333 ASSERT_forbid(
isEnd());
339 if (
isEnd() || other.isEnd())
340 return isEnd() == other.isEnd();
341 return trace_ == other.trace_ &&
position() == other.position();
346 ASSERT_forbid(
isEnd());
348 Decompression &dcomp = decompressionState_[*label_];
352 const Successor &successor =
successors[dcomp.succIdx];
353 if (dcomp.n < successor.end) {
354 label_ = successor.next;
371 typedef typename TraceIndexTraits<Label, Successors, IndexTag>::Index Index;
375 Optional<Label> front_, back_;
410 size_ = nLabels_ = 0;
427 return front_ ? false :
true;
437 return isEmpty() ? false : (*front_ == label || *back_ == label || !index_[label].empty());
468 BOOST_FOREACH (
const Label &label, index_.labels())
481 ASSERT_require(front_);
504 template<
class Visitor>
508 Label label = *front_;
514 Decompression &dcomp = decompressionState[label];
519 if (dcomp.n < successor.
end) {
520 label = successor.
next;
537 const std::string &separator;
540 PrintHelper(std::ostream &out,
const std::string &separator)
541 : out(out), separator(separator), nPrinted(0) {}
543 bool operator()(
const Label &label) {
555 void print(std::ostream &out,
const std::string &separator =
", ")
const {
556 PrintHelper visitor(out, separator);
564 void dump(std::ostream &out)
const {
566 out <<
"Trace(empty)";
568 out <<
"Trace(size=" <<size_ <<
", unique=" <<nLabels_ <<
", front=" <<*front_ <<
", back=" <<*back_;
569 BOOST_FOREACH (
const Label &label, index_.labels()) {
572 out <<
"\n " <<label <<
" => [";
574 out <<
"\n end index=" <<successor.
end <<
", next label=" <<successor.
next;
585 std::vector<Label> vector;
586 bool operator()(
const Label &label) {
587 vector.push_back(label);
599 return visitor.vector;
608 std::set<Label> unique;
609 BOOST_FOREACH (
const Successor &successor, index_[label])
610 unique.insert(successor.
next);
640 return (
double)nUniqueLabels / index_[label].size();
651 BOOST_FOREACH (
const Label &label, index_.labels()) {
670 return index_[label];
677template<
class T,
class IndexTag>
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
boost::iterator_range< ConstIterator > values() const
Iterator range for values.
Container associating values with keys.
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Map & clear()
Remove all nodes.
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
bool insert(const Value &value)
Insert a value.
Tag for a map-based Trace label index.
Tag for a vector-based Trace label index.
size_t position() const
Position of iterator within trace.
bool isEnd() const
Test whether iterator is at the end.
ConstIterator(const Trace &trace)
Construct iterator pointing to first element of the trace, if any.
ConstIterator(const ConstIterator &other)
Copy constructor.
ConstIterator()
Construct iterator point to end of any trace.
Records and replays traces.
Label front() const
Returns the first item in the trace.
double burstiness(const Label &label) const
The burstiness of a label.
ConstIterator begin() const
Returns a forward iterator pointing to first element of this trace.
const Successors & successors(const Label &label) const
Ordered successors for a label.
size_t nLabels() const
Number of distinct labels.
size_t size() const
Total length of a trace, or the number of times a label appears in a trace.
double burstiness() const
The burstiness of a trace.
std::vector< Label > toVector() const
Convert a trace into a vector.
void reserve(size_t n)
Reserve space in the label index.
void traverse(Visitor &visitor) const
Traversal of the trace labels.
std::set< Label > successorSet(const Label &label) const
Set of labels which are successors for the specified label.
bool exists(const Label &label) const
Determines if a label is present in a trace.
bool isEmpty() const
Determines if a trace is empty.
void clear()
Clears the recorded trace.
void print(std::ostream &out, const std::string &separator=", ") const
Print as sequence.
size_t size(const Label &label) const
Total length of a trace, or the number of times a label appears in a trace.
void append(const Label &label)
Append a label to a trace.
Sawyer::Container::Set< Label > labels() const
Set of all labels in the trace.
std::vector< Successor > Successors
Successors for a label.
Label back() const
Returns the last item in the trace.
void dump(std::ostream &out) const
Low-level debugging information.
Trace()
Default constructor.
ConstIterator end() const
Returns a forward iterator pointing past the end of this trace.
Holds a value or nothing.
std::ostream & operator<<(std::ostream &out, const Trace< T, IndexTag > &trace)
Emit the ordered labels for a trace.
Compressed next-label list.
size_t end
Label visitation sequence number.