LazyQueue

LazyQueue.hx

enum StreamCell<T> {
    Cons(x : T, t : Stream<T>) : StreamCell<T>;
    Nil : StreamCell<T>;
}
typedef Stream<T> = Void -> StreamCell<T>

class LazyList<T> {
    private var body : Stream<T>;
    private static var nil = function () : StreamCell<T> {
        return Nil; 
    };
    public var n : Int;
    
    public function new(?s : Stream<T>, ?n = 0) {
        s == null ? this.body = nil : this.body = s;
        this.n = n;
    }
    
    public inline function cons(x : T) : LazyList<T> {
        var s = this.toStream();
        return new LazyList(function() : StreamCell<T> {
            return Cons(x, s);
        }, this.n + 1);
    }
    
    public inline function hd() : T  {
        return switch(this.body()) {
            case Nil: throw "hd error!";
            case Cons(h, _): h;
        }
    }
    
    public inline function tl() : LazyList<T> {
        return switch(this.body()) {
            case Nil: new LazyList();
            case Cons(_, t): new LazyList(t);
        }
    }
    
    public inline function append(a : LazyList<T>) : LazyList<T> {
        function loop (x : Stream<T>, y : Stream<T>) : Stream<T> {
            return switch (x()) {
                case Nil: y;
                case Cons(h, t): function () : StreamCell<T> {
                    return Cons(h, loop(t, y));
                };
            };
        }
        
        return new LazyList(loop(this.body, a.body), this.n + a.n );
    }
    
    public inline function reverse() : LazyList<T> {
        function loop(s : Stream<T>, a : Stream<T>) : Stream<T> {
            return switch(s()) {
                case Nil : a;
                case Cons(h, t): 
                    loop(t, function () { return Cons(h, a); } );
            }
        }
        
        return new LazyList(loop(this.body, nil), this.n);
    }
    
    public inline function take(n : Int) : LazyList<T> {
        return new LazyList<T>(function () : StreamCell<T> {
            return switch (n) {
                  case 0: Nil;
                   case i: (this.tl().take(i - 1).cons(this.hd()).toStream())();
            }
        }, n);
    }
    
    public inline function toStream() : Stream<T> {
        return this.body;
    }
    
    public inline function toArray() : Array<T> {
        function loop(s : Stream<T>) {
            return switch(s()) {
                case Nil: [];
                case Cons(h, t): [h].concat(loop(t));
            };
        }
        
        return loop(this.body);
    }
    
    public inline function length() : Int {
        return this.n;
    }
}

typedef Tuple<T, U> = {
    var fst : T;
    var snd : U;
}
    
class Queue<T> {
    private var l : Array<T>;
    private var r : Array<T>;
    
    public function new (?l : Array<T>, ?r : Array<T>) {
        this.l = (l == null ? [] : l);
        this.r = (r == null ? [] : r);   
    }
    
    public inline function insert(e : T) : Queue<T> {
        var l = this.l;
        l.push(e);
        
        return new Queue<T>(l, this.r);
    }
    
    public inline function remove() : Tuple<T, Queue<T>>{
        var revl = this.l;
        revl.reverse();
        
        return switch(this.r.length) {
            case 0: (new Queue<T>([], revl)).remove();
            case i: {fst : this.r[i - 1], snd : new Queue<T>(this.l, this.r.slice(0, i - 1))};
        }
    }
    
    public inline function toArray() : Array<T> {
        var revr = this.r;
        revr.reverse();
        
        return this.l.concat(revr);
    }
}
    
class LazyQueue<T> {
    private var l : LazyList<T>;
    private var r : LazyList<T>;
    
    public function new(?l : LazyList<T>, ?r : LazyList<T>) {
        this.l = (l == null ? new LazyList<T>() : l);
        this.r = (r == null ? new LazyList<T>() : r);
    }

    // rotate(L, R) = L.append(R.reverse()) if |R| = |L| + 1
    private static inline function rotate<U>(l : LazyList<U>, r : LazyList<U>, ?a : LazyList<U>) : LazyList<U> {
        if (a == null)
            a = new LazyList<U>(); 
        
        return new LazyList<U>(function () : StreamCell<U> {
            return switch((l.toStream())()) {
                case Nil: (a.cons(r.hd()).toStream())();
                case Cons(h, t): (rotate(l.tl(), r.tl(), a.cons(r.hd())).cons(h).toStream())();
            };
        }, l.length() + r.length());
    }
    
    private static inline function makeq<T>(l : LazyList<T>, r : LazyList<T>) {
        if (r.length() == l.length() + 1) {
            return new LazyQueue(rotate(l, r));
        } else {
            return new LazyQueue(l, r);
        }
    }
    
    public inline function insert(e : T): LazyQueue<T> {
        return makeq(this.l, this.r.cons(e));
    }
    
    public inline function remove() : Tuple<T, LazyQueue<T>> {
        return {fst : this.l.hd(),
                snd : makeq(this.l.tl(), this.r)};
    }
    
    public inline function toArray() : Array<T> {
        return this.l.append(this.r.reverse()).toArray();
    }
    
    public inline function length() : Int {
        return this.l.length() + this.r.length();
    }
}

class Test {
    static function benchmark (str, f) {
        var a = 0.0;
        
        for (i in 0 ... 10) {
            var timer = Date.now().getTime();
            f();
            a += Date.now().getTime() - timer;
        }
        
        trace("----" + str + "----");
        trace(a / 10);
        trace("---- end ----");
    }
    
    static function main() {        
        benchmark("Queue 100000", function () {
            var a = new Queue<Int>();
            
            for (i in 0 ... 100000) {
                a = a.insert(i);
        
                a = a.remove().snd;
            }
        });
        
        benchmark("Queue 1000000", function () {
            var a = new Queue<Int>();
            
            for (i in 0 ... 1000000) {
                a = a.insert(i);
        
                a = a.remove().snd;
            }
        });
       
        benchmark("LazyQueue 100000", function () {
            var a = new LazyQueue<Int>();
            
            for (i in 0 ... 100000) {
                a = a.insert(i);
        
                a = a.remove().snd;
            }
        });
        
        benchmark("LazyQueue 1000000", function () {
            var a = new Queue<Int>();
            
            for (i in 0 ... 1000000) {
                a = a.insert(i);
        
                a = a.remove().snd;
            }
        });
   }
}