source: trunk/Jgraph/prio_list.c @ 418

Last change on this file since 418 was 418, checked in by Nicholas Riley, 13 years ago

Jgraph 8.3 from http://www.cs.utk.edu/~plank/plank/jgraph/jgraph.tar.gz

File size: 1.8 KB
RevLine 
[418]1/*
2 * $Source: /tmp_mnt/n/fs/grad1/jsp/src/jgraph/RCS/prio_list.c,v $
3 * $Revision: 8.3 $
4 * $Date: 92/11/30 11:42:32 $
5 * $Author: jsp $
6 */
7
8#include "list.h"
9#include "prio_list.h"
10#include <stdio.h>
11
12typedef int Boolean;
13
14/* A prioirity list is any list with the first three fields being flink,
15 * blink and prio.  Use the routines of list.c to do everything except
16 * insertion */
17 
18typedef struct prio_list {
19  struct prio_list *flink;
20  struct prio_list *blink;
21  int prio;
22} *Prio_list;
23
24/* Prio_insert inserts nodes into their proper places in priority lists.  It first
25 * checks for inserting into the head or tail, and then proceeds sequentially.
26 * Thus, it is worst case linear, but for most cases constant time (right). */
27
28prio_insert(node, list, desc)
29Prio_list node;
30Prio_list list;
31Boolean desc;
32{
33  Prio_list p;
34
35  /* Check nil and head of list */
36  if (first(list) == nil(list) || 
37      (!desc && first(list)->prio >= node->prio) ||
38      (desc  && first(list)->prio <= node->prio) ) {
39    node->blink = list;
40    node->flink = list->flink;
41    list->flink->blink = node;
42    list->flink = node;
43    return;
44  }
45  /* Check tail of list */
46  if ((desc  && last(list)->prio >= node->prio) ||
47      (!desc && last(list)->prio <= node->prio) ) {
48    node->flink = list;
49    node->blink = list->blink;
50    list->blink->flink = node;
51    list->blink = node;
52    return;
53  }
54  /* Check the rest of the list sequentially */
55  for(p = next(first(list));  ; p = next(p)) {
56    if (p == nil(list)) fprintf(stderr, "inserting into tail did not work\n");
57    if ((!desc && p->prio >= node->prio) ||
58        (desc  && p->prio <= node->prio)) {
59      node->flink = p;
60      node->blink = p->blink;
61      p->blink->flink = node;
62      p->blink = node;
63      return;
64    }
65  }
66}
67     
68
69 
Note: See TracBrowser for help on using the repository browser.