what if new task gets added every time.
On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani
<gaurav.mengh...@gmail.com>wrote:
> Instead of a heap, sort the array once. Pick the first element every
> time, and remove it from the array, or just move the 'head pointer'
> ahead.
>
> On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri <anand.shastr...@gmail.com>
> wrote:
> > /* Create a Timer Task that takes in the running time and it's associated
> > function to be called after its running time is elapsed */
> > #include <time.h>
> >
> > #define NUM 5
> > typedef void (*funcToBeCalled)(void);
> >
> > typedef struct timer TIMER;
> >
> > struct timer
> > {
> > int runningTime;
> > funcToBeCalled func;
> > };
> >
> > static TIMER timerArray[NUM];
> > static time_t reference;
> > static int count;
> >
> > int LEFT(int index)
> > {
> > if(index < NUM)
> > return (index * 2 + 1);
> > }
> > int RIGHT(int index)
> > {
> > if(index < NUM)
> > return (index * 2 + 2);
> > }
> > static void print(void)
> > {
> > printf("Timer task has been called\n");
> > }
> >
> > // Initialise the timer data structure
> > void Init()
> > {
> > int index;
> > count = NUM;
> > // Note down the reference time
> > reference = time(0);
> > printf("reference : %ld\n", reference);
> >
> > // Initialise the data structure such that associate function gets
> > // called after 3, 6, 9, 12, 15 seconds respectively.
> > for(index = 0; index < count; index++)
> > {
> > timerArray[index].runningTime = (index + 1) * 3;
> > timerArray[index].func = print;
> > }
> > }
> >
> > // This function check the min heap property and arrange
> > // the element such that at every node, root node should be
> > // less than its right and left child element.
> > Heapify(int index)
> > {
> > int left, right, minIndex;
> > TIMER temp;
> > left = LEFT(index);
> > right = RIGHT(index);
> > if(left < (count) &&
> > (timerArray[left].runningTime < timerArray[index].runningTime))
> > {
> > minIndex = left;
> > }
> > else
> > {
> > minIndex = index;
> > }
> > if(right < (count) &&
> > (timerArray[right].runningTime < timerArray[minIndex].runningTime))
> > {
> > minIndex = right;
> > }
> > if(minIndex != index)
> > {
> > temp.runningTime = timerArray[index].runningTime;
> > temp.func = timerArray[index].func;
> >
> > timerArray[index].runningTime = timerArray[minIndex].runningTime;
> > timerArray[index].func = timerArray[minIndex].func;
> >
> > timerArray[minIndex].runningTime = temp.runningTime;
> > timerArray[minIndex].func = temp.func;
> >
> > Heapify(minIndex);
> > }
> > }
> >
> > // This function builds the MIN heap data structure
> > void BuildHeap()
> > {
> > int len, i;
> > len = sizeof(timerArray)/sizeof(timerArray[0]);
> > i = (len - 1)/2;
> > while(i >= 0)
> > {
> > Heapify(i);
> > i--;
> > }
> > Heapify(0);
> > }
> >
> >
> > // This function extract the top element of the heap
> > // Min heap has the min element at the top always.
> > int HeapExtract()
> > {
> > TIMER temp;
> > // Swap the 0 the element with last element of the array
> > temp.runningTime = timerArray[0].runningTime;
> > temp.func = timerArray[0].func;
> >
> > timerArray[0].runningTime = timerArray[count-1].runningTime;
> > timerArray[0].func = timerArray[count-1].func;
> >
> > timerArray[count-1].runningTime = temp.runningTime;
> > timerArray[count-1].func = temp.func;
> > count--;
> > // Check the heap property heapify if it got violated
> > Heapify(0);
> > // return the minimum element of the heap
> > return (count);
> > }
> > void scheduler()
> > {
> > time_t now;
> > int diff_time, minIndex;
> > while(count >= 0)
> > {
> > now = time(0);
> > printf("Current Time: %ld\n", time(0));
> > diff_time = now- reference;
> > printf("diff_time : %ld\n", diff_time);
> > if(diff_time >= timerArray[0].runningTime)
> > {
> > minIndex = HeapExtract();
> > timerArray[minIndex].func();
> > }
> > else
> > {
> > sleep(timerArray[0].runningTime - diff_time);
> > }
> > }
> > }
> > main()
> > {
> > int index, minIndex;
> > TIMER temp;
> >
> > // Initialise the data structure
> > Init();
> >
> > // Build MIn heap data structure
> > BuildHeap(timerArray);
> >
> > // Run the scheduler
> > scheduler();
> >
> > return;
> > }
> > The ouput of above code is
> >
> > Timer Task is about to run
> > reference : 1312510772
> >
> > Current Time: 1312510775
> > diff_time : 3
> > Timer task has been called
> >
> > Current Time: 1312510778
> > diff_time : 6
> > Timer task has been called
> > Current Time: 1312510781
> > diff_time : 9
> > Timer task has been called
> >
> > Current Time: 1312510784
> > diff_time : 12
> > Timer task has been called
> >
> > Current Time: 1312510787
> > diff_time : 15
> > Timer task has been called
> >
> > Please share your comments
> >
> > On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri <
> anand.shastr...@gmail.com>
> > wrote:
> >>
> >> Obviously you need to run the task that a closet running time.
> >>
> >> For Example
> >>
> >> Task 1 : running time = 2 secs
> >>
> >> Task 2: running time = 4 secs
> >>
> >> This means I want to run the task 1 after 2 secs and task 2 after 4
> >> second.
> >>
> >> How I hope the question is clear to you know
> >>
> >> On Thu, Aug 4, 2011 at 11:37 AM, mohit verma <mohit89m...@gmail.com>
> >> wrote:
> >>>
> >>> there is nothing like "search min or max time and then call function"
> >>> given . It can be the case: "call the functions in order of nodes or
> times
> >>> saved in objects". M i wrong?
> >>>
> >>> On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri
> >>> <anand.shastr...@gmail.com> wrote:
> >>>>
> >>>> You mean to say linked to maintain all time task with its
> corresponding
> >>>> running time and associate function. In that case how will find the
> task
> >>>> which has the closed running time.
> >>>>
> >>>> If you use min heap it would be easy to find the task that has closest
> >>>> runing time in O(1) complexity.
> >>>>
> >>>> On Thu, Aug 4, 2011 at 10:57 AM, mohit verma <mohit89m...@gmail.com>
> >>>> wrote:
> >>>>>
> >>>>> why are u maintaining heap? can't we use link list here?
> >>>>>
> >>>>> On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri
> >>>>> <anand.shastr...@gmail.com> wrote:
> >>>>>>
> >>>>>> You have given a structure which has two member, One which stores
> the
> >>>>>> time and other stores the function pointer Your function has to call
> >>>>>> the
> >>>>>> function stored in the fuction poitner after the time given in the
> >>>>>> structure elapses.
> >>>>>> Design that function?
> >>>>>>
> >>>>>> Approach: To design this function I would use a min Heap data
> >>>>>> structure. Each node of a heap has
> >>>>>> two parameters one is the running time and other one
> >>>>>> is the function pointer.
> >>>>>>
> >>>>>> // Initialise a function pointer
> >>>>>> typedef void (*functionToBeCalled)(int arg1, int arg2);
> >>>>>>
> >>>>>> // Timer structure
> >>>>>> typedef struct timer
> >>>>>> {
> >>>>>> float runingTime; // in terms of seconds
> >>>>>> functionToBeCalled funcToBeCall; // function pointer
> >>>>>> }TIMER;
> >>>>>>
> >>>>>> void initTimer()
> >>>>>> {
> >>>>>> Initialise few nodes with running time and its corresponding
> >>>>>> function
> >>>>>> Initialise a MIN heap data structure
> >>>>>> }
> >>>>>>
> >>>>>> void addTimer(uint32 runingTime, functionToBeCalled func)
> >>>>>> {
> >>>>>> TIMER *temp;
> >>>>>> temp = (TIMER *)malloc(sizeof(TIMER));
> >>>>>> temp->runingTime = runningTime
> >>>>>> temp->funcToBeCall = func;
> >>>>>> HeapAdd(temp);
> >>>>>> Heapify();
> >>>>>> }
> >>>>>>
> >>>>>> void scheduler()
> >>>>>> {
> >>>>>> uint32 currentTime = ObtainCurrentTime();
> >>>>>> // Obtain the runing time of top most element of the min
> >>>>>> Heap
> >>>>>> uint32 runingTime = PeakHeap();
> >>>>>> // if the runningTime is equal to current time then
> >>>>>> extract the top most
> >>>>>> // element of the heap and execute the function
> associate
> >>>>>> with it
> >>>>>> // Heapify the MIN heap data structure
> >>>>>> // Obtain the runing time of top most element of the min
> >>>>>> heap
> >>>>>> // scheduler sleep for that much amount of time.
> >>>>>> if(runingTime == currentTime)
> >>>>>> {
> >>>>>> TIMER * node = ExtractMinHeap();
> >>>>>> CreateThread(node->func, Thread);
> >>>>>> Heapify();
> >>>>>> runingTime = PeakHeap();
> >>>>>> sleep(runningTime);
> >>>>>> }
> >>>>>> else
> >>>>>> {
> >>>>>> // scheduler updates its sleep time
> >>>>>> // if runing time is not equal to current time
> >>>>>> sleep(runningTime);
> >>>>>> }
> >>>>>>
> >>>>>> }
> >>>>>>
> >>>>>> Let me know your comments
> >>>>>>
> >>>>>> --
> >>>>>> You received this message because you are subscribed to the Google
> >>>>>> Groups "Algorithm Geeks" group.
> >>>>>> To post to this group, send email to algogeeks@googlegroups.com.
> >>>>>> To unsubscribe from this group, send email to
> >>>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>>> For more options, visit this group at
> >>>>>> http://groups.google.com/group/algogeeks?hl=en.
> >>>>>
> >>>>>
> >>>>>
> >>>>> --
> >>>>> ........................
> >>>>> MOHIT VERMA
> >>>>>
> >>>>> --
> >>>>> You received this message because you are subscribed to the Google
> >>>>> Groups "Algorithm Geeks" group.
> >>>>> To post to this group, send email to algogeeks@googlegroups.com.
> >>>>> To unsubscribe from this group, send email to
> >>>>> algogeeks+unsubscr...@googlegroups.com.
> >>>>> For more options, visit this group at
> >>>>> http://groups.google.com/group/algogeeks?hl=en.
> >>>>
> >>>> --
> >>>> You received this message because you are subscribed to the Google
> >>>> Groups "Algorithm Geeks" group.
> >>>> To post to this group, send email to algogeeks@googlegroups.com.
> >>>> To unsubscribe from this group, send email to
> >>>> algogeeks+unsubscr...@googlegroups.com.
> >>>> For more options, visit this group at
> >>>> http://groups.google.com/group/algogeeks?hl=en.
> >>>
> >>>
> >>>
> >>> --
> >>> ........................
> >>> MOHIT VERMA
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
>
>
>
> --
> Gaurav Menghani
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
