/*
 *                    BioJava development code
 *
 * This code may be freely distributed and modified under the
 * terms of the GNU Lesser General Public Licence.  This should
 * be distributed with the code.  If you do not have a copy,
 * see:
 *
 *      http://www.gnu.org/copyleft/lesser.html
 *
 * Copyright for this code is held jointly by the individual
 * authors.  These should be listed in @author doc comments.
 *
 * For more information on the BioJava project and its aims,
 * or to join the biojava-l mailing list, visit the home page
 * at:
 *
 *      http://www.biojava.org/
 *
 */
package org.biojava.nbio.genome.parsers.gff;

import org.biojava.nbio.core.sequence.DNASequence;

import java.io.Serializable;
import java.util.*;
import java.util.Map.Entry;



/**
 * A list of FeatureI objects implemented using a Java ArrayList; corresponds to a GFF file.
 * This class is implemented entirely using FeatureI objects, so everything here will work
 * correctly if you choose to implement your own feature class -- there are no dependencies
 * on JavaGene's native Feature class.
 *
 *
 * @author Hanno Hinsch, Carmelo Foti
 */
@SuppressWarnings("serial")
public class FeatureList extends ArrayList<FeatureI> {

	 Map<String, Map<String,List<FeatureI>>> featindex = new HashMap<String,Map<String,List<FeatureI>>>();
	Location mLocation;			//genomic location (union of feature locations)

	/**
	 * Construct an empty list.
	 */
	public FeatureList() {
		mLocation = null;
	}

	/**
	 * Construct a new list containing the same features
	 * as the specified list.
	 *
	 * @param features An existing list or collection of FeatureI objects.
	 */
	public FeatureList(Collection<FeatureI> features) {
		this();
		this.add(features);

		mLocation = null;
	}

	/**
	 * Add specified feature to the end of the list. Updates the bounding location of the
	 * feature list, if needed.
	 *
	 * @param feature The FeatureI object to add.
	 * @return True if the feature was added.
	 */
	@Override
	public boolean add(FeatureI feature) {
		if (mLocation == null) {
			mLocation = feature.location().plus();
		} else if (null != feature.location()) {
			mLocation = mLocation.union(feature.location().plus());
		}
		for (Entry<String, String> entry : feature.getAttributes().entrySet()){
			if (featindex.containsKey(entry.getKey())){
				Map<String,List<FeatureI>> feat = featindex.get(entry.getKey());
				if (feat==null){
					feat= new HashMap<String,List<FeatureI>>();
				}
				List<FeatureI> features = feat.get(entry.getValue());
				if (features==null){
					features = new ArrayList<FeatureI>();
				}
				features.add(feature);
				feat.put(entry.getValue(), features);
				featindex.put(entry.getKey(), feat);
				//featindex.put(key, value)
			}
		}

		return super.add(feature);
	}

	/**
	 * Add all features in the specified list or collection to this list.
	 *
	 * @param list The collection of FeatureI objects.
	 */
	public void add(Collection<FeatureI> list) {
		for (FeatureI f : list) {
			add(f);
		}
	}

	/**
	 * The union of all locations of all features in this list, mapped to the positive strand.
	 * If an added feature is on the negative strand, its positive strand image is added
	 * to the union.
	 * The bounding location is not updated when a feature is removed from the list, so
	 * it is not guaranteed to be the minimal bounding location.
	 *
	 * @return A location that is the union of all feature locations in the list.
	 */
	public Location bounds() {
		return mLocation;
	}

	/**
	 * Check size of gaps between successive features in list. The features in
	 * the list are assumed to be appropriately ordered.
	 *
	 * @param gapLength The minimum gap length to consider. Use a gapLength
	 * of 0 to check if features are contiguous.
	 * @return True if list has any gaps equal to or greater than gapLength.
	 */
	public boolean hasGaps(int gapLength) {
		Location last = null;
		for (FeatureI f : this) {
			if (last != null && gapLength <= f.location().distance(last)) {
				return true;
			} else {
				last = f.location();
			}
		}

		return false;
	}




	/**
	 * Concatenate successive portions of the specified sequence
	 * using the feature locations in the list. The list is assumed to be appropriately
	 * ordered.
	 *
	 * @param sequence The source sequence from which portions should be selected.
	 * @return The spliced data.
	 * @throws IllegalStateException Out of order or overlapping FeatureI locations detected.
	 *
	 */
	public String splice(DNASequence sequence) {
		StringBuilder subData = new StringBuilder();
		Location last = null;

		for (FeatureI f : this) {
			Location loc = f.location();

			if (last == null || loc.startsAfter(last)) {
				subData.append(sequence.getSubSequence(loc.start(), loc.end()).toString());
				last = loc;
			} else {
				throw new IllegalStateException("Splice: Feature locations should not overlap.");
			}

		}

		return subData.toString();
	}

	/**
	 * Create a collection of all unique group ids in the list, as defined
	 * by the group() method of the features. For example, if the
	 * features are from a GFF1 file, then each group id identifies a particular gene,
	 * and this method returns a collection of all gene ids.
	 *
	 * @return A collection (suitable for iteration using Java's "for" loop) of all the
	 * group ids found in this list. The order of the values is undefined; it will not match
	 * the order of features in the list.
	 */
	public Collection<String> groupValues() {
		Set<String> set = new HashSet<String>();
		for (FeatureI f : this) {
			//enter in a set -- removes duplicates
			set.add(f.group());
		}

		return set;
	}

	/**
	 * Create a collection of the unique values for the specified key.
	 * Example: For GTF files, using the "gene_id" key will give the names of all
	 * the genes in this list.
	 *
	 * @return A collection (suitable for iteration using Java's "for" loop) of all the
	 * values found for this key. The order of the values is undefined; it will not match
	 * the order of features in the list.
	 */
	public Collection<String> attributeValues(String key) {
		if (featindex.containsKey(key)){
			Map<String, List<FeatureI>> map = featindex.get(key);
			Collection<String> result = map.keySet();
			if (result == null) result = new HashSet<String>();
			return Collections.unmodifiableCollection(result);
		}
		LinkedHashMap<String, String> hash = new LinkedHashMap<String, String>();
		for (FeatureI f : this) {
			//enter as a key -- removes duplicates
			hash.put(f.getAttribute(key), null);
		}

		return Collections.unmodifiableCollection(hash.keySet());
	}

	/**
	 * Create a list of all features that have the specified group id, as defined by
	 * the group() method of the features.
	 *
	 * @param groupid The group to match.
	 * @return A list of features having the specified group id.
	 */
	public FeatureList selectByGroup(String groupid) {
		FeatureList list = new FeatureList();
		for (FeatureI f : this) {
			if (f.group().equals(groupid)) {
				list.add(f);
			}
		}

		return list;
	}

	/**
	 * Create a list of all features that are of the specified type, as defined by
	 * the type() method of the features.
	 * This might be, for example, "exon" or "CDS".
	 *
	 * @param type The type to match.
	 * @return A list of features of the specified type.
	 */
	public FeatureList selectByType(String type) {
		FeatureList list = new FeatureList();
		for (FeatureI f : this) {
			if (f.type().equals(type)) {
				list.add(f);
			}
		}

		return list;
	}

	/**
	 * Create a list of all features that include the specified attribute key/value pair.
	 * This method now properly supports adding the index before or after adding the features.
	 * Adding features, then then index, then more features is still not supported.
	 *
	 * @param key The key to consider.
	 * @param value The value to consider.
	 * @return A list of features that include the key/value pair.
	 */
	public FeatureList selectByAttribute(String key, String value) {
		if (featindex.containsKey(key)){
			Map<String,List<FeatureI>> featuresmap = featindex.get(key);
			if (featuresmap==null) return new FeatureList();
			List<FeatureI> list = featuresmap.get(value);
			if (list == null){
				return new FeatureList();
			}
			return  new FeatureList(list);
		}
		FeatureList list = new FeatureList();
		for (FeatureI f : this) {
			if (f.hasAttribute(key, value)) {
				list.add(f);
			}
		}
		return list;
	}
	/**
	 * Create a list of all features that include the specified attribute key.
	 *
	 * @param key The key to consider.
	 * @return A list of features that include the key.
	 */
	public FeatureList selectByAttribute(String key) {
		FeatureList list = new FeatureList();
		if (featindex.containsKey(key)){
			Map<String, List<FeatureI>> featsmap =featindex.get(key);
			if(null != featsmap) {
				for (List<FeatureI> feats: featsmap.values()){
					list.addAll(Collections.unmodifiableCollection(feats));
				}
				return list;
			}
		}

		for (FeatureI f : this) {
			if (f.hasAttribute(key)) {
				list.add(f);
			}
		}
		return list;
	}

	/**
	 * Create a list of all features that include the specified key/value pair in their userMap().
	 *
	 * @param key The key to consider.
	 * @param value The value to consider.
	 * @return A list of features that include the key/value pair.
	 */
	public FeatureList selectByUserData(String key, Object value) {
		FeatureList list = new FeatureList();
		for (FeatureI f : this) {
			Object o = f.userData().get(key);
			if (o != null && o.equals(value)) {
				list.add(f);
			}
		}
		return list;
	}
	/**
	 * Create a list of all features that include the specified key in their userMap().
	 *
	 * @param key The key to consider.
	 * @return A list of features that include the key.
	 */
	public FeatureList selectByUserData(String key) {
		FeatureList list = new FeatureList();
		for (FeatureI f : this) {
			if (f.userData().containsKey(key)) {
				list.add(f);
			}
		}
		return list;
	}

	/**
	 * Create a list of all features that overlap the specified location on the specified
	 * sequence.
	 *
	 * @param seqname The sequence name. Only features with this sequence name will be checked for overlap.
	 * @param location The location to check.
	 * @param useBothStrands If true, locations are mapped to their positive strand image
	 * before being checked for overlap. If false, only features whose locations are
	 * on the same strand as the specified location will be considered for inclusion.
	 * @return The new list of features that overlap the location.
	 */
	public FeatureList selectOverlapping(String seqname, Location location, boolean useBothStrands)
			throws Exception {
		FeatureList list = new FeatureList();

		for (FeatureI feature : this) {
			boolean overlaps = false;
			if (feature.seqname().equals(seqname)) {
				if (location.isSameStrand(feature.location())) {
					overlaps = feature.location().overlaps(location);
				} else if (useBothStrands) {
					overlaps = feature.location().overlaps(location.opposite());
				}
			}
			if (overlaps) {
				list.add(feature);
			}
		}
		return list;
	}

	/**
	 * Create a list of all features that do not overlap the specified location on the specified sequence.
	 *
	 * @param seqname The sequence name. Only features with this sequence name will be checked for overlap.
	 * @param location The location to check.
	 * @param useBothStrands If true, locations are mapped to their positive strand image
	 * before being checked for overlap. If false, all features whose locations are
	 * on the opposite strand from the specified location will be considered non-overlapping.
	 * @return The new list of features that do not overlap the location.
	 */
	public FeatureList omitOverlapping(String seqname, Location location, boolean useBothStrands) {
		FeatureList list = new FeatureList();

		for (FeatureI feature : this) {
			boolean overlaps = false;
			if (feature.seqname().equals(seqname)) {
				if (location.isSameStrand(feature.location())) {
					overlaps = feature.location().overlaps(location);
				} else if (useBothStrands) {
					overlaps = feature.location().overlaps(location.opposite());
				}
			}

			if (!overlaps) {
				list.add(feature);
			}
		}

		return list;
	}

	/**
	 * Check if any feature in list has the specified attribute key.
	 *
	 * @param key The attribute key to consider.
	 * @return True if at least one feature has the attribute key.
	 */
	public boolean hasAttribute(String key) {
		if (featindex.containsKey(key)){
			Map<String, List<FeatureI>> mappa = featindex.get(key);
			if (mappa!= null && mappa.size()>0)return true;
			return false;
		}
		for (FeatureI f : this) {
			if (f.hasAttribute(key)) {
				return true;
			}
		}

		return false;
	}

	/**
	 * Check if any feature in list has the specified attribute key/value pair.
	 *
	 * @param key The attribute key to consider.
	 * @param value The attribute value to consider.
	 * @return True if at least one feature has the key/value pair.
	 */
	public boolean hasAttribute(String key, String value) {
		if (featindex.containsKey(key)){
			Map<String, List<FeatureI>> mappa = featindex.get(key);
			if (mappa == null) return false;
			if (mappa.containsKey(value)) return true;
			return false;
		}

		for (FeatureI f : this) {
			if (f.hasAttribute(key, value)) {
				return true;
			}
		}

		return false;
	}

	/**
	 * Return a string representation of all features in this list.
	 *
	 * @return A string.
	 */
	@Override
	public String toString() {
		StringBuilder  s = new StringBuilder("FeatureList: >>\n");
		for (FeatureI f : this) {
			s.append( f.seqname() + ":" + f.toString() + "\n");
		}

		s.append("\n<<\n");
		return s.toString();
	}

	/**
	 * used by sort routine
	 */
	private class FeatureComparator implements Comparator<FeatureI>, Serializable {
        private static final long serialVersionUID = 1;

		@Override
		public int compare(FeatureI a, FeatureI b) {
			if (a.seqname().equals(b.seqname()) && a.location().isSameStrand(b.location())) {
				return a.location().start() - b.location().start();		//sort on start
			} else {
				throw new IndexOutOfBoundsException("Cannot compare/sort features whose locations are on opposite strands or with different seqname().\r\n" + a.toString() + "\r\n" + b.toString() );
			}
		}
	}

	/**
	 * Create a new list that is ordered by the starting index of the features' locations. All locations
	 * must be on the same strand of the same sequence.
	 *
	 * @return An ordered list.
	 * @throws IndexOutOfBoundsException Cannot compare/sort features whose locations are on opposite strands, or
	 * whose seqnames differ.
	 */
	public FeatureList sortByStart() {
		FeatureI[] array = toArray(new FeatureI[1]);

		Arrays.sort(array, new FeatureComparator());

		return new FeatureList(Arrays.asList(array));
	}

	/**
	 * @deprecated
	 *
	 */
	// FIXME features may have a null location() !!
	@Deprecated
	static public void main(String[] args) {
	}


	/**
	 * Add a list of attributes that will be used as indexes for queries
	 * @param indexes  the List containing the attribute_id
	 */
	public void addIndexes(List<String> indexes) {
		for (String index : indexes){
			addIndex(index);
		}

	}
	/**
	 * Add an attribute that will be used as index for queries
	 * @param index an attribute_id
	 */
	public void addIndex(String index) {
		featindex.put(index, null);
	}
}
