Function Logic

Hi

I was hoping someone can help me with the logic of a searching function.

I will have an array filled with 1s and 0s (on and off). I will get the input to find the number of consequtive off bits. I then want to return the positions in the array in which those consequtive bits are found. I will then pass that returned array onto another function, which will in turn, turn them on. I would turn them on in this function, but due to the nature of the search I cant do it all in one function.

I was going to have two pointers which point to the begining of the array. Move one pointer until it encounters a 0. When it finds a 0, move the second pointer to the location of the first. Check if the required bits are available by moving the first pointer, if so, get the locations of those, by moving the second pointer to the first, and save the array locations, which I will return.

Is there another way in which to approach this?

Also, I dont know how I would save those locations, which I want to return.

Thanks.

I would create an array, and an array of pointers of the same size just incase all of the elements in the array are 0's. Search through the array and if there is a 0, pass that address to the corrisponding pointer in the array of pointers, if it is a 1, pass the NULL back to the corrisponding pointer. Then just pass the array of pointers to the function, run through the array of pointers and if != NULL, dereference the pointer and change it to 1. If that is not what you wanted, then let me know.

P.S. For passing the array of pointers, you will probably want to #define a constant the same size of the array. Then pass that constant to the function so it knows when to stop running through the array of pointers.

So your array and array of pointers will look like this:

Code:

#define ARRAYSIZE 20

Array of pointers:		Array:
    | NULL |                    | 1 |
    | pointer |                 | 0 |
    | NULL |                    | 1 |
    | NULL |                    | 1 |
    | pointer |                 | 0 |
    | NULL |                    | 1 |
    | NULL |                    | 1 |
    | NULL |                    | 1 |
    | NULL |                    | 1 |
    | NULL |                    | 1 |
    | pointer |                 | 0 |
    | pointer |                 | 0 |
    | pointer |                 | 0 |
    | NULL |                    | 1 |
    | pointer |                 | 0 |
    | NULL |                    | 1 |
    | NULL |                    | 1 |
    | pointer |                 | 0 |
    | pointer |                 | 0 |
    | NULL |                    | 1 |

Here is the basic 'find' algorithm. If you are using C++ you should template it for reusability:

Code:

typdef char byte;

byte *
 find( const byte data[], const byte * d_end, 
         const byte pattern[], const byte * p_end)
{
 byte * d = data, * p = pattern, * result;
 
   for(result = d; d != d_end; ++d)
 {
     if(p == p_end) return result; // found

     if(*d != *(p++)) p = pattern, result = d+1; // reset
 }

 return NULL;
}

The location of the index to be saved can be calculated by substracting the address of the first element of the array from the returned pointer, then divide that by the sizeof the datatype (in this case, a char).


To turn the bits on and off:

Code:

typedef char bool;

void change_state(const byte * loc, 
        const byte * lc_end, bool state)
{
 byte * first = loc, last = lc_end;
 while(first != last) *(first++) = state;
}

void flip(const byte * loc, 
        const byte * lc_end)
{
 byte state = (*loc == 0) ? 1 : 0;
 change_state(loc, lc_end, state);
}

I hope that helps. Good luck.

I think for this kind of applicaton, you can use a state machine.