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