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 MProperty
  {
    [FlagsAttribute]
    public enum Flags
    {
      None = 		0x00,

      /// On inserting a text in between two characters, if the
      /// preceding and following characters have Sticky properties of
      /// the same key with same values, the inserted text inherits
      /// those properties.  In that case, properties of the inserted
      /// text are overriden.
      Sticky =		0x01,	// 00000001

      /// On inserting a text before a character, if the character has
      /// FrontSticky properties, the inserted text inherits those
      /// properties.
      FrontSticky =	0x03,	// 00000011

      /// On inserting a text after a character, if the character has
      /// RearSticky properties, the inserted text inherits those
      /// properties.
      RearSticky =	0x05,	// 00000101

      /// Like RearSticky, but if the inserted text inherits no
      /// properties from the preceding character, it inherits
      /// BothSticky properties from the following character if any.
      BothSticky =	0x07,	// 00000111

      /// This property is deleted from a span of text if the span is
      /// modified (i.e. one of a character is changed, a text is
      /// inserted, some part is deleted).  Here, "span" means a
      /// sequence of characters that has this property with the same
      /// value.  This property is also deleted if a property of the
      /// same key is added, which means that this property is not
      /// stackable.  In addition this property is never merged with
      /// the same value of preceding or following property.  At last,
      /// this property can't be sticky in any way.
      Sensitive = 	0x10,	// 00010000

      /// Like Sensitive but also this property is deleted from a span
      /// of text if a characeter just before the span is modified,
      /// inserted, or deleted.
      FrontSensitive =	0x30,	// 00110000

      /// Like Sensitive but also this property is deleted from a span
      /// of text if a character just after the span is modified,
      /// inserted, or deleted.
      RearSensitive = 	0x50,	// 01010000

      /// Same as (FrontSensitive | RearSensitive).
      BothSensitive =	0x70,	// 01110000
    };

    internal MSymbol key;
    internal object val;

    public MSymbol Key { get { return key; } }
    public object Val { get { return val; } }

    public MProperty (MSymbol key, object val)
    {
      if (key.flags == null)
	key.flags = Flags.None;
      this.key = key;
      this.val = val;
    }

    public MProperty (string name, object val)
    {
      key = MSymbol.PropertyKey (name);
      this.val = val;
    }

    public static bool HasFlags (MSymbol key, Flags flags)
    {
      return ((key.flags & flags) == flags);
    }

    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 = false;

    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 (Char.IsHighSurrogate (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 (Char.IsHighSurrogate (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 (byte[] str, int offset, int length)
      {
	sb = new StringBuilder (utf8.GetString (str, offset, length));
	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 MText (int c, int len) : this ()
      {
	while (len-- > 0)
	  this.Cat (c);
      }

    public MText (int c) : this (c, 1) { }

    public static MText operator+ (object obj, MText mt)
    {
      if (obj is string)
	{
	  MText mtnew = new MText ((string) obj);
	  return mtnew.Ins (mtnew.Length, mt);
	}
      throw new Exception ("Unknown object type: " + obj.GetType());
    }

    public static MText operator+ (MText mt, object obj)
    {
      if (obj is string)
	return mt + new MText ((string) obj);
      if (obj is int)
	return mt.Dup ().Ins (mt.Length, (int) obj);
      if (obj is char)
	return mt.Dup ().Ins (mt.Length, (int) ((char) obj));
      throw new Exception ("Unknown object type: " + obj.GetType());
    }

    public static MText operator+ (MText mt1, MText mt2)
    {
      return mt1.Dup ().Ins (mt1.Length, mt2);
    }

    // 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 (); }

    public static implicit operator MText (string str)
    {
      return new MText (str);
    }

    public static explicit operator string (MText mt)
    {
      return mt.ToString ();
    }

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

    private static int dec_idx (StringBuilder sb, int i)
    {
      return (i - (Char.IsLowSurrogate (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 pos;
	  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);

      if (M17n.debug)
	{
	  Console.Write ("inserting {0} to {1} of ", from, to);
	  mt2.DumpPropNested ();
	}
      if (from == to)
	return;
      foreach (MPlist plist in intervals)
	{
	  MInterval root = (MInterval) plist.Val;
	  MPlist p = mt2.intervals.Find (plist.Key);
	  MInterval i = p == null ? null : (MInterval) p.Val;

	  root.Insert (pos, i, from, to);
	}
      foreach (MPlist plist in mt2.intervals)
	if (intervals.Find (plist.Key) == null)
	  {
	    MInterval root;

	    if (nchars == 0)
	      root = ((MInterval) plist.Val).Copy (this, from, to);
	    else
	      {
		root = new MInterval (plist.Key, this);
		root.Insert (pos, (MInterval) plist.Val, from, to);
	      }
	    intervals.Push (plist.Key, root);
	  }

      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;
    }

    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, null, 0, 1);
    }

    public int this[int i]
    {
      set {
	i = pos_to_idx (this, i);
	if (value < 0x10000)
	  {
	    if (Char.IsHighSurrogate (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 (! Char.IsHighSurrogate (sb[i]))
	      sb.Insert (i, 0);
	    sb[i] = high;
	    sb[i + 1] = low;
	  }
	PopProp (i, i + 1);
      }
      get {
	i = pos_to_idx (this, i);
	return (Char.IsHighSurrogate (sb[i])
		? ((sb[i] - 0xD800) << 10) + (sb[i + 1] - 0xDC00) + 0x10000
		: sb[i]);
      }
    }

    public MText this[int from, int to]
    {
      set {
	if (from < to)
	  Del (from, to);
	if (value != null)
	  Ins (from, value);
      }
      get { return Dup (from, to); }
    }

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

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

    public MText Dup (int from, int to)
    {
      if (check_range (from, to, true))
	return new MText ();
      int from_idx = pos_to_idx (this, from);
      int len = pos_to_idx (this, to) - from_idx;
      MText mt = new MText (sb.ToString ().Substring (from_idx, len));

      foreach (MPlist p in intervals)
	mt.intervals.Add (p.Key, ((MInterval) p.Val).Copy (mt, from, to));
      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 Cat (MText mt)
    {
      insert (nchars, mt, 0, mt.Length);
      return this;
    }

    public MText Cat (MText mt, int from, int to)
    {
      insert (nchars, mt, from, to);
      return this;
    }

    public MText Del ()
    {
      return Del (0, Length);
    }

    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 root = (MInterval) plist.Val;
	    root.Delete (from, to);
	    if (from > 0 && from < nchars)
	      ((MInterval) plist.Val).MergeAfterChange (from, from);
	  }
      else
	intervals.Clear ();
      if (M17n.debug)
	DumpPropNested ();
      return this;
    }

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

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

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

    public object GetProp (int pos, MSymbol key, out MProperty 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 MProperty[] array)
    {
      check_pos (pos, false);

      MInterval i = (MInterval) intervals.Get (key);
      if (i == null)
	return (array = null);
      MProperty 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 MProperty (key, val));
    }

    public void PushProp (int from, int to, MProperty 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;
	      if (root.isSensitive)
		{
		  root.PopSensitive (from, to);
		  root.MergeAfterChange (from, to);
		  root = (MInterval) p.Val;
		  if (M17n.debug)
		    DumpPropNested ();
		}
	    }
	  root.Push (from, to, prop);
	  root.MergeAfterChange (from, to);
	  root.Balance ();
	}
    }

    public void PopProp (int from, int to)
    {
      if (from < 0)
	{
	  default_property = null;
	}
      else
	{
	  if (check_range (from, to, true))
	    return;
	  for (MPlist p = intervals; ! p.IsEmpty; p = p.next)
	    {
	      MInterval root = (MInterval) p.Val;
	      root.PopAll (from, to);
	      root = (MInterval) p.Val;
	      if (M17n.debug)
		DumpPropNested ();
	      root.MergeAfterChange (from, to);
	      root.Balance ();
	    }
	}
    }

    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 root = (MInterval) p.Val;
	      if (root.isSensitive)
		root.PopSensitive (from, to);
	      else
		root.Pop (from, to);
	      root = (MInterval) p.Val;
	      if (M17n.debug)
		DumpPropNested ();
	      root.MergeAfterChange (from, to);
	      root.Balance ();
	    }
	}
    }

    public object FindProp (MSymbol key, int pos, out int from, out int to)
    {
      from = 0;
      to = Length;
      check_pos (pos, false);
      
      MInterval i = (MInterval) intervals.Get (key);
      if (i != null
	  && (i = i.Find (pos, out from, out to)) != null)
	return GetProp (from, key);
      return null;
    }

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

    public void DumpPropNested ()
    {
      Console.WriteLine ("total length = {0}", Length);
      foreach (MPlist p in intervals)
	((MInterval) p.Val).DumpNested (true);
    }

    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++;
      }

      /// POS must be smaller than Length;
      public MProperty Get (int pos)
      {
	MInterval i = find_head (pos);

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

      /// POS must be smaller than Length;
      public MProperty Get (int pos, out MProperty[] array)
      {
	MInterval i = find_head (pos);

	if (i.To == pos)
	  i = i.Next;
	if (i.Stack.IsEmpty)
	  {
	    array = null;
	    return null;
	  }
	array = new MProperty[i.Stack.Count];

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

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

      private bool isRearSticky
      {
	get { return MProperty.HasFlags (Key, MProperty.Flags.RearSticky) ; }
      }

      private bool isFrontSticky
      {
	get { return MProperty.HasFlags (Key, MProperty.Flags.FrontSticky) ; }
      }

      public bool isSensitive
      {
	get { return MProperty.HasFlags (Key, MProperty.Flags.Sensitive) ; }
      }

      public bool isFrontSensitive
      {
	get { return MProperty.HasFlags (Key,
					 MProperty.Flags.FrontSensitive) ; }
      }

      public bool isRearSensitive
      {
	get { return MProperty.HasFlags (Key,
					 MProperty.Flags.RearSensitive) ; }
      }

      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 {
	  update_from_to ();
	  if (Left == null)
	    return this;
	  return Left.LeftMost;
	}
      }

      private MInterval RightMost
      {
	get {
	  update_from_to ();
	  if (Right == null)
	    return this;
	  return Right.RightMost;
	}
      }

      private MInterval Prev {
	get {
	  MInterval i;

	  if (Left != null)
	    {
	      for (i = Left; i.Right != null; i = i.Right)
		i.update_from_to ();
	      i.update_from_to ();
	    }
	  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)
		i.update_from_to ();
	      i.update_from_to ();
	    }
	  else
	    {
	      MInterval child = this;
	      for (i = Parent; i != null && i.Right == child;
		   child = i, i = i.Parent);
	    }
	  return i;
	}
      }

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

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

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

	if (Stack.IsEmpty && i.Stack.IsEmpty)
	  return true;
	if (isSensitive)
	  return false;
	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 ()
      {
	MInterval c1 = Right.Left;

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

	// Update Right.
	Right.Parent = Parent;
	Right.Left = this;
	Right.Length += LeftLength + (To - From);

	// Update this.
	Parent = Right;
	Right = c1;
	Length = LeftLength + (To - From) + RightLength;

	// Update C1 if necessary.
	if (c1 != null)
	  c1.Parent = this;

	Parent.update_from_to ();
	return Parent;
      }

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

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

	// Update Left.
	Left.Parent = Parent;
	Left.Right = this;
	Left.Length += (To - From) + RightLength;

	// Update this.
	Parent = Left;
	Left = c2;
	Length = LeftLength + (To - From) + RightLength;

	// Update C2 if necessary.
	if (c2 != null)
	  c2.Parent = this;

	Parent.update_from_to ();
	return Parent;
      }

      public MInterval Find (int pos, out int from, out int to)
      {
	MInterval i = find_head (pos);

	from = to = pos;
	if (i.Stack.IsEmpty)
	  i = i.Next;
	if (i != null)
	  {
	    from = i.From;
	    to = i.To;
	  }
	return i;
      }

      public MInterval Balance ()
      {
	MInterval i = this;

	update_from_to ();
	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;
		M17n.DebugPrint ("balancing #{0} by promoting left...", i.ID);
		i = i.promote_left ();
		M17n.DebugPrint ("done\n");
		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;
		M17n.DebugPrint ("balancing #{0} by promoting right\n", i.ID);
		i = i.promote_right ();
		i.Left.Balance ();
	      }
	    else
	      break;
	  }
	return i;
      }

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

	update_from_to ();

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

	copy = new MInterval (Key, null, end - start, Stack);
	copy.mtext = mt;
	if (isSensitive && (From < start || end < To))
	  copy.Stack.Clear ();
	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;
      }

      public MInterval Copy (MText mt, int start, int end,
			     bool first, bool last)
      {
	MInterval copy = Copy (mt, start, end);
	MInterval head = find_head (start);
	MInterval tail = find_tail (end);

	M17n.DebugPrint ("Copying: {0}", copy);

	if (! head.Stack.IsEmpty
	    && (isSensitive && head.From < start
		|| (isFrontSensitive && ! first)))
	  {
	    M17n.DebugPrint (" clear head");
	    head = copy.find_head (0);
	    head.Stack.Clear ();
	  }
	if (! tail.Stack.IsEmpty
	    && (isSensitive && end < tail.To
		|| (isRearSensitive && ! last)))
	  {
	    M17n.DebugPrint (" clear tail");
	    tail = copy.find_tail (copy.Length);
	    tail.Stack.Clear ();
	  }
	M17n.DebugPrint ("\n");
	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 {1}\n", pos, this);
	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 {1}\n", pos, this);
	From = pos;
	if (Left != null)
	  {
	    interval.Left = Left;
	    Left.Parent = interval;
	    interval.Length += Left.Length;
	  }
	interval.Parent = this;
	Left = interval;
	return interval;
      }

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

      private void enlarge (int len)
      {
	Length += len;
	To += len;
	for (MInterval prev = this, i = this.Parent; i != null;
	     prev = i, i = i.Parent)
	  {
	    i.Length += len;
	    if (prev == i.Left)
	      {
		i.From += len;
		i.To += len;;
	      }
	  }
      }

      private int graft_forward (MInterval interval, int start, int end)
      {
	int len;

	if (! Stack.IsEmpty && isRearSticky)
	  len = end - start;
	else if (interval == null)
	  len = Stack.IsEmpty ? end - start : 0;
	else
	  {
	    MInterval i = interval.find_head (start);

	    len = 0;
	    if (Stack.IsEmpty
		&& (isFrontSensitive || (isSensitive && i.From < start)))
	      {
		M17n.DebugPrint (" forward grafting {0}", i);
		if (i.To < end)
		  len = i.To - start;
		else
		  len = end - start;
		i = i.Next;
	      }
	    while (i != null && i.From < end && mergeable (i))
	      {
		M17n.DebugPrint (" forward grafting {0}", i);
		len += i.To - i.From;
		if (i.From < start)
		  len -= start - i.From;
		if (i.To >= end)
		  {
		    len -= i.To - end;
		    break;
		  }
		i = i.Next;
	      }
	  }

	M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
	if (len > 0)
	  enlarge (len);
	return len;
      }

      private int graft_backward (MInterval interval, int start, int end)
      {
	int len;

	if (! Stack.IsEmpty && isFrontSticky)
	  len = end - start;
	else if (interval == null)
	  len = Stack.IsEmpty ? end - start : 0;
	else
	  {
	    MInterval i = interval.find_tail (end);

	    len = 0;
	    if (Stack.IsEmpty
		&& (isRearSensitive || (isSensitive && end < i.To)))
	      {
		M17n.DebugPrint (" backward grafting {0}", i);
		if (i.From <= start)
		  len = end - start;
		else
		  len = end - i.From;
		i = i.Prev;
	      }
	    while (i != null && i.To <= start && mergeable (i))
	      {
		M17n.DebugPrint (" backward grafting {0}", i);
		len += i.To - i.From;
		if (end < i.To)
		  len -= i.To - end;
		if (i.From <= start)
		  {
		    len -= start - i.From;
		    break;
		  }
		i = i.Prev;
	      }
	  }

	M17n.DebugPrint (" grafted {0} in {1}\n", len, this);
	if (len > 0)
	  enlarge (len);
	return len;
      }

      public void Insert (int pos, MInterval interval, int start, int end)
      {
	update_from_to ();

	M17n.DebugPrint ("insert({0} to {1}) at {2} in {3}",
			 start, end, pos, this);

	if (pos < From)
	  Left.Insert (pos, interval, start, end);
	else if (pos == From)
	  {
	    MInterval prev = Left != null ? Prev : null;

	    if (isFrontSensitive)
	      Stack.Clear ();
	    if (prev != null && isRearSensitive)
	      prev.Stack.Clear ();
	    if (prev != null && isRearSticky && ! prev.Stack.IsEmpty)
	      {
		prev.enlarge (end - start);
		M17n.DebugPrint (" done\n");
		return;
	      }
	    if (isFrontSticky && ! Stack.IsEmpty)
	      {
		enlarge (end - start);
		M17n.DebugPrint (" done\n");
		return;
	      }
	    bool front_grafted = false, rear_grafted = false;
	    int grafted;
	    if (prev != null
		&& (grafted = prev.graft_forward (interval, start, end)) > 0)
	      {
		start += grafted;
		if (start == end)
		  {
		    M17n.DebugPrint (" done\n");
		    return;
		  }
		front_grafted = true;
	      }
	    if ((grafted = graft_backward (interval, start, end)) > 0)
	      {
		end -= grafted;
		if (start == end)
		  {
		    M17n.DebugPrint (" done\n");
		    return;
		  }
		rear_grafted = true;
	      }

	    if (interval != null)
	      interval = interval.Copy (mtext, start, end,
					(front_grafted
					 || (prev == null && start == 0)),
					rear_grafted);
	    else
	      interval = new MInterval (Key, mtext, end - start, 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)
	  {
	    if (! Stack.IsEmpty)
	      {
		if (isSensitive)
		  Stack.Clear ();
		else if (isFrontSticky || isRearSticky)
		  {
		    enlarge (end - start);
		    return;
		  }
	      }
	    bool front_grafted = false, rear_grafted = false;
	    int grafted;
	    if ((grafted = graft_forward (interval, start, end)) > 0)
	      {
		start += grafted;
		if (start == end)
		  {
		    M17n.DebugPrint (" done\n");
		    return;
		  }
		front_grafted = true;
		pos += grafted;
	      }
	    if ((grafted = graft_backward (interval, start, end)) > 0)
	      {
		end -= grafted;
		if (start == end)
		  {
		    M17n.DebugPrint (" done\n");
		    return;
		  }
		rear_grafted = true;
	      }
	    if (interval != null)
	      interval = interval.Copy (mtext, start, end,
					front_grafted, rear_grafted);
	    else
	      interval = new MInterval (Key, mtext, end - start, 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 = Right != null ? Next : null;

	    if (isRearSensitive)
	      Stack.Clear ();
	    if (next != null && isFrontSensitive)
	      next.Stack.Clear ();
	    if (isRearSticky && ! Stack.IsEmpty)
	      {
		enlarge (end - start);
		M17n.DebugPrint (" done by enlarging this\n");
		return;
	      }
	    if (next != null && isFrontSticky && ! next.Stack.IsEmpty)
	      {
		M17n.DebugPrint (" next is {0}\n", next);
		next.enlarge (end - start);
		M17n.DebugPrint (" done by enlarging next\n");
		return;
	      }
	    bool front_grafted = false, rear_grafted = false;
	    int grafted;
	    if (next != null
		&& (grafted = next.graft_backward (interval, start, end)) > 0)
	      {
		end -= grafted;
		if (start == end)
		  {
		    M17n.DebugPrint (" done\n");
		    return;
		  }
		rear_grafted = true;
	      }
	    if ((grafted = graft_forward (interval, start, end)) > 0)
	      {
		start += grafted;
		if (start == end)
		  {
		    M17n.DebugPrint (" done\n");
		    return;
		  }
		front_grafted = true;
	      }
	    if (interval != null)
	      interval = interval.Copy (mtext, start, end,
					front_grafted,
					(rear_grafted
					 || (next == null && end == interval.mtext.Length)));
	    else
	      interval = new MInterval (Key, mtext, end - start, 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)
	  Right.Insert (pos, interval, start, end);
	M17n.DebugPrint (" done\n");
      }

      private void vacate_node (MInterval interval)
      {
	vacate_node (interval, null);
      }

      private void vacate_node (MInterval interval, MInterval stop)
      {
	if (interval != null)
	  M17n.DebugPrint ("vacate #{0} to #{1}\n", ID, interval.ID);
	else
	  M17n.DebugPrint ("vacate #{0} to null\n", 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 != stop; i = i.Parent)
	      i.Length -= diff;
	  }
      }

      public void Delete (int start, int end)
      {
	update_from_to ();
	M17n.DebugPrint ("delete({0} {1}) from {2}\n", start, end, this);

	bool front_checked = false;
	bool rear_checked = false;

	if (start < From)
	  {
	    if (end <= From)
	      {
		if (end == From && isFrontSensitive)
		  Stack.Clear ();
		Left.Delete (start, end);
		return;
	      }
	    if (isSensitive)
	      Stack.Clear ();
	    Left.Delete (start, From);
	    To -= From - start;
	    end -= From - start;
	    From = start;
	    front_checked = true;
	  }
	if (end > To)
	  {
	    if (start >= To)
	      {
		if (start == To && isRearSensitive)
		  Stack.Clear ();
		Right.Delete (start, end);
		return;
	      }
	    if (isSensitive)
	      Stack.Clear ();
	    Right.Delete (To, end);
	    end = To;
	    rear_checked = true;
	  }
	if (start == From
	    && ! front_checked
	    && start > 0
	    && isRearSensitive)
	  Prev.Stack.Clear ();
	if (end == To
	    && ! rear_checked
	    && Next != null
	    && isFrontSensitive)
	  Next.Stack.Clear ();
	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;

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

      public void Push (int start, int end, MProperty prop)
      {
	update_from_to ();
	M17n.DebugPrint ("push({0} {1}) at {2}\n", start, end, this);
	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 (! Stack.IsEmpty && isSensitive)
	  Stack.Clear ();
	if (start > From)
	  divide_left (start);
	if (end < To)
	  divide_right (end);
	Stack.Push (prop.key, prop);
      }

      /// Combine intervals between HEAD and TAIL (both inclusive) to
      /// the common parent of HEAD and TAIL.  Callers should assure
      /// that the intervals are mergeable in advance.
      private static void combine (MInterval head, MInterval tail)
      {
	M17n.DebugPrint ("combining {0} through {1}", head, tail);

	head.update_from_to ();
	tail.update_from_to ();
	int from = head.From;
	int to = tail.To;

	// The nearest common parent of HEAD and TAIL.
	MInterval root;
	for (root = head; root.To + root.RightLength < to;
	     root = root.Parent);
	
	M17n.DebugPrint (" with common root {0}\n", root);

	if (from < root.From)
	  {
	    MInterval prev = root.Prev;

	    while (true)
	      {
		M17n.DebugPrint ("merging {0}\n", prev);
		prev.vacate_node (prev.Left, root);
		if (prev == head)
		  break;
		if (prev.Left != null)
		  prev = prev.Left.RightMost;
		else
		  prev = prev.Parent;
	      }
	    root.update_from_to ();
	  }
	if (root.To < to)
	  {
	    MInterval next = root.Next;

	    while (true)
	      {
		M17n.DebugPrint ("merging {0}\n", next);
		next.vacate_node (next.Right, root);
		if (next == tail)
		  break;
		if (next.Right != null)
		  next = next.Right.LeftMost;
		else
		  next = next.Parent;
	      }
	    root.update_from_to ();
	  }
      }

      public void MergeAfterChange (int start, int end)
      {
	update_from_to ();

	MInterval head = find_head (start), i = head;
	MInterval tail = start < end ? find_tail (end) : head;

	if (tail.To < Length)
	  tail = tail.Next;

	if (start == head.From && start > 0)
	  {
	    MInterval prev = head.Prev;
	    if (head.mergeable (prev))
	      head = prev;
	  }
	M17n.DebugPrint ("merge between {0} and {1}\n", head, tail);
	while (i != tail)
	  {
	    MInterval next = i.Next;

	    if (! i.mergeable (next))
	      {
		if (head != i)
		  combine (head, i);
		head = next;
	      }
	    i = next;
	  }
	if (head != i)
	  combine (head, i);
      }

      public void Pop (int start, int end)
      {
	update_from_to ();
	M17n.DebugPrint ("pop({0} {1}) at {2}\n", start, end, this);
	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)
	  {
	    if (isSensitive)
	      Stack.Clear ();
	    else
	      {
		if (start > From)
		  divide_left (start);
		if (end < To)
		  divide_right (end);
		Stack.Pop ();
	      }
	  }
      }

      public void PopSensitive (int start, int end)
      {
	update_from_to ();
	MInterval head = find_head (start);
	MInterval tail = find_tail (end);
	Pop (head.From, tail.To);
      }

      public void PopAll (int start, int end)
      {
	update_from_to ();
	M17n.DebugPrint ("popall({0} {1}) at {2}\n", start, end, this);
	if (start < From)
	  {
	    if (end <= From)
	      {
		Left.PopAll (start, end);
		return;
	      }
	    Left.PopAll (start, From);
	    start = From;
	  }
	if (end > To)
	  {
	    if (start >= To)
	      {
		Right.PopAll (start, end);
		return;
	      }
	    Right.PopAll (To, end);
	    end = To;
	  }

	if (! Stack.IsEmpty)
	  {
	    if (isSensitive)
	      Stack.Clear ();
	    else
	      {
		if (start > From)
		  divide_left (start);
		if (end < To)
		  divide_right (end);
		Stack.Clear ();
	      }
	  }
      }

      public override string ToString ()
      {
	string str = String.Format ("#{0}({1} {2} {3} [", ID, Length, From, To);
	bool first = true;
	foreach (MPlist p in Stack)
	  {
	    if (first)
	      {
		str += ((MProperty) p.Val).Val;
		first = false;
	      }
	    else
	      str += " " + ((MProperty) p.Val).Val;
	  }
	return (str + "])");
      }

      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 && ! Stack.IsEmpty)
	      {
		string prepend = " [";
		foreach (MPlist p in Stack)
		  {
		    Console.Write (prepend + ((MProperty) p.Val).Val);
		    prepend = " ";
		  }
		Console.Write ("]");
	      }
	    Console.Write (")");
	    if (newline)
	      Console.WriteLine ();
	    if (Length <= 0)
	      throw new Exception ("Invalid interval length");
	  }
      }

      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);
	  }
      }

      private int Depth {
	get { return (Parent == null ? 0 : Parent.Depth + 1); }
      }

      public void DumpNested (bool force)
      {
	DumpNested ("  " + Key.ToString () + ":", force);
      }

      public void DumpNested (string indent, bool force)
      {
	if (force || M17n.debug)
	  {
	    int indent_type = (Parent == null ? 1
			       : Parent.Left == this ? 0 : 2);

	    update_from_to ();
	    if (Left != null)
	      {
		if (indent_type <= 1)
		  Left.DumpNested (indent + "  ", force);
		else
		  Left.DumpNested (indent + "| ", force);
	      }
	    Console.Write (indent);
	    if (indent_type == 0)
	      Console.Write (".-");
	    else if (indent_type == 2)
	      Console.Write ("`-");
	    DumpOne (true, true, true);
	    if (Right != null)
	      {
		if (indent_type >= 1)
		  Right.DumpNested (indent + "  ", force);
		else
		  Right.DumpNested (indent + "| ", force);
	      }
	  }
      }
    }

    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];
	}
      }
    }
  }
}