ROSE 0.11.145.147
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://gitlab.com/charger7534/sawyer.git.
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/range.hpp>
18#include <set>
19#include <vector>
20
21namespace Sawyer {
22namespace Container {
23
26
29
31// Implementation Details
33namespace TraceDetail {
34
35// Internal: An index where labels are keys for a tree-based map.
36template<class K, class V>
37class MapIndex {
38 typedef K Label;
39 typedef V Value;
40
42
43public:
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
71template<class K, class V>
73 typedef K Label;
74 typedef V Value;
75
76 const Value dflt_;
77 std::vector<Value> vector_;
78
79public:
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
166template<class Label, class Value, class IndexTypeTag>
170
171template<class Label, class Value>
175
176
178// Trace
180
261template<class T, class IndexTag = TraceMapIndexTag>
262class Trace {
263private:
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
271public:
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
370private:
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
377public:
379 Trace(): size_(0), nLabels_(0) {}
380
383 return ConstIterator(*this);
384 }
385
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
533private:
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
551public:
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
582private:
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
592public:
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
677template<class T, class IndexTag>
678inline std::ostream&
679operator<<(std::ostream &out, const Trace<T, IndexTag> &trace) {
680 trace.print(out);
681 return out;
682}
683
684} // namespace
685} // namespace
686
687#endif
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
Definition Interval.h:173
boost::iterator_range< ConstIterator > values() const
Iterator range for values.
Definition Interval.h:439
Container associating values with keys.
Definition Sawyer/Map.h:72
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition Sawyer/Map.h:711
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition Sawyer/Map.h:400
Map & clear()
Remove all nodes.
Definition Sawyer/Map.h:732
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition Sawyer/Map.h:629
Ordered set of values.
Definition Set.h:56
bool insert(const Value &value)
Insert a value.
Definition Set.h:258
Tag for a map-based Trace label index.
Definition Trace.h:25
Tag for a vector-based Trace label index.
Definition Trace.h:28
size_t position() const
Position of iterator within trace.
Definition Trace.h:326
bool isEnd() const
Test whether iterator is at the end.
Definition Trace.h:319
ConstIterator(const Trace &trace)
Construct iterator pointing to first element of the trace, if any.
Definition Trace.h:307
ConstIterator(const ConstIterator &other)
Copy constructor.
Definition Trace.h:314
ConstIterator()
Construct iterator point to end of any trace.
Definition Trace.h:303
Records and replays traces.
Definition Trace.h:262
Label front() const
Returns the first item in the trace.
Definition Trace.h:394
double burstiness(const Label &label) const
The burstiness of a label.
Definition Trace.h:638
ConstIterator begin() const
Returns a forward iterator pointing to first element of this trace.
Definition Trace.h:382
const Successors & successors(const Label &label) const
Ordered successors for a label.
Definition Trace.h:669
size_t nLabels() const
Number of distinct labels.
Definition Trace.h:459
size_t size() const
Total length of a trace, or the number of times a label appears in a trace.
Definition Trace.h:445
double burstiness() const
The burstiness of a trace.
Definition Trace.h:648
std::vector< Label > toVector() const
Convert a trace into a vector.
Definition Trace.h:596
void reserve(size_t n)
Reserve space in the label index.
Definition Trace.h:417
void traverse(Visitor &visitor) const
Traversal of the trace labels.
Definition Trace.h:505
T Label
Label type.
Definition Trace.h:275
std::set< Label > successorSet(const Label &label) const
Set of labels which are successors for the specified label.
Definition Trace.h:607
bool exists(const Label &label) const
Determines if a label is present in a trace.
Definition Trace.h:436
bool isEmpty() const
Determines if a trace is empty.
Definition Trace.h:426
void clear()
Clears the recorded trace.
Definition Trace.h:408
void print(std::ostream &out, const std::string &separator=", ") const
Print as sequence.
Definition Trace.h:555
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
void append(const Label &label)
Append a label to a trace.
Definition Trace.h:476
Sawyer::Container::Set< Label > labels() const
Set of all labels in the trace.
Definition Trace.h:466
std::vector< Successor > Successors
Successors for a label.
Definition Trace.h:289
Label back() const
Returns the last item in the trace.
Definition Trace.h:401
void dump(std::ostream &out) const
Low-level debugging information.
Definition Trace.h:564
Trace()
Default constructor.
Definition Trace.h:379
ConstIterator end() const
Returns a forward iterator pointing past the end of this trace.
Definition Trace.h:387
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
std::ostream & operator<<(std::ostream &out, const Trace< T, IndexTag > &trace)
Emit the ordered labels for a trace.
Definition Trace.h:679
Sawyer support library.
Traits for a Trace label index.
Definition Trace.h:167
Compressed next-label list.
Definition Trace.h:280
size_t end
Label visitation sequence number.
Definition Trace.h:281