This question is asked on Programming Praxis. The code in the form of Visual Studio 2010 solution can be downloaded from here.
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
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
/// <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.");
}
}
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 element2. 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.
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 ***************************
/// 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.");
}
}