view Implab/Automaton/MapAlphabet.cs @ 170:181119ef3b39 ref20160224

DFA refactoring, rx based dfa.
author cin
date Fri, 04 Mar 2016 01:56:31 +0300
parents ec35731ae299
children 0f70905b4652
line wrap: on
line source

using System;
using System.Collections.Generic;
using System.Linq;

namespace Implab.Automaton {
    public class MapAlphabet<T> : IAlphabetBuilder<T> {
        readonly Dictionary<T,int> m_map;
        int m_nextCls = 1;

        public MapAlphabet() {
            m_map = new Dictionary<T, int>();
        }

        public MapAlphabet(IEqualityComparer<T> comparer) {
            m_map = new Dictionary<T, int>(comparer);
        }

        #region IAlphabetBuilder implementation

        public int DefineSymbol(T symbol) {
            int cls;
            if (m_map.TryGetValue(symbol, out cls))
                return cls;

            cls = m_nextCls++;

            m_map.Add(symbol, cls);

            return cls;
        }

        public int DefineClass(IEnumerable<T> symbols) {
            Safe.ArgumentNotNull(symbols, "symbols");
            symbols = symbols.Distinct();

            foreach (var symbol in symbols) {
                if (!m_map.Contains(symbol))
                    m_map.Add(symbol, m_nextCls);
                else
                    throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
            }
            return m_nextCls++;
        }

        #endregion

        #region IAlphabet implementation

        public List<T>[] CreateReverseMap() {
            var empty = new List<T>();
            var rmap = new List<T>[m_nextCls];

            for (int i = 0; i < rmap.Length; i++)
                rmap[i] = empty;

            foreach (var pair in m_map) {
                var symbols = rmap[pair.Value];
                if (symbols == null) {
                    symbols = new List<T>();
                    rmap[pair.Value] = symbols;
                }

                symbols.Add(pair.Key);
            }

            return rmap;
        }

        public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
            Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
            Safe.ArgumentNotNull(classes, "classes");

            var rmap = CreateReverseMap();
            var map = new int[rmap.Length];

            foreach (var cls in classes) {
                if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
                    continue;
                
                var symbols = new List<T>();
                foreach (var id in cls) {
                    if (id < 0 || id >= rmap.Length)
                        throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", id));
                    if (rmap[id] != null)
                        symbols.AddRange(rmap[id]);
                }

                var newId = newAlphabet.DefineClass(symbols);

                foreach (var id in cls)
                    map[id] = newId;
            }
        }

        public int Translate(T symobl) {
            int cls;
            return m_map.TryGetValue(symobl, out cls) ? cls : DFAConst.UNCLASSIFIED_INPUT;
        }

        public int Count {
            get {
                return m_nextCls;
            }
        }

        #endregion
    }
}