/*
 * Copyright (c) 2003-2008 The University of Wroclaw.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *    1. Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *    2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *    3. The name of the University may not be used to endorse or promote
 *       products derived from this software without specific prior
 *       written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
 * NO EVENT SHALL THE UNIVERSITY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


/* TYPE DEFINITION */

using Nemerle.Collections.List;
using NCL = Nemerle.Collections.List;
using SCG = System.Collections.Generic;
using System.Diagnostics;

namespace Nemerle.Core
{
  /** The core datastructure allowing easy manipulating of small
      and medium sized collections of elements.

      It has a builtin syntax [] for empty list, x :: xs for creating list
      from head element and tail.
   */
  [System.Serializable]
  [Nemerle.MarkOptions (System.Serializable)]  
  [Nemerle.MarkOptions (DebuggerNonUserCode)]  
  [System.Runtime.InteropServices.ComVisible(false)]
  [DebuggerDisplay("Length = {Length}: {ToString()}"), DebuggerNonUserCode]
  public variant list ['a] : 
    SCG.IEnumerable ['a], 
    Nemerle.Collections.ICovariantList ['a],
    System.IEquatable ['a]
    // , Nemerle.Collections.ICovariantEnumerable ['a] //unfortunately this is prevented by MS.NET bug
  {
    | Cons 
      {
        hd : 'a;
        [Nemerle.Extensions.CompilerMutable]
        tl : list ['a];
        
        // For debugging purpose.
        [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
        AsArray2 : array ['a] { get { _ = AsArray; ToArray () } }
      }

    | Nil { public override ToString () : string { "[]" } }

    public override ToString () : string
    {
      def sb = System.Text.StringBuilder ("[");
      concat_helper (", ", sb);
      sb.Append ("]").ToString ()
    }

    public ToString (separator : string) : string
    {
      def sb = System.Text.StringBuilder ("");
      concat_helper (separator, sb);
      sb.ToString ()
    }
    
    
    public CovariantTail : Nemerle.Collections.ICovariantList ['a] {
      get { Tail }
    }
    
    public static @== (x : list ['a], y : list ['a]) : bool
    {
      if (x : object == y)
        true
      else if (x : object == null || y : object == null)
        false
      else
        x.Equals(y)
    }

    public static @!= (x : list ['a], y : list ['a]) : bool
    {
      if (x : object == y)
        false
      else if (x : object == null || y : object == null)
        true
      else
        !x.Equals(y)
    }

    [Nemerle.OverrideObjectEquals]
    public Equals (other : list ['a]) : bool
    {
      match (this) {
        | x :: xs =>
          match (other) {
            | y :: ys when x.Equals (y) => xs.Equals (ys)
            | _ => false
          }
          
        | [] => other.IsEmpty
      }
    }

    public Equals[T2] (lst2 : list [T2], compare : 'a * T2 -> bool) : bool
    {
      NCL.Equals (this, lst2, compare)
    }

    public override GetHashCode () : int
    {
      match (this){
        | []          => 36
        | [x]         => x.GetHashCode () 
        | x :: y :: _ => x.GetHashCode () %^ y.GetHashCode ()
      }
    }

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public Length : int
    {
      get {
        NCL.Length (this)
      }
    }

    public GetElementType () : System.Type {
      _ = this; // suppress warning 
      typeof ('a)
    }

    /**
     * Returns true if the given list is empty.
     */
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public IsEmpty : bool
    {
      get {
        match (this) {
          | [] => true
          | _ => false
        }
      }
    }

    /**
     * Returns head (first element) of list.
     * Given empty list throws System.ArgumentException.
     */
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public Head : 'a {
      get {
        match (this) {
          | x :: _ => x
          | [] => throw System.ArgumentException ("List.Head called with empty list");
        }
      }
    }

    /**
     * Returns tail (all elements except the first one) of list.
     */
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public Tail : list ['a] {
      get {
        match (this) {
          | _ :: tl => tl
          | [] => throw System.ArgumentException ("List.Tail called for empty list")
        }
      }
    }

    /**
     * Returns last element of list.
     * Given empty list throws InvalidArgument exception.
     * Works in time O(n) and memory O(1).
     */
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public Last : 'a {
      get {
        NCL.Last (this)
      }
    }
    
    
    /* -- ENUMERATION SUPPORT   -------------------------------------------- */

    /**
     * Creates enumerator for elements of list.
     */
    public GetEnumerator () : Nemerle.Collections.ListEnumerator['a]
    {
      Nemerle.Collections.ListEnumerator(this)
    }

    public static @+ (x : list ['a], y : list ['a]) : list ['a]
    {
      NCL.Append (x, y)
    }


    /**
     * Returns first n elements of the list.
     * Works in time and memory O(n).
     */
    public FirstN (n : int) : list ['a]
    {
      def loop (k, acc, lst) {
        if (k == 0) Rev (acc)
        else
          match (lst) {
            | x :: xs => loop (k - 1, x :: acc, xs)
            | [] =>
              throw System.ArgumentException ("List.FirstN called for too short list")
          }
      }

      loop (n, [], this)
    }


    /** Return [this] without first [n] elements. Works in time O(n)
        and constant memory. Throws ArgumentException when called on
        too short list.  */
    public ChopFirstN (n : int) : list ['a]
    {
      def loop (n, l) {
        if (n == 0) l
        else
          match (l) {
            | _ :: xs => loop (n - 1, xs)
            | [] =>
              throw System.ArgumentException ("List.ChopFirstN called for too short list")
          }
      }
      loop (n, this)
    }


    public LastN (n : int) : list ['a]
    {
      def len = Length;
      if (n > len)
        throw System.ArgumentException ("List.LastN called for too short list")
      else
        ChopFirstN (len - n)
    }


    public Nth (n : int) : 'a {
      NCL.Nth (this, n)
    }


    /**
     * Returns reversed list, i.e. [1,2,3].Reverse().Equals ([3,2,1]).
     * Works in time and memory O(n).
     */
    public Reverse () : list ['a] {
      NCL.Rev (this)
    }
    
    /**
     * Returns list made from appending list y at end of list x.
     * Original list are not modified.
     * Works in time and memory O(length(x)).
     */
    public Append (y : list ['a]) : list ['a] {
      NCL.RevAppend (Reverse (), y)
    }
    
    /**
     * Equivalent to Reverse().Append(y), but faster.
     */
    public RevAppend (y : list ['a]) : list ['a] {
      NCL.RevAppend(this, y)
    }
    

    /**
     * Returns current list without elements equal to x.
     * Equals method is used to compare elements.
     */
    public Remove (x : 'a) : list['a]
    {
      NCL.Remove (this, x)
    }

    
    /**
     * Returns a list without its last element and the list's last element
     */
    public DivideLast () : list ['a] * 'a
    {
      NCL.DivideLast (this)
    }

    
    /* -- ITERATORS -------------------------------------------------------- */
    
    public Iter (f : 'a -> void) : void {
      NCL.Iter (this, f)
    }

    public IterI (mutable acc : int, f : int * 'a -> void) : void {
      foreach (x in this) {
        f (acc, x);
        acc++
      }
    }
    
    public Map['b] (convert : 'a -> 'b) : list ['b] {
      NCL.Map (this, convert)
    }

    public MapFiltered['b] (predicate : 'a -> bool, convert : 'a -> 'b) : list ['b] {
      NCL.MapFiltered (this, predicate, convert)
    }

    public RevMap['b] (f : 'a -> 'b) : list ['b] {
      NCL.RevMap (this, f)
    }

    public FoldLeft['b] (acc : 'b, f : 'a * 'b -> 'b) : 'b {
      NCL.FoldLeft (this, acc, f)
    }

    public FoldRight['b] (acc : 'b, f : 'a * 'b -> 'b) : 'b {
      NCL.FoldRight (this, acc, f)
    }

    public Group (cmp : 'a * 'a -> int) : list [list ['a]] {
      NCL.Group (this, cmp)
    }
    
    /* -- LIST SCANNING ----------------------------------------------------- */

    /**
     * Returns 'true' if all of the 'l' list's elements satisfy
     * the condition 'f'.
     *
     * Example of use:
     *
     *   List.ForAll ([2, 4, 6, 8], fun (x) { x % 2 == 0 })
     *
     * evaluates to 'true' as all the list's elements are even.
     */
    public ForAll (f : 'a -> bool) : bool 
    {
      NCL.ForAll (this, f)
    }
    
    public ForAll2[T2] (lst2 : list [T2], predicate : 'a * T2 -> bool) : bool 
    {
      NCL.ForAll2 (this, lst2, predicate)
    }
    
    /**
     * Returns 'true' if at least one of the 'l' list's elements
     * satisfies the condition 'f'.
     *
     * Example of use:
     *
     *   List.Exists (["a", "b", "abc", "d", "e"], fun (x) { x.Length > 2 })
     *
     * evaluates to 'true' as there is one string of length 3 on the list.
     */
    public Exists (f : 'a -> bool) : bool
    {
      NCL.Exists (this, f)
    }

    /**
     * List membership test, using the `Equals' method to compare objects.
     */
    public Contains (a : 'a) : bool
    {
      NCL.Member (this, a)
    }
    
    
    /* -- LIST SEARCHING --------------------------------------------------- */
    
    /**
     * Finds the first elements for which a predicate is true.
     */
    public Find (pred : 'a -> bool) : option ['a]
    {
      NCL.Find (this, pred)
    }

    /**
     * Finds the first elements for which a predicate is true.
     */
    public FindWithDefault (default : 'a, pred : 'a -> bool) : 'a
    {
      def loop (l) {
        | h :: t =>
          if (pred (h)) h else loop (t)
        | [] => default
      }
      loop (this)
    }

    
    
    /**
     * Returns the number of elements for which a predicate is true.
     */
    public FilteredLength (f : 'a -> bool) : int
    {
      NCL.FilteredLength (this, f)
    }

    
    /**
     * Removes elements for which predicate is false
     */
    public Filter (f : 'a -> bool) : list ['a]
    {
      NCL.Filter (this, f)
    }

    
    /**
     * Removes elements for which predicate is false.
     * The resulting list is reversed (operation is faster this way).
     */
    public RevFilter (f : 'a -> bool) : list ['a]
    {
      NCL.RevFilter (this, f)
    }


    /**
     * Return list, reversed or not, with elements not fulfilling [f] removed.
     * Avoid allocation if possible. 
     */
    public RevFilterWhenNeeded (f : 'a -> bool) : list ['a]
    {
      if (NCL.ForAll (this, f)) this
      else NCL.RevFilter (this, f)
    }

    /**
     * This is an alias for ``Filter''
     */
    public FindAll (f : 'a -> bool) : list ['a]
    {
      Filter (f)
    }


    /**
     * Partitions a list into two sublists according to a predicate.
     */
    public Partition (pred : 'a -> bool) : list ['a] * list ['a]
    {
      NCL.Partition (this, pred)
    }

    /**
     * Returns reversed list, i.e. Rev([1,2,3]) = [3,2,1].
     * Works in time and memory O(n).
     */
    public Rev () : list ['a]
    {
      NCL.Rev (this)
    }
    

    /* -- SORTING ---------------------------------------------------------- */
  
    public Sort (cmp : 'a * 'a -> int) : list ['a] 
    {
      NCL.Sort (this, cmp)
    }

    public static IsOrdered [T] (this lst : list[T], great : T * T -> bool) : bool
    {
      match (lst)
      {
        | first :: ((second :: _) as tail) => 
          if (great (first, second)) false else IsOrdered (tail, great)

        | [_] | [] | null => true
      }
    }

    public static IsOrdered[T](this lst : list[T]) : bool
      where T: System.IComparable[T]
    {
      IsOrdered(lst, (x, y) => x.CompareTo(y) > 0)
    }


    public RemoveDuplicates () : list ['a]
    {
      NCL.RemoveDuplicates (this)
    }

    // For debugging purpose.
    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    protected AsArray : array ['a]
    {
      get { ToArray () }
    }

    public ToArray () : array ['a]
    {
      def result = array (Length);
      CopyTo (result);
      result
    }
    
    /**
     * Copies first [len] elements from current list to specified array beginning with index 0
     */
    public CopyTo (dest : array ['a], len : int) : void
    {
      mutable i = 0;
      foreach (el in this) {
        when (i >= len) Nemerle.Imperative.Break ();
        dest [i] = el;
        i++;
      }
      when (i < len)
        throw System.ArgumentException ($"insufficient amount of elements in current list: expected $len, has $i");
    }

    /**
     * Copies all elements from current list to specified array beginning with index 0
     */
    public CopyTo (dest : array ['a]) : void
    {
      mutable i = 0;
      foreach (el in this) {
        dest [i] = el;
        i++;
      }
    }
    
    public MapToArray ['b] (f : 'a -> 'b) : array ['b]
    {
      def result = array (Length);
      mutable i = 0;
      foreach (x in this) {
        result [i] = f (x);
        i++;
      }
      result
    }

    // private helpers
    concat_helper (sep : string, sb : System.Text.StringBuilder) : void
    {
      def to_string (value : object)
      {
        match (value)
        {
          //| str is string => "\"" + str + "\""
          | null          => "<null>"
          | _             => value.ToString ()
        }
      };

      def loop (lst) {
        | [x] => ignore (sb.Append (to_string (x)))
        | x :: xs =>
          ignore (sb.Append (to_string (x)).Append (sep));
          loop (xs)
          
        | [] => ()
      };

      loop (this)
    }
  }
}

  
namespace Nemerle.Collections 
{
  [DebuggerNonUserCode]
  public module List
  {
    /**
     * Tests equality of two lists.  Uses Equal method of
     * objects to test wether they are the same.
     */
    public Equals['a] (x : list ['a], y : list ['a]) : bool
    {
      x.Equals (y)
    }


    /**
     * Compare two lists lexicographically over the order defined on
     * their elements with function [cmp].  Returns [-1] if [l1] is smaller,
     * [1] if [l2] is smaller, and [0] if they equal.
     */
    public static Compare ['a] (l1 : list ['a], l2 : list ['a],
                                cmp : 'a * 'a -> int) : int
    {
      match ((l1, l2)){
        | ([], []) => 0
        | ([], _) => -1
        | (_, []) => 1
        | (x :: xs, y :: ys) =>
          def ret = cmp (x, y);
          if (ret == 0){
            Compare (xs, ys, cmp)
          } else {
            ret
          }
      }
    }


    /**
     * Compare two lists lexicographically over the order defined on
     * their elements.  Returns [-1] if [l1] is smaller, [1] if [l2]
     * is smaller, and [0] if they equal.
     */
    public static Compare ['a] (l1 : list ['a], l2 : list ['a]) : int
      where 'a : System.IComparable ['a]
    {
      def cmp (x, y){
        x.CompareTo (y)
      }
      
      Compare (l1, l2, cmp)
    }


    /**
     * Returns [l] with duplicates removed with respect to Equals method
     * It is assumed that equal elements of [l] are next to each other,
     * or that the list is sorted.
     *
     * Example:
     *
     * def result = RemoveDuplicates ([1, 2, 2, 3, 4, 4]);
     *     // result = [1, 2, 3, 4]
     */
    public static RemoveDuplicates ['a] (lst : list ['a]) : list ['a]
    {
      def loop (lst, acc){
        match (lst){
          | [] => acc.Reverse ();
          | [x] => (x :: acc).Reverse ();
          | x :: ((y :: _) as xs) =>
            if (x.Equals (y)){
              loop (xs, acc)
            } else {
              loop (xs, x :: acc)
            }
        }
      }

      loop (lst, [])
    }

    
    /* -- CONVERSION OPERATIONS -------------------------------------------- */
  
    /**
     * Converts an array into a list.
     */  
    public FromArray ['a] (x : array ['a]) : list ['a] {
      def loop (index, acc) : list ['a] {
        if (index >= 0)
          loop (index - 1, x [index] :: acc)
        else
          acc
      };
    
      loop (x.Length - 1, [])
    }
    
    public ToListRev [T] (this seq : SCG.IEnumerable [T]) : list [T]
    {
      mutable lst = [];
      
      foreach (elem in seq)
        lst ::= elem;
      
      lst;
    }

    public ToListRev [T] (this seq : SCG.IEnumerable [T], filter : T -> bool) : list [T]
    {
      mutable lst = [];
      
      foreach (elem in seq)
        when (filter (elem))
          lst ::= elem;
      
      lst;
    }

    public ToList [T] (this seq : SCG.IEnumerable [T]) : list [T]
    {
      ToListRev(seq).Rev()
    }

    public ToList [T] (this source : SCG.IList [T]) : list [T]
    {
      mutable lst = [];
      
      for (mutable i = source.Count - 1; i >= 0; i--)
        lst ::= source[i];
      
      lst;
    }

    public ToList [T] (this source : SCG.IList [T], filter : T -> bool) : list [T]
    {
      mutable lst = [];
      
      for (mutable i = source.Count - 1; i >= 0; i--)
      {
        def elem = source[i];
        when (filter (elem))
          lst ::= elem;
      }
      
      lst;
    }

    public ToList [T] (this seq : SCG.IEnumerable [T], filter : T -> bool) : list [T]
    {
      ToListRev(seq, filter).Rev()
    }

    /* -- BASIC LIST OPERATIONS -------------------------------------------- */

    /**
     * Returns true if the given list is empty.
     */
    public IsEmpty ['a] (lst : list ['a]) : bool { lst.IsEmpty }
    
    /**
     * Returns length of given list. Time O(n), Mem O(1).
     */
    public Length ['a] (x : list ['a]) : int {
      def loop (acc : int, x : list ['a]) : int {
        match (x) {
          | _ :: xs => loop (acc + 1, xs)
          | _ => acc
        }
      };
      loop (0, x)
    }
    
    
    /**
     * Returns head (first element) of list.
     * Given empty list throws System.ArgumentException.
     */
    public Head ['a] (l : list ['a]) : 'a {
      l.Head
    }
    
    /**
     * Alias for Head(l).
     */
    public Hd ['a] (l : list ['a]) : 'a {
      l.Head
    }
    
    /**
     * Returns tail (all elements except first one) of list.
     */
    public Tail['a] (l : list ['a]) : list ['a] {
      l.Tail
    }
    
    /**
     * Alias for Tail(l).
     */
    public Tl['a] (l : list ['a]) : list ['a] {
      l.Tail
    }
    
    /**
     * Returns n-th element of list, where 0-th is head.
     * Throws InvalidArgument exception when given too short list.
     * Works in time O(n) and memory O(1).
     */
    public Nth['a] (l : list ['a], n : int) : 'a {
      match (l) {
        | h :: t => 
          if ( n == 0 )
            h
          else
            Nth(t, n-1)
        | [] => throw System.ArgumentOutOfRangeException ("List.Nth")
      }
    }

    /**
     * Returns last element of list.
     * Given empty list throws InvalidArgument exception.
     * Works in time O(n) and memory O(1).
     */
    public Last['a] (l : list ['a]) : 'a {
      match (l) {
        | [x] => x
        | _ :: xs => Last (xs)
        | [] => throw System.ArgumentException ("List.Last called for empty list")
      }
    }


    /**
     * Returns reversed list, i.e. Rev([1;2;3]) = [3;2;1].
     * Works in time and memory O(n).
     */
    public Rev['a] (l : list ['a]) : list ['a] {
      def loop (acc : list ['a], l : list ['a]) : list ['a] {
        match (l) {
          | x :: xs => loop (x :: acc, xs)
          | [] => acc
        }
      };
      loop ([], l)
    }
    
    /**
     * Returns list made from appending list y at end of list x.
     * Original list are not modified.
     * Works in time and memory O(length(x)).
     */
    public Append['a] (x : list ['a], y : list ['a]) : list ['a] {
      List.RevAppend (List.Rev (x), y)
    }
    
    /**
     * Equivalent to Append(Rev(x),y).
     */
    public RevAppend['a] (x : list ['a], y : list ['a]) : list ['a] {
      match (x) {
        | h :: t => RevAppend(t, h :: y)
        | [] => y
      }
    }
    
    /**
     * Makes list one level more flat, i.e. Concat([[1;2];[3;4]]) = [1;2;3;4].
     * Does not work deeper, i.e. Concat([[[1;2];[3]];[[4]]]) = [[1;2];[3];[4]].
     */
    public Concat['a] (this l : list [list ['a]]) : list ['a]
    {
      FoldLeft (l, [], fun (x, y) { Append (y, x) })
    }    

    
    /**
     * Alias for Concat(l).
     */
    public Flatten ['a] (this l : list [list ['a]]) : list ['a]
    {
      Concat (l)
    }

    
    /**
     * Returns list l without elements equal to x.
     */
    public Remove['a] (l : list['a], x : 'a) : list['a]
    {
      def loop (acc : list ['a],from : list['a]) : list['a]
      {
        match (from) {
          | [] => List.Rev(acc)
          | y :: ys  => loop( if ( y.Equals ( x ) ) acc else y::acc ,ys)
        }
      }
      
      loop ([], l)
    }

    
    /**
     * Returns a list without its last element and the list's last element
     */
    public DivideLast ['a] (l : list ['a]) : list ['a] * 'a
    {
      def loop (ls, acc) {
        match (ls) {
          | [x] => (List.Rev (acc), x)
          | x :: xs => loop (xs, x :: acc)
          | _ =>
            throw System.ArgumentException ("List.DivideLast called for empty list")
        }
      }
      
      loop (l, [])
    }

    
    /* -- ITERATORS -------------------------------------------------------- */
    
    public Iter['a] (l : list ['a], f : 'a -> void) : void {
      match (l) {
        | x :: xs => f (x); Iter (xs, f)
        | [] => ()
      }
    }

    public MapFiltered['a, 'b] (lst : list ['a], predicate : 'a -> bool, convert : 'a -> 'b) : list ['b] {
      $[ convert(x) | x in lst, predicate (x) ]
    }

    public Map['a, 'b] (lst : list ['a], convert : 'a -> 'b) : list ['b] {
      $[ convert(x) | x in lst ]
    }

    public RevMap['a, 'b] (l : list ['a], convert : 'a -> 'b) : list ['b] {
      def loop (acc : list ['b], x : list ['a]) : list ['b] {
        match (x) {
          | h :: t => loop (convert (h) :: acc, t)
          | [] => acc
        }
      };
      loop ([], l)
    }

    public RevMapFiltered['a, 'b] (l : list ['a], predicate : 'a -> bool, convert : 'a -> 'b) : list ['b] {
      def loop (acc : list ['b], x : list ['a]) : list ['b] {
        match (x) {
          | h :: t => if (predicate (h)) loop (convert (h) :: acc, t) else loop (acc, t)
          | [] => acc
        }
      };
      loop ([], l)
    }

    public FoldLeft['a, 'b] (l : list ['a], mutable acc : 'b, f : 'a * 'b -> 'b) : 'b {
      def loop (_) {
        | [] => acc
        | x :: xs =>
          acc = f (x, acc);
          loop (xs)
      }
      loop (l);
    }

    public FoldRight['a, 'b] (l : list ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
      match (l) {
        | [] => acc
        | x :: xs => f (x, FoldRight (xs, acc, f))
      }
    }
    
    public MapFromArray['a, 'b] (x : array ['a], f : 'a -> 'b) : list ['b] 
    { 
      $[ f (e) | e in x ]
    }
    
    /* -- ITERATORS ON TWO LISTS ------------------------------------------- */
    
    public Iter2['a, 'b] (a : list ['a], b : list ['b], f : 'a  * 'b -> void) : void {
      match ((a, b)) {
        | ([], []) => ()
        | (x :: xs, y :: ys) => f (x, y); Iter2 (xs, ys, f)
        | _ => throw System.ArgumentException ("List.Iter2")
      }
    }

    public Map2['a, 'b, 'c] (x : list ['a], y : list ['b], f : 'a * 'b -> 'c) : list ['c] {
      match ((x, y)) {
        | ([], []) => []
        | (x :: xs, y :: ys) => f (x, y) :: Map2 (xs, ys, f)
        | _ => throw System.ArgumentException ("List.Map2")
      }
    }

    public RevMap2['a,'b,'c] (x : list ['a], y : list ['b], f : 'a * 'b -> 'c) 
    : list ['c] 
    {
      def loop (acc : list ['c], x : list ['a], y : list ['b]) : list ['c] {
        match ((x, y)) {
          | ([], []) => acc
          | (x :: xs, y :: ys) => loop (f (x, y) :: acc, xs, ys)
          | _ => throw System.ArgumentException ("List.RevMap2")
        }
      };
      loop([], x, y)
    }

    public FoldLeft2['a, 'b, 'c] (a : list ['a], 
                                  b : list ['b], 
                                  acc : 'c, 
                                  f : 'a  * 'b * 'c -> 'c) : 'c 
    {
      match ((a, b)) {
        | ([], []) => acc
        | (x :: xs, y :: ys) => FoldLeft2 (xs, ys, f (x, y, acc), f)
        | _ => throw System.ArgumentException ("List.FoldLeft2")
      }
    }

    public FoldRight2['a, 'b, 'c] (a : list ['a], 
                                   b : list ['b],
                                   c : 'c, 
                                   f : 'a * 'b  * 'c -> 'c) : 'c
    {
      match ((a, b)) {
        | ([], []) => c
        | (x :: xs, y :: ys) => f (x, y, FoldRight2 (xs, ys, c, f))
        | _ => throw System.ArgumentException ("List.FoldRight2")
      }
    }


    /* -- LIST SCANNING ----------------------------------------------------- */

    /**
     * Returns 'true' if all of the 'l' list's elements satisfy
     * the condition 'f'.
     *
     * Example of use:
     *
     *   List.ForAll ([2, 4, 6, 8], fun (x) { x % 2 == 0 })
     *
     * evaluates to 'true' as all the list's elements are even.
     */
    public ForAll[T] (lst : list [T], predicate : T -> bool) : bool
    {
      match (lst) {
        | x :: xs => predicate (x) && ForAll (xs, predicate)
        | [] => true
      }
    }

    public Equals[T1, T2] (lst1 : list [T1], lst2 : list [T2], compare : T1 * T2 -> bool) : bool
    {
      match (lst1, lst2)
      {
        | (x1 :: xs1, x2 :: xs2) => compare (x1, x2) && Equals (xs1, xs2, compare)
        | ([], []) => true
        | _ => false
      }
    }

    /**
     * Returns 'true' if at least one of the 'l' list's elements
     * satisfies the condition 'f'.
     *
     * Example of use:
     *
     *   List.Exists (["a", "b", "abc", "d", "e"], fun (x) { x.Length > 2 })
     *
     * evaluates to 'true' as there is one string of length 3 on the list.
     */
    public Exists['a] (l : list ['a], f : 'a -> bool) : bool
    {
      match (l) {
        | [] => false
        | h :: t => f (h) || Exists (t, f)
      }
    }

    public ForAll2['a, 'b] (a : list ['a], b : list ['b], f : 'a * 'b -> bool) : bool {
      match ((a, b)) {
        | ([], []) => true
        | (x :: xs, y :: ys) => f (x, y) && ForAll2 (xs, ys, f)
        | _ => throw System.ArgumentException ("List.ForAll2")
      }
    }

    public Exists2['a, 'b] (a : list ['a], b : list ['b], f : 'a * 'b -> bool) : bool {
      match ((a,b)) {
        | ([], []) => false
        | (x :: xs, y :: ys) => f(x,y) || Exists2(xs, ys, f)
        | _ => throw System.ArgumentException ("List.Exists2")
      }
    }


    /**
     * List membership test, using the `Equals' method to compare objects.
     */
    public Member ['a] (l : list ['a], a : 'a) : bool
    {
      match (l) {
        | h :: t  => h.Equals (a) || Member (t, a)
        | [] => false
      }
    }

    
    /**
     * List membership test, using the reference equality.
     *
     * Returns true if and only if list [Collection] contains object with reference
     * equal to [Obj] object  
     */
    public ContainsRef ['a] (Collection : list ['a], Obj : 'a) : bool
    where 'a : class
    {
      match (Collection) {
        | h :: t  => (h : object) == Obj || ContainsRef (t, Obj)
        | [] => false
      }
    }

    
    /**
     * List membership test, using the `Equals' method to compare objects.
     *
     * This is an alias for the `Member' method.
     */
    public Contains ['a] (l : list ['a], a : 'a) : bool
    {
      Member (l, a)
    }
    
    
    /* -- LIST SEARCHING --------------------------------------------------- */
    
    /**
     * Finds the first elements for which a predicate is true.
     */
    public Find ['a] (l : list ['a], pred : 'a -> bool) : option ['a]
    {
      match (l)
      {
        | h :: t =>
          if (pred (h)) Some (h) else Find (t, pred)
        | [] => None ()
      }
    }

    
    /**
     * Returns the number of elements for which a predicate is true.
     */
    public FilteredLength ['a] (l : list ['a], f : 'a -> bool) : int
    {
      def filtered_length (l, acc : int)
      {
        match (l) {
          | [] => acc
          | head :: tail =>
            filtered_length (tail, if (f (head)) acc + 1 else acc)
        }
      }

      filtered_length (l, 0)
    }

    
    /**
     * Removes elements for which predicate is false
     */
    public Filter ['a] (l : list ['a], f : 'a -> bool) : list ['a]
    {
      $[ x | x in l, f (x) ]
    }

    
    /**
     * Removes elements for which predicate is false.
     * The resulting list is reversed (operation is faster this way).
     */
    public RevFilter ['a] (l : list ['a], f : 'a -> bool) : list ['a]
    {
      def loop (acc, l)
      {
        match (l) {
          | x :: xs =>
            if (f (x)) loop (x :: acc, xs)
            else loop (acc, xs)
          | [] => acc
        }
      }

      loop ([], l)
    }


    /**
     * This is an alias for ``Filter''
     */
    public FindAll ['a] (l : list ['a], f : 'a -> bool) : list ['a]
    {
      Filter (l, f)
    }


    /**
     * Partitions a list into two sublists according to a predicate.
     */
    public Partition['a] (l : list ['a], pred : 'a -> bool) : list ['a] * list ['a]
    {
      def loop (l : list ['a], sat : list ['a], notsat : list ['a])
      {
        match (l) {
          | h :: t => 
            if (pred (h)) 
              loop (t, h :: sat, notsat)
            else 
              loop (t, sat, h :: notsat)
          | [] => (Rev (sat), Rev (notsat))
        }
      };
      loop (l, [], [])  
    }

    
    /**
     * Groups equal element into lists
     */
    public Group ['a] (l : list ['a], cmp : 'a * 'a -> int) : list [list ['a]]
    {
      def walk (l : list ['a], acc : list ['a]) : list [list ['a]]
      { 
        def h = List.Head (acc);
      
        match (l) {
          | e :: rest =>
            if (cmp (e, h) == 0)
              walk (rest, e :: acc)
            else
              acc :: walk (rest, [e])
          | [] => [acc]
        }
      }

      if (List.IsEmpty (l)) []
      else {
        def sorted = List.Sort (l, cmp);
      
        walk (List.Tail (sorted), [List.Head (sorted)])
      }
    }


    /* -- ASSOCIATION LISTS ------------------------------------------------ */
    
    public Assoc ['a, 'b] (l : list ['a * 'b], key : 'a) : option ['b]
    {
      match (l) {
        | (k, v) :: t =>
          if (key.Equals (k))
            Some (v)
          else
            Assoc (t, key)
        | [] => None ()
      }
    }

    public MemAssoc['a, 'b] (l : list ['a * 'b], key : 'a) : bool {
      match (l) {
        | (k, _) :: t =>
          if (key.Equals (k))
            true
          else
            MemAssoc (t, key)
        | [] => false
      }
    }

    public RemoveAssoc ['a, 'b] (l : list ['a * 'b], key : 'a) : list ['a * 'b] {
      def loop (acc : list ['a * 'b], l : list ['a * 'b]) : list ['a * 'b]
      {
        match (l) {
          | (k, v) :: t => 
              if (key.Equals (k))
                loop (acc, t)
              else
                loop ((k, v) :: acc, t)
          | [] => Rev (acc)
        }
      };
      loop ([], l)  
    }


    /* -- LISTS OF PAIRS --------------------------------------------------- */

    
    public Split['a, 'b] (this l : list ['a * 'b]) : list ['a] * list ['b] {
      def loop (acc1 : list ['a], acc2 : list ['b], l : list ['a * 'b]) 
      {
        match (l) {
          | (a, b) :: t => loop (a :: acc1, b :: acc2, t)
          | [] => (Rev (acc1), Rev (acc2))
        }
      };
      loop([], [], l)
    }

    public Combine ['a, 'b] (this a : list ['a], b : list ['b]) : list ['a * 'b] {
      def loop (acc : list ['a * 'b], a : list ['a], b : list ['b]) : list ['a * 'b]
      {
        match ((a, b)) {
          | (x :: xs, y :: ys) => loop((x, y) :: acc, xs, ys)
          | ([], []) => Rev (acc)
          | _ => throw System.ArgumentException ("List.Combine")
        }
      };
      loop ([],a,b)
    }

    /* -- SORTING ---------------------------------------------------------- */
  
    MergeSort['a] (cmp : ('a * 'a) -> int, l : list ['a]) : list ['a] {
      def split (l) {
        def aux (l, acc, n) {
          if (n == 0)
            (List.Rev (acc), l)
          else 
            match (l) {
              | x :: xs => aux (xs, x :: acc, (n - 1))
              | [] => aux (l, acc, 0)
            }
        };
        aux (l, [], (List.Length (l) / 2))
      };
      def merge (cmp : ('a * 'a) -> int, l1, l2) {
        def aux (l1, l2, acc) {
          match ((l1, l2)) {
            | ([], _) => List.RevAppend (acc, l2)
            | (_, []) => List.RevAppend (acc, l1)
            | (x :: xs, y :: ys) => 
              if (cmp (x, y) <= 0)
                aux (xs, l2, x :: acc)
              else
                aux (l1, ys, y :: acc)
          }
        };
        aux (l1, l2, [])
      };

      match (l) {
        | []
        | [_] => l
        | _ =>
          def (l1, l2) = split (l);
          merge (cmp, MergeSort (cmp, l1), MergeSort (cmp, l2))
      }
    }

    public Sort['a] (l : list ['a], cmp : 'a * 'a -> int) : list ['a] 
    {
      MergeSort (cmp, l)
    }

    // what is it for?!
    public Copy['a] (l : list ['a]) : list ['a]
    {
      def loop (acc : list['a], what : list['a]) {
        match (what) {
          | x::xs => loop (x::acc,xs)
          | [] => Rev (acc)
        }
      };
      loop ([],l)
    }

    /**
     * Assumes that [prod] is a product of n - 1 lists, and extends
     * product by adding every possible element of [x] to these lists.
     */
    private Product ['a]
        (
         x    : list ['a],
         prod : list [list ['a]]
        )
        : list [list ['a]]
    {
        def extend (a, list, result)
        {
            match (a){
                | []      => result
                | x :: xs => extend (xs, list, (x :: list) :: result)
            }
        };
        
        def product (a, prod, result)
        {
            match (prod){
                | []      => result
                | x :: xs => 
                  product (a, xs, extend (a, x, []) + result)
            }
        };
        
        product (x, prod, [])
    }
    
    
    /**
     * Returns a product of lists stored in list [list].  Elements of
     * result are lists of the same length = List.Length (list).
     *
     * E.g.:
     *    Product ([[1, 2], [3, 4, 5]]) =
     *        [[1, 3],
     *         [1, 4],
     *         [1, 5],
     *         [2, 3],
     *         [2, 4],
     *         [2, 5]]
     *
     *    Product ([[1, 2], [3, 4, 5], []]) = []
     */
    public Product ['a]
        (
         list : list [list ['a]]
        )
        : list [list ['a]]
    {
        def product (list, result)
        {
            match (list){
                | []      => result
                | x :: xs => product (xs, Product (x, result))
            }
        };

        def list = 
            match (list){
                | []      => []
                | x :: xs => product (xs, List.Map (x, fun (a) { [a] }))
            };

        List.Map (list, List.Rev)
    }


    /**
     * Return a list of all possible partitions of [set] into [count] subsets.
     */
    public SubsetsPartitions ['a]
        (
         set   : list ['a],
         count : int
        )
        : list [list [list ['a]]]
    {
        /* Generate a list of [n] empty lists. */
        def gen_empty (result, n)
        {
            | (result, 0) => result
            | (result, n) => gen_empty ([] :: result, n - 1)
        };

        /* Pushes an element [elem] to a partition consisting of
           [left] and [list], by putting a variable exactly inbetween. */
        def push (elem, list, left, result)
        {
            match (list){
                | []      => result
                | x :: xs =>
                      push (elem, xs, x :: left,
                            (left + [elem :: x] + xs) :: result)
            }
        };

        /* Extends a partition stored in list [list] with an element [elem]. */
        def extend (elem, list, result)
        {
            match (list){
                | []      => result
                | x :: xs =>
                  extend (elem, xs, push (elem, x, [], []) + result)
            }
        };

        /* Partitions elements stored in list [list] accross subsets,
           by extending partition with one element at time. */
        def partition (list, result)
        {
            match (list){
                | []      => result
                | x :: xs =>
                  partition (xs, extend (x, result, []))
            }
        };

        partition (set, [gen_empty ([], count)])
    }


    public Singletons ['a] (list : list ['a])
                  : list [list ['a]]
    {
        List.RevMap (list, fun (a){ [a] })
    }


    /**
     * Return list of all possible [n]-element subsets of set [list].
     */
    public SizeSubsets ['a]
        (
         list : list ['a],
         n    : int
        )
        : list [list ['a]]
    {
        /* Add [elem] to head of every element of [set]. */
        def extend (elem, set, result)
        {
            match (set){
                | []      => result
                | x :: xs => extend (elem, xs, (elem :: x) :: result)
            }
        };
        
        match ((list, n)){
            | (_, 0)       => []
            | ([], _)      => []
            | (_, 1)       => Singletons (list)
            | (x :: xs, n) =>
              List.RevAppend (extend (x, SizeSubsets (xs, n - 1), []),
                              SizeSubsets (xs, n))
        }
    }

    // List creation

    /** Return list consisting of [count] references to [elem].  */
    public Repeat ['a] (elem : 'a, count : int) : list ['a]
    {
      def loop (acc, n) {
        if (n <= 0) acc
        else loop (elem :: acc, n - 1)
      }
      loop ([], count)
    }

    /** Return a list of integers from 0 to [end], excluding [end]. */
    public Range (end : int) : list [int] {
      Range (0, end)
    }

    /** 
     * Return a list of values incremented by [step], beginning
     * with [beg], up/down to [end], excluding [end] itself.
     */
    public Range (beg : int, end : int, step = 1) : list [int] {
      when (step == 0)
        throw System.ArgumentException ("Range () step argument must not be zero");

      def loop (acc, i) {
        if (i != beg)
          loop (i :: acc, i - step)
        else
          i :: acc
      }
    
      if (beg < end && step < 0 || beg > end && step > 0 || beg == end)
        []
      else {
        def last = if (end >= 0) end - 1 else end + 1;
        loop ([], last - ((last - beg) % step))
      }
    }
  
    /** Return a list of characters from 'a' to [end], excluding [end]. */
    public Range (end : char) : list [char] {
      Range ('a', end)
    }

    /** 
     * Return a list of characters, which values are incremented by [step],
     * beginning with [beg], up/down to [end], excluding [end] itself.
     */
    public Range (b : char, e : char, step = 1) : list [char] {
      when (step == 0)
        throw System.ArgumentException ("Range () step argument must not be zero");

      def (beg, end) = (b :> int, e :> int);

      def loop (acc, i) {
        if (i != beg)
          loop ((i :> char) :: acc, i - step)
        else
          (i :> char) :: acc
      }
    
      if (beg < end && step < 0 || beg > end && step > 0 || beg == end)
        []
      else {
        def last = if (step > 0) end - 1 else end + 1;
        loop ([], last - ((last - beg) % step))
      }
    }

  } /* end of module List */
  
} /* end of namespace Nemerle.Collections */