ROSE  0.11.96.11
Trace.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_Trace_H
9 #define Sawyer_Trace_H
10 
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/iterator.hpp>
18 #include <set>
19 #include <vector>
20 
21 namespace Sawyer {
22 namespace Container {
23 
26 
29 
31 // Implementation Details
33 namespace TraceDetail {
34 
35 // Internal: An index where labels are keys for a tree-based map.
36 template<class K, class V>
37 class MapIndex {
38  typedef K Label;
39  typedef V Value;
40 
42 
43 public:
44  // Reset index to initial state
45  void clear() {
46  map_.clear();
47  }
48 
49  // Return all labels, and possibly more (although this implementation is exact). If any extra labels are returned, their
50  // values are the default constructed.
51  boost::iterator_range<typename Sawyer::Container::Map<Label, Value>::ConstKeyIterator> labels() const {
52  return map_.keys();
53  }
54 
55  // Return the value stored for a label. If the label has no value then return a default constructed value and do not modify
56  // the index.
57  const Value& operator[](const Label &label) const {
58  return map_.getOrDefault(label);
59  }
60 
61  // Return the value stored for a label. If the label has no value then first insert a default constructed value.
62  Value& operator[](const Label &label) {
63  return map_.insertMaybeDefault(label);
64  }
65 
66  // If the index supports it, reserve space for the specified number of labels.
67  void reserve(size_t /*n*/) {}
68 };
69 
70 // Internal: An index where labels are indexes into a vector. For member documentation see TraceMapIndex
71 template<class K, class V>
72 class VectorIndex {
73  typedef K Label;
74  typedef V Value;
75 
76  const Value dflt_;
77  std::vector<Value> vector_;
78 
79 public:
80  VectorIndex() {}
81 
82  void clear() {
83  vector_.clear(0);
84  }
85 
86  boost::iterator_range<typename Sawyer::Container::Interval<Label>::ConstIterator> labels() const {
87  return Sawyer::Container::Interval<Label>::baseSize(0, vector_.size()).values();
88  }
89 
90  const Value& operator[](Label label) const {
91  return (size_t)label < vector_.size() ? vector_[label] : dflt_;
92  }
93 
94  Value& operator[](Label label) {
95  if ((size_t)label >= vector_.size())
96  vector_.resize(label+1, dflt_);
97  return vector_[label];
98  }
99 
100  void reserve(size_t n) {
101  vector_.reserve(n);
102  }
103 };
104 
105 } // namespace
106 
107 
109 // Traits
111 
166 template<class Label, class Value, class IndexTypeTag>
169 };
170 
171 template<class Label, class Value>
172 struct TraceIndexTraits<Label, Value, TraceVectorIndexTag> {
174 };
175 
176 
178 // Trace
180 
261 template<class T, class IndexTag = TraceMapIndexTag>
262 class Trace {
263 private:
264  struct Decompression {
265  size_t n; // label visitation sequence number (starts at zero for each label)
266  size_t succIdx; // index into a Successors list;
267 
268  Decompression(): n(0), succIdx(0) {}
269  };
270 
271 public:
275  typedef T Label;
276 
280  struct Successor {
281  size_t end;
284  Successor(): end(0) {}
285  Successor(size_t end, const Label &next): end(end), next(next) {}
286  };
287 
289  typedef std::vector<Successor> Successors;
290 
294  class ConstIterator: public boost::iterator_facade<ConstIterator, const Label, boost::forward_traversal_tag, Label> {
295  friend class boost::iterator_core_access;
296  const Trace *trace_;
298  size_t position_;
300 
301  public:
304  : trace_(NULL), position_(0) {}
305 
307  explicit ConstIterator(const Trace &trace)
308  : trace_(&trace), position_(0) {
309  if (!trace_->isEmpty())
310  label_ = trace_->front();
311  }
312 
315  : trace_(other.trace_), label_(other.label_), position_(other.position_),
316  decompressionState_(other.decompressionState_) {}
317 
319  bool isEnd() const {
320  return !label_;
321  }
322 
326  size_t position() const {
327  return position_;
328  }
329 
330  private:
331  // core operation from iterator_facade needed for readable iterator concept
332  Label dereference() const {
333  ASSERT_forbid(isEnd());
334  return *label_;
335  }
336 
337  // core operation from iterator_facade needed for single pass iterator concept
338  bool equal(const ConstIterator &other) const {
339  if (isEnd() || other.isEnd())
340  return isEnd() == other.isEnd();
341  return trace_ == other.trace_ && position() == other.position();
342  }
343 
344  // core operation from iterator_facade needed for incrementable iterator concept
345  void increment() {
346  ASSERT_forbid(isEnd());
347  const Successors &successors = trace_->index_[*label_];
348  Decompression &dcomp = decompressionState_[*label_];
349  if (dcomp.succIdx >= successors.size()) {
350  label_ = Nothing();
351  } else {
352  const Successor &successor = successors[dcomp.succIdx];
353  if (dcomp.n < successor.end) {
354  label_ = successor.next;
355  ++dcomp.n;
356  } else {
357  ++dcomp.succIdx;
358  if (dcomp.succIdx >= successors.size()) {
359  label_ = Nothing();
360  } else {
361  label_ = successors[dcomp.succIdx].next;
362  ++dcomp.n;
363  }
364  }
365  }
366  ++position_;
367  }
368  };
369 
370 private:
371  typedef typename TraceIndexTraits<Label, Successors, IndexTag>::Index Index;
372  Index index_; // encoded sequence of labels
373  size_t size_; // total length of sequence
374  size_t nLabels_; // number of distinct labels in sequence
375  Optional<Label> front_, back_; // first and last labels in the sequence if size_ > 0
376 
377 public:
379  Trace(): size_(0), nLabels_(0) {}
380 
383  return ConstIterator(*this);
384  }
385 
387  ConstIterator end() const {
388  return ConstIterator();
389  }
390 
394  Label front() const {
395  return *front_;
396  }
397 
401  Label back() const {
402  return *back_;
403  }
404 
408  void clear() {
409  index_.clear();
410  size_ = nLabels_ = 0;
411  front_ = back_ = Nothing();
412  }
413 
417  void reserve(size_t n) {
418  index_.reserve(n);
419  }
420 
426  bool isEmpty() const {
427  return front_ ? false : true;
428  }
429 
436  bool exists(const Label &label) const {
437  return isEmpty() ? false : (*front_ == label || *back_ == label || !index_[label].empty());
438  }
439 
445  size_t size() const {
446  return size_;
447  }
448  size_t size(const Label &label) const {
449  const Successors &successors = index_[label];
450  return successors.empty() ? 0 : successors.back().end;
451  }
459  size_t nLabels() const {
460  return nLabels_;
461  }
462 
468  BOOST_FOREACH (const Label &label, index_.labels())
469  retval.insert(label);
470  return retval;
471  }
472 
476  void append(const Label &label) {
477  if (isEmpty()) {
478  front_ = label;
479  ++nLabels_;
480  } else {
481  ASSERT_require(front_);
482  if (!exists(label))
483  ++nLabels_;
484  Successors &successors = index_[*back_];
485  if (successors.empty()) {
486  successors.push_back(Successor(1, label));
487  } else if (successors.back().next == label) {
488  ++successors.back().end;
489  } else {
490  successors.push_back(Successor(successors.back().end+1, label));
491  }
492  }
493  back_ = label;
494  ++size_;
495  }
496 
504  template<class Visitor>
505  void traverse(Visitor &visitor) const {
506  if (isEmpty())
507  return;
508  Label label = *front_;
510  while (1) {
511  if (!visitor(label))
512  return;
513  const Successors &successors = index_[label];
514  Decompression &dcomp = decompressionState[label];
515  if (dcomp.succIdx >= successors.size()) { // FIXME[Robb Matzke 2016-12-08]: simplify these nested "if"s
516  return;
517  } else {
518  const Successor &successor = successors[dcomp.succIdx];
519  if (dcomp.n < successor.end) {
520  label = successor.next;
521  ++dcomp.n;
522  } else {
523  ++dcomp.succIdx;
524  if (dcomp.succIdx >= successors.size())
525  return;
526  label = successors[dcomp.succIdx].next;
527  ++dcomp.n;
528  }
529  }
530  }
531  }
532 
533 private:
534  // helper for the "print" method
535  struct PrintHelper {
536  std::ostream &out;
537  const std::string &separator;
538  size_t nPrinted;
539 
540  PrintHelper(std::ostream &out, const std::string &separator)
541  : out(out), separator(separator), nPrinted(0) {}
542 
543  bool operator()(const Label &label) {
544  if (1 != ++nPrinted)
545  out <<separator;
546  out <<label;
547  return true;
548  }
549  };
550 
551 public:
555  void print(std::ostream &out, const std::string &separator = ", ") const {
556  PrintHelper visitor(out, separator);
557  traverse(visitor);
558  }
559 
564  void dump(std::ostream &out) const {
565  if (isEmpty()) {
566  out <<"Trace(empty)";
567  } else {
568  out <<"Trace(size=" <<size_ <<", unique=" <<nLabels_ <<", front=" <<*front_ <<", back=" <<*back_;
569  BOOST_FOREACH (const Label &label, index_.labels()) {
570  const Successors &successors = index_[label];
571  if (!successors.empty()) {
572  out <<"\n " <<label <<" => [";
573  BOOST_FOREACH (const Successor &successor, successors)
574  out <<"\n end index=" <<successor.end <<", next label=" <<successor.next;
575  out <<"]\n";
576  }
577  }
578  out <<")";
579  }
580  }
581 
582 private:
583  // helper for the "toVector" method
584  struct ToVector {
585  std::vector<Label> vector;
586  bool operator()(const Label &label) {
587  vector.push_back(label);
588  return true;
589  }
590  };
591 
592 public:
596  std::vector<Label> toVector() const {
597  ToVector visitor;
598  traverse(visitor);
599  return visitor.vector;
600  }
601 
607  std::set<Label> successorSet(const Label &label) const {
608  std::set<Label> unique;
609  BOOST_FOREACH (const Successor &successor, index_[label])
610  unique.insert(successor.next);
611  return unique;
612  }
613 
638  double burstiness(const Label &label) const {
639  if (size_t nUniqueLabels = successorSet(label).size())
640  return (double)nUniqueLabels / index_[label].size();
641  return 0.0;
642  }
648  double burstiness() const {
649  size_t size = 0;
650  double sum = 0.0;
651  BOOST_FOREACH (const Label &label, index_.labels()) {
652  if (double x = burstiness(label)) {
653  sum += x;
654  ++size;
655  }
656  }
657  return size ? sum / size : 0.0;
658  }
659 
669  const Successors& successors(const Label &label) const {
670  return index_[label];
671  }
672 };
673 
677 template<class T, class IndexTag>
678 inline std::ostream&
679 operator<<(std::ostream &out, const Trace<T, IndexTag> &trace) {
680  trace.print(out);
681  return out;
682 }
683 
684 } // namespace
685 } // namespace
686 
687 #endif
Sawyer::Container::Trace::successors
const Successors & successors(const Label &label) const
Ordered successors for a label.
Definition: Trace.h:669
Sawyer::Container::Trace::isEmpty
bool isEmpty() const
Determines if a trace is empty.
Definition: Trace.h:426
Sawyer::Optional< Label >
Sawyer::Nothing
Represents no value.
Definition: Optional.h:32
Sawyer::CommandLine::sum
Sum< T >::Ptr sum()
Factory for value agumenter.
Definition: util/Sawyer/CommandLine.h:1981
Sawyer::Container::Trace::begin
ConstIterator begin() const
Returns a forward iterator pointing to first element of this trace.
Definition: Trace.h:382
Sawyer::Container::Map::insertMaybeDefault
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:668
Sawyer::Container::Trace::Successors
std::vector< Successor > Successors
Successors for a label.
Definition: Trace.h:289
Sawyer::Container::Trace::append
void append(const Label &label)
Append a label to a trace.
Definition: Trace.h:476
Sawyer::Container::Trace::back
Label back() const
Returns the last item in the trace.
Definition: Trace.h:401
Sawyer::Container::TraceIndexTraits
Traits for a Trace label index.
Definition: Trace.h:167
Sawyer::Container::TraceDetail::MapIndex
Definition: Trace.h:37
Sawyer::Container::Trace::dump
void dump(std::ostream &out) const
Low-level debugging information.
Definition: Trace.h:564
Sawyer::Container::Trace::size
size_t size(const Label &label) const
Total length of a trace, or the number of times a label appears in a trace.
Definition: Trace.h:448
Sawyer::Container::Map< Label, Value >
Sawyer::Container::Trace::front
Label front() const
Returns the first item in the trace.
Definition: Trace.h:394
Sawyer::Container::Trace::clear
void clear()
Clears the recorded trace.
Definition: Trace.h:408
Sawyer::Container::Trace::ConstIterator
Forward iterator.
Definition: Trace.h:294
Sawyer::Container::Trace::Successor::end
size_t end
Label visitation sequence number.
Definition: Trace.h:281
Sawyer::Container::Trace::ConstIterator::ConstIterator
ConstIterator(const Trace &trace)
Construct iterator pointing to first element of the trace, if any.
Definition: Trace.h:307
Sawyer::Container::TraceDetail::VectorIndex
Definition: Trace.h:72
Sawyer::Container::Trace::burstiness
double burstiness(const Label &label) const
The burstiness of a label.
Definition: Trace.h:638
Sawyer::Container::Trace::exists
bool exists(const Label &label) const
Determines if a label is present in a trace.
Definition: Trace.h:436
Sawyer::Container::Interval::baseSize
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:162
Sawyer::Container::TraceVectorIndexTag
Tag for a vector-based Trace label index.
Definition: Trace.h:28
Sawyer::Container::TraceMapIndexTag
Tag for a map-based Trace label index.
Definition: Trace.h:25
Sawyer::Container::Trace::Successor::next
Label next
Next label.
Definition: Trace.h:282
Sawyer::Container::Trace::ConstIterator::position
size_t position() const
Position of iterator within trace.
Definition: Trace.h:326
Sawyer::Container::Map::getOrDefault
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:586
Sawyer::Container::Trace::Successor
Compressed next-label list.
Definition: Trace.h:280
Sawyer::Container::Interval::values
boost::iterator_range< ConstIterator > values() const
Iterator range for values.
Definition: Interval.h:416
Sawyer::Container::Trace
Records and replays traces.
Definition: Trace.h:262
Sawyer::Container::Trace::toVector
std::vector< Label > toVector() const
Convert a trace into a vector.
Definition: Trace.h:596
Sawyer::Container::Trace::ConstIterator::ConstIterator
ConstIterator(const ConstIterator &other)
Copy constructor.
Definition: Trace.h:314
Sawyer::Container::Set::insert
bool insert(const Value &value)
Insert a value.
Definition: Set.h:228
Sawyer::Container::Trace::successorSet
std::set< Label > successorSet(const Label &label) const
Set of labels which are successors for the specified label.
Definition: Trace.h:607
Sawyer::Container::Trace::Label
T Label
Label type.
Definition: Trace.h:275
Sawyer
Name space for the entire library.
Definition: Access.h:13
Sawyer::Container::Trace::reserve
void reserve(size_t n)
Reserve space in the label index.
Definition: Trace.h:417
Sawyer::Container::Trace::size
size_t size() const
Total length of a trace, or the number of times a label appears in a trace.
Definition: Trace.h:445
Sawyer::Container::Trace::traverse
void traverse(Visitor &visitor) const
Traversal of the trace labels.
Definition: Trace.h:505
Sawyer::Container::Trace::Trace
Trace()
Default constructor.
Definition: Trace.h:379
Sawyer::Container::Trace::burstiness
double burstiness() const
The burstiness of a trace.
Definition: Trace.h:648
Sawyer::Container::Trace::end
ConstIterator end() const
Returns a forward iterator pointing past the end of this trace.
Definition: Trace.h:387
Sawyer::Container::Trace::print
void print(std::ostream &out, const std::string &separator=", ") const
Print as sequence.
Definition: Trace.h:555
Sawyer::Container::Trace::nLabels
size_t nLabels() const
Number of distinct labels.
Definition: Trace.h:459
Sawyer::Container::Map::keys
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:357
Sawyer::Container::operator<<
std::ostream & operator<<(std::ostream &out, const Trace< T, IndexTag > &trace)
Emit the ordered labels for a trace.
Definition: Trace.h:679
Sawyer::Container::Set
Ordered set of values.
Definition: Set.h:52
Sawyer::Container::Trace::labels
Sawyer::Container::Set< Label > labels() const
Set of all labels in the trace.
Definition: Trace.h:466
Sawyer::Container::Map::clear
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:689
Sawyer::Container::Trace::ConstIterator::isEnd
bool isEnd() const
Test whether iterator is at the end.
Definition: Trace.h:319
Sawyer::Container::Trace::ConstIterator::ConstIterator
ConstIterator()
Construct iterator point to end of any trace.
Definition: Trace.h:303