package org.varienaja.util;
   
   import java.util.Iterator;
   import java.util.Set;
   import java.util.TreeSet;
   
   /**
    * A Range contains a set of long-values between a start- and an end-value. 
    * The values in between are assumed to be there, but they are not stored
   * in memory.
   * @author Arjan Verstoep
   *
   */
  class Range implements Comparable<Range> {
  	//TODO Checking for start<=end etc.
  	private long _start, _end;
  	
  	public Range(long start, long end) {
  		setStart(start);
  		setEnd(end);
  	}
  
  	public long getEnd() {
  		return _end;
  	}
  
  	public void setEnd(long end) {
  		if (end>=_start) _end = end;
  	}
  
  	public long getStart() {
  		return _start;
  	}
  
  	public void setStart(long start) {
  		_start = start;
  	}
  	
  	public boolean contains(long l) {
  		return (_start<=l) && (l<=_end);
  	}
  	
  	public boolean equals(Object o) {
  		if (o instanceof Range) {
  			Range test = (Range) o;
  			return (test.getEnd()==getEnd()) && (test.getStart()==getStart());
  		} else {
  			return false;
  		}
  	}
  	
  	public int hashCode() {
  		Long l = _start * _end;
  		return l.intValue();
  	}
  	
  	public int compareTo(Range test) {
  		if (test.getStart()>getEnd()) {
  			return -1;
  		} else {
  			if (test.getEnd()<getStart()) {
  				return 1;
  			} else {
  				return 0;
  			}
  		}
  	}
  	
  	public long itemCount() {
  		return 1+_end-_start;
  	}
  	
  	public String toString() {
  		return "["+_start+"..."+_end+"]";
  	}
  	
  }
  
  /**
   * A Dense Set is a set of long-values. The Set is meant to contain many consecutive longs
   * while using as little memory as possible. The more holes there are in the list of
   * long-values, the more memory will be consumed. The memory consumption per hole is
   * constant and independent of the size of the hole.
   * 
   * The advantage of a DenseSet over a BitSet, is that the DenseSet has a
   * constant size. It can hold MAX_LONG values, and still use two longs memory.
   * Only the holes consume memory. A Bitset containing MAX_LONG bits would take
   * an insane amount of 2^64/8 bytes, regardless of the amount of holes. So, when
   * the amount of holes stays low enough, the DenseSet is a better choise than a
   * BitSet.
   * 
   * @author varienaja
   */
  public class DenseSet { //TODO implements Set, SortedSet, Collection, etc...
  	protected Set<Range> _ranges;
  	
  	public DenseSet() {
  		_ranges = new TreeSet<Range>();
  	}
 	
 	/**
 	 * @return The amount of long-values that is contained in the Set
 	 */
 	public int size() {
 		int result = 0;
 		for (Range range:_ranges) {
 			result += range.itemCount();
 		}
 		return result;
 	}
 	
 	/**
 	 * Adds a long to the Set of longs.
 	 * @param l The value to be added.
 	 * @return Whether the Set changed because of this operation
 	 */
 	public boolean add(long l) {
 		Range candidate = findRangeContaining(l);
 		if (candidate==null) {
 			//We've got work to do. Maybe l can be put in a range just besides it..
 			Range candidateSmaller = findRangeContaining(l-1);
 			Range candidateLarger = findRangeContaining(l+1);
 			if (candidateSmaller==null) {
 				if (candidateLarger==null) {
 					_ranges.add(new Range(l,l));
 				} else {
 					candidateLarger.setStart(l);
 				}
 			} else {
 				if (candidateLarger==null) {
 					candidateSmaller.setEnd(l);
 				} else {
 					//Merge candidateLarger and candidateSmaller
 					_ranges.remove(candidateLarger);
 					candidateSmaller.setEnd(candidateLarger.getEnd());
 				}
 			}
 			return true;
 		} else {
 			return false; //Element is already contained in this Set
 		}
 	}
 	
 	/**
 	/**
 	 * Removes a long value from the Set of longs.
 	 * @param l The long-value to be removed.
 	 * @return Whether the long was removed
 	 */
 	public boolean remove(long l) {
 		Range range = findRangeContaining(l);
 		if (range!=null) {
 			if (range.getStart()==l) {
 				//Make range smaller
 				if (range.getEnd()>l) {
 					range.setStart(l+1);
 				} else {
 					_ranges.remove(range);
 				}
 			} else {
 				//Make range smaller
 				if (range.getEnd()==l) {
 					if (range.getStart()<l) {
 						range.setEnd(l-1);
 					} else {
 						_ranges.remove(range);
 					}
 				} else {
 					//Split range
 					Range newOne = new Range(l+1,range.getEnd()); 
 					range.setEnd(l-1);
 					_ranges.add(newOne);
 				}
 			}
 			return true;
 		} else {
 			return false;
 		}
 	}
 	
 	/**
 	 * Removes all Long-values from the Set
 	 *
 	 */
 	public void clear() {
 		_ranges.clear();
 	}
 	
 	/**
 	 * Find the Range-object that contains a long-value
 	 * @param l The long-value that we're looking for
 	 * @return The Range that contains the long-value, or null if there is no such Range 
 	 */
 	private Range findRangeContaining(long l) {
 		//TODO Create Range, use that one to binary-search the TreeSet
 		for (Range range:_ranges) {
 			if (range.contains(l)) return range;
 		}
 		return null;
 	}
 	
 	public String toString() {
 		StringBuilder sb = new StringBuilder();
 		sb.append("Size: ");
 		sb.append(size());
 		sb.append(" Elements: ");
 		sb.append(_ranges.size());
 		sb.append(" ");
 		Iterator<Range> it = _ranges.iterator();
 		while (it.hasNext()) {
 			sb.append(it.next().toString());
 			if (it.hasNext()) sb.append(", ");
 		}
 		return sb.toString();
 	}
 	
 	/**
 	 * Returns a string representation of the contents of the set in
 	 * the format: a-b,c,d-e, ...
 	 * @return A String representation of the contents of the dense set.
 	 */
 	public String prettyPrint() {
 		StringBuilder sb = new StringBuilder();
 		Iterator<Range> it = _ranges.iterator();
 		while(it.hasNext()) {
 			Range range = it.next();
 			long start = range.getStart();
 			long end = range.getEnd();
 			sb.append(start);
 			if(start!=end) {
 				sb.append("-");
 				sb.append(range.getEnd());
 			}
 			if(it.hasNext()) {
 				sb.append(",");
 			}
 		}
 		return sb.toString();
 	}
 	
 	/**
 	 * Searches for a long-value at a specific position.
 	 * @param index The position to look in
 	 * @return returns the long that is at position index in the Set
 	 */
 	public long get(long index) {
 		for (Range range:_ranges) {
 			index -= range.itemCount();
 			if (index<0) {
 				return range.getStart() + index + range.itemCount();
 			}
 		}
 		return -1; //TODO ArrayOutOfBoundsException or something alike
 	}
 	
 	/**
 	 * Checks whether a certain value exists in the Set.
 	 * @param l The value to check for.
 	 * @return True, if this value is contained in this Set, False otherwise.
 	 */
 	public boolean contains(long l) {
 		return findRangeContaining(l)!=null;
 	}
 
 	public boolean equals(Object o) {
 		boolean result = false;
 		if (o instanceof DenseSet) {
 			DenseSet other = (DenseSet) o;
 			if (this.size()==other.size()) {
 				result = true;
 				Iterator<Range> it1 = _ranges.iterator();
 				Iterator<Range> it2 = other._ranges.iterator();
 				while(it1.hasNext()) {
 					Range r1 = it1.next();
 					if(it2.hasNext()) {
 						Range r2 = it2.next();
 						if(!r1.equals(r2)) {
 							break;
 						}
 					} else {
 						break;
 					}
 				}
 			}
 		}
 		return result;
 	}
 	
 	public int hashCode() {
 		int result = 0;
 		for(Range range: _ranges) {
 			result = (3 * result) + range.hashCode();
 		}
 		return result;
 	}
 }