Grammar Composition System

/src/agree-sys/40-tfs-marking-array.cs

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

using miew.Debugging;

namespace agree
{
#if false
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// MarkingArrayTfs : low-impact, flat array edge storage
	/// </summary>
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public class MarkingArrayTfs : MarkingTfs
	{
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// construct a MarkingArrayTfs with the specified capacity
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public MarkingArrayTfs(TypeMgr tm, int c)
			: base(tm)
		{
			this.entries = new arr_tfs_entry[c];
			c |= 1;
			while (c % 3 == 0 || c % 5 == 0 || c % 7 == 0)
				c += 2;
			this.hidx = new int[c];
			for (int i = 0; i < c; i++)
				hidx[i] = -1;
			c_entries = 0;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// construct a MarkingArrayTfs from a BootstrapTfs
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public MarkingArrayTfs(BootstrapTfs dtfs)
			: this(dtfs.tm, dtfs.d.Count)
		{
			this.Edge = dtfs.Edge;

			foreach (var kvp in dtfs.d)
			{
				int i_feat = (int)(kvp.Key >> 32);
				int mark = (int)kvp.Key;
				Edge e = kvp.Value;
				if (e.FlagsId < 0)
				{
					if (corefs == null)
						corefs = new Dictionary<Edge, int> { { e, 1 } };
					else if (corefs.ContainsKey(e))
						corefs[e]++;
					else
						corefs.Add(e, 1);
				}

				uint v;
				int dx, cur = hidx[v = (uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
				if (cur == -1 || (dx = mark - entries[cur].mark) < 0 || (dx == 0 && i_feat <= entries[cur].i_feat))
					hidx[v] = c_entries;
				else
				{
					int prv;
					do
					{
						prv = cur;
						cur = entries[cur].next;
					}
					while (cur != -1 && ((dx = mark - entries[cur].mark) > 0 || (dx == 0 && i_feat > entries[cur].i_feat)));
					entries[prv].next = c_entries;
				}
				entries[c_entries++] = new arr_tfs_entry { i_feat = i_feat, mark = mark, e = e, next = cur };
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// construct a MarkingArrayTfs from a BootstrapTfs-style Edge dictionary and coreference overrides from a TargetTfs
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public MarkingArrayTfs(
						TypeMgr tm,
						Edge top_edge,
						IDictionary<UInt64, Edge> edges,
						int coref_tfsid,
						Dictionary<Int64, Unification.UnifCoref> u_corefs,
						ref int c_corefs)
			: this(tm, edges.Count)
		{
			this.Edge = top_edge;

			foreach (var kvp in edges)
			{
				int i_feat = (int)(kvp.Key >> 32);
				int mark = (int)kvp.Key;
				Edge e = kvp.Value;
				if (e.FlagsId < 0)
				{
					Unification.UnifCoref uc = u_corefs[((long)coref_tfsid << 32) | (uint)e.Mark];
					while (uc.f_redirect)
						uc = uc.next;

					if (uc.c_fm == 1)
					{
						Edge.Flag nf = e.FlagsId & ~Edge.Flag.Coreference;
#if DEBUG
						uc.single_fm = default(FeatMark);
#endif
						uc.c_fm = 0;
						c_corefs--;
						if (nf == 0)
							continue;
						e = new Edge(nf, (nf & Edge.Flag.EtmNonBareType) == 0 ? 0 : e.Mark);
					}
					else
					{
						e = uc.e_cur;
						if (corefs == null)
							corefs = new Dictionary<Edge, int> { { e, 1 } };
						else if (corefs.ContainsKey(e))
							corefs[e]++;
						else
							corefs.Add(e, 1);
					}
				}

				uint v;
				int dx, cur = hidx[v = (uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
				if (cur == -1 || (dx = mark - entries[cur].mark) < 0 || (dx == 0 && i_feat <= entries[cur].i_feat))
					hidx[v] = c_entries;
				else
				{
					int prv;
					do
					{
						prv = cur;
						cur = entries[cur].next;
					}
					while (cur != -1 && ((dx = mark - entries[cur].mark) > 0 || (dx == 0 && i_feat > entries[cur].i_feat)));
					entries[prv].next = c_entries;
				}
				entries[c_entries++] = new arr_tfs_entry { i_feat = i_feat, mark = mark, e = e, next = cur };
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// clone of a MarkingArrayTfs (or derived instance). However, because c_entries is a value type, we currently
		/// don't allow modifying the source through the clone.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public MarkingArrayTfs(MarkingArrayTfs to_clone)
			: base(to_clone.tm, to_clone.Edge)
		{
			this.entries = to_clone.entries;
			//this.corefs = to_clone.corefs;
			this.coref_tallies = to_clone.coref_tallies;
			this.hidx = to_clone.hidx;
			this.c_entries = to_clone.c_entries;
			this.f_locked = true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// edges
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		arr_tfs_entry[] entries;
		int freelist = -1;
		int c_entries = 0;
		bool f_locked = false;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// hash-to-index
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int[] hidx;

		//[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		//Dictionary<Edge, int> corefs;

		//[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		//public override int CorefCount { get { return corefs == null ? 0 : corefs.Count; } }

		//[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		//public override IDictionary<Edge, int> CorefTallies { get { return corefs; } }

		public override Tfs Clone() { return c_corefs == 0 ? this : new MarkingArrayTfs(this); }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public override int EdgeCount { get { return c_entries; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override bool TryGetEdge(int i_feat, int mark, out Edge e)
		{
			Debug.Assert(mark != 0);
			int ix = hidx[(uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (ix != -1)
			{
				arr_tfs_entry ent;
				int d;
				do
				{
					ent = entries[ix];
					if ((d = ent.mark - mark) == 0)
						d = ent.i_feat - i_feat;
					if (d == 0)
					{
						e = ent.e;
						return true;
					}
				}
				while (d < 0 && (ix = ent.next) != -1);
			}
			e = default(Edge);
			return false;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override Edge GetEdge(int i_feat, int mark)
		{
			Debug.Assert(mark != 0);
			int ix = hidx[(uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (ix != -1)
			{
				arr_tfs_entry ent;
				int d;
				do
				{
					ent = entries[ix];
					if ((d = ent.mark - mark) == 0)
						d = ent.i_feat - i_feat;
					if (d == 0)
						return ent.e;
				}
				while (d < 0 && (ix = ent.next) != -1);
			}
			return default(Edge);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override bool ContainsFeatMark(int i_feat, int mark)
		{
			Debug.Assert(mark != 0);
			int ix = hidx[(uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (ix != -1)
			{
				arr_tfs_entry ent;
				int d;
				do
				{
					ent = entries[ix];
					if ((d = ent.mark - mark) == 0)
						d = ent.i_feat - i_feat;
					if (d == 0)
						return true;
				}
				while (d < 0 && (ix = ent.next) != -1);
			}
			return false;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override void SetEdge(int i_feat, int mark, Edge e)
		{
			Debug.Assert(!f_locked, "Cannot modify Tfs through clone");
			Debug.Assert(mark != 0);

			int ix = hidx[(uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (ix != -1)
			{
				arr_tfs_entry ent;
				int d;
				do
				{
					ent = entries[ix];
					if ((d = ent.mark - mark) == 0)
						d = ent.i_feat - i_feat;
					if (d == 0)
						goto got_ix;
				}
				while (d < 0 && (ix = ent.next) != -1);
			}
			if (c_entries < entries.Length - 1)
				ix = c_entries++;
			else if ((ix = freelist) != -1)
				freelist = entries[ix].next;
			else
				throw new Exception(String.Format("{0} is an insufficient allocation for this MarkingArrayTfs", entries.Length));

		got_ix:
			uint v;
			int dx, cur = hidx[v = (uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (cur == -1 || (dx = mark - entries[cur].mark) < 0 || (dx == 0 && i_feat <= entries[cur].i_feat))
				hidx[v] = ix;
			else
			{
				int prv;
				do
				{
					prv = cur;
					cur = entries[cur].next;
				}
				while (cur != -1 && ((dx = mark - entries[cur].mark) > 0 || (dx == 0 && i_feat > entries[cur].i_feat)));
				entries[prv].next = ix;
			}
			entries[ix] = new arr_tfs_entry { i_feat = i_feat, mark = mark, e = e, next = cur };
			if (e.FlagsId < 0)
			{
				if (corefs == null)
					corefs = new Dictionary<Edge, int> { { e, 1 } };
				else if (corefs.ContainsKey(e))
					corefs[e]++;
				else
					corefs.Add(e, 1);
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override void AddEdge(int i_feat, int mark, Edge e)
		{
			Debug.Assert(mark != 0);
			Debug.Assert(!ContainsFeatMark(i_feat, mark));
			Debug.Assert(!f_locked, "Cannot modify Tfs through clone");

			int ix;
			if (c_entries < entries.Length - 1)
				ix = c_entries++;
			else if ((ix = freelist) != -1)
				freelist = entries[ix].next;
			else
				throw new Exception(String.Format("{0} is an insufficient allocation for this MarkingArrayTfs", entries.Length));

			uint v;
			int dx, cur = hidx[v = (uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (cur == -1 || (dx = mark - entries[cur].mark) < 0 || (dx == 0 && i_feat <= entries[cur].i_feat))
				hidx[v] = ix;
			else
			{
				int prv;
				do
				{
					prv = cur;
					cur = entries[cur].next;
				}
				while (cur != -1 && ((dx = mark - entries[cur].mark) > 0 || (dx == 0 && i_feat > entries[cur].i_feat)));
				entries[prv].next = ix;
			}
			entries[ix] = new arr_tfs_entry { i_feat = i_feat, mark = mark, e = e, next = cur };
			if (e.FlagsId < 0)
			{
				if (corefs == null)
					corefs = new Dictionary<Edge, int> { { e, 1 } };
				else if (corefs.ContainsKey(e))
					corefs[e]++;
				else
					corefs.Add(e, 1);
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public unsafe override bool RemoveEdge(int i_feat, int mark)
		{
			Debug.Assert(!f_locked, "Cannot modify Tfs through clone");
			Debug.Assert(mark != 0);

			uint v;
			int ix = hidx[v = (uint)((i_feat << 16) ^ mark) % (uint)hidx.Length];
			if (ix != -1)
			{
				arr_tfs_entry ent;
				int d, prv = -1;
				do
				{
					ent = entries[ix];
					if ((d = ent.mark - mark) == 0)
						d = ent.i_feat - i_feat;
					if (d == 0)
					{
						if (ent.e.FlagsId < 0 && --corefs[ent.e] == 0)
							corefs.Remove(ent.e);

						if (prv == -1)
							hidx[v] = ent.next;
						else
							entries[prv].next = ent.next;
#if DEBUG
						entries[ix] = default(arr_tfs_entry);
#else
						entries[ix].mark = 0;
#endif
						entries[ix].next = freelist;
						freelist = ix;
						c_entries--;
						return true;
					}
					if (d > 0)
						break;
					prv = ix;
				}
				while ((ix = ent.next) != -1);
			}
			return false;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override bool _ContainsInMark(int mark)
		{
			Debug.Assert(mark != 0);
			for (int i = 0; i < entries.Length; i++)
				if (entries[i].mark == mark)
					return true;
			return false;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public override IEnumerable<FeatMarkEdge> FeatMarkEdges
		{
			get
			{
				foreach (arr_tfs_entry ent in entries)
					if (ent.mark != 0)
						yield return new FeatMarkEdge(ent.i_feat, ent.mark, ent.e);
			}
		}
	};
#endif
}