/*
 * 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.NList;
using NCL = Nemerle.Collections.NList;
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 [T] : 
    SCG.IEnumerable [T], 
    Nemerle.Collections.ICovariantList [T],
    System.IEquatable [T]
    // , Nemerle.Collections.ICovariantEnumerable [T] //unfortunately this is prevented by MS.NET bug
  {
    | Cons 
      {
        hd : T;
        [Nemerle.Extensions.CompilerMutable]
        tl : list [T];
        
        // For debugging purpose.
        [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
        AsArray2 : array [T] { get { _ = NToArray; ToArray () } }
      }

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

    public override ToString () : string { "[" + ToString(", ") + "]" }

    public ToString (separator : string) : string 
    {
      $"..$(this; separator)"
    }
    
    public CovariantTail : Nemerle.Collections.ICovariantList [T] {
      get { Tail }
    }
    
    public static @== (x : list [T], y : list [T]) : bool
    {
      if (x : object == y)
        true
      else if (x : object == null || y : object == null)
        false
      else
        x.Equals(y)
    }

    public static @!= (x : list [T], y : list [T]) : 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 [T]) : bool
    {
      match (this) {
        | x :: xs =>
          match (other) {
            | y :: ys when x.Equals (y) => xs.Equals (ys)
            | _ => false
          }
          
        | [] => other.IsEmpty
      }
    }

    public Equals[TSecond] (lst2 : list [TSecond], compare : T * TSecond -> 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 (T)
    }

    /**
     * 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 : T {
      get {
        match (this) {
          | x :: _ => x
          | [] => throw System.ArgumentException ("NList.Head called with empty list");
        }
      }
    }

    /**
     * Returns tail (all elements except the first one) of list.
     */
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    public Tail : list [T] {
      get {
        match (this) {
          | _ :: tl => tl
          | [] => throw System.ArgumentException ("NList.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 : T {
      get {
        NCL.Last (this)
      }
    }
    
    
    /* -- ENUMERATION SUPPORT   -------------------------------------------- */

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

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


    /**
     * Returns first n elements of the list.
     * Works in time and memory O(n).
     */
    public FirstN (n : int) : list [T]
    {
      def loop (k, acc, lst) {
        if (k == 0) Rev (acc)
        else
          match (lst) {
            | x :: xs => loop (k - 1, x :: acc, xs)
            | [] =>
              throw System.ArgumentException ("NList.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 [T]
    {
      def loop (n, l) {
        if (n == 0) l
        else
          match (l) {
            | _ :: xs => loop (n - 1, xs)
            | [] =>
              throw System.ArgumentException ("NList.ChopFirstN called for too short list")
          }
      }
      loop (n, this)
    }


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


    public Nth (n : int) : T {
      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 [T] {
      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 [T]) : list [T] {
      NCL.RevAppend (Reverse (), y)
    }
    
    /**
     * Equivalent to Reverse().Append(y), but faster.
     */
    public RevAppend (y : list [T]) : list [T] {
      NCL.RevAppend(this, y)
    }
    

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

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

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

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

    public MapFiltered[TOut] (predicate : T -> bool, convert : T -> TOut) : list [TOut] {
      NCL.MapFiltered (this, predicate, convert)
    }

    public RevMap[TOut] (f : T -> TOut) : list [TOut] {
      NCL.RevMap (this, f)
    }

    public FoldLeft[TOut] (acc : TOut, f : T * TOut -> TOut) : TOut {
      NCL.FoldLeft (this, acc, f)
    }

    public FoldRight[TOut] (acc : TOut, f : T * TOut -> TOut) : TOut {
      NCL.FoldRight (this, acc, f)
    }

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

    /**
     * Returns 'true' if all of the 'l' list's elements satisfy
     * the condition 'f'.
     *
     * Example of use:
     *
     *   NList.ForAll ([2, 4, 6, 8], fun (x) { x % 2 == 0 })
     *
     * evaluates to 'true' as all the list's elements are even.
     */
    public ForAll (f : T -> bool) : bool 
    {
      NCL.ForAll (this, f)
    }
    
    public ForAll2[TSecond] (lst2 : list [TSecond], predicate : T * TSecond -> 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:
     *
     *   NList.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 : T -> bool) : bool
    {
      NCL.Exists (this, f)
    }

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

    /**
     * Finds the first elements for which a predicate is true.
     */
    public FindWithDefault (default : T, pred : T -> bool) : T
    {
      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 : T -> bool) : int
    {
      NCL.FilteredLength (this, f)
    }

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

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


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

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


    /**
     * Partitions a list into two sublists according to a predicate.
     */
    public Partition (pred : T -> bool) : list [T] * list [T]
    {
      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 [T]
    {
      NCL.Rev (this)
    }
    

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

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

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

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


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

    // For debugging purpose.
    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    protected NToArray : array [T]
    {
      get { ToArray () }
    }

    public ToArray () : array [T]
    {
      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 [T], 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 [T]) : void
    {
      mutable i = 0;
      foreach (el in this) {
        dest [i] = el;
        i++;
      }
    }
    
    public MapToArray [TOut] (f : T -> TOut) : array [TOut]
    {
      def result = array (Length);
      mutable i = 0;
      foreach (x in this) {
        result [i] = f (x);
        i++;
      }
      result
    }
  }
}

namespace Nemerle.Collections
{
  [DebuggerNonUserCode]
  public module NList
  {
    /**
     * Tests equality of two lists.  Uses Equal method of
     * objects to test wether they are the same.
     */
    public Equals[T] (x : list [T], y : list [T]) : 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 [T] (l1 : list [T], l2 : list [T],
                                cmp : T * T -> 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 [T] (l1 : list [T], l2 : list [T]) : int
      where T : System.IComparable [T]
    {
      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 [T] (lst : list [T]) : list [T]
    {
      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 [T] (x : array [T]) : list [T] {
      def loop (index, acc) : list [T] {
        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 AsList [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 [T] (lst : list [T]) : bool { lst.IsEmpty }
    
    /**
     * Returns length of given list. Time O(n), Mem O(1).
     */
    public Length [T] (x : list [T]) : int {
      def loop (acc : int, x : list [T]) : 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 [T] (l : list [T]) : T { l.Head }
    
    /// Alias for l.Head.
    public Hd [T] (l : list [T]) : T { l.Head }
    
    /**
     * Returns tail (all elements except first one) of list.
     */
    public Tail[T] (l : list [T]) : list [T] {
      l.Tail
    }
    
    /**
     * Alias for Tail(l).
     */
    public Tl[T] (l : list [T]) : list [T] {
      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[T] (l : list [T], n : int) : T {
      match (l) {
        | h :: t => 
          if ( n == 0 )
            h
          else
            Nth(t, n-1)
        | [] => throw System.ArgumentOutOfRangeException ("NList.Nth")
      }
    }

    /**
     * Returns last element of list.
     * Given empty list throws InvalidArgument exception.
     * Works in time O(n) and memory O(1).
     */
    public Last[T] (l : list [T]) : T {
      match (l) {
        | [x] => x
        | _ :: xs => Last (xs)
        | [] => throw System.ArgumentException ("NList.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[T] (l : list [T]) : list [T] {
      def loop (acc : list [T], l : list [T]) : list [T] {
        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[T] (x : list [T], y : list [T]) : list [T]
    {
      NList.RevAppend (NList.Rev (x), y)
    }
    
    /**
     * Equivalent to Append(Rev(x),y).
     */
    public RevAppend[T] (x : list [T], y : list [T]) : list [T] {
      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[T] (this l : list [list [T]]) : list [T]
    {
      FoldLeft (l, [], fun (x, y) { Append (y, x) })
    }    

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

    
    /**
     * Returns list l without elements equal to x.
     */
    public Remove[T] (l : list[T], x : T) : list[T]
    {
      def loop (acc : list [T],from : list[T]) : list[T]
      {
        match (from) {
          | [] => NList.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 [T] (l : list [T]) : list [T] * T
    {
      def loop (ls, acc) {
        match (ls) {
          | [x] => (NList.Rev (acc), x)
          | x :: xs => loop (xs, x :: acc)
          | _ =>
            throw System.ArgumentException ("NList.DivideLast called for empty list")
        }
      }
      
      loop (l, [])
    }

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

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

    public Map[T, TOut] (lst : list [T], convert : T -> TOut) : list [TOut] {
      $[ convert(x) | x in lst ]
    }

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

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

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

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

    public Map2[T, TSecond, TOut] (x : list [T], y : list [TSecond], f : T * TSecond -> TOut) : list [TOut] {
      match ((x, y)) {
        | ([], []) => []
        | (x :: xs, y :: ys) => f (x, y) :: Map2 (xs, ys, f)
        | _ => throw System.ArgumentException ("NList.Map2")
      }
    }

    public RevMap2[T, TSecond, TOut] (x : list [T], y : list [TSecond], f : T * TSecond -> TOut) 
    : list [TOut] 
    {
      def loop (acc : list [TOut], x : list [T], y : list [TSecond]) : list [TOut] {
        match ((x, y)) {
          | ([], []) => acc
          | (x :: xs, y :: ys) => loop (f (x, y) :: acc, xs, ys)
          | _ => throw System.ArgumentException ("NList.RevMap2")
        }
      }
      loop([], x, y)
    }

    public FoldLeft2[TFirst, TSecond, TOut] (this a : list [TFirst], 
                                  b : list [TSecond], 
                                  acc : TOut, 
                                  f : TFirst  * TSecond * TOut -> TOut) : TOut 
    {
      match ((a, b)) {
        | ([], []) => acc
        | (x :: xs, y :: ys) => FoldLeft2 (xs, ys, f (x, y, acc), f)
        | _ => throw System.ArgumentException ("NList.FoldLeft2")
      }
    }

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


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

    /**
     * Returns 'true' if all of the 'l' list's elements satisfy
     * the condition 'f'.
     *
     * Example of use:
     *
     *   NList.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, TSecond] (lst1 : list [T1], lst2 : list [TSecond], compare : T1 * TSecond -> 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:
     *
     *   NList.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[T] (l : list [T], f : T -> bool) : bool
    {
      match (l) 
      {
        | [] => false
        | h :: t => f (h) || Exists (t, f)
      }
    }

    public ForAll2[T, TSecond] (a : list [T], b : list [TSecond], f : T * TSecond -> bool) : bool {
      match (a, b) {
        | ([], []) => true
        | (x :: xs, y :: ys) => f (x, y) && ForAll2 (xs, ys, f)
        | _ => false
      }
    }

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


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

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

    
    /**
     * NList membership test, using the `Equals' method to compare objects.
     *
     * This is an alias for the `Member' method.
     */
    public Contains [T] (l : list [T], a : T) : bool
    {
      Member (l, a)
    }
    
    
    /* -- LIST SEARCHING --------------------------------------------------- */
    
    /**
     * Finds the first elements for which a predicate is true.
     */
    public Find [T] (l : list [T], pred : T -> bool) : option [T]
    {
      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 [T] (l : list [T], f : T -> 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 [T] (l : list [T], f : T -> bool) : list [T]
    {
      $[ 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 [T] (l : list [T], f : T -> bool) : list [T]
    {
      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 [T] (l : list [T], f : T -> bool) : list [T]
    {
      Filter (l, f)
    }


    /**
     * Partitions a list into two sublists according to a predicate.
     */
    public Partition[T] (l : list [T], pred : T -> bool) : list [T] * list [T]
    {
      def loop (l : list [T], sat : list [T], notsat : list [T])
      {
        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 [T] (l : list [T], cmp : T * T -> int) : list [list [T]]
    {
      def walk (l : list [T], acc : list [T]) : list [list [T]]
      { 
        def h = NList.Head (acc);
      
        match (l) {
          | e :: rest =>
            if (cmp (e, h) == 0)
              walk (rest, e :: acc)
            else
              acc :: walk (rest, [e])
          | [] => [acc]
        }
      }

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


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

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

    public RemoveAssoc [T, TSecond] (l : list [T * TSecond], key : T) : list [T * TSecond] {
      def loop (acc : list [T * TSecond], l : list [T * TSecond]) : list [T * TSecond]
      {
        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[T, TSecond] (this l : list [T * TSecond]) : list [T] * list [TSecond] {
      def loop (acc1 : list [T], acc2 : list [TSecond], l : list [T * TSecond]) 
      {
        match (l) {
          | (a, b) :: t => loop (a :: acc1, b :: acc2, t)
          | [] => (Rev (acc1), Rev (acc2))
        }
      }
      loop([], [], l)
    }

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

    /* -- SORTING ---------------------------------------------------------- */
  
    MergeSort[T] (cmp : (T * T) -> int, l : list [T]) : list [T] {
      def split (l) {
        def aux (l, acc, n) {
          if (n == 0)
            (NList.Rev (acc), l)
          else 
            match (l) {
              | x :: xs => aux (xs, x :: acc, (n - 1))
              | [] => aux (l, acc, 0)
            }
        }
        aux (l, [], (NList.Length (l) / 2))
      }
      def merge (cmp : (T * T) -> int, l1, l2) {
        def aux (l1, l2, acc) {
          match ((l1, l2)) {
            | ([], _) => NList.RevAppend (acc, l2)
            | (_, []) => NList.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[T] (l : list [T], cmp : T * T -> int) : list [T] 
    {
      MergeSort (cmp, l)
    }

    // what is it for?!
    public Copy[T] (l : list [T]) : list [T]
    {
      def loop (acc : list[T], what : list[T]) {
        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 [T]
        (
         x    : list [T],
         prod : list [list [T]]
        )
        : list [list [T]]
    {
        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 = NList.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 [T]
        (
         list : list [list [T]]
        )
        : list [list [T]]
    {
        def product (list, result)
        {
            match (list){
                | []      => result
                | x :: xs => product (xs, Product (x, result))
            }
        }

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

        NList.Map (list, NList.Rev)
    }


    /**
     * Return a list of all possible partitions of [set] into [count] subsets.
     */
    public SubsetsPartitions [T]
        (
         set   : list [T],
         count : int
        )
        : list [list [list [T]]]
    {
        /* 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 [T] (list : list [T])
                  : list [list [T]]
    {
        NList.RevMap (list, fun (a){ [a] })
    }


    /**
     * Return list of all possible [n]-element subsets of set [list].
     */
    public SizeSubsets [T]
        (
         list : list [T],
         n    : int
        )
        : list [list [T]]
    {
        /* 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) =>
              NList.RevAppend (extend (x, SizeSubsets (xs, n - 1), []),
                              SizeSubsets (xs, n))
        }
    }

    // NList creation

    /** Return list consisting of [count] references to [elem].  */
    public Repeat [T] (elem : T, count : int) : list [T]
    {
      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 NList */
  
} /* end of namespace Nemerle.Collections */