ROSE  0.9.10.91
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 <boost/foreach.hpp>
16 #include <set>
17 #include <vector>
18 
19 namespace Sawyer {
20 namespace Container {
21 
24 
27 
29 // Implementation Details
31 namespace TraceDetail {
32 
33 // Internal: An index where labels are keys for a tree-based map.
34 template<class K, class V>
35 class MapIndex {
36  typedef K Label;
37  typedef V Value;
38 
40 
41 public:
42  // Reset index to initial state
43  void clear() {
44  map_.clear();
45  }
46 
47  // Return all labels, and possibly more (although this implementation is exact). If any extra labels are returned, their
48  // values are the default constructed.
49  boost::iterator_range<typename Sawyer::Container::Map<Label, Value>::ConstKeyIterator> labels() const {
50  return map_.keys();
51  }
52 
53  // Return the value stored for a label. If the label has no value then return a default constructed value and do not modify
54  // the index.
55  const Value& operator[](const Label &label) const {
56  return map_.getOrDefault(label);
57  }
58 
59  // Return the value stored for a label. If the label has no value then first insert a default constructed value.
60  Value& operator[](const Label &label) {
61  return map_.insertMaybeDefault(label);
62  }
63 
64  // If the index supports it, reserve space for the specified number of labels.
65  void reserve(size_t /*n*/) {}
66 };
67 
68 // Internal: An index where labels are indexes into a vector. For member documentation see TraceMapIndex
69 template<class K, class V>
70 class VectorIndex {
71  typedef K Label;
72  typedef V Value;
73 
74  const Value dflt_;
75  std::vector<Value> vector_;
76 
77 public:
78  void clear() {
79  vector_.clear(0);
80  }
81 
82  boost::iterator_range<typename Sawyer::Container::Interval<Label>::ConstIterator> labels() const {
83  return Sawyer::Container::Interval<Label>::baseSize(0, vector_.size()).values();
84  }
85 
86  const Value& operator[](Label label) const {
87  return (size_t)label < vector_.size() ? vector_[label] : dflt_;
88  }
89 
90  Value& operator[](Label label) {
91  if ((size_t)label >= vector_.size())
92  vector_.resize(label+1, dflt_);
93  return vector_[label];
94  }
95 
96  void reserve(size_t n) {
97  vector_.reserve(n);
98  }
99 };
100 
101 } // namespace
102 
103 
105 // Traits
107 
162 template<class Label, class Value, class IndexTypeTag>
165 };
166 
167 template<class Label, class Value>
168 struct TraceIndexTraits<Label, Value, TraceVectorIndexTag> {
170 };
171 
172 
174 // Trace
176 
257 template<class T, class IndexTag = TraceMapIndexTag>
258 class Trace {
259 public:
263  typedef T Label;
264 
268  struct Successor {
269  size_t end;
270  Label next;
272  Successor(): end(0) {}
273  Successor(size_t end, const Label &next): end(end), next(next) {}
274  };
275 
277  typedef std::vector<Successor> Successors;
278 
279 private:
280  struct Decompression {
281  size_t n; // label visitation sequence number (starts at zero for each label)
282  size_t succIdx; // index into a Successors list;
283 
284  Decompression(): n(0), succIdx(0) {}
285  };
286 
288  Index index_; // encoded sequence of labels
289  size_t size_; // total length of sequence
290  size_t nLabels_; // number of distinct labels in sequence
291  Optional<Label> front_, back_; // first and last labels in the sequence if size_ > 0
292 public:
294  Trace(): size_(0), nLabels_(0) {}
295 
299  void clear() {
300  index_.clear();
301  size_ = nLabels_ = 0;
302  front_ = back_ = Nothing();
303  }
304 
308  void reserve(size_t n) {
309  index_.reserve(n);
310  }
311 
317  bool isEmpty() const {
318  return front_ ? false : true;
319  }
320 
327  bool exists(const Label &label) const {
328  return isEmpty() ? false : (*front_ == label || *back_ == label || !index_[label].empty());
329  }
330 
336  size_t size() const {
337  return size_;
338  }
339  size_t size(const Label &label) const {
340  const Successors &successors = index_[label];
341  return successors.empty() ? 0 : successors.back().end;
342  }
350  size_t nLabels() const {
351  return nLabels_;
352  }
353 
357  void append(const Label &label) {
358  if (isEmpty()) {
359  front_ = label;
360  ++nLabels_;
361  } else {
362  ASSERT_require(front_);
363  if (!exists(label))
364  ++nLabels_;
365  Successors &successors = index_[*back_];
366  if (successors.empty()) {
367  successors.push_back(Successor(1, label));
368  } else if (successors.back().next == label) {
369  ++successors.back().end;
370  } else {
371  successors.push_back(Successor(successors.back().end+1, label));
372  }
373  }
374  back_ = label;
375  ++size_;
376  }
377 
385  template<class Visitor>
386  void traverse(Visitor &visitor) const {
387  if (isEmpty())
388  return;
389  Label label = *front_;
391  while (1) {
392  if (!visitor(label))
393  return;
394  const Successors &successors = index_[label];
395  Decompression &dcomp = decompressionState[label];
396  if (dcomp.succIdx >= successors.size()) { // FIXME[Robb Matzke 2016-12-08]: simplify these nested "if"s
397  return;
398  } else {
399  const Successor &successor = successors[dcomp.succIdx];
400  if (dcomp.n < successor.end) {
401  label = successor.next;
402  ++dcomp.n;
403  } else {
404  ++dcomp.succIdx;
405  if (dcomp.succIdx >= successors.size())
406  return;
407  label = successors[dcomp.succIdx].next;
408  ++dcomp.n;
409  }
410  }
411  }
412  }
413 
414 private:
415  // helper for the "print" method
416  struct PrintHelper {
417  std::ostream &out;
418  const std::string &separator;
419  size_t nPrinted;
420 
421  PrintHelper(std::ostream &out, const std::string &separator)
422  : out(out), separator(separator), nPrinted(0) {}
423 
424  bool operator()(const Label &label) {
425  if (1 != ++nPrinted)
426  out <<separator;
427  out <<label;
428  return true;
429  }
430  };
431 
432 public:
436  void print(std::ostream &out, const std::string &separator = ", ") const {
437  PrintHelper visitor(out, separator);
438  traverse(visitor);
439  }
440 
445  void dump(std::ostream &out) const {
446  if (isEmpty()) {
447  out <<"Trace(empty)";
448  } else {
449  out <<"Trace(size=" <<size_ <<", unique=" <<nLabels_ <<", front=" <<*front_ <<", back=" <<*back_;
450  BOOST_FOREACH (const Label &label, index_.labels()) {
451  const Successors &successors = index_[label];
452  if (!successors.empty()) {
453  out <<"\n " <<label <<" => [";
454  BOOST_FOREACH (const Successor &successor, successors)
455  out <<"\n end index=" <<successor.end <<", next label=" <<successor.next;
456  out <<"]\n";
457  }
458  }
459  out <<")";
460  }
461  }
462 
463 private:
464  // helper for the "toVector" method
465  struct ToVector {
466  std::vector<Label> vector;
467  bool operator()(const Label &label) {
468  vector.push_back(label);
469  return true;
470  }
471  };
472 
473 public:
477  std::vector<Label> toVector() const {
478  ToVector visitor;
479  traverse(visitor);
480  return visitor.vector;
481  }
482 
488  std::set<Label> successorSet(const Label &label) const {
489  std::set<Label> unique;
490  BOOST_FOREACH (const Successor &successor, index_[label])
491  unique.insert(successor.next);
492  return unique;
493  }
494 
519  double burstiness(const Label &label) const {
520  if (size_t nUniqueLabels = successorSet(label).size())
521  return (double)nUniqueLabels / index_[label].size();
522  return 0.0;
523  }
529  double burstiness() const {
530  size_t size = 0;
531  double sum = 0.0;
532  BOOST_FOREACH (const Label &label, index_.labels()) {
533  if (double x = burstiness(label)) {
534  sum += x;
535  ++size;
536  }
537  }
538  return size ? sum / size : 0.0;
539  }
540 
550  const Successors& successors(const Label &label) const {
551  return index_[label];
552  }
553 };
554 
558 template<class T, class IndexTag>
559 inline std::ostream&
560 operator<<(std::ostream &out, const Trace<T, IndexTag> &trace) {
561  trace.print(out);
562  return out;
563 }
564 
565 } // namespace
566 } // namespace
567 
568 #endif
Records and replays traces.
Definition: Trace.h:258
Sum< T >::Ptr sum()
Factory for value agumenter.
Traits for a Trace label index.
Definition: Trace.h:163
size_t nLabels() const
Number of distinct labels.
Definition: Trace.h:350
void append(const Label &label)
Append a label to a trace.
Definition: Trace.h:357
double burstiness() const
The burstiness of a trace.
Definition: Trace.h:529
T Label
Label type.
Definition: Trace.h:263
double burstiness(const Label &label) const
The burstiness of a label.
Definition: Trace.h:519
void reserve(size_t n)
Reserve space in the label index.
Definition: Trace.h:308
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:339
void traverse(Visitor &visitor) const
Traversal of the trace labels.
Definition: Trace.h:386
std::set< Label > successorSet(const Label &label) const
Set of labels which are successors for the specified label.
Definition: Trace.h:488
Tag for a map-based Trace label index.
Definition: Trace.h:23
size_t size() const
Total length of a trace, or the number of times a label appears in a trace.
Definition: Trace.h:336
void dump(std::ostream &out) const
Low-level debugging information.
Definition: Trace.h:445
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:597
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:618
Compressed next-label list.
Definition: Trace.h:268
Name space for the entire library.
Definition: Access.h:13
bool exists(const Label &label) const
Determines if a label is present in a trace.
Definition: Trace.h:327
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:550
void clear()
Clears the recorded trace.
Definition: Trace.h:299
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:515
void print(std::ostream &out, const std::string &separator=", ") const
Print as sequence.
Definition: Trace.h:436
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:286
std::vector< Successor > Successors
Successors for a label.
Definition: Trace.h:277
std::vector< Label > toVector() const
Convert a trace into a vector.
Definition: Trace.h:477
Tag for a vector-based Trace label index.
Definition: Trace.h:26
Represents no value.
Definition: Optional.h:32
size_t end
Label visitation sequence number.
Definition: Trace.h:269
bool isEmpty() const
Determines if a trace is empty.
Definition: Trace.h:317
Trace()
Default constructor.
Definition: Trace.h:294