Insert Into A Cyclic Sorted List
August 16, 2011
This exercise is harder than it looks. There are four possibilities:
- The cyclic list is null. Create a new cyclic list containing the new element.
- There are two adjacent items in the cyclic list such that prev ≤ x ≤ next, where x is the item being inserted. Insert the new element between them.
- The new element is either less than all the elements currently in the cyclic list, or greater than all the elements currently in the cyclic list. Insert the new element before the smallest item currently in the cyclic list.
- All the elements in the cyclic list are identical; a singleton cyclic list is a special case. Insert the new element anywhere in the cyclic list.
We begin with a function that creates cycles by linking the last cdr of the list back to the head of the list; we provide last-pair even though many Scheme systems provide it natively, because it is not part of the standard:
(define (last-pair xs)
(if (null? (cdr xs)) xs
(last-pair (cdr xs))))
(define (cycle . xs)
(set-cdr! (last-pair xs) xs) xs)
For simplicity, we assume that all the elements are integers:
(define (ins-cycle xs x)
(if (null? xs) (cycle x) ; possibility 1
(let loop ((prev xs) (next (cdr xs)))
(cond ((<= (car prev) x (car next)) ; possibility 2
(set-cdr! prev (cons x next)) prev)
((and (<= (car next) (car prev)) ; possibility 3
(or (<= x (car next)) (<= (car prev) x)))
(set-cdr! prev (cons x next)) prev)
((eqv? next xs) ; possibility 4
(set-cdr! prev (cons x next)) prev)
(else (loop next (cdr next)))))))
The test that identifies each of the possibilities is marked; if none of the possibilities are identifed, the else loops to the next item in the cyclic list. If xs is null, a newly-created cycle is formed; otherwise, the current cycle is modified to insert the new element, using the same code (set-cdr! prev) (cons x next)) prev in each cond clause. The test for possibility 4 uses eqv?, which tests pointer equivalence (two pointers that both point to the same object).
We give a variety of examples to show all the possibilities:
> (ins-cycle '() 1)
#0=(1 . #0#)
> (ins-cycle (cycle 1) 1)
#0=(1 1 . #0#)
> (ins-cycle (cycle 1) 2)
#0=(1 2 . #0#)
> (ins-cycle (cycle 2) 1)
#0=(2 1 . #0#)
> (ins-cycle (cycle 1 3) 2)
#0=(1 2 3 . #0#)
> (ins-cycle (cycle 1 1) 1)
#0=(1 1 1 . #0#)
> (ins-cycle (cycle 1 1) 2)
#0=(1 2 1 . #0#)
> (ins-cycle (cycle 2 2) 1)
#0=(2 1 2 . #0#)
> (ins-cycle (cycle 1 2 3 5) 4)
#0=(3 4 5 1 2 . #0#)
You can run the program at http://programmingpraxis.codepad.org/JRWWLoi1.
Here’s my clojure solution. I’ve got more detail at my blog
;;cyclic list insertion (def start-node (atom [1 (fn [] start-node)])) (defn insert-after [node val] (let [new-node (atom [val (last @node)])] (swap! node (fn [n] [(first n) (fn [] new-node)])))) (defn find-insert-spot [node val] (loop [cnode node ctr 0] (let [next-node ((last @cnode)) cval (first @cnode) nval (first @next-node)] (if (= next-node node) cnode (if (or (<= cval val nval) (and (> cval nval) (or (>= val cval) (<= val nval)))) cnode (recur next-node (inc ctr))))))) (defn insert-val [node val] (insert-after (find-insert-spot node val) val)) (defn get-nth-after [start cnt] (loop [cnode start i cnt] (if (= i 0) cnode (recur ((last @cnode)) (dec i))))) (defn ring-vals [start] (loop [cnode start acc []] (let [next-node ((last @cnode)) cval (first @cnode)] (if (= next-node start) (conj acc cval) (recur next-node (conj acc cval))))))In Lisp, the nodes are predefined (they’re called CONS cells).
We can use the standard operators PUSH and POP to insert an element in a circular list and advance into the circular list.
;; Common Lisp: (setf *print-circle* t) (defun make-circular (list) (setf (rest (last list)) list)) (defun insert-in-order-in-circular-list (list element &key (key 'identity) (lessp '<)) (cond ((endp list) ; empty list (make-circular (list element))) ((eql list (rest list)) ; a single element (setf (rest list) (list element) (rest (rest list)) list) (rest list)) (t (flet ((lt (a b) (funcall lessp (funcall key a) (funcall key b)))) (loop :for s<f = (lt (second list) (first list)) :for k<f = (lt element (first list)) :for s<k = (lt (second list) element) :do (cond ((or (and (not k<f) (not s<k)) ; f<=k<=s ; new in the middle (and s<f (not s<k)) ; k<=s<f ; new smallest (and s<f (not k<f))) ; s<f<=k ; new biggest (push element (rest list)) (loop-finish)) (t (pop list))) :finally (return (rest list))))))) ;;; Examples: (defun insert-elements (elements &key (key 'identity) (lessp '<)) (let ((circular-list '())) (dolist (element elements circular-list) (setf circular-list (insert-in-order-in-circular-list circular-list element :key key :lessp lessp))))) (list (insert-elements '(10 20 30)) (insert-elements '(10 20 30 5)) (insert-elements '(10 20 30 15)) (insert-elements '(10 20 30 25)) (insert-elements '(10 20 30 35)) (insert-elements '(10 20 30 10)) (insert-elements '(10 20 30 20)) (insert-elements '(10 20 30 30))) ;; --> (#1=(30 10 20 . #1#) ;; #2=(5 10 20 30 . #2#) ;; #3=(15 20 30 10 . #3#) ;; #4=(25 30 10 20 . #4#) ;; #5=(35 10 20 30 . #5#) ;; #6=(10 10 20 30 . #6#) ;; #7=(20 20 30 10 . #7#) ;; #8=(30 10 20 30 . #8#)) (defstruct color red green blue) (defun color-black (color) (min (- 1 (color-red color)) (- 1 (color-green color)) (- 1 (color-blue color)))) (insert-elements (list (make-color :red 0.5 :green 0.7 :blue 0.2) (make-color :red 0.6 :green 0.2 :blue 0.3) (make-color :red 1.0 :green 1.0 :blue 1.0) (make-color :red 0.0 :green 0.0 :blue 0.0)) :key (function color-black) :lessp (function >)) ;; --> #1=(#S(COLOR :RED 0.0 :GREEN 0.0 :BLUE 0.0) ;; #S(COLOR :RED 0.6 :GREEN 0.2 :BLUE 0.3) ;; #S(COLOR :RED 0.5 :GREEN 0.7 :BLUE 0.2) ;; #S(COLOR :RED 1.0 :GREEN 1.0 :BLUE 1.0) . #1#)Here are my solutions in both Racket and C: https://github.com/adolfopa/programmingpraxis/tree/master/2011/20110816. The racket one is virtually the same you provide here, but using mutable conses instead of regular ones.
My java solution (class Elem has only the fields value and next):
public static void addToList(Elem start, int x) {
Elem i, newElem;
for(i=start;;i=i.next){
if(
(xi.value) ||
(x<i.next.value && i.next.valuei.value && i.value>i.next.value)
){
newElem=new Elem();
newElem.value=x;
newElem.next=i.next;
i.next=newElem;
return;
}
}
}
private static void addToList(Elem start, int x) { Elem i, newElem; for(i=start;;i=i.next){ if( (x<i.next.value && x>i.value) || (x<i.next.value && i.next.value<i.value) || (x>i.value && i.value>i.next.value) ){ newElem=new Elem(); newElem.value=x; newElem.next=i.next; i.next=newElem; return; } } }Here is my solution in C#:
///
/// This method adds an int element to a cyclic sorted list of int elements.
///
/// Integer element to be inserted
/// Pointer to a node in the cyclic sorted list
///
/// List of all elements in the list starting from nodePtr.
/// The return value is really a test hook.
///
public List AddElementAndGetFullListOfElements(int element, Node nodePtr)
{
Node newNode = new Node(element);
// if list has no node, make newNode the first node and return
if (null == nodePtr)
{
_listPtr = newNode;
newNode.NextPtr = newNode;
return GetListOfElements(nodePtr);
}
// if list has only one node, insert newNode as the next element
if (nodePtr.NextPtr.Equals(nodePtr))
{
InsertNodeAfterCurrentNode(newNode, nodePtr);
return GetListOfElements(nodePtr);
}
Node currentNode = nodePtr;
Node nextNode = nodePtr.NextPtr;
do
{
// if currentNode <= newNode <= nextNode : Insert the number
// ahead of the currentNode
if (currentNode.Element <= newNode.Element &&
newNode.Element <= nextNode.Element)
{
InsertNodeAfterCurrentNode(newNode, currentNode);
return GetListOfElements(nodePtr);
}
// if currentNode = nextNode.
// currentNode points to list’s end.
// Insert the number ahead of the currentNode.
if (currentNode.Element >= nextNode.Element &&
newNode.Element >= currentNode.Element)
{
InsertNodeAfterCurrentNode(newNode, currentNode);
return GetListOfElements(nodePtr);
}
// currentNode >= nextNode. newNode = nextNode.Element &&
newNode.Element <= nextNode.Element)
{
InsertNodeAfterCurrentNode(newNode, currentNode);
return GetListOfElements(nodePtr);
}
currentNode = nextNode;
nextNode = currentNode.NextPtr;
} while (!currentNode.Equals(nodePtr));
throw new Exception("Error : Unable to find a place to insert the new element in the list.");
}
private void InsertNodeAfterCurrentNode(Node newNode, Node currentNode)
{
Node nextNode = currentNode.NextPtr;
newNode.NextPtr = nextNode;
currentNode.NextPtr = newNode;
return;
}
******************* TEST CODE ****************************************************************************
private static List givenList = new List() { 2, 3, 4, 5, 7 };
///
/// Insert minimum element to the list
///
[TestMethod()]
public void AddMinimumElement()
{
CyclicSortedList target = new CyclicSortedList(givenList);
int elementToInsert = 1;
Node nodePtr = target.GetXthNode(0);
List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
List expectedList = new List(givenList);
expectedList.Add(elementToInsert);
if (!CheckArrayEquality(expectedList, actualList))
{
Assert.Fail(“Error : Method returned an unexpected list.”);
}
}
///
/// Insert maximum element to the list
///
[TestMethod]
public void AddMaximumElement()
{
CyclicSortedList target = new CyclicSortedList(givenList);
int elementToInsert = 10;
Node nodePtr = target.GetXthNode(0);
List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
List expectedList = new List(givenList);
expectedList.Add(elementToInsert);
if (!CheckArrayEquality(expectedList, actualList))
{
Assert.Fail(“Error : Method returned an unexpected list.”);
}
}
///
/// Insert greater element to the list. Greater element is bigger than the list pointer
/// but smaller than maximum number in the list.
///
[TestMethod]
public void AddGreaterElement()
{
CyclicSortedList target = new CyclicSortedList(givenList);
int elementToInsert = 6;
Node nodePtr = target.GetXthNode(1);
List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
List expectedList = new List() { 3, 4, 5, 6, 7, 2 };
if (!CheckArrayEquality(expectedList, actualList))
{
Assert.Fail(“Error : Method returned an unexpected list.”);
}
}
///
/// Insert smaller element to the list. Smaller element is smaller than the list pointer
/// but greater than the smallest number in the list.
///
[TestMethod]
public void AddSmallerElement()
{
CyclicSortedList target = new CyclicSortedList(givenList);
int elementToInsert = 6;
Node nodePtr = target.GetXthNode(4);
List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
List expectedList = new List() { 7, 2, 3, 4, 5, 6 };
if (!CheckArrayEquality(expectedList, actualList))
{
Assert.Fail(“Error : Method returned an unexpected list.”);
}
}
///
/// Insert identical element to the list where all elements are identical.
///
[TestMethod]
public void AddIdenticalElement()
{
CyclicSortedList target = new CyclicSortedList(new List() { 1, 1, 1, 1, 1 } );
int elementToInsert = 1;
Node nodePtr = target.GetXthNode(0);
List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
List expectedList = new List() { 1, 1, 1, 1, 1, 1 };
if (!CheckArrayEquality(expectedList, actualList))
{
Assert.Fail(“Error : Method returned an unexpected list.”);
}
}
Complete Visual Studio Project is at my website.
My website is here: http://tech-nuggets.blogspot.com/2011/08/insert-into-cyclic-sorted-list.html