Jolt.Collections : Circular Lists and Enumeration

Circular lists are collections in which the element following (or linked after) the "last" element is indeed the "first" element of the collcetion. Thus, the graphical arrangement of the collection elements form a circle with generally no explicit start or end.

There are many application of circular data structures, such as ciruclar buffers and selecting items in a time-shared or round-robin fashion. However, support for such data structures in the current .NET Framework is limited to using linear collections and custom enumeration and element-access logic. Jolt.NET aims to bridge this gap by providing collections that implement circular-link semantics.

Table Of Contents

  1. Design Scope
  2. Usage Examples
    1. Circular Enumerator
    2. Circular List
      1. Enumerating the collection
      2. Iterating the collection elements by index
      3. Rotating or shifting the collection
    3. Circular Linked List
      1. Enumerating the collection
      2. Iterating the collection elements via CircularLinkedListNode<T>
      3. Rotating or shifting the collection

Design Scope

The Jolt.NET circular data structures are designed to support the following features.
  • An enumerator providing circular enumeration semantics for any implementation of the IEnumerable<T> interface
  • An implementation of the IList<T> interface, providing a circular list data structure
  • An implementation that emulates a LinkedList<T>, providing a circular linked-list data structure
    • An implementation that emulates LinkedListNode<T>, providing circular navigation through the Next and Previous properties

Usage Examples


Circular Enumerator

The CircularEnumerator<T> type is an IEnumerator<T> implementation that adapts an enumerator returned from an associated enumerable collection. The adapted enumerator iterates through the collection elements, continuing to the first collection element after visiting the last collection element. To illustrate, consider the following example.

using Jolt.Collections;
using System;
using System.Collections.Generic;

void PrintCollectionContents<T>(IEnumerable<T> collection)
{
    IEnumerator<T> circularEnumerator = new CircularEnumerator<T>(collection);
    while(circularEnumerator.MoveNext())
    {
        // Caution!  This loop will never end if collection is non-empty.
        Console.Write(circularEnumerator.Current);
    }
}

int main()
{
    // Print nothing.
    PrintCollectionContents(new int[0]);

    // Print 12345123451234512345 ... indefinitely.
    PrintCollectionContents(new[] { 1, 2, 3, 4, 5 });
}


Circular List

The CircularList<T> class implements the IList<T> interface, and providing a list with circular enumeration and element-access semantics. CircularList<T> uses List<T> internally for storage, and all the CircularList<T> operations have the same memory and time complexity as their List<T> counterparts, unless otherwise mentioned.

The following examples demonstrate features of CircularList<T> which differ from List<T>.


CircularList<T> creates enumerators with circular-enumeration semantics, as demonstrated by the following example.

using Jolt.Collections;
using System;
using System.Collections.Generic;

void PrintCollectionContents<T>(IEnumerable<T> sourceCollection)
{
    IList<T> circularList = new CircularList<T>(sourceCollection);  // Copy construction
    foreach(T t in circularList)
    {
        // Caution!  This loop will never end if sourceCollection is non-empty.
        Console.Write(t);
    }
}


Like any IList<T>, CircularList<T> may also be enumerated in a finite number of iterations, by fetching elements via its indexer.

using Jolt.Collections;
using System;
using System.Collections.Generic;

void PrintCollectionContents<T>(IEnumerable<T> sourceCollection)
{
    IList<T> circularList = new CircularList<T>(sourceCollection);  // Copy construction
    for(int i = 0; i < circularList.Count; ++i)
    {
        // Count returns the actual number of elements in the circular list.
        Console.Write(circularList[i]);
    }
}

Since the CircularList<T> is circular, it is a valid operation to query an element using an index that exceeds the size of the collection. In this case, a modulus operation is performed internally to offset the given index value by the size of the collection, as demonstrated by the following example.

using Jolt.Collections;
using System;
using System.Collections.Generic;

void ModularIndex()
{
    IList<int> circularList = new CircularList<int>();
    circularList.Add(1);
    circularList.Add(2);
    circularList.Add(3);
    circularList.Add(4);

    // Outputs 341234123 to the console.
    for(int i = 10; i < 20; ++i)
    {
        Console.Write(circularList[i]);
    }
}


CircularList<T> may be rotated or shifted by a given number of elements, effectively redefining the head or first element of the collection. A shift operation runs in O(1) time and is demonstrated in the following example.

using Jolt.Collections;
using System;

void Shift()
{
    CircularList<char> collection = new CircularList<char>
    {
        // C# 3.0-style initialization; auto default construction + collection.Add() calls
        'a', 'b', 'c', 'd', 'e'
    };

    collection >>= 3;	// Forward shift of three elements

    // Outputs cdeab to the console.
    for(int i = 0; i < collection.Count; ++i)
    {
        Console.Write(collection[i]);
    }
	
    collection <<= 4;	// Backward shift of four elements

    // Outputs bcdea to the console.
    for(int i = 0; i < collection.Count; ++i)
    {
        Console.Write(collection[i]);
    }
}

operator>> implements the forward shift and operator<< implements the backward shift. Passing a negative number to either of these operators reverses the direction of the shift, as demonstrated in the following example.

using Jolt.Collections;
using System;

void Shift()
{
    CircularList<char> collection = new CircularList<char>
    {
        'a', 'b', 'c', 'd', 'e'
    };

    collection >>= -3;	// Backward shift of three elements

    // Outputs deabc to the console.
    for(int i = 0; i < collection.Count; ++i)
    {
        Console.Write(collection[i]);
    }
	
    collection <<= -4;	// Forward shift of four elements

    // Outputs cdeab to the console.
    for(int i = 0; i < collection.Count; ++i)
    {
        Console.Write(collection[i]);
    }
}

Important! Since a shift operation changes the internal index-to-element mapping of CircularList<T>, methods that rely on the position of an element will start to operate with the new mapping after a shift operation. To illustrate, consider the following example.

using Jolt.Collections;

void CopyToArray()
{
    CircularList<char> collection = new CircularList<char>
    {
        'a', 'b', 'c', 'd', 'e'
    };

    collection <<= 3;

    // Returns an array with elements deabc.
    char[] array = new char[collection.Count];
    collection.CopyTo(array, 0);
    return array;
}


Circular Linked List

The CircularLinkedList<T> class implements the ICollection<T> and ICollection interfaces, and also mimics the LinkedList<T> interface. CircularLinkedList<T> uses LinkedList<T> internally for storage, providing a linked-list interface with circular enumeration and element-access semantics. All CircularLinkedList<T> operations have the same memory and time complexity as their LinkedList<T> counterparts, unless otherwise mentioned.

The following examples demonstrate features of CircularLinkedList<T> which differ from LinkedList<T>.


CircularLinkedList<T> creates enumerators with circular-enumeration semantics, as demonstrated by the following example.

using Jolt.Collections;
using System;

void PrintCollectionContents<T>(IEnumerable<T> sourceCollection)
{
    CircularLinkedList<T> circularList = new CircularLinkedList<T>(sourceCollection);  // Copy construction
    foreach(T t in circularList)
    {
        // Caution!  This loop will never end if sourceCollection is non-empty.
        Console.Write(t);
    }
}


As with LinkedList<T>, a CircularLinkedList<T> is accompanied by a type to represent its elements: CircularLinkedListNode<T>. This type internally uses a LinkedListNode<T> for storage and defines its equality semantics to perform a reference comparison on the encapsultated LinkedListNode<T>. The following example demonstrates how to navigate the nodes of a CircularLinkedList<T> using the circular enumeration semantics of CircularLinkedListNode<T>.

using Jolt.Collections;
using System;

void IterateCircularLinkedList()
{
    CircularLinkedList<int> collection = new CircularLinkedList
    {
        // C# 3.0-style initialization; auto default construction + collection.Add() calls
        1, 2, 3, 4, 5, 6
    };
	
    CircularLinkedListNode<int> node = collection.First;
	
    // Outputs 123456123456123456 ... indefinitely to the console.
    while(node.Next != null)
    {
        // Caution! This loop never terminates.
        Console.Write(node.CircularPrevious().Value);
        node = node.CircularNext();
    }
}


CircularLinkedList<T> implements the same shift operations as CircularList<T>, and also carries the same implementation caveats. All CircularList<T> shifting examples are equally applicable to CircularLinkedList<T> (with the necessary type changes).

CircularLinkedList<T> shift operations run in O(n) time, where n is the size of the circular linked list. Furthermore, there will only be at most n/2 shifts performed for any given input value.

Last edited Jan 25, 2010 at 2:17 PM by SteveGuidi, version 2

Comments

No comments yet.