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));
#if false
      if (root_interval != null)
	{
	  MInterval interval;

	  if (mt2.root_interval != null)
	    interval = mt2.root_interval.Copy (from, to);
	  root_interval.Insert (pos, interval);
	}
#endif
      nchars += to - from;
    }

    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 (0, true, sb.Length, true);
      root_interval.Push (from, to, prop);
    }

    private class MInterval
    {
      // 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 relatie to
      // the parent's total_end.
      private int total_start, total_end;
      // Stack of MTextProperty
      private Stack<MTextProperty> stack;
      private int depth;
      private MInterval left, right, parent;

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

      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> ();
	this.depth = 1;
      }

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

      public MInterval Copy (int start, int end, MInterval interval)
      {
	MInterval new_interval;

	start = adjust_position (start, true);
	end  = adjust_position (end, true);
	new_interval = new MInterval (start, end, interval.stack);
	return new_interval;
      }

      private MInterval Copy ()
      {
	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 interval;

	  if (left != null)
	    for (interval = left;
		 interval.right != null;
		 interval = interval.right);
	  else
	    for (interval = parent;
		 interval != null && interval.total_start == 0;
		 interval = interval.parent);

	  return interval;
	}
      }

      private MInterval Right {
	get {
	  MInterval interval;

	  if (right != null)
	    for (interval = right;
		 interval.left != null;
		 interval = interval.left);
	  else
	    for (interval = parent;
		 interval != null && interval.total_start < 0;
		 interval = interval.parent);

	  return interval;
	}
      }

      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 start, int end, MInterval interval)
      {
      }

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

	if (left == null || (right != null && left.depth < right.depth))
	  {
	    interval.left = this;
	    interval.right = right;
	    interval.parent = parent;
	    if (parent != null)
	      {
		if (total_start == 0)
		  parent.left = interval;
		else
		  parent.right = interval;
	      }
	    interval.depth = depth;
	    if (right == null)
	      interval.depth++;
	    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 = Copy ();
	int this_start = Start;
	int this_end = End;

	if (left == null || (right != null && left.depth < right.depth))
	  {
	    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;
	      }
	    interval.depth = depth;
	    if (left == null)
	      interval.depth++;
	    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];
	}
      }
    }
  }
}