ROSE  0.9.11.125
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 <set>
18 #include <vector>
19 
20 namespace Sawyer {
21 namespace Container {
22 
25 
28 
30 // Implementation Details
32 namespace TraceDetail {
33 
34 // Internal: An index where labels are keys for a tree-based map.
35 template<class K, class V>
36 class MapIndex {
37  typedef K Label;
38  typedef V Value;
39 
41 
42 public:
43  // Reset index to initial state
44  void clear() {
45  map_.clear();
46  }
47 
48  // Return all labels, and possibly more (although this implementation is exact). If any extra labels are returned, their
49  // values are the default constructed.
50  boost::iterator_range<typename Sawyer::Container::Map<Label, Value>::ConstKeyIterator> labels() const {
51  return map_.keys();
52  }
53 
54  // Return the value stored for a label. If the label has no value then return a default constructed value and do not modify
55  // the index.
56  const Value& operator[](const Label &label) const {
57  return map_.getOrDefault(label);
58  }
59 
60  // Return the value stored for a label. If the label has no value then first insert a default constructed value.
61  Value& operator[](const Label &label) {
62  return map_.insertMaybeDefault(label);
63  }
64 
65  // If the index supports it, reserve space for the specified number of labels.
66  void reserve(size_t /*n*/) {}
67 };
68 
69 // Internal: An index where labels are indexes into a vector. For member documentation see TraceMapIndex
70 template<class K, class V>
71 class VectorIndex {
72  typedef K Label;
73  typedef V Value;
74 
75  const Value dflt_;
76  std::vector<Value> vector_;
77 
78 public:
79  void clear() {
80  vector_.clear(0);
81  }
82 
83  boost::iterator_range<typename Sawyer::Container::Interval<Label>::ConstIterator> labels() const {
84  return Sawyer::Container::Interval<Label>::baseSize(0, vector_.size()).values();
85  }
86 
87  const Value& operator[](Label label) const {
88  return (size_t)label < vector_.size() ? vector_[label] : dflt_;
89  }
90 
91  Value& operator[](Label label) {
92  if ((size_t)label >= vector_.size())
93  vector_.resize(label+1, dflt_);
94  return vector_[label];
95  }
96 
97  void reserve(size_t n) {
98  vector_.reserve(n);
99  }
100 };
101 
102 } // namespace
103 
104 
106 // Traits
108 
163 template<class Label, class Value, class IndexTypeTag>
166 };
167 
168 template<class Label, class Value>
169 struct TraceIndexTraits<Label, Value, TraceVectorIndexTag> {
171 };
172 
173 
175 // Trace
177 
258 template<class T, class IndexTag = TraceMapIndexTag>
259 class Trace {
260 public:
264  typedef T Label;
265 
269  struct Successor {
270  size_t end;
271  Label next;
273  Successor(): end(0) {}
274  Successor(size_t end, const Label &next): end(end), next(next) {}
275  };
276 
278  typedef std::vector<Successor> Successors;
279 
280 private:
281  struct Decompression {
282  size_t n; // label visitation sequence number (starts at zero for each label)
283  size_t succIdx; // index into a Successors list;
284 
285  Decompression(): n(0), succIdx(0) {}
286  };
287 
289  Index index_; // encoded sequence of labels
290  size_t size_; // total length of sequence
291  size_t nLabels_; // number of distinct labels in sequence
292  Optional<Label> front_, back_; // first and last labels in the sequence if size_ > 0
293 public:
295  Trace(): size_(0), nLabels_(0) {}
296 
300  void clear() {
301  index_.clear();
302  size_ = nLabels_ = 0;
303  front_ = back_ = Nothing();
304  }
305 
309  void reserve(size_t n) {
310  index_.reserve(n);
311  }
312 
318  bool isEmpty() const {
319  return front_ ? false : true;
320  }
321 
328  bool exists(const Label &label) const {
329  return isEmpty() ? false : (*front_ == label || *back_ == label || !index_[label].empty());
330  }
331 
337  size_t size() const {
338  return size_;
339  }
340  size_t size(const Label &label) const {
341  const Successors &successors = index_[label];
342  return successors.empty() ? 0 : successors.back().end;
343  }
351  size_t nLabels() const {
352  return nLabels_;
353  }
354 
360  BOOST_FOREACH (const Label &label, index_.labels())
361  retval.insert(label);
362  return retval;
363  }
364 
368  void append(const Label &label) {
369  if (isEmpty()) {
370  front_ = label;
371  ++nLabels_;
372  } else {
373  ASSERT_require(front_);
374  if (!exists(label))
375  ++nLabels_;
376  Successors &successors = index_[*back_];
377  if (successors.empty()) {
378  successors.push_back(Successor(1, label));
379  } else if (successors.back().next == label) {
380  ++successors.back().end;
381  } else {
382  successors.push_back(Successor(successors.back().end+1, label));
383  }
384  }
385  back_ = label;
386  ++size_;
387  }
388 
396  template<class Visitor>
397  void traverse(Visitor &visitor) const {
398  if (isEmpty())
399  return;
400  Label label = *front_;
402  while (1) {
403  if (!visitor(label))
404  return;
405  const Successors &successors = index_[label];
406  Decompression &dcomp = decompressionState[label];
407  if (dcomp.succIdx >= successors.size()) { // FIXME[Robb Matzke 2016-12-08]: simplify these nested "if"s
408  return;
409  } else {
410  const Successor &successor = successors[dcomp.succIdx];
411  if (dcomp.n < successor.end) {
412  label = successor.next;
413  ++dcomp.n;
414  } else {
415  ++dcomp.succIdx;
416  if (dcomp.succIdx >= successors.size())
417  return;
418  label = successors[dcomp.succIdx].next;
419  ++dcomp.n;
420  }
421  }
422  }
423  }
424 
425 private:
426  // helper for the "print" method
427  struct PrintHelper {
428  std::ostream &out;
429  const std::string &separator;
430  size_t nPrinted;
431 
432  PrintHelper(std::ostream &out, const std::string &separator)
433  : out(out), separator(separator), nPrinted(0) {}
434 
435  bool operator()(const Label &label) {
436  if (1 != ++nPrinted)
437  out <<separator;
438  out <<label;
439  return true;
440  }
441  };
442 
443 public:
447  void print(std::ostream &out, const std::string &separator = ", ") const {
448  PrintHelper visitor(out, separator);
449  traverse(visitor);
450  }
451 
456  void dump(std::ostream &out) const {
457  if (isEmpty()) {
458  out <<"Trace(empty)";
459  } else {
460  out <<"Trace(size=" <<size_ <<", unique=" <<nLabels_ <<", front=" <<*front_ <<", back=" <<*back_;
461  BOOST_FOREACH (const Label &label, index_.labels()) {
462  const Successors &successors = index_[label];
463  if (!successors.empty()) {
464  out <<"\n " <<label <<" => [";
465  BOOST_FOREACH (const Successor &successor, successors)
466  out <<"\n end index=" <<successor.end <<", next label=" <<successor.next;
467  out <<"]\n";
468  }
469  }
470  out <<")";
471  }
472  }
473 
474 private:
475  // helper for the "toVector" method
476  struct ToVector {
477  std::vector<Label> vector;
478  bool operator()(const Label &label) {
479  vector.push_back(label);
480  return true;
481  }
482  };
483 
484 public:
488  std::vector<Label> toVector() const {
489  ToVector visitor;
490  traverse(visitor);
491  return visitor.vector;
492  }
493 
499  std::set<Label> successorSet(const Label &label) const {
500  std::set<Label> unique;
501  BOOST_FOREACH (const Successor &successor, index_[label])
502  unique.insert(successor.next);
503  return unique;
504  }
505 
530  double burstiness(const Label &label) const {
531  if (size_t nUniqueLabels = successorSet(label).size())
532  return (double)nUniqueLabels / index_[label].size();
533  return 0.0;
534  }
540  double burstiness() const {
541  size_t size = 0;
542  double sum = 0.0;
543  BOOST_FOREACH (const Label &label, index_.labels()) {
544  if (double x = burstiness(label)) {
545  sum += x;
546  ++size;
547  }
548  }
549  return size ? sum / size : 0.0;
550  }
551 
561  const Successors& successors(const Label &label) const {
562  return index_[label];
563  }
564 };
565 
569 template<class T, class IndexTag>
570 inline std::ostream&
571 operator<<(std::ostream &out, const Trace<T, IndexTag> &trace) {
572  trace.print(out);
573  return out;
574 }
575 
576 } // namespace
577 } // namespace
578 
579 #endif
Ordered set of values.
Definition: Set.h:46
Records and replays traces.
Definition: Trace.h:259
Sum< T >::Ptr sum()
Factory for value agumenter.
Traits for a Trace label index.
Definition: Trace.h:164
size_t nLabels() const
Number of distinct labels.
Definition: Trace.h:351
void append(const Label &label)
Append a label to a trace.
Definition: Trace.h:368
double burstiness() const
The burstiness of a trace.
Definition: Trace.h:540
bool insert(const Value &value)
Insert a value.
Definition: Set.h:222
T Label
Label type.
Definition: Trace.h:264
double burstiness(const Label &label) const
The burstiness of a label.
Definition: Trace.h:530
void reserve(size_t n)
Reserve space in the label index.
Definition: Trace.h:309
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:340
void traverse(Visitor &visitor) const
Traversal of the trace labels.
Definition: Trace.h:397
std::set< Label > successorSet(const Label &label) const
Set of labels which are successors for the specified label.
Definition: Trace.h:499
Tag for a map-based Trace label index.
Definition: Trace.h:24
size_t size() const
Total length of a trace, or the number of times a label appears in a trace.
Definition: Trace.h:337
void dump(std::ostream &out) const
Low-level debugging information.
Definition: Trace.h:456
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:659
Sawyer::Container::Set< Label > labels() const
Set of all labels in the trace.
Definition: Trace.h:358
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:680
Compressed next-label list.
Definition: Trace.h:269
Name space for the entire library.
bool exists(const Label &label) const
Determines if a label is present in a trace.
Definition: Trace.h:328
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:161
const Successors & successors(const Label &label) const
Ordered successors for a label.
Definition: Trace.h:561
void clear()
Clears the recorded trace.
Definition: Trace.h:300
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:577
void print(std::ostream &out, const std::string &separator=", ") const
Print as sequence.
Definition: Trace.h:447
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:348
std::vector< Successor > Successors
Successors for a label.
Definition: Trace.h:278
std::vector< Label > toVector() const
Convert a trace into a vector.
Definition: Trace.h:488
Tag for a vector-based Trace label index.
Definition: Trace.h:27
Represents no value.
Definition: Optional.h:32
size_t end
Label visitation sequence number.
Definition: Trace.h:270
bool isEmpty() const
Determines if a trace is empty.
Definition: Trace.h:318
Trace()
Default constructor.
Definition: Trace.h:295