using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using M17N;
using M17N.Core;

namespace M17N.Core
{
#if false
  public enum MTextFormat
    {
      MTEXT_FORMAT_US_ASCII,
      MTEXT_FORMAT_UTF_8,
      MTEXT_FORMAT_UTF_16BE,
      MTEXT_FORMAT_UTF_16LE,
      MTEXT_FORMAT_UTF_32BE,
      MTEXT_FORMAT_UTF_32LE,
    }
#endif

  public class MTextProperty
  {
    internal MSymbol key;
    internal object val;

    [FlagsAttribute]
    internal enum Flag : byte
      {
	None = 		0,
	FrontSticky =	1,
	RearSticky =	2,
	Sensitive = 	4
      };
    internal Flag flags;

    public MSymbol Key { get { return key; } }
    public object Val { get { return val; } }
    public bool FrontSticky
    {
      get { return (flags & Flag.FrontSticky) != Flag.None; }
    }
    public bool RearSticky
    {
      get { return (flags & Flag.RearSticky) != Flag.None; }
    }
    public bool Sensitive
    {
      get { return (flags & Flag.Sensitive) != Flag.None; }
    }

    public MTextProperty (MSymbol key, object val)
    {
      this.key = key;
      this.val = val;
      flags |= Flag.RearSticky;
    }

    public MTextProperty (MSymbol key, object val,
			  bool front_sticky, bool rear_sticky, bool sensitive)
    {
      this.key = key;
      this.val = val;
      if (front_sticky)
	flags |= Flag.FrontSticky;
      if (rear_sticky)
	flags |= Flag.RearSticky;
      if (sensitive)
	flags |= Flag.Sensitive;
    }

    public override string ToString ()
    {
      return key.ToString () + ":" + val;
    }
  }

  public class MText : IEnumerable, IEquatable<MText>, IComparable<MText>
  {
#if false
    public enum MTextFormat format;
#endif
    private StringBuilder sb;
    private int nchars;
    private int cache_pos;
    private int cache_idx;
    private MPlist intervals;
    private MPlist default_property;
    private bool read_only;

    private static UTF8Encoding utf8 = new UTF8Encoding ();

    private static int count_chars (String str)
    {
      int len = str.Length, n = 0;

      for (int i = 0; i < len; i++, n++) 
	if (surrogate_high_p (str[i]))
	  i++;
      return n;
    }

    private static int count_chars (StringBuilder str)
    {
      int len = str.Length, n = 0;

      for (int i = 0; i < len; i++, n++) 
	if (surrogate_high_p (str[i]))
	  i++;
      return n;
    }

    public MText ()
      {
	sb = new StringBuilder ();
	intervals = new MPlist ();
      }

    public MText (byte[] str)
      {
	sb = new StringBuilder (utf8.GetString (str));
	nchars = count_chars (sb);
	intervals = new MPlist ();
      }

    public MText (String str)
      {
	sb = new StringBuilder (str);
	nchars = count_chars (str);
	intervals = new MPlist ();
      }

    public MText (StringBuilder str)
      {
	sb = str;
	nchars = count_chars (str);
	intervals = new MPlist ();
      }

    public static MText operator+ (MText mt1, MText mt2)
    {
      MText mt = new MText ();

      mt.sb.Append (mt1.sb);
      mt.sb.Append (mt2.sb);
      mt.nchars = mt1.nchars + mt2.nchars;
      return mt;
    }

    // Public properties
    public bool ReadOnly { get { return read_only; } }
    public int Length { get { return nchars; } }

    // Public methods

    // for IEnumerable interface
    public IEnumerator GetEnumerator() { return new MTextEnum (this); }

    // for IEquatable interface
    public bool Equals (MText other) { return this.sb.Equals (other.sb); }

    // for IComparable interface
    public int CompareTo (MText other)
    {
      return this.sb.ToString ().CompareTo (other.sb.ToString ());
    }

    public override String ToString () { return "\"" + sb.ToString () + "\""; }

    private static bool surrogate_high_p (char c)
    {
      return (c >= 0xD800 && c < 0xDC00);
    }

    private static bool surrogate_low_p (char c)
    {
      return (c >= 0xDC00 && c < 0xE000);
    }

    private static int inc_idx (StringBuilder sb, int i)
    {
      return (i + (surrogate_high_p (sb[i]) ? 2 : 1));
    }

    private static int dec_idx (StringBuilder sb, int i)
    {
      return (i - (surrogate_low_p (sb[i - 1]) ? 2 : 1));
    }

    private static int pos_to_idx (MText mt, int pos)
    {
      if (pos == mt.cache_pos)
	return mt.cache_idx;

      int p, i;
      bool forward;

      if (pos < mt.cache_pos)
	{
	  if (mt.cache_pos == mt.cache_idx)
	    return mt.cache_idx;
	  if (pos < mt.cache_pos - pos)
	    {
	      p = i = 0;
	      forward = true;
	    }
	  else
	    {
	      p = mt.cache_pos; i = mt.cache_idx;
	      forward = false;
	    }
	}
      else
	{
	  if (mt.nchars - mt.cache_pos == mt.sb.Length - mt.cache_idx)
	    return (mt.cache_idx + pos - mt.cache_pos);
	  if (pos - mt.cache_pos < mt.nchars - pos)
	    {
	      p = mt.cache_pos; i = mt.cache_idx;
	      forward = true;
	    }
	  else
	    {
	      p = mt.nchars; i = mt.sb.Length;
	      forward = false;
	    }
	}
      if (forward)
	for (; p < pos; i = inc_idx (mt.sb, i), p++);
      else
	for (; p > pos; i = dec_idx (mt.sb, i), p--);
      mt.cache_pos = p;
      mt.cache_idx = i;
      return i;
    }

    private void check_pos (int pos, bool tail_ok)
    {
      if (pos < 0 || (tail_ok ? pos > nchars : pos >= nchars))
	throw new Exception ("Invalid MText position:" + pos);
    }

    private bool check_range (int from, int to, bool zero_ok)
    {
      if (from < 0 || (zero_ok ? from > to : from >= to)
	  || to > nchars)
	throw new Exception ("Invalid MText range");
      return (from == to);
    }

    private void insert (int pos, MText mt2, int from, int to)
    {
      check_pos (pos, true);

      int pos_idx = pos_to_idx (this, pos);
      int from_idx = pos_to_idx (mt2, from);
      int to_idx = pos_to_idx (mt2, to);

      sb.Insert (pos_idx, mt2.sb.ToString (from_idx, to_idx - from_idx));
      nchars += to - from;

      foreach (MPlist plist in mt2.intervals)
	if (intervals.Find (plist.Key) == null)
	  intervals.Push (plist.Key, new MInterval (plist.Key, this));
      foreach (MPlist plist in intervals)
	{
	  MPlist p = mt2.intervals.Find (plist.Key);
	  MInterval interval;

	  if (p == null)
	    interval = new MInterval (plist.Key, this, to - from);
	  else
	    interval = ((MInterval) p.Val).Copy (from, to);
	  ((MInterval) plist.Val).Insert (pos, interval);
	}
    }

    private void insert (int pos, int c)
    {
      check_pos (pos, true);

      int pos_idx = pos_to_idx (this, pos);

      if (c < 0x10000)
	{
	  char ch = (char) c;
	  sb.Insert (pos_idx, ch);
	}
      else
	{
	  char high = (char) (0xD800 + ((c - 0x10000) >> 10));
	  char low = (char) (0xDC00 + ((c - 0x10000) & 0x3FF));
	  sb.Insert (pos_idx, low);
	  sb.Insert (pos_idx, high);
	}
      nchars++;
      foreach (MPlist plist in intervals)
	((MInterval) plist.Val).Insert (pos,
					new MInterval (plist.Key, this, 1));
    }

    public int this[int i]
    {
      set {
	i = pos_to_idx (this, i);
	if (value < 0x10000)
	  {
	    if (surrogate_high_p (sb[i]))
	      sb.Remove (i, 1);
	    sb[i] = (char) value;
	  }
	else
	  {
	    char high = (char) (0xD800 + ((value - 0x10000) >> 10));
	    char low = (char) (0xDC00 + ((value - 0x10000) & 0x3FF));

	    if (! surrogate_high_p (sb[i]))
	      sb.Insert (i, 0);
	    sb[i] = high;
	    sb[i + 1] = low;
	  }
      }
      get {
	i = pos_to_idx (this, i);
	return (surrogate_high_p (sb[i])
		? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
		: sb[i]);
      }
    }

    public MText Dup ()
    {
      MText mt = new MText (sb.ToString ());

      foreach (MPlist p in intervals)
	mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (0, Length));
      return mt;
    }

    public MText Ins (int pos, int c)
    {
      insert (pos, c);
      return this;
    }

    public MText Ins (int pos, MText mt)
    {
      insert (pos, mt, 0, mt.nchars);
      return this;
    }

    public MText Ins (int pos, MText mt, int from, int to)
    {
      insert (pos, mt, from, to);
      return this;
    }

    public MText Cat (int c)
    {
      insert (nchars, c);
      return this;
    }

    public MText Del (int from, int to)
    {
      if (check_range (from, to, true))
	return this;

      sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
      nchars -= to - from;

      if (nchars > 0)
	foreach (MPlist plist in intervals)
	  ((MInterval) plist.Val).Delete (from, to);
      else
	intervals = new MPlist ();
      return this;
    }

    public object GetProp (int pos, MSymbol key)
    {
      check_pos (pos, false);

      MInterval i = (MInterval) intervals.Get (key);
      if (i == null)
	return null;

      MTextProperty prop = i.Get (pos);
      return (prop != null ? prop.Val : null);
    }

    public object GetProp (int pos, MSymbol key, out MTextProperty prop)
    {
      check_pos (pos, false);

      MInterval i = (MInterval) intervals.Get (key);
      if (i == null)
	return (prop = null);
      prop = i.Get (pos);
      return (prop != null ? prop.Val : null);
    }

    public object GetProp (int pos, MSymbol key, out MTextProperty[] array)
    {
      check_pos (pos, false);

      MInterval i = (MInterval) intervals.Get (key);
      if (i == null)
	return (array = null);
      MTextProperty prop = i.Get (pos, out array);
      return (prop != null ? prop.Val : null);
    }

    public void PushProp (int from, int to, MSymbol key, object val)
    {
      if (! check_range (from, to, true))
	PushProp (from, to, new MTextProperty (key, val));
    }

    public void PushProp (int from, int to, MTextProperty prop)
    {
      if (from < 0)
	{
	  if (default_property == null)
	    default_property = new MPlist ();
	  default_property.Push (prop.key, prop.val);
	}
      else
	{
	  if (check_range (from, to, true))
	    return;

	  MPlist p = intervals.Find (prop.key);
	  MInterval root;

	  if (p == null)
	    {
	      root = new MInterval (prop.key, this);
	      intervals.Push (prop.key, root);
	    }
	  else
	    root = (MInterval) p.Val;

	  root.Push (from, to, prop);
	}
    }

    public void PopProp (int from, int to, MSymbol key)
    {
      if (from < 0)
	{
	  if (default_property == null)
	    return;
	  MPlist p = default_property.Find (key);

	  if (p != null)
	    p.Pop ();
	}
      else
	{
	  if (check_range (from, to, true))
	    return;

	  MPlist p = intervals.Find (key);

	  if (p != null)
	    ((MInterval) p.Val).Pop (from, to);
	}
    }

    public void DumpProp ()
    {
      Console.Write ("(");
      foreach (MPlist p in intervals)
	((MInterval) p.Val).Dump (true);
      Console.WriteLine (")");
    }

    public void DumpPropNested ()
    {
      Console.Write ("(");
      foreach (MPlist p in intervals)
	((MInterval) p.Val).DumpNested (true);
      Console.WriteLine (")");
    }

    private class MInterval
    {
      // position: 0   1   2   3   4   5   6   7
      //           | A | B | C | D | E   F | G |
      // interval  |---|---|---|<->|-------|---|
      //           |---|<->|---|   |<----->|---|
      //           |<->|   |<->|           |<->|
      // 
      //                      [7 (3 4)]
      //              [3 (1 2)]       [3 (4 6)]
      //         [1 (0 1)] [2 (2 3)]      [1 (6 7)]
      //
      private static int count = 0;
      private int ID;
      private int Length;
      private int From, To;
      private MSymbol Key;
      private MPlist Stack;
      private MInterval Left, Right, Parent;
      private MText mtext;

      public MInterval (MSymbol key, MText mt, int length)
      {
	if (length <= 0)
	  throw new Exception ("Invalid interval length");
	Key = key;
	mtext = mt;
	Length = length;
	Stack = new MPlist ();
	ID = count++;
      }

      public MInterval (MSymbol key, MText mt)
      {
	Key = key;
	mtext = mt;
	Length = mt.sb.Length;
	From = 0;
	To = Length;
	Stack = new MPlist ();
	ID = count++;
      }

      public MTextProperty Get (int pos)
      {
	MInterval i = find (pos);

	return (i.Stack.IsEmpty ? null : (MTextProperty) i.Stack.Val);
      }

      public MTextProperty Get (int pos, out MTextProperty[] array)
      {
	MInterval i = find (pos);

	if (i.Stack.IsEmpty)
	  {
	    array = null;
	    return null;
	  }
	array = new MTextProperty[i.Stack.Count];

	int idx;
	MPlist p;
	for (idx = 0, p = i.Stack; ! p.IsEmpty; idx++, p = p.Next)
	  array[idx] = (MTextProperty) p.Val;
	return array[idx - 1];
      }

      private MInterval (MSymbol key, MText mt, int length, MPlist stack)
      {
	Key = key;
	mtext = mt;
	Length = length;
	From = 0;
	To = Length;
	Stack = stack.Clone ();
	ID = count++;
      }

      private void update_from_to ()
      {
	if (Parent == null)
	  {
	    From = LeftLength;
	    To = Length - RightLength;
	  }
	else if (Parent.Left == this)
	  {
	    From = Parent.From - Length + LeftLength;
	    To = Parent.From - RightLength;
	  }
	else
	  {
	    From = Parent.To + LeftLength;
	    To = Parent.To + Length - RightLength;
	  }
      }

      private int LeftLength
      {
	get { return (Left == null ? 0 : Left.Length); }
      }

      private int RightLength
      {
	get { return (Right == null ? 0 : Right.Length); }
      }

      private MInterval LeftMost
      {
	get { return (Left == null ? this : Left.LeftMost); }
      }

      private MInterval RightMost
      {
	get { return (Right == null ? this : Right.RightMost); }
      }

      private MInterval Prev {
	get {
	  MInterval i;

	  if (Left != null)
	    for (i = Left; i.Right != null; i = i.Right);
	  else
	    {
	      MInterval child = this;
	      for (i = Parent; i != null && i.Left == child;
		   child = i, i = i.Parent);
	    }
	  return i;
	}
      }

      private MInterval Next {
	get {
	  MInterval i;

	  if (Right != null)
	    for (i = Right; i.Left != null; i = i.Left);
	  else
	    {
	      MInterval child = this;
	      for (i = Parent; i != null && i.Right == child;
		   child = i, i = i.Parent);
	    }
	  return i;
	}
      }

      private MInterval find (int pos)
      {
	update_from_to ();
	if (pos < From)
	  return Left.find (pos);
	if (pos >= To)
	  return Right.find (pos);
	return this;
      }

      private bool mergeable (MInterval i)
      {
	MPlist p1, p2;

	for (p1 = Stack, p2 = i.Stack; ! p1.IsEmpty && ! p2.IsEmpty;
	     p1 = p1.Next, p2 = p2.Next)
	  if (p1.Val != p2.Val)
	    return false;
	return (p1.IsEmpty && p2.IsEmpty);
      }

      //      p-. or .-p              p-. or .-p
      //       .-this-.                .-right-.
      //    left   .-right-.  ->   .-this-.    c2
      //          c1       c2    left     c1
      private MInterval promote_right ()
      {
	int right_length = Right.Length;
	MInterval c1;

	if (Parent == null)
	  mtext.intervals.Put (Key, Right);
	else if (Parent.Left == this)
	  Parent.Left = Right;
	else
	  Parent.Right = Right;
	Right.Parent = Parent;
	c1 = Right.Left;
	Right.Left = this;

	Parent = Right;
	Right = c1;
	Parent.Length += Length;
	Length -= right_length;
	if (c1 != null)
	  {
	    c1.Parent = this;
	    Parent.Length -= c1.Length;
	    Length += c1.Length;
	  }
	return Parent;
      }

      //      p-. or .-p              p-. or .-p
      //       .-this-.                .-left-.
      //  .-left-.  .-right-.  ->     c1    .-this-.
      // c1      c2                        c2     right
      private MInterval promote_left ()
      {
	int left_length = Left.Length;
	MInterval c1;

	if (Parent == null)
	  mtext.intervals.Put (Key, Left);
	else if (Parent.Left == this)
	  Parent.Left = Left;
	else
	  Parent.Right = Left;
	Left.Parent = Parent;
	c1 = Left.Left;
	Left.Right = this;

	Parent = Left;
	Left = c1;
	Parent.Length += Length;
	Length -= left_length;
	if (c1 != null)
	  {
	    c1.Parent = this;
	    Parent.Length -= c1.Length;
	    Length += c1.Length;
	  }
	return Parent;
      }

      private MInterval balance ()
      {
	MInterval i = this;

	while (true)
	  {
	    //       .-this-.
	    //  .-left-.  .-right-.
	    // c1     c2  c3      c4
	    int diff = i.LeftLength - i.RightLength;
	    int new_diff;

	    if (diff > 0)
	      {
		new_diff = (i.Length - i.LeftLength
			    + i.Left.RightLength - i.Left.LeftLength);
		if (Math.Abs (new_diff) >= diff)
		  break;
		i = i.promote_left ();
		i.Right.balance ();
	      }
	    else if (diff < 0)
	      {
		new_diff = (i.Length - i.RightLength
			    + i.Right.LeftLength - i.Right.RightLength);
		if (Math.Abs (new_diff) >= diff)
		  break;
		i = i.promote_right ();
		i.Left.balance ();
	      }
	  }
	return i;
      }

      public MInterval Copy (int start, int end)
      {
	MInterval copy, left_copy = null, right_copy = null;

	update_from_to ();

	if (start < From)
	  {
	    if (end <= From)
	      return Left.Copy (start, end);
	    left_copy = Left.Copy (start, From);
	  }
	if (end > To)
	  {
	    if (start >= To)
	      return Right.Copy (start, end);
	    right_copy = Right.Copy (To, end);
	  }

	copy = new MInterval (Key, null, end - start, Stack);
	remove_properties (MTextProperty.Flag.Sensitive);
	if (left_copy != null)
	  {
	    copy.Left = left_copy;
	    left_copy.Parent = copy;
	  }
	if (right_copy != null)
	  {
	    copy.Right = right_copy;
	    right_copy.Parent = copy;
	  }
	return copy;
      }

      //  this-.   ==>   this-.
      //     right          newright-.
      //                            right
      private MInterval divide_right (int pos)
      {
	MInterval interval = new MInterval (Key, mtext, To - pos, Stack);

	M17N.DebugPrint ("divide-right({0}) at ", pos); DumpOne (false, true);
	To = pos;
	if (Right != null)
	  {
	    interval.Right = Right;
	    Right.Parent = interval;
	    interval.Length += Right.Length;
	  }
	interval.Parent = this;
	Right = interval;
	return interval;
      }

      //    .-this   ==>       .-this
      //  left             .-newleft
      //                 left
      private MInterval divide_left (int pos)
      {
	MInterval interval = new MInterval (Key, mtext, pos - From, Stack);

	M17N.DebugPrint ("divide-left({0}) at ", pos); DumpOne (false, true);
	From = pos;
	if (Left != null)
	  {
	    interval.Left = Left;
	    Left.Parent = interval;
	    interval.Length += Left.Length;
	  }
	interval.Parent = this;
	Left = interval;
	return interval;
      }

      private void remove_properties (MTextProperty.Flag flags)
      {
	for (MPlist p = Stack; ! p.IsEmpty;)
	  {
	    MTextProperty prop = (MTextProperty) p.Val;

	    if ((prop.flags & flags) == flags)
	      p.Pop ();
	    else
	      p = p.Next;
	  }
      }

      private void inherit_front_properties (MPlist plist)
      {
	for (MInterval i = LeftMost; i != null; i = i.Next)
	  {
	    if (! Stack.IsEmpty)
	      break;
	    for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
	      {
		MTextProperty prop = (MTextProperty) p.Val;

		if ((prop.flags & MTextProperty.Flag.RearSticky)
		    == MTextProperty.Flag.RearSticky)
		  i.Stack.Add (prop.key, prop);
	      }
	  }
      }

      private void inherit_rear_properties (MPlist plist)
      {
	for (MInterval i = RightMost; i != null; i = i.Prev)
	  {
	    if (! Stack.IsEmpty)
	      break;
	    for (MPlist p = plist; ! p.IsEmpty; p = p.Next)
	      {
		MTextProperty prop = (MTextProperty) p.Val;

		if ((prop.flags & MTextProperty.Flag.FrontSticky)
		    == MTextProperty.Flag.FrontSticky)
		  i.Stack.Add (prop.key, prop);
	      }
	  }
      }

      private MInterval delete_node_forward ()
      {
	if (Parent != null)
	  {
	    int len = Length - RightLength;

	    for (MInterval i = Parent; i != null; i = i.Parent)
	      i.Length -= len;
	    if (Parent.Left == this)
	      Parent.Left = Right;
	    else
	      Parent.Right = Right;
	  }

	if (Right != null)
	  {
	    Right.Parent = Parent;
	    return Right.LeftMost;
	  }
	return Parent;
      }

      private MInterval delete_node_backward ()
      {
	if (Parent != null)
	  {
	    int len = Length - RightLength;

	    for (MInterval i = Parent; i != null; i = i.Parent)
	      i.Length -= len;
	    if (Parent.Left == this)
	      Parent.Left = Left;
	    else
	      Parent.Right = Left;
	  }

	if (Left != null)
	  {
	    Left.Parent = Parent;
	    return Left.RightMost;
	  }
	return Parent;
      }

      private void set_mtext (MText mt)
      {
	mtext = mt;
	if (Left != null)
	  Left.set_mtext (mt);
	if (Right != null)
	  Right.set_mtext (mt);
      }

      private MInterval graft (MInterval interval, bool forward, out int len)
      {
	MInterval i;

	len = 0;
	if (forward)
	  {
	    i = interval.LeftMost;
	    while (i != null)
	      {
		if (! mergeable (i))
		  break;
		len += i.Length - i.RightLength;
		i = i.delete_node_forward ();
	      }
	  }
	else
	  {
	    i = interval.RightMost;
	    while (i != null)
	      {
		if (! mergeable (i))
		  break;
		len += i.Length - i.LeftLength;
		i = i.delete_node_backward ();
	      }
	  }

	Length += len;
	To += len;
	for (MInterval prev = this, ii = this.Parent; ii != null;
	     prev = ii, ii = ii.Parent)
	  {
	    ii.Length += len;
	    if (prev == ii.Left)
	      {
		ii.From += len;
		ii.To += len;;
	      }
	  }
	if (i != null)
	  while (i.Parent != null) i = i.Parent;
	return i;
      }

      public void Insert (int pos, MInterval interval)
      {
	update_from_to ();
	M17N.DebugPrint ("insert({0}) at {1} in ", interval.Length, pos);
	DumpOne (false, true);

	interval.set_mtext (mtext);

	if (pos < From)
	  Prev.Insert (pos, interval);
	else if (pos == From)
	  {
	    MInterval prev = Prev;

	    if (prev != null)
	      {
		if (Left == null)
		  {
		    prev.Insert (pos, interval);
		    return;
		  }
		prev.remove_properties
		  (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
		interval.inherit_front_properties (prev.Stack);
	      }
	    remove_properties
	      (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
	    interval.inherit_rear_properties (Stack);

	    int len;
	    interval = graft (interval, false, out len);
	    if (interval != null && prev != null)
	      interval = prev.graft (interval, true, out len);
	    if (interval != null)
	      {
		MInterval i;

		if (Left != null)
		  {
		    //    .-this-.   ==>          .-this-.
		    // left-.                 .-left-.
		    //    child                     child-.
		    //                                 interval
		    i = Left.RightMost;
		    i.Right = interval;
		  }
		else
		  {
		    Left = interval;
		    i = this;
		  }
		interval.Parent = i;
		for (; i != null; i = i.Parent)
		  i.Length += interval.Length;
	      }
	  }
	else if (pos < To)
	  {
	    remove_properties (MTextProperty.Flag.Sensitive);

	    int len;
	    interval = graft (interval, true, out len);
	    pos += len;
	    if (interval != null)
	      interval = graft (interval, false, out len);
	    if (interval != null)
	      {
		divide_right (pos);
		Right.Left = interval;
		interval.Parent = Right;
		for (MInterval i = Right; i != null; i = i.Parent)
		  i.Length += interval.Length;
	      }
	  }
	else if (pos == To)
	  {
	    MInterval next = Next;

	    if (next != null)
	      {
		if (Right == null)
		  {
		    next.Insert (pos, interval);
		    return;
		  }
		next.remove_properties
		  (MTextProperty.Flag.Sensitive|MTextProperty.Flag.FrontSticky);
		interval.inherit_rear_properties (next.Stack);
	      }
	    remove_properties
	      (MTextProperty.Flag.Sensitive|MTextProperty.Flag.RearSticky);
	    interval.inherit_front_properties (Stack);

	    int len;
	    interval = graft (interval, true, out len);
	    if (interval != null && next != null)
	      interval = next.graft (interval, false, out len);
	    if (interval != null)
	      {
		MInterval i;

		if (Right != null)
		  {
		    //    .-this-.   ==>          .-this-.
		    //         .-right                 .-right
		    //     child                  .-child
		    //                        interval

		    i = Right.LeftMost;
		    i.Left = interval;
		  }
		else
		  {
		    Right = interval;
		    i = this;
		  }
		interval.Parent = i;
		for (; i != null; i = i.Parent)
		  i.Length += interval.Length;
	      }
	  }
	else			// (pos > To)
	  Next.Insert (pos, interval);
      }

      private void vacate_node (MInterval interval)
      {
	M17N.DebugPrint ("vacate #{0} to #{1}", ID, interval.ID);
	if (interval != null)
	  interval.Parent = Parent;
	if (Parent == null)
	  {
	    if (mtext != null)
	      mtext.intervals.Put (Key, interval);
	  }
	else
	  {
	    if (this == Parent.Right)
	      Parent.Right = interval;
	    else
	      Parent.Left = interval;

	    int diff = Length;
	    if (interval != null)
	      diff -= interval.Length;
	    for (MInterval i = Parent; i != null; i = i.Parent)
	      i.Length -= diff;
	  }
      }

      public void Delete (int start, int end)
      {
	update_from_to ();
	M17N.DebugPrint ("delete({0} {1}) from ", start, end); DumpOne (false, true);
	if (start < From)
	  {
	    if (end <= From)
	      {
		Left.Delete (start, end);
		return;
	      }
	    Left.Delete (start, From);
	    To -= From - start;
	    end -= From - start;
	    From = start;
	  }
	if (end > To)
	  {
	    if (start >= To)
	      {
		Right.Delete (start, end);
		return;
	      }
	    Right.Delete (To, end);
	    end = To;
	  }
	if (start == From && end == To)
	  {
	    if (Right == null)
	      {
		vacate_node (Left);
	      }
	    else
	      {
		if (Left != null)
		  {
		    MInterval i;
		
		    for (i = Right; i.Left != null; i = i.Left)
		      i.Length += Left.Length;
		    i.Length += Left.Length;
		    i.Left = Left;
		    Left.Parent = i;
		  }
		vacate_node (Right);
	      }
	  }
	else
	  {
	    int len = end - start;

	    for (MInterval i = this; i != null; i = i.Parent)
	      i.Length -= len;
	  }
      }

      public void Push (int start, int end, MTextProperty prop)
      {
	update_from_to ();
	M17N.DebugPrint ("push({0} {1}) at ", start, end); DumpOne (false, true);
	if (start < From)
	  {
	    if (end <= From)
	      {
		Left.Push (start, end, prop);
		return;
	      }
	    Left.Push (start, From, prop);
	    start = From;
	  }
	if (end > To)
	  {
	    if (start >= To)
	      {
		Right.Push (start, end, prop);
		return;
	      }
	    Right.Push (To, end, prop);
	    end = To;
	  }

	if (start > From)
	  divide_left (start);
	if (end < To)
	  divide_right (end);
	Stack.Push (prop.key, prop);
      }

      private bool try_merge_prev ()
      {
	MInterval prev = Prev;

	if (! mergeable (prev))
	  return false;

	int len = prev.Length - prev.LeftLength;

	// PREV is Left, Left.Right, ..., or Left....Right.
	if (prev != Left)
	  {
	    prev.Parent.Right = prev.Left;
	    while (prev.Parent != Left)
	      {
		prev.Length -= len;
		prev = prev.Parent;
	      }
	  }
	Left.Length -= len;
	if (Left.Length == Left.LeftLength)
	  Left = Left.Left;
	return true;
      }

      private bool try_merge_next ()
      {
	MInterval next = Next;

	if (! mergeable (next))
	  return false;

	int len = next.Length - next.LeftLength;

	// NEXT is Right, Right.Left, ..., or Right....Left.
	if (next != Right)
	  {
	    next.Parent.Left = next.Right;
	    while (next.Parent != Right)
	      {
		next.Length -= len;
		next = next.Parent;
	      }
	  }
	Right.Length -= len;
	if (Right.Length == Right.LeftLength)
	  Right = Right.Left;

	return true;
      }


      public void Pop (int start, int end)
      {
	update_from_to ();
	M17N.DebugPrint ("pop({0} {1}) at ", start, end); DumpOne (false, true);
	if (start < From)
	  {
	    if (end <= From)
	      {
		Left.Pop (start, end);
		return;
	      }
	    Left.Pop (start, From);
	    start = From;
	  }
	if (end > To)
	  {
	    if (start >= To)
	      {
		Right.Pop (start, end);
		return;
	      }
	    Right.Pop (To, end);
	    end = To;
	  }

	if (! Stack.IsEmpty)
	  {
	    bool check_prev = start == From && start > 0;
	    bool check_next = end == To && end < mtext.Length;

	    if (! check_prev)
	      divide_left (start);
	    if (! check_next)
	      divide_right (end);
	    Stack.Pop ();
	    if (check_prev && Left != null)
	      check_prev = try_merge_prev () && (Left != null);
	    if (check_next && Right != null)
	      check_next = try_merge_next () && (Right != null);
	    if (check_prev)
	      {
		if (Prev.try_merge_next () && check_next)
		  Prev.try_merge_next ();
	      }
	    else if (check_next)
	      {
		Next.try_merge_prev ();
	      }
	  }
      }

      private void DumpOne (bool with_prop, bool newline)
      {
	DumpOne (with_prop, newline, false);
      }

      private void DumpOne (bool with_prop, bool newline, bool force)
      {
	if (force || M17N.debug)
	  {
	    Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
	    if (with_prop)
	      foreach (MPlist p in Stack)
		Console.Write (" " + p.Val);
	    Console.Write (")");
	    if (newline)
	      Console.WriteLine ();
	  }
      }

      public void Dump () { Dump (false); }

      public void Dump (bool force)
      {
	if (force || M17N.debug)
	  {
	    update_from_to ();

	    if (Left != null)
	      Left.Dump (force);
	    if (From > 0)
	      Console.Write (" ");
	    DumpOne (true, false, force);
	    if (Right != null)
	      Right.Dump (force);
	  }
      }

      public void DumpNested (bool force)
      {
	if (force || M17N.debug)
	  {
	    update_from_to ();

	    Console.Write ("#{0}({1} {2} {3}", ID, Length, From, To);
	    foreach (MPlist p in Stack)
	      Console.Write (" " + p.Val);
	    if (Left != null)
	      {
		Console.Write (" left=");
		Left.DumpNested (force);
	      }
	    if (Right != null)
	      {
		Console.Write (" right=");
		Right.DumpNested (force);
	      }
	    Console.Write (")");
	  }
      }
    }

    private class MTextEnum : IEnumerator
    {
      private MText mt;
      private int pos = -1;

      public MTextEnum (MText mt)
	{
	  this.mt = mt;
	}

      public bool MoveNext ()
      {
        pos++;
        return (pos < mt.nchars);
      }

      public void Reset ()
      {
        pos = -1;
      }

      public object Current
      {
        get {
	  //if (pos < 0 || pos >= mt.nchars)
	  //throw new InvalidOperationException ();
	  return mt[pos];
	}
      }
    }
  }
}