From 3caa298fc0f881aeaab514c835ff20a2201bc329 Mon Sep 17 00:00:00 2001
From: Jan Huwald <jh@sotun.de>
Date: Wed, 27 Feb 2013 14:41:01 +0100
Subject: add cycle statistics function


diff --git a/cacount.cpp b/cacount.cpp
index 7c052d3..3b385ab 100644
--- a/cacount.cpp
+++ b/cacount.cpp
@@ -1,10 +1,13 @@
-#include <string.h>
 #include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
 #include <array>
 #include <bitset>
 #include <functional>
 #include <iostream>
-#include <stdlib.h>
+#include <map>
+
 
 using namespace std;
 
@@ -26,14 +29,17 @@ State update(State s) {
 
 typedef array<State, maxState> Trans;
 
+void iterState(function<void(int)> f) {
+  for (State s=0; s<maxState; s++)
+    f(s);
+}
 void iterTrans(int times, function<void(int)> f) {
   while (times--)
-    for (State s=0; s<maxState; s++)
-      f(s);
+    iterState(f);
 }
 
 void init(Trans &t) {
-  iterTrans(1, [&](int s) { 
+  iterState([&](int s) { 
       t[s] = update(s); });
 }
 
@@ -41,10 +47,10 @@ Trans* findCycle(Trans &t) {
   // forward to t=maxState; now every state is in a cycle
   iterTrans(logState, [&](int s) {
       t[s] = t[t[s]]; });
-  // compute loop id (lowest state no): go through the loop again and
-  // record the lowest occuring state no
+  // compute loop id (lowest occuring state no): go through the loop again and
+  // record the lowest occuring state number
   Trans &c(*new Trans());
-  iterTrans(1, [&](int s) { 
+  iterState([&](int s) { 
       c[s] = t[s]; });
   iterTrans(logState, [&](int s) {
       c[s] = min(c[s], c[t[s]]);
@@ -52,6 +58,35 @@ Trans* findCycle(Trans &t) {
   return &c;
 }
 
+void cycleStat(Trans &c) {
+  struct Stat {
+    State basin, len, minState;
+    Stat() : basin(0), len(0), minState(maxState) {}
+  };
+  map<State, Stat> cyc;
+  // how big is the basin of attraction?
+  iterState([&](int s) { cyc[c[s]].basin++; });
+  // how long is the cycle, what is the actual minimal state
+  for (auto i : cyc) {
+    Stat &s = cyc[i.first];
+    State cur, start;
+    cur = start = c[i.first]; 
+    do {
+      s.len++;
+      s.minState = min(s.minState, cur);
+      cur=update(cur);
+    } while (cur != start);
+  }
+  // print it
+  for (auto i : cyc) {
+    Stat &s = i.second;
+    cout << s.minState << "\t"
+	 << bitset<logState>(s.minState) << "\t"
+	 << s.len << "\t"
+	 << s.basin << endl;
+  }
+}
+
 void print(Trans &t) {
   for (auto s : t)
     cout << bitset<logState>(s) << endl;
@@ -75,7 +110,7 @@ int main(int argc, char **argv) {
     Trans &t = *(new Trans);
     init(t);
     Trans &c(*findCycle(t));
-    print(c);
+    cycleStat(c);
   }
   return 0;
 }
-- 
cgit v0.10.1