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_t &	operator= (rolling_median_t &&m)
	~rolling_median_t ()
void	clear ()
int	size () const
void	insert (Item v)
Item	median () const

Protected Member Functions
rolling_median_t &	operator= (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

Here is the call graph for this function:

Here is the caller graph for this function:

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.

                            : N(N)
  {
    int size = N * (sizeof(Item) + sizeof(int) * 2);
    data = (Item*)malloc(size);
    pos = (int*) (data + N);
    heap = pos + N + (N / 2); //points to middle of storage.
    clear();
  }

Here is the call graph for this function:

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.

  {
    free(data);
    memcpy(this, &m, sizeof(rolling_median_t));
    m.data = NULL;
  }

Here is the call graph for this function:

~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.

  {
    free(data);
  }

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.

  {
    idx = 0;
    minCt = 0;
    maxCt = 0;
    sz = 0;
    int nItems = N;
    while (nItems--)  //set up initial heap fill pattern: median,max,min,max,...
    {
      pos[nItems] = ((nItems + 1) / 2) * ((nItems & 1) ? -1 : 1);
      heap[pos[nItems]] = nItems;
    }
  }

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.

  {
    int p = pos[idx];
    Item old = data[idx];
    data[idx] = v;
    idx = (idx + 1) % N;
    sz = std::min<int>(sz + 1, N);
    if (p > 0)         //new item is in minHeap
    {
      if (minCt < (N - 1) / 2)
      {
        ++minCt;
      }
      else if (v > old)
      {
        minSortDown(p);
        return;
      }
      if (minSortUp(p) && mmCmpExch(0, -1))
        maxSortDown(-1);
    }
    else if (p < 0)   //new item is in maxheap
    {
      if (maxCt < N / 2)
      {
        ++maxCt;
      }
      else if (v < old)
      {
        maxSortDown(p);
        return;
      }
      if (maxSortUp(p) && minCt && mmCmpExch(1, 0))
        minSortDown(1);
    }
    else //new item is at median
    {
      if (maxCt && maxSortUp(-1))
        maxSortDown(-1);
      if (minCt && minSortUp(1))
        minSortDown(1);
    }
  }

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.

  {
    Item v = data[heap[0]];
    if (minCt < maxCt)
    {
      v = (v + data[heap[-1]]) / 2;
    }
    return v;
  }

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

Here is the call graph for this function:

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.

  {
    free(data);
    memcpy(this, &m, sizeof(rolling_median_t));
    m.data = NULL;
    return *this;
  }

Here is the call graph for this function:

size()

template<typename Item>

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

inline

Definition at line 173 of file rolling_median.h.

  {
    return sz;
  }

Here is the caller graph for this function:

---

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

• /home/abuild/rpmbuild/BUILD/electroneum-5.1.3.1-build/electroneum-5.1.3.1/contrib/epee/include/rolling_median.h