/*
 * Copyright (c) 2004-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.
 */

using System.Diagnostics;
using SCG = System.Collections.Generic; 
 
namespace Nemerle.Collections
{
  [DebuggerDisplay("Count = {Count}: {ToString()}")]
  [DebuggerNonUserCode]
  public class Set ['a] : SCG.ICollection ['a]
    where 'a : System.IComparable ['a]
  {
    root : Tree.Node ['a];
    
    public static Singleton (elem : 'a) : Set ['a]
    {
      Set ().Add (elem)
    }

    public this (coll : SCG.IEnumerable ['a]) 
    {
      this (Tree.Node.Leaf (), coll)
    }
    
    this (mutable tree : Tree.Node ['a], coll : SCG.IEnumerable ['a]) 
    {
      foreach (x in coll)
        tree = Tree.Insert (tree, x, false);
      root = tree;
    }
    
    public static FromList (elems : list ['a]) : Set ['a]
    {
      Set (elems)
    }
    
    public this ()
    {
      root = Tree.Node.Leaf ();
    }

    this (x : Tree.Node ['a])
    {
      root = x;
    }

    public Add (elem : 'a) : Set ['a]
    {
      Set (Tree.Insert (root, elem, false))
    }

    public AddRange (elems : SCG.IEnumerable ['a]) : Set ['a]
    {
      Set (root, elems)
    }
    
    public AddList (elems : list ['a]) : Set ['a]
    {
      AddRange (elems)
    }

    public ReplaceList (elems : list ['a]) : Set ['a]
    {
      Set (List.FoldLeft (elems, root, 
                          fun (elem, root) { 
                             Tree.Insert (root, elem, true) 
                          }))
    }

    public Replace (elem : 'a) : Set ['a]
    {
      Set (Tree.Insert (root, elem, true))
    }

    public Fold ['b] (ini : 'b, f : 'a * 'b -> 'b) : 'b
    {
      Tree.Fold (root, ini, f)
    }

    public Iter (f : 'a -> void) : void
    {
      _ = Tree.Fold (root, null, fun (e, _) { f (e); null })
    }

    public Filter (f : 'a -> bool) : Set ['a]
    {
      Fold (Set (), fun (elem, set : Set ['a]) {
        if (f (elem)) set.Add (elem)
        else set
      })
    }

    public Contains (elem : 'a) : bool
    {
      Tree.Get (root, elem).IsSome
    }

    public Remove (elem : 'a) : Set ['a]
    {
      Set (Tree.Delete (root, elem, false))
    }

    public Sum (s : Set ['a]) : Set ['a]
    {
      Set (Tree.Fold (s.root, root, fun (e, s) { Tree.Insert (s, e, true) }))
    }

    public Subtract (s : Set ['a]) : Set ['a]
    {
      Set (Tree.Fold (s.root, root, fun (e, s) { Tree.Delete (s, e, false) }))
    }

    public Intersect (s : Set ['a]) : Set ['a]
    {
      Set (Tree.Fold (s.root, Tree.Node.Leaf (), fun (e, s) { 
          match (Tree.Get (root, e)) {
            | Some => Tree.Insert (s, e, false)
            | None => s
          }
        }))
    }

    public Xor (o : Set ['a]) : Set ['a]
    {
      def s1 = 
        Tree.Fold (root, Tree.Node.Leaf (), fun (e, s) {
            match (Tree.Get (o.root, e)) {
              | Some => s
              | None => Tree.Insert (s, e, false)
            }
          });
      def s2 =
        Tree.Fold (o.root, s1, fun (e, s) {
            match (Tree.Get (root, e)) {
              | Some => s
              | None => Tree.Insert (s, e, false)
            }
          });

      Set (s2)
    }

    public ToList () : list ['a]
    {
      Fold ([], fun (e, a) { e :: a })
    }

    [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
    public AsArray : array ['a]
    {
      get { ToList ().ToArray () }
    }

    public static Sum (sets : list [Set ['a]]) : Set ['a]
    {
      List.FoldLeft (sets, Set (), fun (e, s : Set ['a]) { s.Sum (e) })
    }
    
    public Item [elem : 'a] : bool
    {
      get { Contains (elem) }
    }

    public IsEmpty : bool
    {
      get { root is Tree.Node[_].Leaf }
    }

    public override ToString () : string
    {
      "Set" + ToList ().ToString ()
    }
    
    public GetEnumerator () : SCG.IEnumerator ['a]
    {
      root.GetEnumerator ();
    }
    
    public CopyTo (arr : array ['a], mutable arrayIndex : int) : void
    {
      _ = Tree.Fold (root, null, fun (x, _) {
        arr [arrayIndex] = x;
        arrayIndex++;
        null
      });
    }

    public IsReadOnly : bool {
      get { true }
    }
    
    public Count : int {
      get { root.Count }
    }
    
    private Remove_Invalid (_ : 'a) : bool implements SCG.ICollection.Remove
    {
      throw System.NotSupportedException ("this is functional set, which is read-only");
    }

    private Clear_Invalid() : void implements SCG.ICollection.Clear
    {
      throw System.NotSupportedException ("this is functional set, which is read-only");
    }

    private Add_Invalid (_ : 'a) : void implements SCG.ICollection.Add
    {
      throw System.NotSupportedException ("this is functional set, which is read-only and returns new instanc upon adding element");
    }
  }
}