using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;
using miew.BitArray;
namespace miew.Dag
{
using String = System.String;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class Dag<T> : IList<T>, INotifyPropertyChanged where T : Dag<T>.Node
{
T[] rg_nodes;
HashSet<T> hs_nodes = new HashSet<T>();
IEnumerable<T> nodes { get { return (IEnumerable<T>)rg_nodes ?? hs_nodes; } }
HashSet<T> tops = new HashSet<T>();
HashSet<T> leaves = new HashSet<T>();
bool f_cycle_prevention = false;
bool f_index_ok = true;
int max_level = -1;
//bool f_levels_ok = true;
//internal void CheckNodeLevels()
//{
// if (!f_levels_ok)
// {
// foreach (Node n in this)
// n._set_level(-1);
// f_levels_ok = true;
// Debug.WriteLine(new StackTrace().ToString());
// }
//}
static int nest = 0;
internal void ComputeNodeLevels()
{
var old_vals = nodes.Select(x => x._set_level(-1)).ToArray();
var new_vals = nodes.Select(x => x.Level).ToArray();
max_level = new_vals.Max();
int i = 0;
nest++;
Debug.Print("---");
foreach (Node n in nodes)
{
int ov = old_vals[i];
if (ov != -1 && ov != new_vals[i])
{
Debug.Print("{0} node {1}: {2} -> {3}", nest, n.Index, old_vals[i], new_vals[i]);
n.NotifyPropertyChanged("Level");
}
i++;
}
Debug.Print("---");
nest--;
}
[DebuggerDisplay("{max_level==-1?\"not computed\":max_level.ToString()}")]
public int MaxLevel
{
get
{
//CheckNodeLevels();
if (max_level == -1)
{
//int lvl;
//foreach (T t in nodes)
// if ((lvl = t.Level) > max_level)
// max_level = lvl;
ComputeNodeLevels();
}
return max_level;
}
}
void SwitchToHash()
{
if (hs_nodes == null)
{
hs_nodes = new HashSet<T>(rg_nodes);
rg_nodes = null;
}
}
void SwitchToArray()
{
if (rg_nodes == null)
{
bool f_tmp = f_index_ok;
f_index_ok = true;
rg_nodes = hs_nodes.OrderBy(t => t.Index).ToArray();
hs_nodes = null;
if (!f_tmp)
{
for (int i = 0; i < rg_nodes.Length; i++)
rg_nodes[i]._set_index(i);
}
}
}
public HashSet<T> Tops { get { return tops; } }
public HashSet<T> Leaves { get { return leaves; } }
public bool CyclePrevention
{
get { return f_cycle_prevention; }
set { f_cycle_prevention = value; }
}
//public HashSet<T> AsHashSet()
//{
// SwitchToHash();
// return hs_nodes;
//}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[DebuggerDisplay("{ToString(),nq}")]
public abstract class Node : INotifyPropertyChanged
{
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
T This { get { return (T)this; } }
Node(Dag<T> dag, int level)
{
this.dag = dag;
this.level = level;
this.index = dag.Count;
dag.Add(This);
dag.tops.Add(This);
dag.leaves.Add(This);
}
public Node(Dag<T> dag)
: this(dag, 0)
{
}
internal Node(Dag<T> dag, int level, BitArr code, Flags flags)
: this(dag, level)
{
this.m_code = code;
this.flags |= flags;
}
[Flags]
public enum Flags
{
GlbType = 0x00000004,
};
int index;
readonly Dag<T> dag;
readonly HashSet<T> parents = new HashSet<T>();
readonly HashSet<T> children = new HashSet<T>();
int id;
int level;
Flags flags;
BitArr m_code;
internal void _set_index(int i) { index = i; }
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public Dag<T> Dag { get { return dag; } }
public bool IsTop { get { return parents.Count == 0; } }
public bool IsLeaf { get { return children.Count == 0; } }
public bool IsGlbType { get { return (flags & Flags.GlbType) > 0; } }
public void AddParent(T parent)
{
if (parent == this || parents.Contains(parent) || (dag.f_cycle_prevention && AllDescendants.Contains(parent)))
return;
//if (parent.level < this.level - 1)
// parent.LocalTop.reset_subtree_levels();
//else if (this.level < parent.level + 1)
// this.LocalTop.reset_subtree_levels();
parents.Add(parent);
parent.children.Add(This);
if (parents.Count == 1)
dag.tops.Remove(This);
if (parent.children.Count == 1)
dag.leaves.Remove(parent);
//dag.f_levels_ok = false;
dag.ComputeNodeLevels();
/// -- Notification barrier point --
if (parents.Count == 1)
NotifyPropertyChanged("IsTop");
if (parent.children.Count == 1)
parent.NotifyPropertyChanged("IsLeaf");
NotifyPropertyChanged("Parent.Item");
parent.NotifyPropertyChanged("Child.Item");
}
public void AddChild(T child)
{
if (child == this || children.Contains(child) || (dag.f_cycle_prevention && AllAncestors.Contains(child)))
return;
//if (child.level < this.level + 1)
// child.LocalTop.reset_subtree_levels();
//else if (this.level < child.level - 1)
// this.LocalTop.reset_subtree_levels();
children.Add(child);
child.parents.Add(This);
if (children.Count == 1)
dag.leaves.Remove(This);
if (child.parents.Count == 1)
dag.tops.Remove(child);
//dag.f_levels_ok = false;
dag.ComputeNodeLevels();
/// -- Notification barrier point --
if (children.Count == 1)
NotifyPropertyChanged("IsLeaf");
if (child.parents.Count == 1)
child.NotifyPropertyChanged("IsTop");
NotifyPropertyChanged("Child.Item");
child.NotifyPropertyChanged("Parent.Item");
}
public void RemoveParent(T parent)
{
if (parent == this || !parents.Remove(parent))
return;
parent.children.Remove(This);
if (parents.Count == 0)
dag.tops.Add(This);
if (parent.children.Count == 0)
dag.leaves.Add(parent);
//dag.f_levels_ok = false;
dag.ComputeNodeLevels();
/// -- Notification barrier point --
if (parents.Count == 0)
NotifyPropertyChanged("IsTop");
if (parent.children.Count == 0)
parent.NotifyPropertyChanged("IsLeaf");
NotifyPropertyChanged("Parent.Item");
parent.NotifyPropertyChanged("Child.Item");
}
public void RemoveChild(T child)
{
if (child == this || !children.Remove(child))
return;
child.parents.Remove(This);
if (children.Count == 0)
dag.leaves.Add(This);
if (child.parents.Count == 0)
dag.tops.Add(child);
//dag.f_levels_ok = false;
dag.ComputeNodeLevels();
/// -- Notification barrier point --
if (children.Count == 0)
NotifyPropertyChanged("IsLeaf");
if (child.parents.Count == 0)
child.NotifyPropertyChanged("IsTop");
NotifyPropertyChanged("Child.Item");
child.NotifyPropertyChanged("Parent.Item");
}
public void RemoveAllChildren()
{
List<KeyValuePair<Node, String>> notifications = null;
foreach (T child in children)
{
if (child.parents.Remove(This))
{
notifications = notifications ?? new List<KeyValuePair<Node, String>>();
notifications.Add(new KeyValuePair<Node, string>(child, "Parent.Item"));
if (child.parents.Count == 0)
notifications.Add(new KeyValuePair<Node, String>(child, "IsTop"));
}
}
if (notifications == null)
return;
children.Clear();
dag.ComputeNodeLevels();
//dag.f_levels_ok = false;
/// -- Notification barrier point --
foreach (var kvp in notifications)
kvp.Key.NotifyPropertyChanged(kvp.Value);
this.NotifyPropertyChanged("IsLeaf");
this.NotifyPropertyChanged("Child.Item");
}
public void RemoveAllParents()
{
List<KeyValuePair<Node, String>> notifications = null;
foreach (T parent in parents)
{
if (parent.children.Remove(This))
{
notifications = notifications ?? new List<KeyValuePair<Node, String>>();
notifications.Add(new KeyValuePair<Node, string>(parent, "Child.Item"));
if (parent.children.Count == 0)
notifications.Add(new KeyValuePair<Node, String>(parent, "IsLeaf"));
}
}
if (notifications == null)
return;
parents.Clear();
dag.ComputeNodeLevels();
//dag.f_levels_ok = false;
/// -- Notification barrier point --
foreach (var kvp in notifications)
kvp.Key.NotifyPropertyChanged(kvp.Value);
this.NotifyPropertyChanged("IsTop");
this.NotifyPropertyChanged("Parent.Item");
}
public HashSet<T> Parents { get { return parents; } }
public HashSet<T> Children { get { return children; } }
public IEnumerable<T> NextLevelChildren
{
get { return Children.Where(cn => cn.Level == Level + 1); }
}
public IEnumerable<T> PreviousLevelParents
{
get { return Parents.Where(cn => cn.Level == Level - 1); }
}
public HashSet<T> AllAncestors
{
get
{
HashSet<T> hs = new HashSet<T>();
AllAncestorsInclusive(hs);
hs.Remove(This);
return hs;
}
}
public void AllAncestorsInclusive(HashSet<T> hs)
{
foreach (T t in parents)
if (!hs.Contains(t))
t.AllAncestorsInclusive(hs);
hs.Add(This);
}
public HashSet<T> AllDescendants
{
get
{
HashSet<T> hs = new HashSet<T>();
AllDescendantsInclusive(hs);
hs.Remove(This);
return hs;
}
}
public void AllDescendantsInclusive(HashSet<T> hs)
{
foreach (T t in children)
if (!hs.Contains(t))
t.AllDescendantsInclusive(hs);
hs.Add(This);
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public BitArr Code
{
get { return m_code; }
set { m_code = value; }
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public int Id
{
get { return id; }
set { id = value; }
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public int Index
{
get
{
if (dag.hs_nodes != null && !dag.f_index_ok)
dag.SwitchToArray();
return index;
}
}
//void DownwardsLevel()
//{
// if (parents.Count == 0)
// {
// level = 0;
// return;
// }
//}
//Node LocalTop { get { return IsTop ? this : parents.First().LocalTop; } }
//void reset_subtree_levels()
//{
// foreach (Node child in children)
// child.reset_subtree_levels();
// level = -1;
//}
//void SetLocalTopLevel(ref int i)
//{
// if (parents.Count == 0)
// {
// reset_subtree_levels();
// level = i;
// }
// else
// {
// i++;
// parents.ArgMax(p => p.level).SetLocalTopLevel(ref i);
// }
//}
[DebuggerDisplay("{level==-1?\"not computed\":level.ToString()}")]
public int Level
{
get
{
//dag.CheckNodeLevels();
if (level == -1)
{
level = IsTop ? 0 : parents.Max(p => p.Level) + 1;
//NotifyPropertyChanged("Level");
}
return level;
}
}
internal int _set_level(int new_val)
{
int old_val = level;
if (level != new_val)
{
level = new_val;
if (level != -1)
NotifyPropertyChanged("Level");
}
return old_val;
}
public override string ToString()
{
return String.Format("level: {0} {1}", level == -1 ? "(not computed)" : level.ToString(), flags);
}
public event PropertyChangedEventHandler PropertyChanged;
internal void NotifyPropertyChanged(String s_field)
{
var h = PropertyChanged;
if (h != null)
h(this, new PropertyChangedEventArgs(s_field));
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// EmbedBcpo
///
/// Embed the type hierarchy in a bounded complete partial order (BCPO) lattice by inserting greatest-
/// lower bound (GLB) types as required.
///
/// References:
/// Hassan Ait-Kaci, Robert Boyer, Patrick Lincoln, Roger Nasr. 1989. "Efficient Implementation of Lattice
/// Operations"
/// Ulrich Callmeier. 2001. "Efficient Parsing with Large-Scale Unification Grammars" p.28-30.
/// Gerald Penn. 2000. "The Algebraic Structure of Attributed Type Signatures" p. 30-34
/// Bernd Kiefer, Hans-Ulrich Krieger, John Carroll, Rob Malouf. "A Bag of Useful Techniques for Efficient
/// and Robust Parsing" p. 475.
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int code_size;
int c_types;
public Dictionary<BitArr, T> code_dict;
public void EmbedBcpo(Func<T> glb_factory)
{
// retain the number of types prior to adding GLBs
code_size = Count;
//// check for inheritance from *top* and assign a maximal-depth value to each node
//foreach (DagNode t in entries.Keys)
// t.Level;
// generate Aït-Kaci transitive-closure codes for all user-specified types, in order according to
// the depth values just determined.
code_dict = new Dictionary<BitArr, T>();
T[] bitpos2type = new T[code_size];
int cur_code = code_size - 1;
foreach (T tt in nodes.OrderByDescending(e => e.Level))
{
BitArr code = new BitArr(code_size);
code[cur_code] = true;
foreach (T tc in tt.Children)
code.OrEq(tc.Code);
tt.Code = code;
code_dict.Add(code, tt);
bitpos2type[cur_code] = tt;
cur_code--;
}
/// determine codes for the GLB types which will be needed to close the graph
T[] rg_tfs = nodes.Where(t => !t.IsLeaf).ToArray();
while (true)
{
List<T> added_glbs = new List<T>();
for (int i = 0; i < rg_tfs.Length; i++)
{
T t0 = rg_tfs[i];
BitArr ba0 = t0.Code;
for (int j = i + 1; j < rg_tfs.Length; j++)
{
T t1 = rg_tfs[j];
// todo: fast test and with hash at once
if (ba0.FastTest(t1.Code))
{
BitArr z = ba0.AndWithHash(t1.Code);
int thislevel = t0.Level;
if (t1.Level > thislevel)
thislevel = t1.Level;
T glbt;
if (code_dict.TryGetValue(z, out glbt))
{
if (thislevel > glbt.Level)
glbt._set_level(thislevel);
}
else
{
//glbt = new T(this, thislevel, z, Node.Flags.GlbType);
glbt = glb_factory();
code_dict.Add(z, glbt);
added_glbs.Add(glbt);
}
}
}
}
if (added_glbs.Count == 0)
break;
rg_tfs = added_glbs.ToArray();
}
c_types = code_dict.Count;
if (c_types > ushort.MaxValue)
throw new Exception(String.Format("System supports a maximum of {0} types and {1} types were specified.", ushort.MaxValue, c_types));
/// sort all types including the new GLB types into a certain topological order
T[] type_arr = code_dict
.Values
.OrderBy(e => e.Level)
.ThenByDescending(e => e.Code.OnesCount())
.ToArray();
/// create a set of negations for all the codes, for use in step 1.
BitArr[] notcodes = new BitArr[c_types];
for (int i = 0; i < c_types; i++)
notcodes[i] = ~type_arr[i].Code;
int ops = 0;
List<T> draft = new List<T>();
BitArr r = new BitArr(code_size);
for (int i = c_types - 1; i > 0; i--)
{
T node = type_arr[i];
/// node ids correspond to their index in 'type_arr'. Set it now.
node.Id = i;
/// Looking only at GLBs, we can directly obtain the transitive closure of the graph by carefully manipulating
/// their parents and children.
if (!node.IsGlbType)
continue;
/// 1. This GLB as a parent: add its children
/// 1a. get a list of draft candidates: all descendants of 'node'
/// The order in which these are added is important because it determines the order of testing children
/// in step 1b. It's just a topological order. The list is needed because children may be eliminated from
/// the list before the point at which they'd otherwise be added.
draft.Clear();
for (int j = i + 1; j < c_types; j++)
{
T upper = type_arr[j];
if (!upper.Code.FastTest(notcodes[i]))
draft.Add(upper);
}
/// 1b. pick the subset of immediate children from this list
/// While the list is not empty, add the oldest item as a child and then remove all of its descendants from the
/// list.
while (draft.Count > 0)
{
T new_child = draft[0];
draft.RemoveAt(0);
if (!new_child.IsGlbType)
foreach (T par in new_child.Parents.ToArray())
{
ops++;
if (node.Code.AndGivesExact(par.Code))
new_child.RemoveParent(par);
}
node.AddChild(new_child);
for (int q = 0; q < draft.Count; q++)
{
ops++;
if (draft[q].Code.AndGivesExact(new_child.Code))
draft.RemoveAt(q--);
}
}
/// 2. This GLB as a child: add its parents
/// 2a. get a list of draft candidates between 'node' and *top*
draft.Clear();
BitArr nc = node.Code;
for (int j = i - 1; j >= 0; j--)
{
T lower = type_arr[j];
if (!lower.IsLeaf)
{
ops++;
if (nc.AndGivesExact(lower.Code))
draft.Add(lower);
}
}
/// 2b. pick a minimal set of parents from this list.
/// Each selection allows us to eliminate others others from the list. This effect is maximized by starting
/// with candidates with the fewest additional bits set beyond the required match. This was the reason for
/// the secondary sort on 'arr' above.
r.CopyFrom(nc);
for (int j = 0; j < draft.Count; j++)
{
T lower = draft[j];
if (lower.Code.FastTestNotArg(r))
{
r.OrEq(lower.Code);
for (int k = j + 1; k < draft.Count; k++)
{
ops++;
if (lower.Code.AndGivesExact(draft[k].Code))
draft.RemoveAt(k--);
}
// all GLB-to-GLB edges are all added as children, above
if (!lower.IsGlbType)
{
foreach (uint bit_pos in nc.OnesPositions())
lower.RemoveChild(bitpos2type[bit_pos]);
node.AddParent(lower);
}
}
}
}
Console.WriteLine("types {0} closed {1} glb {2} ops {3}", code_size, type_arr.Length, type_arr.Length - code_size, ops);
}
public int Count { get { return rg_nodes != null ? rg_nodes.Length : hs_nodes.Count; } }
public int IndexOf(T item)
{
SwitchToArray();
return System.Array.IndexOf<T>(rg_nodes, item);
}
public void Insert(int index, T item)
{
throw new NotImplementedException();
}
public void RemoveAt(int index)
{
throw new NotImplementedException();
}
public T this[int index]
{
get
{
SwitchToArray();
return rg_nodes[index];
}
set
{
throw new NotImplementedException();
}
}
public void Add(T node)
{
SwitchToHash();
hs_nodes.Add(node);
}
public void Clear()
{
rg_nodes = null;
hs_nodes = new HashSet<T>();
}
public bool Contains(T item)
{
if (hs_nodes != null)
return hs_nodes.Contains(item);
return System.Array.IndexOf<T>(rg_nodes, item) != -1;
}
public void CopyTo(T[] array, int arrayIndex)
{
foreach (T t in nodes)
array[arrayIndex++] = t;
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(T item)
{
SwitchToHash();
if (!hs_nodes.Contains(item))
return false;
item.RemoveAllChildren();
item.RemoveAllParents();
hs_nodes.Remove(item);
f_index_ok = false;
return true;
}
public IEnumerator<T> GetEnumerator()
{
return nodes.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public event PropertyChangedEventHandler PropertyChanged;
void NotifyPropertyChanged(String s_field)
{
var h = PropertyChanged;
if (h != null)
h(this, new PropertyChangedEventArgs(s_field));
}
};
}