Thread: sorting a linked list by order of time

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    9

    sorting a linked list by order of time

    hello,

    I wont bother you long, but I originally came to this site for help in programming and seem to been distracted by you games forum.
    I was wondering if you could tell me if there is an error in the following code:

    Code:
     ///////add unit task//////////////
    void Add_unit_Task (
         LPUNIT_DOING_TASK newTask    // the task to be added
         )
    {   // added by order of time
    
    ////start debug: turn off
      // if no other task
     if (g_bottom_unit_task == (LPUNIT_DOING_TASK) NULL )          
     {
      g_bottom_unit_task = newTask;
      g_top_unit_task=     newTask;
      newTask->prev = (LPUNIT_DOING_TASK) NULL ;
      newTask->next = (LPUNIT_DOING_TASK) NULL ;
      return;
     }
     else if ( (newTask->time) >= (g_bottom_unit_task->time) )  // if at end of list
     {
       g_bottom_unit_task->next=newTask;
       newTask->prev = g_bottom_unit_task ;
       newTask->next = (LPUNIT_DOING_TASK) NULL ;
       g_bottom_unit_task = newTask;
       return;
     }
     else if ( (newTask->time) < (g_top_unit_task->time) )      // if first of list 
     {
       g_top_unit_task->prev=newTask;
       newTask->prev = (LPUNIT_DOING_TASK) NULL ;
       newTask->next = g_top_unit_task ;
       g_top_unit_task = newTask;
       return;
     }
     else
     {                                                      // else in middle
       LPUNIT_DOING_TASK temp_task; LPUNIT_DOING_TASK next_task = (LPUNIT_DOING_TASK) NULL;
       for ( temp_task=g_top_unit_task; temp_task != (LPUNIT_DOING_TASK)NULL; temp_task=next_task )
       {
        next_task = temp_task->next;
        if ( (newTask->time) < (temp_task->time) )
        {
         newTask->prev      = temp_task->prev ;
         newTask->next   = temp_task ;
           newTask->prev->next = newTask;
           temp_task->prev     = newTask;
           return;
        }
       }
     }
    ////end debug: turn off
    }
    this code should place the following double linked node in order of time. It is needed so that only those nodes whose time are up are accessed.
    Code:
    typedef struct _UNIT_DOING_TASK              // struct tasks
    {
      struct _unit*    unit_doing;
      struct _unit*    link_to_another_unit;
      struct _UNIT_DOING_TASK* next;
      struct _UNIT_DOING_TASK* prev;
      int       going_to_x;
      int       going_to_y;
      long      start_at_x;
      long      start_at_y;
      short int      doing;
      DWORD       time;
      DWORD      start_time;
    }UNIT_DOING_TASK;
    //////////////////////////
    typedef UNIT_DOING_TASK* LPUNIT_DOING_TASK;
    LPUNIT_DOING_TASK g_bottom_unit_task ;
    LPUNIT_DOING_TASK g_top_unit_task ;
    the code does not do what it is suposed to (but runs) and is turned off in the program, with the bellow code used to stitch it up (replacing where the //debug turn: off begines and ends. In the above code the unites effectively overshot the hexes (the locotion they must be at at the end of the time) by a margin that seems to increase according to a) the number of nodes in the list and b) the the number that are path finding. Perhaps indicative of an influence in the games latency ie. it works with one node, with ten but not 30, 40 etc, the speed of the time also increases the overshooting.

    Code:
     //debugfile ("add task\n", 1 ); ///debug: just add to bottom
     if (g_top_unit_task == (LPUNIT_DOING_TASK) NULL )          // if no other task
     {
      g_bottom_unit_task = newTask;
      g_top_unit_task=     newTask;
      newTask->prev = (LPUNIT_DOING_TASK) NULL ;
      newTask->next = (LPUNIT_DOING_TASK) NULL ;
      return;
     }
     else  //  at top of list
     {
       g_top_unit_task->prev=newTask;
       newTask->prev = (LPUNIT_DOING_TASK) NULL ;
       newTask->next = g_top_unit_task ;
       g_top_unit_task = newTask;
       return;
     }
    this replacement code works but is slow (it must go through the hole list every time it is called which is about 20 times a second.), at the moment it is fine, but my project has ambitions of thousands of LPUNIT_DOING_TASK's in the waiting list, and I forsee this to be a problem erea.

    I have done a few linked lists so these are not my first foray into organising them, everything seems in order. Perhaps it is one of those problems that you can't see for looking and need fresh eyes.

    these codes file can be found in unit_movement.h and structures.h within the “code file” of the projects downloaded zip file. the project is housed at: ad-infinitum | Download ad-infinitum software for free at SourceForge.net

    yours ever,
    BB

    ps, please do not critasize (as they do in your Games forum) my use of outdated libraries. I use the libraries I use and I am tired of explaining why.

  2. #2
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Do you know how to build and maintain a sorted linked list? The algorithm will be the same no matter what specific field you're sorting on (AKA the sort key). In your case, it'll be some kind of "time" field.

    The general algorithm in psuedocode goes something like:

    cursor := head(list)
    while (searchKey < key(cursor.next))
    cursor := cursor.next
    // now we want to insert a node node, making cursor as its predecessor and cursor.next as its successor
    node := make_node(searchKey)
    node.next = cursor.next.next
    cursor.next = node

    Of course there's the special case of inserting into an empty list (or at the head of the list) but that is straightforward.

    Maybe you already knew all that but maybe not. Anyways, I would suggest you write a simple linked list module that demonstrates the problem without all the application-specific code surrounding it; that will avoid confusion. If you can do that, you'll know where the problem lies. Plus, you won't have to ever write a linked list ever again.
    Last edited by MacNilly; 10-04-2011 at 01:37 PM.

  3. #3
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    I looked over the linked list insertions and don't see a problem there, like you said.

    Did you set your head and tail to the empty list? I don't see that done anywhere in the code you provided and I'm not downloading your entire program.

    Also, it is really necessary to cast every NULL? I'd get rid of that and just set the pointers to NULL.
    Last edited by MacNilly; 10-04-2011 at 01:58 PM.

  4. #4
    Registered User
    Join Date
    Sep 2011
    Posts
    9
    I looked over the linked list insertions and don't see a problem there, like you said.
    aye, thank you for that, I did'nt think there was an error, but needed confirmation; when I placed the corection patch code over it and it worked i thought I was'nt seing the obvious, that the problem must be there. But I think you have hit upon the answer:
    Did you set your head and tail to the empty list?
    At first I thought "why yes, g_top_unit_task and g_bottom_unit_task", but I then realized you probably meant Did you set your head or tail to the list? And then it dawned...the code below is the first part of where the list is read and the nodes removed if they are out of time (cut as it is long and not relevant to the point). Unfortunately I deleted the old code and replaced it with a routine that goes through all the nodes...but i am pretty sure the old code here had the problem, I must have been accessing the list from the wrong end, or looking through the list the wrong way (prev/next). It all makes sence, the nodes would have overshot as they would only be accessed one one at a time, It would work with a few, even ten without noticing much of a diference as it is accessed 20 times a second, but the problem would obvious if more nodes were on the list (1 second for tweenty nodes, 2 second delay for 40 etc).

    Code:
    void Unit_Task_waiting_list()
    {
    // debugfile ("Unit_Task_waiting_list()\n", 1 );
       if ( g_top_unit_task != (LPUNIT_DOING_TASK) NULL  )
       {
    LPUNIT_DOING_TASK the_next_task=g_top_unit_task;
      dwCopy_time = timeGetTime();
       for ( the_next_task=g_top_unit_task; 
         the_next_task!=(LPUNIT_DOING_TASK) NULL; 
       the_next_task=the_next_task->next )              //debug: go through all
       {
      if ( (the_next_task->time) <= ( dwCopy_time ) )
      {
       //debugfile ("g top unit task time up\n", 1 );
       LPunit theunit = the_next_task->unit_doing ;
       if (  theunit->task->doing == MOVING )
       {
    etc...
    ect...
    I will update it tonight. In way of thanks I'll name one of the randomly generated worlds "MacNilly". Cheers.

    The general algorithm in psuedocode goes something like:
    I am self tought in C and your code was chinese to me, can you direct me to a site or publication that explains this algorithm. I have developed many bad programming habits over the years and should address these.

    it is really necessary to cast every NULL?
    No, one of my odd habits, only it is not one I want to correct as I find it very useful when debuging to see which nodes are declared as null.

    Yours ever
    BB
    Last edited by BrodieBrodie; 10-05-2011 at 05:57 AM. Reason: typo

  5. #5
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. putting linked list in order
    By mackieinva in forum C Programming
    Replies: 14
    Last Post: 09-25-2007, 01:26 AM
  2. inserting in order a linked list
    By qubit67 in forum C Programming
    Replies: 2
    Last Post: 04-23-2007, 09:17 PM
  3. Doubly linked list add in order
    By Dan17 in forum C++ Programming
    Replies: 2
    Last Post: 10-23-2006, 01:53 PM
  4. Doubly linked list add in order
    By Dan17 in forum C Programming
    Replies: 4
    Last Post: 10-23-2006, 01:36 PM
  5. re-order of linked list
    By nomes in forum C Programming
    Replies: 3
    Last Post: 10-16-2002, 09:04 AM