FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
stat.h
1 #ifndef __MY_STAT_H__
2 #define __MY_STAT_H__
3 
4 /*
5  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of FlashGraph.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include <limits.h>
24 #include <math.h>
25 #include <assert.h>
26 
27 #include <map>
28 #include <vector>
29 #include <boost/foreach.hpp>
30 
31 #include "FG_basic_types.h"
32 
33 namespace fg
34 {
35 
36 class log_hist_bucket
37 {
38  size_t lower_bound;
39  size_t upper_bound;
40  size_t count;
41 public:
42  log_hist_bucket() {
43  count = 0;
44  lower_bound = 0;
45  upper_bound = INT_MAX;
46  }
47 
48  log_hist_bucket(int idx) {
49  count = 0;
50  lower_bound = pow(10, idx);
51  if (idx == 0)
52  lower_bound = 0;
53  upper_bound = pow(10, idx + 1);
54  }
55 
56  size_t get_lower_bound() const {
57  return lower_bound;
58  }
59 
60  size_t get_upper_bound() const {
61  return upper_bound;
62  }
63 
64  size_t get_count() const {
65  return count;
66  }
67 
68  void inc_count(size_t num) {
69  count += num;
70  }
71 };
72 
73 class log_histogram
74 {
75  std::vector<log_hist_bucket> buckets;
76 public:
77  log_histogram(int num_buckets): buckets(num_buckets) {
78  assert(num_buckets > 0);
79  for (int i = 0; i < num_buckets; i++)
80  buckets[i] = log_hist_bucket(i);
81  }
82 
83  log_hist_bucket &find_bucket(size_t v) {
84  for (size_t i = 0; i < buckets.size(); i++)
85  if (buckets[i].get_lower_bound() <= v
86  && v < buckets[i].get_upper_bound())
87  return buckets[i];
88  fprintf(stderr,
89  "can't find a bucket for %ld. All buckets cover [%ld, %ld).\n",
90  v, buckets.front().get_lower_bound(),
91  buckets.back().get_upper_bound());
92  abort();
93  }
94 
95  void add_value(size_t v) {
96  find_bucket(v).inc_count(1);
97  }
98 
99  int get_num_buckets() const {
100  return buckets.size();
101  }
102 
103  const log_hist_bucket &get_bucket(int idx) const {
104  return buckets[idx];
105  }
106 
107  void print(FILE *f) const {
108  int non_empty = get_num_buckets() - 1;
109  for (; non_empty > 0 && get_bucket(non_empty).get_count() == 0; non_empty--);
110  for (int i = 0; i <= non_empty; i++) {
111  fprintf(f, "[%ld, %ld): %ld\n", get_bucket(i).get_lower_bound(),
112  get_bucket(i).get_upper_bound(),
113  get_bucket(i).get_count());
114  }
115  }
116 };
117 
118 /*
119  * This count the apperances of each value of type T.
120  */
121 template<class T>
122 class count_map
123 {
124  typedef std::map<T, size_t> map_t;
125  map_t map;
126 public:
127  void add(const T &value) {
128  typename map_t::iterator it = map.find(value);
129  if (it == map.end())
130  map.insert(std::pair<T, vsize_t>(value, 1));
131  else
132  it->second++;
133  }
134 
135  void merge(const count_map &map) {
136  BOOST_FOREACH(typename map_t::value_type v, map.map) {
137  typename map_t::iterator it = this->map.find(v.first);
138  if (it == this->map.begin())
139  this->map.insert(std::pair<T, size_t>(v.first, v.second));
140  else
141  it->second += v.second;
142  }
143  }
144 
145  std::pair<T, size_t> get_max_count() const {
146  size_t max_counts = 0;
147  vertex_id_t max_v = T();
148  BOOST_FOREACH(typename map_t::value_type v, map) {
149  if (max_counts < v.second) {
150  max_counts = v.second;
151  max_v = v.first;
152  }
153  }
154  return std::pair<T, size_t>(max_v, max_counts);
155  }
156 
157  template<class ApplyFunc>
158  void apply(ApplyFunc func) const {
159  BOOST_FOREACH(const typename map_t::value_type v, map) {
160  func(v);
161  }
162  }
163 
164  size_t get_size() const {
165  return map.size();
166  }
167 
168  bool exists(const T &key) const {
169  typename map_t::const_iterator it = map.find(key);
170  return it != map.end();
171  }
172 
173  size_t get(const T &key) const {
174  typename map_t::const_iterator it = map.find(key);
175  assert(it != map.end());
176  return it->second;
177  }
178 
179  void remove(const T &key) {
180  map.erase(key);
181  }
182 };
183 
184 }
185 
186 #endif