/*
  set.d
  Author: Fredrik Olsson <peylow@gmail.com>
  Copyright (c) 2006 Fredrik Olsson, <http://peylow.no-ip.org>
  All rights reserved.

    This file is part of D sets.
    D sets is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 2.1 of the License, or
    (at your option) any later version.

    D sets is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with D sets; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

/**
 *  Classes for working with ranges and sets according to naive set theory.
 *
 *  As sets and ranges will probably not be part of the language, this module
 *  provides a wider range of set and range functionality. In fact a complete
 *  implementation of naive set algebra.
 *
 *  Ramnges are finite and empty. Sets can be empty finite and infinite.
 *  Exception is thrown when using a range or set in a mathematically illegal
 *  way, or in a way that would potentionally use infinite resources to compute.
 *
 *  The template set classes can be used for numeric sets or any set.
 *
 *  Example:
 *  --------------------------------------------------------------------------
 *  auto employees = fetchAllEmployees();
 *  auto women = FunctionSet!(Person)(delegate bool(Person p){ return p.sex == female; });
 *  auto vacation = FunctionSet!(Person)(delegate bool(Person p){ return p.onvacation; });
 *  auto goodCandidatesForProject = employees ^ women - vacation;
 *  writefln(femaleEmployees.toString());
 *  --------------------------------------------------------------------------
 *
 * Authors: Fredrik Olsson <peylow@gmail.com>
 * Bugs: Probably many.
 * Date: 2006-07-08
 * 
 */
module toys.set;

private import std.stdarg;
private import std.conv;
private import std.string;
private import std.math;


/**
 *  Illegal range exception. Thrown when using or constructing an illegal range.
 */
public class IllegalRangeException : Exception {
  this(char[] msg) {
    super(msg);
  }
}

/**
 * Empty range exception. Thrown when non empty ranges are illegal.
 */
public class EmptyRangeException : IllegalRangeException {
  this(char[] msg) {
    super(msg);
  }
}

/**
 *  Illegal set exception. Thrown when using or constructing an illegal set.
 */
public class IllegalSetException : Exception {
  this(char[] msg) {
    super(msg);
  }
}

/**
 *  Infionite set exception. Thrown when an infinite set would claim infinite
 *  resources.
 */
public class InfiniteSetException : IllegalSetException {
  this(char[] msg) {
    super(msg);
  }
}


/**
 *  A range.
 *
 *  Any numeric range is valid. Only integer ranges can be iterated, or used
 *  alongside sets. A real range have infinite members.
 */
public class Range(T) {
private:
  bool _isempty, _isreversed;
  T _start, _end;
  T min(T a, T b) { return a < b ? a : b; }
  T max(T a, T b) { return a > b ? a : b; }
  T abs(T a) { return a < 0.0 ? -a : a; }
  bool isfloat() { return cast(T)(1 / 2) == 0.5; }

public:
/**
 *  Construct a new empty range. 
 *
 *  Params:
 *    d =     Descending, default to false.
 */
  this(bool d = false) {
    _isempty = true;
    _isreversed = d;
  }

/**
 *  Construct a new range. 
 *
 *  If the end is less than the start the range is descending.
 *
 *  Params:
 *    s =     Start of range.
 *    e =     End of range.
 */
  this(T s, T e) {
    _isempty = false;
    this._start = s;
    this._end = e;
    _isreversed = e < s;
  }
  
/**
 *  Convert range to string.
 *
 *  Returns: Range as string.
 */
  char[] toString() {
    if (_isempty) {
      return "?..?";
    } else {
      return std.string.toString(_start) ~ ".." ~ std.string.toString(_end);
    }
  }
  
/**
 *  Create a duplicate of range.
 *
 *  Returns: A copy of range.
 */
  Range!(T) dup() { 
    if (_isempty) {
      return new Range!(T)(_isreversed);
    } else {
      return new Range!(T)(this._start, this._end); 
    }
  }
  
/**
 *  Create a reversed duplicate of range.
 *
 *  Returns: A reversed copy of range.
 */
  Range!(T) reversed() {
    Range!(T) r = this.dup;
    r.reverse();
    return r;
  }
  
/**
 *  Create an ascending duplicate of range.
 *
 *  Returns: An ascending copy of range.
 */
  Range!(T) ascending() {
    Range!(T) r = this.dup;
    r.ascend;
    return r;
  }

/**
 *  Create a descending duplicate of range.
 *
 *  Returns: A descending copy of range.
 */
  Range!(T) descending() {
    Range!(T) r = this.dup;
    r.descend;
    return r;
  }
  
/**
 *  Get and set range's start.
 *
 *  Throws: EmptyRangeException if range is empty.
 */
  T start() {
    if (_isempty) {
      throw new EmptyRangeException("Empty range have no start.");
    }
    return _start;
  }
/**
 *  ditto
 */
  T start(T s) {
    if (_isempty) {
      throw new EmptyRangeException("Empty range can not have only start.");
    }
    _start = s;
    if (_start != _end) {
      _isreversed = _end < _start;
    }
    return s;
  }
  
/**
 *  Get and set range's end.
 *
 *  Throws: EmptyRangeException if range is empty.
 */
  T end() {
    if (_isempty) {
      throw new EmptyRangeException("Empty range have no end.");
    }
    return _start;
  }
/**
 *  ditto
 */
  T end(T e) {
    if (_isempty) {
      throw new EmptyRangeException("Empty range can not have only end.");
    }
    _end = e;
    if (_start != _end) {
      _isreversed = _end < _start;
    }
    return e;
  }
  
/**
 *  Get and set range's length.
 *
 *  A Descending range have a negative length.
 */
  T length() { 
    if (_isempty) {
      return 0;
    } else {
      if (_isreversed) {
        return _start - _end + 1;
      } else {
        return _start - _end - 1;
      }
    }
  }
/**
 *  ditto
 */
  T length(T l) {
    if (l == 0) {
      _isempty = true;
    } else if (l > 0) {
      _end = _start + l - 1;
      _isreversed = false;
    } else {
      _end = _start + l + 1;
      _isreversed = true;
    }
    return l;
  }
  
/**
 *  Query range's properties.
 *
 *  Returns: True if range conforms.
 */
  bool isEmpty() { return _isempty; }
/**
 *  ditto
 */
  bool isAscending() { return !_isreversed; }
/**
 *  ditto
 */
  bool isDescending() { return _isreversed; }

/**
 *  Reverse range's ascending or descending order.
 */
  void reverse() { 
    T t = _start; 
    _start = _end; _end = t; 
    _isreversed = !_isreversed; 
  }
  
/**
 *  Force range as ascending.
 */
  void ascend() {
    if (_isreversed) {
      this.reverse();
    }
  }

/**
 *  Force range as descending.
 */
  void descend() {
    if (!_isreversed) {
      this.reverse();
    }
  }

/**
 *  Compare range to other range.
 *
 *  Is equal if all members are shared, regardles or order.
 *
 *  Params:
 *    r =      Other set to compare to.
 *  Returns: True if equal.
 */
  bool opEquals(Range!(T) r) {
    if (this._isempty && r._isempty) {
      return true;
    } else if (this._isreversed == r._isreversed) {
      return this._start == r._start && this._end == r._end;
    } else {
      return this._start == r._end && this._end == r._start;
    }
  }

/**
 *  Compare range to other set.
 *
 *  Is equal if all members are shared.
 *
 *  Params:
 *    r =      Other set to compare to.
 *  Returns: True if equal.
 */
  bool opEquals(AbstractSet!(T) s) {
    if (s.isFinite() && s.length == this.length) {
      foreach (i; this) {
        if (!(s.have(i))) {
          return false;
        }
      }
      return true;
    }
    return false;
  }
  
/**
 *  Query membership of range.
 *
 *  Params:
 *    v =     Value to query for membership.
 *
 *  Returns: True if value is member of range.
 */
  bool have(T v) { 
    if (_isempty) {
      return false;
    } else if (_isreversed) {
      return v <= _start && v >= _end; 
    } else {
      return v >= _start && v <= _end; 
    }
  }
  
/**
 *  Query intersection of ranges.
 *
 *  Ranges only intersect if they share members. Adjescending integer ranges 
 *  that as a union could create a continious range, do not intersect.
 *
 *  Params:
 *    r =     Range to test intersection with.
 *
 *  Returns:  True if the ranges intersects.
 */
  bool intersects(Range!(T) r) { 
    return this.have(r._start) || this.have(r._end); 
  }
  
/**
 *  Query if range completely covers other range.
 *
 *  Params:
 *    r =     Range to test if covered.
 *
 *  Returns:  True if range completely covers other range,
 */
  bool covers(Range!(T) r) { return this.have(r._start) && this.have(r._end); }
  
/**
 *  Union of ranges.
 *
 *  A union is a new range with all members of both operand ranges.
 *
 *  Params:
 *    r =     Orther range.
 *  
 *  Returns:  A union of the ranges.
 *
 *  Throws:   IllegalRangeException if ranges do not intersect or are adjescent.
 */
  Range!(T) opCat(Range!(T) r) { // Union, ~
    if (r._isempty) {
      return this.dup;
    }
    bool reversed = _isreversed;
    if (_isempty) {
      r = r.dup;
      if (_isreversed != r._isreversed) {
        r.reverse();
      }
      return r;
    }
    Range!(T) a = _isreversed ? this.ascending() : this;
    Range!(T) b = r._isreversed ? r.ascending() : r;
    if (!a.intersects(b)) {
      if (isfloat() || a._end + 1 != b._start) {
        throw new IllegalRangeException("Can not make union of separated ranges");
      }
    } else {
      r = new Range!(T)(min(a._start, b._start), max(a._end, b._end));
      if (reversed) {
        r.reverse;
      }
    return r;
    }
  }

/**
 *  Intersection of ranges.
 *
 *  An intersection is a new range with all members shared by both operand
 *  ranges.
 *
 *  Params:
 *    r =     Other range.
 *
 *  Returns:  An intersection of the ranges.
 */
  Range!(T) opXor(Range!(T) r) { // Intersection, ^
    if (_isempty || r._isempty) {
      return new Range!(T)(_isreversed);
    }
    bool reversed = _isreversed;
    Range!(T) a = _isreversed ? this.ascending() : this;
    Range!(T) b = r._isreversed ? r.ascending() : r;
    if (!a.intersects(b)) {
      return new Range!(T)(reversed);
    } else {
      r = new Range!(T)(max(a._start, b._start), min(a._end, b._end));
      if (reversed) {
        r.reverse;
      }
      return r;
    }
  }
  
/**
 *  Complement of ranges.
 *
 *  A complemet is a new range with all members of left operand range, not in 
 *  right operand range.
 *
 *  Params:
 *    r =     Other range.
 *  
 *  Returns:  A complement of ranges.
 *
 *  Throws:   IllegalRangeException if resulting in a non continious range.
 */
  Range!(T) opSub(Range!(T) r) { // Complement, -
    if (isfloat()) {
      throw new IllegalRangeException("Can not take complement of non integer set.");
    }
    if (_isempty || r.covers(this)) {
      return new Range!(T)(_isreversed);
    }
    if (!this.intersects(r)) {
      return this.dup;
    } else {
      bool reversed = _isreversed;
      Range!(T) a = _isreversed ? this.ascending() : this;
      Range!(T) b = r._isreversed ? r.ascending() : r;
      if (a._start > b._start) {
        r = new Range!(T)(b._end + 1, a._end);
      } else {
        r = new Range!(T)(a._start, b._start - 1);
      }
      if (reversed) {
        r.reverse;
      }
      return r;
    }
  }
  
/**
 *  Foreach iterator method over range.
 *
 *  Ascending and descending order is respected.
 */
  int opApply(int delegate(inout T)dg) {
    if (isfloat()) {
      throw new IllegalRangeException("Can not iterate over a non integer set.");
    }
    int r = 0;
    if (_isreversed) {
      for (int i = _start; i >= _end; i--) {
        r = dg(i);
        if (r) {
          break;
        }
      }
    } else {
      for (int i = _start; i <= _end; i++) {
        r = dg(i);
        if (r) {
          break;
        }
      }
    }
    return r;
  }
  
}

/**
 *  Abstract base class for sets.
 */
public class AbstractSet(T) {
public:

/**
 *  Create string representation of set.
 *
 *  Infinite sets are represented as {...}.
 *
 *  Returns:  Set as string.
 */
  char[] toString() {
    if (!isFinite()) {
      return "{...}";
    } else {
      char[] ret = "";
      foreach (T m; this) {
        ret ~= std.string.toString(m) ~ ",";
      }
      if (ret.length) {
        ret = ret[0..($-1)];
      }
      return "{" ~ ret ~ "}";
    }
  }
  
/**
 *  Duplicate set.
 *  
 *  Returns: A copy of set.
 */
  abstract AbstractSet!(T) dup();

/**
 *  Query set membership.
 *  
 *  Abstract method must be overridden in subclasses.
 *
 *  Params:
 *    m =     Member to query for membership.
 *
 *  Returns: True if a member of set.
 */
  abstract bool have(T m);
  
/**
 *  Query set if finite.
 *
 *  Infinite sets can not be iterated or used with ranges.
 *
 *  Default inplementation returns false, must override in subclasses for
 *  finite sets.
 *  
 *  Returns:  True if set is finite.
 */
  bool isFinite() { return false; }
  
/**
 *  Query set's length.
 *
 *  The length of a set is the total member count. Must return uint.max for
 *  infinite sets, and should be ignored for infinite sets.
 *
 *  Default implementation returns uint.max, must override in subclasses for
 *  finite sets.
 *
 */
  uint length() { return uint.max; }
  
/**
 *  Foreach iterator method for set.
 *  
 *  Used to iterate over all members of set.
 *
 *  Throws: InfiniteSetException if set is not finite.
 */
  int opApply(int delegate(inout T)dg) {
    if (isFinite()) {
      throw new InfiniteSetException("Can not iterate over infinite set.");
    } else {
      assert(0);
    }
  }
  
/**
 *  Query sets for equality.
 * 
 *  Sets are equal if of same length and sharing all members.
 *
 *  Params:
 *    s =     Other set to test for equality.
 *
 *  Returns:  True if sets are equal.
 *
 *  Throws:   InfiniteSetException if both sets are infinite, and not same 
 *            instance.
 */
  bool opEqual(AbstractSet!(T) s) {
    if (this is s) {
      return true;
    } else {
      if (isFinite() && s.isFinite()) {
        if (length() == s.length()) {
          foreach (T m; this) {
            if (!s.have(m)) {
              return false;
            }
          }
          return true;
        }
      } else if (!isFinite() && !s.isFinite()) {
        throw new InfiniteSetException("Can not compare infinite sets.");
      }
    }
    return false;
  }

/**
 *  Union of sets.
 *
 *  A union is a new set with all members from both operand sets.
 *
 *  Params:
 *    s =     Other set.
 * 
 *  Returns:  An union of sets.
 */ 
  AbstractSet!(T) opCat(AbstractSet!(T) s) { // Union
    if (this.isFinite() && s.isFinite()) {
      return new Set!(T)(this, s);
    } else {
      return new CombinedSet!(T)(SetCombination.Union, this, s);
    }
  }

/**
 *  Intersection of sets.
 *
 *  An intersection is a new set with all members shared by both operand sets.
 *
 *  Params:
 *    s =     Other set.
 *
 *  Returns: An intersection of sets.
 */
  AbstractSet!(T) opXor(AbstractSet!(T) s) { // Intersection
    if (this.isFinite() || s.isFinite()) {
      AbstractSet!(T) a, b;
      Set!(T) r = new Set!(T)();
      if (this.isFinite()) {
        a = this; b = s;
      } else {
        a = s; b = this;
      }
      foreach (T m; a) {
        if (b.have(m)) {
          r.add(m);
        }
      }
      return r;
    } else {
      return new CombinedSet!(T)(SetCombination.Intersection, this, s);
    }
  }

/**
 *  Complement of sets.
 *  
 *  A complement is a new set with all members of left operand set, not in
 *  right operand set.
 *
 *  Params:
 *    s =     Other set.
 *
 *  Returns:  Complement of set.
 */
  AbstractSet!(T) opSub(AbstractSet!(T) s) { // Complement
    if (this.isFinite()) {
      Set!(T) r = new Set!(T)();
      foreach(T m; this) {
        if (!s.have(m)) {
          r.add(m);
        }
      }
      return r;
    } else {
      return new CombinedSet!(T)(SetCombination.Intersection, this, s);
    }
  }
  
/**
 *  Complement of set.
 *  
 *  A complement is a new set with all members not in operand set.
 *
 *  Returns:  Complement of set.
 */
  AbstractSet!(T) opNeg() {
    return new CombinedSet!(T)(SetCombination.Complement, this);
  }
  
}


/**
 *  Combination operation for a combination set class.
 */
public enum SetCombination {
  Union = 0,        // Union of two sets.
  Intersection = 1, // Intersection of two sets.
  Complement = 2    // Complement of one, or two sets.
}


/**
 *  Helper class for handling an infinite combination of two sets.
 */
final public class CombinedSet(T) : AbstractSet!(T) {
private:
  SetCombination _comb;
  AbstractSet!(T) _a, _b;
public:
  this(SetCombination c, AbstractSet!(T) a, AbstractSet!(T) b = null) {
    _comb = c;
    _a = a.dup;
    if (_b) {
      _b = b.dup;
    } else {
      if (_comb != SetCombination.Complement) {
        throw new IllegalSetException("Only complemented sets can be constructed froma  single set.");
      }
      _b = null;
    }
  }
  
  CombinedSet!(T) dup() {
    return new CombinedSet!(T)(_comb, _a, _b);
  }
  
  bool have(T m) {
    switch (_comb) {
      case SetCombination.Union:
        return _a.have(m) || _b.have(m);
      case SetCombination.Intersection:
        return _a.have(m) && _b.have(m);
      case SetCombination.Complement:
        if (_b) {
          return _a.have(m) && !_b.have(m);
        } else {
          return !_a.have(m);
        }
      default:
        assert(0);
    }
  }
}


/**
 *  A set class for handling a set with membership defined by function.
 */
public class FunctionSet(T) : AbstractSet!(T) {
private:
  bool delegate(T m)_dg;

public:
/**
 *  Create new set with function delegate to determine set membership.
 *
 *  Params:
 *    dg =    A function delegate returning true if member of set.
 */
  this(bool delegate(T m)dg) {
    _dg = dg;
  }

  FunctionSet!(T) dup() {
    return new FunctionSet!(T)(_dg);
  }
  
  bool have(T m) {
    return _dg(m);
  }

}


/**
 *  A set class for handling a finite mutable set.
 */
public class Set(T) : AbstractSet!(T) {
private:
  bool[T] _set;

public:
/**
 *  Create a new set with variadric members of values, sets, and ranges of 
 *  values.
 *
 *  Params:
 *    ... =   Values, sets, or ranges of base sets base type.
 */
  this(...) {
    for(uint i = 0; i < _arguments.length; i++) {
      if (_arguments[i] == typeid(T)) {
        this.add(va_arg!(T)(_argptr));
      } else if (_arguments[i] == typeid(Range!(T))) {
        auto range = va_arg!(Range!(T))(_argptr);
        foreach (T value; range) {
          add(value);
        } 
      } else if (_arguments[i] == typeid(AbstractSet!(T))) {
        auto set = va_arg!(AbstractSet!(T))(_argptr);
        foreach (T value; set) {
          add(value);
        }
      } else {
        assert(0);
      }
    }
  }
  
  
  Set!(T) dup() {
    return new Set!(T)(this);
  }
  
  bool have(T v) { return cast(bool)(v in _set); }

  bool isFinite() { return true; }
  
  uint length() { return _set.length; }  
  
/**
 *  Add member to set.
 *
 *  Params:
 *    m =     New member of set.
 */
  T add(T m) {
    _set[m] = false;
    return m;
  }
  
/**
 *  Remove member from set.
 *
 *  Params:
 *    m =     Member to remove from set.
 */
  void remove(T m) {
    _set.remove(m);
  }
    
  int opApply(int delegate(inout T)dg) {
    int r = 0;
    foreach (T m, bool dummy; _set) {
      r = dg(m);
      if (r) {
        break;
      }
    }
    return r;
  }

}

/**
 *  A set of all even numbers of type int.
 */
public FunctionSet!(int) evenIntSet;

/**
 *  A set of all odd numbers of type int.
 */
public AbstractSet!(int) oddIntSet;

/**
 *  A set of all prime numbers of type int.
 */
public FunctionSet!(int) primeIntSet;

private Set!(int) dummyIntSet;

static this() {
  evenIntSet = new FunctionSet!(int)(delegate bool (int a){ return (a & 1) == 0; });
  oddIntSet = -evenIntSet;;
  bool isPrime(int v) {
    if (v < 2) {
      return false;
    } else if (v > 3) {
      if ((v % 2) == 0 || (v % 3) == 0) return false;
    }
    int inc = 2, mdiv = cast(int)sqrt(cast(double)v) + 1;
    for (int div = 5; div <= mdiv;) {
      if ((v % div) == 0) return false;
      div +=inc; inc = 6 - inc;
    }
    return true;
  }
  primeIntSet = new FunctionSet!(int)(&isPrime);
}