Click here to Skip to main content
15,896,118 members
Articles / Programming Languages / C#

Optimized Indexed Matching

Rate me:
Please Sign up or sign in to vote.
4.26/5 (8 votes)
1 Nov 2011CPOL7 min read 19.1K   242   13  
Optimized matching using sorted indexes
using System;
using System.Collections.Generic;
using System.Linq;

namespace Matching.Expressions
{
    /// <summary>
    /// A matching expression that performs an And operation.
    /// </summary>
    public class AndMatchingExpression : IEnumerable<int>
    {
        private const int StopValue = Int32.MinValue;

        private List<IEnumerable<int>> enumerables = new List<IEnumerable<int>>();

        public AndMatchingExpression()
        { }

        public AndMatchingExpression(params IEnumerable<int>[] indexes)
        {
            foreach (var index in indexes)
                this.Add(index);
        }

        public AndMatchingExpression(IEnumerable<IEnumerable<int>> indexes)
        {
            foreach (var index in indexes)
                this.Add(index);
        }

        /// <summary>
        /// Adds the index to this matching session.
        /// </summary>
        public void Add(IEnumerable<int> index)
        {
            this.enumerables.Add(index);
        }

        public IEnumerator<int> GetEnumerator()
        {
            // Get enumerators:
            var enumerators = this.enumerables.Select(e => e.GetEnumerator()).ToArray();
            var enumeratorCount = enumerators.Length;
            int cursor = 0;

            try
            {
                int prevValue = StopValue;
                int prevValueCursor = StopValue;

                // Search values common to all enumerators:
                while (true)
                {
                    var v = GetNextOfEnumerator(enumerators[cursor], prevValue);

                    if (v > prevValue)
                    {
                        prevValue = v;
                        prevValueCursor = cursor;
                        cursor = ((cursor + 1) % enumeratorCount);
                    }
                    else if (v == StopValue)
                    {
                        break;
                    }
                    else
                    {
                        cursor = ((cursor + 1) % enumeratorCount);
                        if (cursor == prevValueCursor)
                        {
                            yield return prevValue;
                        }
                    }
                }
            }
            finally
            {
                // Dispose all enumerators:
                foreach (var enumerator in enumerators)
                    enumerator.Dispose();
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return (System.Collections.IEnumerator)this.GetEnumerator();
        }

        private static int GetNextOfEnumerator(IEnumerator<int> enumerator, int atLeast)
        {
            do
            {
                if (!enumerator.MoveNext())
                {
                    return StopValue;
                }
            } while (enumerator.Current < atLeast);
            return enumerator.Current;
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect AREBIS
Belgium Belgium
Senior Software Architect and independent consultant.

Comments and Discussions