Is this some kind of pattern?
 

Hi,

I have a flag to control over the time. I need to decide if the flag
has been mostly true in the last second.
I am sure this kind of problems have been solved before. Could anyone
give me a hint on this?

Thanks

Re: Is this some kind of pattern?
 

On Apr 21, 11:21 am, Giff <Giffn...@gmail.com> wrote:
> Hi,
>
> I have a flag to control over the time. I need to decide if the flag
> has been mostly true in the last second.
> I am sure this kind of problems have been solved before. Could anyone
> give me a hint on this?
>
> Thanks

First you need to define what is "mostly true". You would probably say
that "mostly true" means the flag has been true for at least 50% of
the last second.

You would then have to poll or sample the flag often (e.g. 20 times
per second, or some other suitable rate). Each time you find the flag
true, increment a counter. Each time you find it false, do nothing.
Then, for every 20 samples:

- check if the counter is greater than or less than 10 (i.e. 50% of
the samples acquired in the last second)
- report the "mostly true" status of the flag
- reset the counter

If you are doing this under Win32, I have plenty of experience with
similar things and would be happy to send you some sample code if
interested. I usually implement stuff like this in a separate thread,
and have the thread post/send a message to another window or thread,
to report the status of the process.

Regards,
Markus.

Re: Is this some kind of pattern?
 

Giff wrote:
> Hi,
>
> I have a flag to control over the time. I need to decide if the flag
> has been mostly true in the last second.
> I am sure this kind of problems have been solved before. Could anyone
> give me a hint on this?

Do you have control of how the flag is set or reset ?

Re: Is this some kind of pattern?
 

Gianni Mariani ha scritto:

> Do you have control of how the flag is set or reset ?

Yes, I do it.

Re: Is this some kind of pattern?
 

Markus Svilans ha scritto:

> First you need to define what is "mostly true". You would probably say
> that "mostly true" means the flag has been true for at least 50% of
> the last second.
>

Precisely what I was assuming.


> You would then have to poll or sample the flag often (e.g. 20 times
> per second, or some other suitable rate).

The thing is that I sample it every frame (it is computer vision that I
am doing, and this method is called for each frame grabbed from the camera).

Each time you find the flag
> true, increment a counter. Each time you find it false, do nothing.


What I did is to increment a int counter and then do
counter%numOfFramesToCheck, where numOfFramesToCheck should be the
frames processed in one second (now it is just set to 30).
Then I check the value and if it is > 15 I declare the flag "mostly true".

It works quite fine.


> If you are doing this under Win32, I have plenty of experience with
> similar things and would be happy to send you some sample code if
> interested.


That would definitely not harm, my email is correct, just remove .invalid
Thanks a lot for your reply.

Cheers

Re: Is this some kind of pattern?
 

Giff wrote:
> Gianni Mariani ha scritto:
>
>> Do you have control of how the flag is set or reset ?
>
> Yes, I do it.

You can use a data structure that records the last N states of the value
and then count the states when you want to know the answer. If you only
need 32 or less of the last samples, (or 64 if you have a 64 bit
machine), then you can use simple bit manipulation.

This below is a basic flag class that records history. This brute
forces the count of the number of set bits. You could keep a separate
count of the number of set bits and avoid the computation, however, the
computation only takes 20 cycles and on a modern superscalar CPU,
probably more like 12, so it depends on how often you need to count bits
as to which one is faster. I would go with the smaller class and bet
that you don't need this count very often but that's a design decision
for you.

---------------------------------------------------------------------

// Fast routine for counting number of set bits
// ... lifted from
//http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

template <typename T>
int CountBits( T v )
{
enum { bits_in_char = 8 };

v = v - ((v >> 1) & (T)~(T)0/3); // temp
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp
return (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * bits_in_char;
}


// ======== FlagWithHistory ===========================================
/**
* Special flag that stores the flag state for the last 32 (for 32 bit
* word systems).
*
*/

class FlagWithHistory
{
// change to unsigned long long for 64 bits on platform that support
// long long - and if you need 64 history values.
typedef unsigned int t_FlagValue;

t_FlagValue m_value;

public:

FlagWithHistory( bool i_state = false )
: m_value( i_state ? 1 : 0 )
{
}

bool Set( bool i_state )
{
m_value <<= 1;
m_value |= i_state ? 1 : 0;
return i_state;
}

bool Get()
{
return m_value & 1;
}

bool operator=( bool i_state )
{
return Set( i_state );
}

operator bool()
{
return Get();
}

static const unsigned bits_in_word = 8 * sizeof( t_FlagValue );

// GetHistoryCount gets the number of times the flag was
// set over the last "i_event_history" modifications of the
// flag.

unsigned GetHistoryCount( unsigned i_event_history = bits_in_word )
{
if ( i_event_history <= bits_in_word )
{
t_FlagValue l_mask = ~ t_FlagValue();

if ( i_event_history < bits_in_word )
{
l_mask = ( 1 << ( i_event_history ) ) -1;
}

return CountBits( m_value & l_mask );
}

throw "out of range";
}

};


#include <iostream>

int main()
{

FlagWithHistory flag( true );

std::cout << "Flag state is " << flag << "\n";

std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";

flag = true;

std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";

flag = false;

std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";

flag = true;

std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";

flag = false;

std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";
std::cout << "Flag state is " << flag << "\n";

std::cout << "Flag count(3) is " << flag.GetHistoryCount(3) << "\n";

}

Re: Is this some kind of pattern?
 

Gianni Mariani wrote:

>
> This below is a basic flag class that records history.

Thanks, your example looks useful, I will study it.