namespace leppie.FA
{
/******************************************************************************************
* Open Source Software License. Copyright 2003. Llewellyn Pritchard. All rights reserved.*
* ****************************************************************************************
* This notice may not be removed. *
* Software is refered to all code following this notice up to the end of the file. *
* The software is provided as is. *
* The software may not be sublicensed without permission from the license provider. *
* The software is free to use and distribute without permission in the original or *
* modified form for all non-commercial purposes. *
* Explicit permission is required from the license provider for all commercial purposes. *
* In such a case, a commercial license might be required. *
* Any vagueness about the license granted, must be verified by contacting the *
* license provider (llewellyn@pritchard.org or leppie@ataris.co.za). *
******************************************************************************************/
using System;
using System.Collections;
public class AtomicState
{
protected AtomicState() : this(new object()){}
private AtomicState(object key)
{
this.key = key;
this.tag = null;
child = null;
next = null;
}
protected object key;
//can be used for data, but this is really just a toggle
//cant see where data would be used..., maybe later, maybe a surprise at the end???
internal object tag;
internal AtomicState child;
internal AtomicState next;
private AtomicState GetLastNext()
{
AtomicState last = this;
while (last.next != null)
last = last.next;
return last;
}
private AtomicState MatchKey(object key)
{
AtomicState currentnode = this;
while (currentnode != null)
{
if (currentnode.key.Equals(key))
return currentnode;
currentnode = currentnode.next;
}
return null;
}
public AtomicState GetAtomicStateAt(Array stack)
{
if (stack == null || stack.Length == 0) return null;
AtomicState parent = this;
int counter = 0;
do
{
AtomicState i = parent.MatchKey(stack.GetValue(counter++));
if (null == i)
return null;
if (null == i.child && counter < stack.Length)
return null;
if (counter == stack.Length)
return i;
parent = i.child;
}
while (true);
}
private bool AddStackToAtomicState(Array stack, AtomicState parent,
AtomicState prev, int counter, object tag)
{
do
{
if (counter == stack.Length)
{
if (tag == null || parent.tag != null)
{
parent.tag = null;
return true;
}
if (parent.tag != null)
return false;
parent.tag = tag;
}
else
{
AtomicState pnode = new AtomicState(stack.GetValue(counter));
if (null != parent)
parent.child = pnode;
if (null != prev)
{
prev.GetLastNext().next = pnode;
prev = null;
}
parent = pnode;
}
}
while (counter++ < stack.Length);
return true;
}
protected Array Match(Array stack)
{
ArrayList arr = new ArrayList();
//again I hate M$ here, if we dont do this, the setvalue will fail below
object[] ostack = new object[stack.Length];
stack.CopyTo(ostack, 0);
MatchWild(ostack, ostack, arr);
if (arr.Count > 0)
return arr.ToArray(arr[0].GetType());
else
return null;
}
private void MatchWild(Array stack, Array stacktemp, ArrayList results)
{
AtomicState pn = null;
int i = 0;
for (; i < stacktemp.Length; i++)
{
if (stacktemp.GetValue(i) == null)
break;
}
object[] substack = new object[stacktemp.Length - i];
for (int j = 0; j < substack.Length; j++)
substack.SetValue(stacktemp.GetValue(i + j), j);
if (substack.Length > 0)
{
pn = GetAtomicStateAt(Trim(stacktemp));
if (pn != null)
pn = pn.child;
else if (i == 0)
pn = this;
while (pn != null)
{
substack.SetValue(pn.key, 0);
//this one
stack.SetValue(pn.key, i);
pn.MatchWild(stack, substack, results);
pn = pn.next;
}
substack.SetValue(null, 0);
}
else
{
pn = GetAtomicStateAt(stacktemp);
if (pn != null)
if (pn.tag != null)
results.Add(stack.Clone());
}
}
protected bool Add(Array stack)
{
return Add(stack, this);
}
protected bool Remove(Array stack)
{
return Add(stack, null);
}
private bool Add(Array stack, object tag)
{
if (stack.Length == 0) return false;
AtomicState parent = this;
int counter = 0;
do
{
AtomicState i = parent.MatchKey(stack.GetValue(counter++));
if (null == i)
return AddStackToAtomicState(stack, null, parent, --counter, tag);
if (null == i.child && counter < stack.Length)
return AddStackToAtomicState(stack, i, null, counter, tag);
if (counter == stack.Length)
return AddStackToAtomicState(stack, i, null, counter, tag);
parent = i.child;
}
while (true);
}
protected bool Accepts(Array stack)
{
AtomicState i = GetAtomicStateAt(stack);
if (null != i)
if (i.tag != null)
return true;
return false;
}
public int AcceptStateCount
{
get
{
int size = 0;
if (next != null)
size += next.AcceptStateCount;
if (child != null)
size += child.AcceptStateCount;
if (tag != null)
size++;
return size;
}
}
public int TotalStateCount
{
get
{
int size = 0;
if (next != null)
size += next.TotalStateCount;
if (child != null)
size += child.TotalStateCount;
size++;
return size;
}
}
private Array Trim(Array buffer)
{
int i = 0;
for (; i < buffer.Length; i++)
if (buffer.GetValue(i) == null)
break;
Array newbuf = Array.CreateInstance(key.GetType(), i);
for (i = 0; i < newbuf.Length; i++)
newbuf.SetValue(buffer.GetValue(i), i);
return newbuf;
}
private bool MatchItem(Array buffer, ref int index, int pos, int size, Array results)
{
buffer.SetValue(key, pos);
if (tag != null && index != 0)
{
buffer.SetValue(null, pos + 1);
results.SetValue(Trim(buffer) ,size - index--);
}
if (index >= 0 & child != null)
if (child.MatchItem(buffer, ref index, pos + 1, size, results))
return true;
if (index >= 0 & next != null)
if (next.MatchItem(buffer, ref index, pos, size, results))
return true;
return false;
}
public Array AcceptStates(Array stack)
{
AtomicState pnode = GetAtomicStateAt(stack);
if (stack == null || stack.Length == 0)
pnode = this;
else
{
if (pnode == null || pnode.child == null)
return null;
else
pnode = pnode.child;
}
int index = pnode.AcceptStateCount;
int size = index;
Array buffer = Array.CreateInstance(typeof(object), pnode.Depth(2)); //pad it, and child (boxing)
Array results = Array.CreateInstance(typeof(Array), size);
pnode.MatchItem(buffer, ref index, 0, size, results);
//dont have to check, already knows there is at least one
Array newres = Array.CreateInstance(results.GetValue(0).GetType(), size);
results.CopyTo(newres, 0);
return newres;
}
internal int Depth(int depth)
{
int c = 0, n = 0;
if (child != null)
c = child.Depth(depth + 1);
if (next != null)
n = next.Depth(depth);
if (c > depth)
depth = c;
if (n > depth)
depth = n;
return depth;
}
public override string ToString()
{
return key.ToString();
}
}
#region Implementations
public class CharState : AtomicState
{
public CharState() : base(){}
public bool Add(char[] stack) { return base.Add(stack);}
public bool Remove(char[] stack) { return base.Remove(stack);}
public char[][] AcceptStates(char[] stack) {return (char[][]) base.AcceptStates(stack);}
public bool Accepts(char[] stack) { return base.Accepts(stack);}
public char[][] Match(char[] stack)
{
//setup the "null" value
object[] ostack = new object[stack.Length];
for (int i = 0; i < stack.Length; i++)
{
if ((char)stack.GetValue(i) == '\0')
ostack[i] = null;
else
ostack[i] = stack.GetValue(i);
}
Array res = base.Match(ostack);
//god I hate M$, why cant I cast (even if I did specify the type)????
//someone should shoot someone!!!!!!!!!!!!!!!!
if (res != null)
{
char[][] output = new char[res.Length][];
for (int i = 0; i < output.Length; i++)
{
Array inarr = (Array)res.GetValue(i);
char[] cinarr = new char[inarr.Length];
inarr.CopyTo(cinarr, 0);
output[i] = cinarr;
}
return output;
}
else return null;
}
}
public class StringState : AtomicState
{
public StringState() : base(){}
public bool Add(string[] stack) { return base.Add(stack);}
public bool Remove(string[] stack) { return base.Remove(stack);}
public string[][] AcceptStates(string[] stack) { return (string[][]) base.AcceptStates(stack);}
public bool Accepts(string[] stack) { return base.Accepts(stack);}
public string[][] Match(string[] stack)
{
Array res = base.Match(stack);
//god I hate M$, why cant I cast (even if I did specify the type)????
string[][] output = new string[res.Length][];
res.CopyTo(output, 0);
return output;
}
}
public class Int32State : AtomicState
{
public Int32State() : base(){}
public bool Add(int[] stack) { return base.Add(stack);}
public bool Remove(int[] stack) { return base.Remove(stack);}
public int[][] AcceptStates(int[] stack) { return (int[][]) base.AcceptStates(stack);}
public bool Accepts(int[] stack) { return base.Accepts(stack);}
}
public class FloatState : AtomicState
{
public FloatState() : base(){}
public bool Add(float[] stack) { return base.Add(stack);}
public bool Remove(float[] stack) { return base.Remove(stack);}
public float[][] AcceptStates(float[] stack) { return (float[][]) base.AcceptStates(stack);}
public bool Accepts(float[] stack) { return base.Accepts(stack);}
}
public class BooleanState : AtomicState
{
public BooleanState() : base(){}
public bool Add(bool[] stack) { return base.Add(stack);}
public bool Remove(bool[] stack) { return base.Remove(stack);}
public bool[][] AcceptStates(bool[] stack) { return (bool[][]) base.AcceptStates(stack);}
public bool Accepts(bool[] stack) { return base.Accepts(stack);}
}
public class ObjectState : AtomicState
{
public ObjectState() : base(){}
public bool Add(object[] stack) { return base.Add(stack);}
public bool Remove(object[] stack) { return base.Remove(stack);}
public object[][] AcceptStates(bool[] stack) { return (object[][]) base.AcceptStates(stack);}
public bool Accepts(object[] stack) { return base.Accepts(stack);}
}
public class TypeState : AtomicState
{
public TypeState() : base(){}
public bool Add(Type[] stack) { return base.Add(stack);}
public bool Remove(Type[] stack) { return base.Remove(stack);}
public Type[][] AcceptStates(bool[] stack) { return (Type[][]) base.AcceptStates(stack);}
public bool Accepts(Type[] stack) { return base.Accepts(stack);}
public override string ToString()
{
if (key is Type)
return ((Type)key).Name;
else return base.ToString();
}
}
#endregion
}
Submit an article or tip