Thursday, August 18, 2011

Insert Into A Cyclic Sorted List

This question is asked on Programming Praxis. The code in the form of Visual Studio 2010 solution can be downloaded from here.

This is the design of my solution:

While you are looping through the list, these are the various cases (given number refers to the number to be inserted):
1. Current list element <= given number <= next list element : Insert the given number ahead of the current list element
2. Current list element <= next list element <= given number : advance the iterator
3. Current list element <= given number. current list element >= next list element. : Current list element points to list's end and given number is maximum number. Insert the number ahead of the current list element.
4. Current list element >= given number. current list element <= Next list element. iterate till the end of the list
5. Current list element >= next list element. given number <= next list element. Given number is the least number. Insert it after the current list element.
6. Current list element >= given number. Current list element >= next list element. given number > next list element. Advance iterator

Corner cases:
1. pointer to list is null. Make a self referencing node.
2. list has only one elt. Insert the given elt after the list pointer.

Tests:
1. given number > list pointer
 1a. given number belongs to end of list
 1b. given number belongs to a place before end of list

2. given number < list pointer
 2a. given number belongs to start of list
 2b. given number belongs to a place after first element but before current elt

3. All numbers are identical.

*********** SOLUTION CODE ***************************

        /// <summary>
        /// This method adds an int element to a cyclic sorted list of int elements.
        /// </summary>
        /// <param name="element"> Integer element to be inserted </param>
        /// <param name="nodePtr"> Pointer to a node in the cyclic sorted list </param>
        /// <returns>
        /// List of all elements in the list starting from nodePtr.
        /// The return value is really a test hook.
        /// </returns>
        public List<int> 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 <= newNode. 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.
                // newNode represents the least number. Insert it after the currentNode.
                if (currentNode.Element >= 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<int> givenList = new List<int>() { 2, 3, 4, 5, 7 };
       
        /// <summary>
        /// Insert minimum element to the list
        ///</summary>
        [TestMethod()]
        public void AddMinimumElement()
        {           
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 1;
            Node nodePtr = target.GetXthNode(0);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>(givenList);
            expectedList.Add(elementToInsert);
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert maximum element to the list
        /// </summary>
        [TestMethod]
        public void AddMaximumElement()
        {
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 10;
            Node nodePtr = target.GetXthNode(0);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>(givenList);
            expectedList.Add(elementToInsert);
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert greater element to the list. Greater element is bigger than the list pointer
        /// but smaller than maximum number in the list.
        /// </summary>
        [TestMethod]
        public void AddGreaterElement()
        {
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 6;
            Node nodePtr = target.GetXthNode(1);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>() { 3, 4, 5, 6, 7, 2 };           
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert smaller element to the list. Smaller element is smaller than the list pointer
        /// but greater than the smallest number in the list.
        /// </summary>
        [TestMethod]
        public void AddSmallerElement()
        {
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 6;
            Node nodePtr = target.GetXthNode(4);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>() { 7, 2, 3, 4, 5, 6 };
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert identical element to the list where all elements are identical.        
        /// </summary>
        [TestMethod]
        public void AddIdenticalElement()
        {
            CyclicSortedList target = new CyclicSortedList(new List<int>() { 1, 1, 1, 1, 1 } );
            int elementToInsert = 1;
            Node nodePtr = target.GetXthNode(0);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>() { 1, 1, 1, 1, 1, 1 };
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }       
       

No comments:

Post a Comment

Post a Comment