using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
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 MProperty prop;
    internal bool front_sticky;
    internal bool rear_sticky;
    internal bool merginable;
    public MProperty Prop { get { return prop; } }
    public bool FrontSticky { get { return front_sticky; } }
    public bool RearSticky { get { return rear_sticky; } }
    public bool Merginable { get { return merginable; } }

    public MTextProperty (bool front_sticky, bool rear_sticky)
    {
      this.front_sticky = front_sticky;
      this.rear_sticky = rear_sticky;
    }
    public MTextProperty (bool front_sticky, bool rear_sticky, bool merginable)
    {
      this.front_sticky = front_sticky;
      this.rear_sticky = rear_sticky;
      this.merginable = merginable;
    }
  }

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

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

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

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

    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 insert (int pos, MText mt2, int from, int to)
    {
      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;
      if (root_interval != null)
	{
	  MInterval interval = (mt2.root_interval == null
				? new MInterval (0, false, to - from, false)
				: mt2.root_interval.CopyTree (from, to));
	  root_interval.Insert (pos, interval);
	}
    }

    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 ()
    {
      return (new MText (sb.ToString ()));
    }

    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 del (int from, int to)
    {
      sb.Remove (from, pos_to_idx (this, to) - pos_to_idx (this, from));
      nchars -= to - from;
      return this;
    }

    public void PushProp (int from, int to, MTextProperty prop)
    {
      if (root_interval == null)
	root_interval = new MInterval (this);
      root_interval.Push (from, to, prop);
    }

    private class MInterval
    {
      // position:    0           1           2           3
      // index:   -1  0  1  2  3  4  5  6  7  8  9  10 11 12 13
      //           |     |  A  |     |  B  |     |  C  |     |
      // interval  |<--------->|<--->|<--------------->|<----|
      // 
      //                   [-1 99 (9 89)]
      //       [0 10 (-1 9)]            [-10 0 (89 99)]
      // [0 4 (-1 3)] [-4 0 (5 9)] [0 4 (89 93)] [-2 0 (97 99)]
      //
      // Start and end positions of this interval and its children.
      // If this is the left node, the values are relative to the
      // parent's total_start.  Otherwise, the values are relative to
      // the parent's total_end.  So:
      //                       total_start    total_end
      //   left-side interval  0              positive even
      //   right-side interval negative even  0
      //   top-most interval   -1             positive odd
      private int total_start, total_end;
      // Stack of MTextProperty
      private Stack<MTextProperty> stack;
      private MInterval left, right, parent;
      private MText mt;

      private static int adjust_position (int pos, bool front_inclusive)
      {
	return (pos << 2) + (front_inclusive ? -1 : 1);
      }

      private static bool before_point_p (int pos)
      {
	return ((pos + 1) % 4) == 0;
      }

      public MInterval (int start, bool front_inclusive,
			int end, bool rear_inclusive)
      {
	if (start > end)
	  throw new Exception ("Invalid Interval Range");
	this.total_start = (start << 2) + (front_inclusive ? -1 : 1);
	this.total_end = (end << 2) + (rear_inclusive ? 1 : -1);
	this.stack = new Stack<MTextProperty> ();
      }

      public MInterval (MText mt)
      {
	this.mt = mt;
	this.total_start = -1;
	this.total_end = (mt.sb.Length << 2) + 1;
	this.stack = new Stack<MTextProperty> ();
      }

      private MInterval () { }

      private MInterval (int start, int end, Stack<MTextProperty> stack)
      {
	this.total_start = start;
	this.total_end = end;
	this.stack = new Stack<MTextProperty> (stack);
      }

      private MInterval find (int pos, out int offset)
      {
	if (pos < total_start || total_end < pos)
	  {
	    offset = 0;
	    return null;
	  }
	if (pos < Start)
	  return left.find (pos, out offset);
	if (End < pos)
	  return right.find (pos - total_end, out offset);
	offset = pos - Start;
	return this;
      }

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

	if (parent == null)
	  mt.root_interval = right;
	else if (total_start == 0)
	  parent.left = right;
	else
	  parent.right = right;
	right.parent = parent;
	c1 = right.left;
	right.left = this;

	parent = right;
	right = c1;
	if (c1 != null)
	  c1.parent = this;

	parent.total_start = total_start;
	parent.total_end = total_end;
	total_start = 0;
	total_end -= right_length - (c1 == null ? 0 : c1.total_end);
	
	if (c1 != null)
	  {
	    c1.total_end = - c1.total_start;
	    c1.total_start = 0;
	  }
	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.total_end;
	MInterval c2;

	if (parent == null)
	  mt.root_interval = left;
	else if (total_start == 0)
	  parent.left = left;
	else
	  parent.right = left;
	left.parent = parent;
	c2 = left.right;
	left.right = this;

	parent = left;
	left = c2;
	if (c2 != null)
	  c2.parent = this;

	parent.total_start = total_start;
	parent.total_end = total_end;
	total_start -= left_length + (c2 == null ? 0 : c2.total_end);;
	total_end = 0;
	
	if (c2 != null)
	  {
	    c2.total_start = - c2.total_end;
	    c2.total_end = 0;
	  }
	return parent;
      }

      private MInterval balance ()
      {
	MInterval interval = this;

	while (true)
	  {
	    int this_start = interval.Start;
	    int this_end = interval.End;
	    int diff = ((this_start - interval.total_start)
			- (interval.total_end - this_end));
	    int abs = Math.Abs (diff);

	    if (abs < this_end - this_start)
	      break;
	    if (diff < 0)
	      {
		interval = interval.promote_right ();
		interval.left.balance ();
	      }
	    else
	      {
		interval = interval.promote_left ();
		interval.right.balance ();
	      }
	  }
	return interval;
      }

      public MInterval CopyTree (int start, int end)
      {
	MInterval interval_start, interval_end, interval;
	int offset_start, offset_end;

	start <<= 2;
	end  <<= 2;
	interval_start = find (start, out offset_start);
	interval_end = find (end, out offset_end);

	interval = new MInterval ();
	interval.total_start = 0;
	interval.total_end = end - start;
	interval.stack = new Stack<MTextProperty> (interval_start.stack);
	interval = interval.divide_right (offset_start);
	while (interval_start != interval_end)
	  {
	    interval_start = interval_start.Right;
	    interval = interval.divide_right (interval_start.End
					      - interval_start.Start);
	  }
	return interval;
      }

      private MInterval CopyNode ()
      {
	return new MInterval (total_start, total_end, stack);
      }

      private int Start {
	get {
	  return (left == null ? total_start : total_start + left.total_end);
	}
      }

      private int End {
	get {
	  return (right == null ? total_end : total_end + right.total_start);
	}
      }

      private MInterval Left {
	get {
	  MInterval i;
	  if (left != null)
	    for (i = left; i.right != null; i = i.right);
	  else
	    for (i = parent; i != null && i.total_start == 0; i = i.parent);
	  return i;
	}
      }

      private MInterval Right {
	get {
	  MInterval i;
	  if (right != null)
	    for (i = right; i.left != null; i = i.left);
	  else
	    for (i = parent; i != null && i.total_start < 0; i = i.parent);
	  return i;
	}
      }

      public void Push (int start, int end, MTextProperty prop)
      {
	start <<= 2;
	if (prop.FrontSticky)
	  start--;
	else
	  start++;
	end <<= 2;
	if (prop.RearSticky)
	  end++;
	else
	  end--;
	if (start >= end)
	  throw new Exception ("Invalid Text Property Range");

	push (start, end, prop);
      }

      public void Insert (int pos, MInterval interval)
      {
	if (pos < Start)
	  Left.Insert (pos - total_start, interval);
	else if (pos > End)
	  Right.Insert (pos - total_end, interval);
	else
	  {
	    // position:    0           1           2           3
	    // index:   -1  0  1  2  3  4  5  6  7  8  9  10 11 12 13
	    // this      |<----------<----------->---->|
	    //           |<--------->|           |<--->|
	    // 
	    // interval  |<====>---------->|
	    //                 |<aaaa>---->|
	    //                       |<...>|
	    //                             
	    // new       |<----------<----->----->-->------------>->|
	    //           |<--------->|     |<---->-->------------>->|
	    //                                      |<----------->->|
	    //                                                   |<>|	    
	    int len = interval.total_end - interval.total_start;
	    MInterval temp;

	    total_end += len;
	    for (temp = this; temp.parent != null;
		 temp = temp.parent)
	      temp.parent.total_end += len;
	    if (End - pos < interval.End)
	      {
		

	      }

	    temp = divide_right (Start + 2);
	    temp.left = interval;
	    right = interval;
	  }	    
	    

      }

      private MInterval divide_right (int pos)
      {
	MInterval interval = CopyNode ();
	int this_start = Start;
	int this_end = End;

	if (left == null
	    || (right != null && left.total_end < - right.total_start))
	  {
	    interval.left = this;
	    interval.right = right;
	    interval.parent = parent;
	    if (parent != null)
	      {
		if (total_start == 0)
		  parent.left = interval;
		else
		  parent.right = interval;
	      }
	    total_start = 0;
	    total_end = pos - this_start;
	  }
	else
	  {
	    interval.total_start = pos - this_end;
	    interval.total_end = 0;
	    if (right != null)
	      right.parent = interval;
	    right = interval;
	  }

	return interval;
      }

      private MInterval divide_left (int pos)
      {
	MInterval interval = CopyNode ();
	int this_start = Start;
	int this_end = End;

	if (left == null
	    || (right != null && left.total_end < - right.total_start))
	  {
	    interval.total_start = 0;
	    interval.total_end = pos - this_start;
	    if (left != null)
	      left.parent = interval;
	    left = interval;
	  }
	else
	  {
	    interval.right = this;
	    interval.left = left;
	    interval.parent = parent;
	    if (parent != null)
	      {
		if (total_start == 0)
		  parent.left = interval;
		else
		  parent.right = interval;
	      }
	    total_start = pos - this_end;
	    total_end = 0;
	  }

	return interval;
      }

      private void push (int start, int end, MTextProperty prop)
      {
	int this_start = Start;
	int this_end = End;

	if (start < this_start)
	  {
	    if (end <= this_start)
	      {
		Left.push (start, end, prop);
		return;
	      }
	    Left.push (start, this_start, prop);
	    start = this_start;
	  }
	if (this_end < end)
	  {
	    if (this_end < start)
	      {
		Right.push (start, end, prop);
		return;
	      }
	    Right.push (this_end, end, prop);
	    end = this_end;
	  }
	if (this_start < start)
	  divide_left (start);
	if (end < this_end)
	  divide_right (end);
	stack.Push (prop);
      }
    }

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