August 16, 2011 9:00 AM
This exercise is harder than it looks. There are four possibilities:
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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))))))By Kevin Hostelley on August 16, 2011 at 8:41 PM
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#)By Pascal Bourguignon on August 17, 2011 at 5:53 AM
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.
By Adolfo on August 17, 2011 at 8:30 PM
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;
}
}
}
By Simone on August 18, 2011 at 1:56 PM
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; } } }By Simone on August 18, 2011 at 2:00 PM
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.
By Ravi (@RavisACS) on August 19, 2011 at 2:02 AM
My website is here: http://tech-nuggets.blogspot.com/2011/08/insert-into-cyclic-sorted-list.html
By Ravi (@RavisACS) on August 19, 2011 at 2:04 AM