package org.maths
{
    import org.maths.Fraction;
    import flash.events.EventDispatcher;
    import flash.events.Event;
    
    public class CFraction extends EventDispatcher
    {
        public var parts:Array;
        public var sign:int = 1;
        
        function CFraction() {
            parts = [];
        }
        
        protected function clone():CFraction {
            var f:CFraction = new CFraction();
            for(var i:int = 0; i < parts.length; i++) {
                var s:Fraction = parts[i] as Fraction;
                f.parts[i] = new Fraction(s.p, s.q);
            }
            return f;
        }
        
        public function add(f:Fraction):void {
            var end:int = 0;
            if(parts.length < 1)
                return;    // infinity //throw Error("cfrac underflow");
            var g:Fraction = f.clone();
            if(sign < 0)
                g.negate();
            parts[end] = (parts[end] as Fraction).plus(g);
            normaliseSign();
            notifyChange();
        }
        
        public function negate():void {
            sign = -sign;
            normaliseSign();    
        }
        
        private function invertSigns():void {
            for(var i:int = 0; i < parts.length; i++) 
                (parts[i] as Fraction).negate();
        }
        
        public function unshift(f:Fraction):void {
            var g:Fraction = f.clone();
            if(sign < 0) g.negate();
            parts.unshift(g);
            normaliseSign();
            notifyChange();
        }
        
        public function getPartAt(i:int):Fraction {
            return parts[i] as Fraction;    
        }
        
        public function evaluate(n:int = 0):Fraction {
            if(parts.length == 0)
                return new Fraction(1,0);;
            var g:Fraction = getPartAt(n);
            var f:Fraction = new Fraction(g.p,g.q);
            if(n == parts.length-1) {
                return f;
            }
            else {
                var h:Fraction = evaluate(n+1).reciprocal;
                return f.plus(h);
            }
        }
        
        public function parse(text:String):void {
            parts = [];
            text = text.replace(/(\[|\]| )*/,"");
            var sparts:Array = text.split(",");
            for(var i:int = 0; i < sparts.length; i++) {
                var s:String = (sparts[i] as String);
                var pq:Array = s.split("/");
                var pp:int;
                switch(pq.length) {
                    case 1: {
                        pp = pq[0];
                        if(isNaN(pp))
                            throw new Error("Bad Continued Fraction: " + s);
                        unshift(new Fraction(pp,1));
                        break;
                    }
                    case 2: {
                        pp = pq[0] as int;
                        if(isNaN(pp))
                            throw new Error("Bad Continued Fraction: " + s);
                        var qq:int = pq[1];
                        if(isNaN(qq))
                            throw new Error("Bad Continued Fraction: " + s);
                        unshift(new Fraction(pp,qq));
                        break;
                    }
                    default:
                        throw new Error("Bad Continued Fraction: " + s);
                }
            }
            notifyChange();
        }

        public function simplify():void {
            
            var i:int;
            var f:Fraction;
            var g:Fraction;
            var a:Fraction;
            var b:Fraction;

            
            if(parts.length < 2) return;
            
            // Remove all zero turns
            // a,0,b -> a+b   -- no-op
            for(i = 1; i >= 1 && i+1 < parts.length; i++) {
                while(parts[i]==0 && i>=1 && i+1 < parts.length) {
                    parts[i-1] = (parts[i-1] as Fraction).plus(parts[i+1] as Fraction); 
                    parts.splice(i--,2);
                }
            }
            if(parts.length < 2) {
                notifyChange();
                return;
            }
            
            // Eliminate final zero inducing an R1 move
            if((parts[parts.length-1] as Fraction).p==0) {
                parts.pop();
                parts.pop();
                trace("R1");
                notifyChange();
                return;
            }
            
            // Merge a single final twist inducing an R2 move
            f = (parts[parts.length-1] as Fraction);
            f.simplify();
            if((f.p==1 || f.p==-1) && f.q==1) {
                parts.pop();
                parts[parts.length-1] = (parts[parts.length-1] as Fraction).plus(f);
                trace("R2");
                notifyChange();
                return;
            }
            
            // If deepest part is negative, make it positive by changing overall sign
            f = (parts[parts.length-1] as Fraction);
            f.simplify();
            if(f.p < 0) {
                sign = -sign;
                invertSigns();
                //for(i=0; i < parts.length; i++)
                //    (parts[i] as Fraction).invertSigns();
            }
            
            // Now detect the deepest negative part
            for(i = parts.length-2; i >= 0; i--) {
                f = parts[i] as Fraction;
                f.simplify();
                
                if(f.p >= 0) continue;
                
                // deepest negative part detected; i is its index in parts.

                // else we have something like [...a, -b, c,...]
                if(f.p==-1 && i > 0) {
                    // may be one of the Lagrange special cases
                    g = parts[i-1] as Fraction;
                    g.simplify();
                    var a0:Array;
                    if(g.p == 1) {
                        // ...,a, 1,-1, b, ...] -> a,0,-b+1, ...]    b R3s and an R1
                        a0 = parts.splice(0,i); // a0 -> [..., a, 1]   parts -> [-1, b, ....]
                        a0.pop();
                        a0.push(new Fraction(0,1));    // a0 -> [..., a, 0]
                        parts.shift();        // parts -> [b,...]
                        invertSigns();        // parts -> [-b, -...]
                        b = parts[0] as Fraction;
                        b.simplify();
                        b.p += b.q;            // parts -> [-b+1, -...]
                        parts = a0.concat(parts); // parts -> [...,a, 0, -b+1, -...]

                        trace("R3 special 1");                            
                        notifyChange();
                        return;
                    }
                    g = parts[i+1] as Fraction;
                    g.simplify();
                    if(g.p == 1) {
                        // ...,a,-1, 1, b] -> a,0,-b-1]    b R3s and an R1
                        a0 = parts.splice(0,i+1); // a0 -> [..., a, -1]   parts -> [1, b, ....]
                        a0.pop();
                        a0.push(new Fraction(0,1));    // a0 -> [..., a, 0]
                        parts.shift();        // parts -> [b,...]
                        invertSigns();        // parts -> [-b, -...]
                        b = parts[0] as Fraction;
                        b.simplify();
                        b.p -= b.q;            // parts -> [-b-1, -...]
                        parts = a0.concat(parts); // parts -> [...,a, 0, -b-1, -...]

                        trace("R3 special 2");                            
                        notifyChange();
                        return;
                    }                     
                }
                
                // May have a sign change at zero s[-a,b] = -s[a,-b] = -s[a-1,1,b-1] 
                b = f;
                var insert:Array = [];
                if(i == 0) {
                    
                    if(parts.length == 2) {
                        // s[-a,b] -> -s[a,-b];  
                        sign = -sign;
                        a = (parts[0] as Fraction);
                        a.p = -a.p;                 // make a positive
                        a.p -= a.q;
                        b = (parts[1] as Fraction); // b remains positive
                        b.p -= b.q;
                        parts = [a,new Fraction(1,1), b]
                        
                        trace("R3 @0 length 2");
                        notifyChange();
                        return;
                    }
                    else {
                        // s[-a, b, c, ...] -> -s[a, -b, -c, ...]
                        sign = -sign;
                        var ab:Array = parts.splice(0,2); // ab -> [-a, b]; parts -> [c,...]
                        a = ab[0] as Fraction;
                        a.negate();
                        if(a.p < 0) throw new Error("unexpected -a"); // assert a is positive
                        b = ab[1] as Fraction;
                        if(b.p < 0) throw new Error("unexpected -b"); // assert b is positive
                        a.p -= a.q;     // a = a-1
                        b.p -= b.q        // b = b-1;
                        // [a, -b, -c, -...] -> [a-1, 1, b-1, c]
                        parts = [a, new Fraction(1,1), b].concat(parts);
                        // [a, -b, -c, -...] -> [a-1, 1, b-1, c]
                        
                        trace("R3 @0");
                        notifyChange();
                        return;
                    }
                }
                
                //
                //
                // TODO: The case where i==0 and parts.length > 0 is not handled correctly below
                // [a, -b, -c] = [a-1, 1, b-1, c]
                // [1, -1, -2] = [0, 1, 0, 2]
                // but algorithm below delivers -[0,0,1,0]
                //
                // or we could use [-a, b, c] -> [1-a, -1, 1-b, -c]
                
                
                /*
                if(i==0) {
                    notifyChange();
                    return;
                }
                */
                
                // set up the Lagrange general case
                // a,-b,c -> a-1,1,b-2,1,c-1
                b.negate();
                // b and c are positive at this point. a unknown
                b.p -= b.q;
                
                var c:Fraction = parts[i+1] as Fraction;
                c.p -= c.q;
                insert = [new Fraction(1,1), c];

                for(var j:int = i-1; j >= 0; j--) {
                    a = parts[j] as Fraction;
                    a.simplify();
                    if(a.p < 0) {
                        insert.unshift(b);
                        b = a;
                        //b.p -= b.q;
                    }
                    else {
                        b.p -= b.q;
                        insert.unshift(b);
                        insert.unshift(new Fraction(1,1));
                        a.p -= a.q;
                        insert.unshift(a);
                        break;
                    }
                }
                //parts.concat();
                parts.splice(j,i-j+2);
                for(var k:int = 0; k < insert.length; k++) {
                    parts.splice(j+k,0,insert[k]);
                }
                
                trace("R3 general");
                break;
                
            }
            notifyChange();
            return;
        }

        
        public function normaliseSign():void {
            for(var i:int=0; i < parts.length; i++) {
                var a:Fraction = parts[i] as Fraction;
                a.simplify();
                if(a.p > 0)
                    break;
                else if(a.p < 0) {
                    sign = -sign;
                    invertSigns();
                    break;
                }
                // if(a.p==0) continue;
            }
        }

        override public function toString():String {
            var s:String = sign>0 ? "[" : "-[";
            var sep:String = "";
            for(var i:int=0; i < parts.length; i++) {
                var f:Fraction = getPartAt(i);
                s += (sep + f);
                sep = ",";
            }
            var n:Fraction = evaluate();
            n.negate();
            return s + "]=" + (((sign > 0) ? evaluate() : n)) ;

        }
        
        public function notifyChange():void {
            normaliseSign();
            dispatchEvent(new Event("cfracChanged"));
        }
        
        //[Bindable(event="cfracChanged")]
        public function get text():String {
            return toString();
        }        
        public function set text(s:String):void {
            parse(s);
        }
    }
}