GNU Astronomy Utilities Doubly linked ordered list of size_t

An ordered list of indices is required in many contexts, one example was discussed at the beginning of Ordered list of size_t. But the list that was introduced there only has one point of entry: you can always only parse the list from smallest to largest. In this section, the doubly-linked gal_list_dosizet_t node is defined which will allow us to parse the values in ascending or descending order.

Type (C struct): gal_list_dosizet_t

Doubly-linked, ordered size_t list node structure. Each node in this Doubly-linked list contains a size_t value and a floating point value. The floating point value is used as a reference to add new nodes in a sorted manner. In the functions here, this linked list can be pointed to by two pointers (largest and smallest) with the following format:

            largest pointer
   NULL <-- (v0,s0) <--> (v1,s1) <--> ... (vn,sn) --> NULL
                           smallest pointer

At any moment, the two pointers will point to the nodes containing the “largest” and “smallest” values and the rest of the nodes will be sorted. This is useful when an unknown number of nodes are being added continuously and during the operations it is important to have the nodes in a sorted format.

typedef struct gal_list_dosizet_t
  size_t v;                       /* The actual value. */
  float s;                        /* The parameter to sort by. */
  struct gal_list_dosizet_t *prev;
  struct gal_list_dosizet_t *next;
} gal_list_dosizet_t;
gal_list_dosizet_add (gal_list_dosizet_t **largest, gal_list_dosizet_t **smallest, size_t value, float tosort)

Allocate space for a new node in list, and store value and tosort into it. If the list is empty, both largest and smallest must be NULL.

gal_list_dosizet_pop_smallest (gal_list_dosizet_t **largest, gal_list_dosizet_t **smallest, float tosort)

Pop the value with the smallest reference from the doubly linked list and store the reference into the space pointed to by tosort. Note that even though only the smallest pointer will be popped, when there was only one node in the list, the largest pointer also has to change, so we need both.

gal_list_dosizet_print (gal_list_dosizet_t *largest, gal_list_dosizet_t *smallest)

Print the largest and smallest values sequentially until the list is parsed.

gal_list_dosizet_to_sizet (gal_list_dosizet_t *in, gal_list_sizet_t **out)

Convert the doubly linked, ordered size_t list into a singly-linked list of size_t.

gal_list_dosizet_free (gal_list_dosizet_t *largest)

Free the doubly linked, ordered sizet_t list.