Electroneum
epee::misc_utils::rolling_median_t< Item > Struct Template Reference

#include <rolling_median.h>

Public Member Functions

 rolling_median_t (size_t N)
 
 rolling_median_t (rolling_median_t &&m)
 
rolling_median_toperator= (rolling_median_t &&m)
 
 ~rolling_median_t ()
 
void clear ()
 
int size () const
 
void insert (Item v)
 
Item median () const
 

Protected Member Functions

rolling_median_toperator= (const rolling_median_t &)=delete
 
 rolling_median_t (const rolling_median_t &)=delete
 

Detailed Description

template<typename Item>
struct epee::misc_utils::rolling_median_t< Item >

Definition at line 46 of file rolling_median.h.

Constructor & Destructor Documentation

◆ rolling_median_t() [1/3]

template<typename Item>
epee::misc_utils::rolling_median_t< Item >::rolling_median_t ( const rolling_median_t< Item > &  )
protecteddelete

◆ rolling_median_t() [2/3]

template<typename Item>
epee::misc_utils::rolling_median_t< Item >::rolling_median_t ( size_t  N)
inline

Definition at line 131 of file rolling_median.h.

131  : N(N)
132  {
133  int size = N * (sizeof(Item) + sizeof(int) * 2);
134  data = (Item*)malloc(size);
135  pos = (int*) (data + N);
136  heap = pos + N + (N / 2); //points to middle of storage.
137  clear();
138  }

◆ rolling_median_t() [3/3]

template<typename Item>
epee::misc_utils::rolling_median_t< Item >::rolling_median_t ( rolling_median_t< Item > &&  m)
inline

Definition at line 140 of file rolling_median.h.

141  {
142  free(data);
143  memcpy(this, &m, sizeof(rolling_median_t));
144  m.data = NULL;
145  }
void * memcpy(void *a, const void *b, size_t c)
rolling_median_t(const rolling_median_t &)=delete

◆ ~rolling_median_t()

template<typename Item>
epee::misc_utils::rolling_median_t< Item >::~rolling_median_t ( )
inline

Definition at line 154 of file rolling_median.h.

155  {
156  free(data);
157  }

Member Function Documentation

◆ clear()

template<typename Item>
void epee::misc_utils::rolling_median_t< Item >::clear ( )
inline

Definition at line 159 of file rolling_median.h.

160  {
161  idx = 0;
162  minCt = 0;
163  maxCt = 0;
164  sz = 0;
165  int nItems = N;
166  while (nItems--) //set up initial heap fill pattern: median,max,min,max,...
167  {
168  pos[nItems] = ((nItems + 1) / 2) * ((nItems & 1) ? -1 : 1);
169  heap[pos[nItems]] = nItems;
170  }
171  }
Here is the caller graph for this function:

◆ insert()

template<typename Item>
void epee::misc_utils::rolling_median_t< Item >::insert ( Item  v)
inline

Definition at line 179 of file rolling_median.h.

180  {
181  int p = pos[idx];
182  Item old = data[idx];
183  data[idx] = v;
184  idx = (idx + 1) % N;
185  sz = std::min<int>(sz + 1, N);
186  if (p > 0) //new item is in minHeap
187  {
188  if (minCt < (N - 1) / 2)
189  {
190  ++minCt;
191  }
192  else if (v > old)
193  {
194  minSortDown(p);
195  return;
196  }
197  if (minSortUp(p) && mmCmpExch(0, -1))
198  maxSortDown(-1);
199  }
200  else if (p < 0) //new item is in maxheap
201  {
202  if (maxCt < N / 2)
203  {
204  ++maxCt;
205  }
206  else if (v < old)
207  {
208  maxSortDown(p);
209  return;
210  }
211  if (maxSortUp(p) && minCt && mmCmpExch(1, 0))
212  minSortDown(1);
213  }
214  else //new item is at median
215  {
216  if (maxCt && maxSortUp(-1))
217  maxSortDown(-1);
218  if (minCt && minSortUp(1))
219  minSortDown(1);
220  }
221  }
Here is the caller graph for this function:

◆ median()

template<typename Item>
Item epee::misc_utils::rolling_median_t< Item >::median ( ) const
inline

Definition at line 224 of file rolling_median.h.

225  {
226  Item v = data[heap[0]];
227  if (minCt < maxCt)
228  {
229  v = (v + data[heap[-1]]) / 2;
230  }
231  return v;
232  }
Here is the caller graph for this function:

◆ operator=() [1/2]

template<typename Item>
rolling_median_t& epee::misc_utils::rolling_median_t< Item >::operator= ( const rolling_median_t< Item > &  )
protecteddelete

◆ operator=() [2/2]

template<typename Item>
rolling_median_t& epee::misc_utils::rolling_median_t< Item >::operator= ( rolling_median_t< Item > &&  m)
inline

Definition at line 146 of file rolling_median.h.

147  {
148  free(data);
149  memcpy(this, &m, sizeof(rolling_median_t));
150  m.data = NULL;
151  return *this;
152  }
void * memcpy(void *a, const void *b, size_t c)
rolling_median_t(const rolling_median_t &)=delete

◆ size()

template<typename Item>
int epee::misc_utils::rolling_median_t< Item >::size ( ) const
inline

Definition at line 173 of file rolling_median.h.

174  {
175  return sz;
176  }
Here is the caller graph for this function:

The documentation for this struct was generated from the following file: