Racket and C solutions to http://programmingpraxis.com/2011/08/16/insert-into-a-cyclic-sorted-list/

cyclic-sorted-list.c

/*
 * C solution to http://programmingpraxis.com/2011/08/16/insert-into-a-cyclic-sorted-list/
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

struct node {
     int value;
     struct node *next;
     int freed;
};

struct node *
node_create(int value, struct node *next)
{
     struct node *node = malloc(sizeof(struct node));

     node->value = value;
     node->next = next;
     node->freed = 0;

     return node;
}

int
str_to_int(char *s)
{
     assert(s != NULL);

     return strtol(s, NULL, 10);
}

struct node *
node_last(struct node *node)
{
     assert(node != NULL);

     while (node->next)
	  node = node->next;

     return node;
}

struct node *
node_cycle(struct node *node)
{
     assert(node != NULL);

     return node_last(node)->next = node;
}

struct node *
node_insert(struct node *node, int value)
{
     struct node *prev = NULL;
     struct node *curr = NULL;
     struct node *inserted = NULL;

     assert(node != NULL);

     prev = node;
     curr = node->next;

     while (inserted == NULL) {
	  if (prev->value <= value && value <= curr->value)
	       inserted = prev->next = node_create(value, curr);
	  else if (prev->value >= curr->value && value <= curr->value)
	       inserted = prev->next = node_create(value, curr);
	  else if (prev->value <= value && curr->value <= prev->value)
	       inserted = prev->next = node_create(value, curr);
	  else {
	       prev = curr;
	       curr = curr->next;
	  }
     }

     return inserted;
}

struct node *
node_print(struct node *node, FILE *out, int limit)
{
     struct node *p = NULL;

     assert(node != NULL);
     assert(out != NULL);
     assert(limit >= 0);

     for (p = node; p && limit--; p = p->next)
	  fprintf(out, "%d -> ", p->value);

     fprintf(out, limit == -1 ? "...\n" : "nil\n");

     return node;
}

void
node_free(struct node *node)
{
     struct node *p = NULL;
     struct node *q = NULL;

     assert(node != NULL);

     for (p = node; p && !p->freed; p = q) {
	  q = p->next;
	  p->freed = 1;
	  free(p);
     }
}

struct node *
node_from_p(int *elts, size_t n)
{
     int i;
     struct node *head = NULL;

     assert(elts != NULL);

     for (i = n - 1; i >= 0; i--)
	  head = node_create(elts[i], head);

     return head;
}

void
test_insertion(int value, int *elts, size_t n)
{
     struct node *head = NULL;

     assert(elts != NULL);
     assert(n > 1);

     head = node_from_p(elts, n);

     assert(head != NULL);

     node_cycle(head);
     node_insert(head, value);
     node_print(head, stdout, 15);
     node_free(head);
}

#define ASIZE(a) (sizeof((a))/sizeof((a)[0]))

int
main(int argc, char **argv)
{
     unsigned int i;
     struct node* head = NULL;
     int initial_list[] = {1, 2, 4, 5};
     int values[] = {0, 3, 6};

     for (i = 0; i < ASIZE(values); i++)
	  test_insertion(values[i], initial_list, 4);

     return EXIT_SUCCESS;
}

cyclic-sorted-list.rkt

#lang racket

;;
;; Racket solution to http://programmingpraxis.com/2011/08/16/insert-into-a-cyclic-sorted-list/
;;

(require rackunit)

(define (make-cycle lst)
  (let ((first-cell (mcons #f #f)))
    (let recur ((lst lst) (cell first-cell))
      (cond ((null? lst)
             first-cell)
            (else (set-mcar! cell (car lst))
                  (set-mcdr! cell (recur (cdr lst) (mcons #f #f)))
                  cell)))))

(define (cycle-insert! cycle elt)
  (if (null? cycle)
      (make-cycle (list elt))
      (let loop ((prev cycle) (curr (mcdr cycle)))
        (cond ((or (<= (mcar prev) elt (mcar curr))
                   (<= (mcar curr) (mcar prev) elt)
                   (<= elt (mcar curr) (mcar prev)))
               (let ((cell (mcons elt curr)))
                 (set-mcdr! prev cell)
                 cell))
              (else
               (loop curr (mcdr curr)))))))

(check-equal? (cycle-insert! '() 0)
              (make-cycle '(0)))
(check-equal? (cycle-insert! (make-cycle '(1 2 4 5)) 0)
              (make-cycle '(0 1 2 4 5)))
(check-equal? (cycle-insert! (make-cycle '(1 2 4 5)) 3)
              (make-cycle '(3 4 5 1 2)))
(check-equal? (cycle-insert! (make-cycle '(1 2 4 5)) 6)
              (make-cycle '(6 1 2 4 5)))
(check-equal? (cycle-insert! (make-cycle '(1 1 1 1)) 2)
              (make-cycle '(2 1 1 1 1)))
(check-equal? (cycle-insert! (make-cycle '(2 2 2 2)) 1)
              (make-cycle '(1 2 2 2 2)))
(check-equal? (cycle-insert! (make-cycle '(1 1 1)) 1)
              (make-cycle '(1 1 1 1 1)))