/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
 * Use of this file is governed by the BSD 3-clause license that
 * can be found in the LICENSE.txt file in the project root.
 */

const {Token} = require('./Token');

/* stop is not included! */
class Interval {
	constructor(start, stop) {
		this.start = start;
		this.stop = stop;
	}

	contains(item) {
		return item >= this.start && item < this.stop;
	}

	toString() {
		if(this.start===this.stop-1) {
			return this.start.toString();
		} else {
			return this.start.toString() + ".." + (this.stop-1).toString();
		}
	}

	get length(){
		return this.stop - this.start;
	}
}


class IntervalSet {
	constructor() {
		this.intervals = null;
		this.readOnly = false;
	}

	first(v) {
		if (this.intervals === null || this.intervals.length===0) {
			return Token.INVALID_TYPE;
		} else {
			return this.intervals[0].start;
		}
	}

	addOne(v) {
		this.addInterval(new Interval(v, v + 1));
	}

	addRange(l, h) {
		this.addInterval(new Interval(l, h + 1));
	}

	addInterval(toAdd) {
		if (this.intervals === null) {
			this.intervals = [];
			this.intervals.push(toAdd);
		} else {
			// find insert pos
			for (let pos = 0; pos < this.intervals.length; pos++) {
				const existing = this.intervals[pos];
				// distinct range -> insert
				if (toAdd.stop < existing.start) {
					this.intervals.splice(pos, 0, toAdd);
					return;
				}
				// contiguous range -> adjust
				else if (toAdd.stop === existing.start) {
					this.intervals[pos].start = toAdd.start;
					return;
				}
				// overlapping range -> adjust and reduce
				else if (toAdd.start <= existing.stop) {
					this.intervals[pos] = new Interval(Math.min(existing.start, toAdd.start), Math.max(existing.stop, toAdd.stop));
					this.reduce(pos);
					return;
				}
			}
			// greater than any existing
			this.intervals.push(toAdd);
		}
	}

	addSet(other) {
		if (other.intervals !== null) {
			other.intervals.forEach( toAdd => this.addInterval(toAdd), this);
		}
		return this;
	}

	reduce(pos) {
		// only need to reduce if pos is not the last
		if (pos < this.intervals.length - 1) {
			const current = this.intervals[pos];
			const next = this.intervals[pos + 1];
			// if next contained in current
			if (current.stop >= next.stop) {
				this.intervals.splice(pos + 1, 1);
				this.reduce(pos);
			} else if (current.stop >= next.start) {
				this.intervals[pos] = new Interval(current.start, next.stop);
				this.intervals.splice(pos + 1, 1);
			}
		}
	}

	complement(start, stop) {
		const result = new IntervalSet();
		result.addInterval(new Interval(start,stop+1));
		if(this.intervals !== null)
			this.intervals.forEach(toRemove => result.removeRange(toRemove));
		return result;
	}

	contains(item) {
		if (this.intervals === null) {
			return false;
		} else {
			for (let k = 0; k < this.intervals.length; k++) {
				if(this.intervals[k].contains(item)) {
					return true;
				}
			}
			return false;
		}
	}

	removeRange(toRemove) {
		if(toRemove.start===toRemove.stop-1) {
			this.removeOne(toRemove.start);
		} else if (this.intervals !== null) {
			let pos = 0;
			for(let n=0; n<this.intervals.length; n++) {
				const existing = this.intervals[pos];
				// intervals are ordered
				if (toRemove.stop<=existing.start) {
					return;
				}
				// check for including range, split it
				else if(toRemove.start>existing.start && toRemove.stop<existing.stop) {
					this.intervals[pos] = new Interval(existing.start, toRemove.start);
					const x = new Interval(toRemove.stop, existing.stop);
					this.intervals.splice(pos, 0, x);
					return;
				}
				// check for included range, remove it
				else if(toRemove.start<=existing.start && toRemove.stop>=existing.stop) {
					this.intervals.splice(pos, 1);
					pos = pos - 1; // need another pass
				}
				// check for lower boundary
				else if(toRemove.start<existing.stop) {
					this.intervals[pos] = new Interval(existing.start, toRemove.start);
				}
				// check for upper boundary
				else if(toRemove.stop<existing.stop) {
					this.intervals[pos] = new Interval(toRemove.stop, existing.stop);
				}
				pos += 1;
			}
		}
	}

	removeOne(value) {
		if (this.intervals !== null) {
			for (let i = 0; i < this.intervals.length; i++) {
				const existing = this.intervals[i];
				// intervals are ordered
				if (value < existing.start) {
					return;
				}
				// check for single value range
				else if (value === existing.start && value === existing.stop - 1) {
					this.intervals.splice(i, 1);
					return;
				}
				// check for lower boundary
				else if (value === existing.start) {
					this.intervals[i] = new Interval(existing.start + 1, existing.stop);
					return;
				}
				// check for upper boundary
				else if (value === existing.stop - 1) {
					this.intervals[i] = new Interval(existing.start, existing.stop - 1);
					return;
				}
				// split existing range
				else if (value < existing.stop - 1) {
					const replace = new Interval(existing.start, value);
					existing.start = value + 1;
					this.intervals.splice(i, 0, replace);
					return;
				}
			}
		}
	}

	toString(literalNames, symbolicNames, elemsAreChar) {
		literalNames = literalNames || null;
		symbolicNames = symbolicNames || null;
		elemsAreChar = elemsAreChar || false;
		if (this.intervals === null) {
			return "{}";
		} else if(literalNames!==null || symbolicNames!==null) {
			return this.toTokenString(literalNames, symbolicNames);
		} else if(elemsAreChar) {
			return this.toCharString();
		} else {
			return this.toIndexString();
		}
	}

	toCharString() {
		const names = [];
		for (let i = 0; i < this.intervals.length; i++) {
			const existing = this.intervals[i];
			if(existing.stop===existing.start+1) {
				if ( existing.start===Token.EOF ) {
					names.push("<EOF>");
				} else {
					names.push("'" + String.fromCharCode(existing.start) + "'");
				}
			} else {
				names.push("'" + String.fromCharCode(existing.start) + "'..'" + String.fromCharCode(existing.stop-1) + "'");
			}
		}
		if (names.length > 1) {
			return "{" + names.join(", ") + "}";
		} else {
			return names[0];
		}
	}

	toIndexString() {
		const names = [];
		for (let i = 0; i < this.intervals.length; i++) {
			const existing = this.intervals[i];
			if(existing.stop===existing.start+1) {
				if ( existing.start===Token.EOF ) {
					names.push("<EOF>");
				} else {
					names.push(existing.start.toString());
				}
			} else {
				names.push(existing.start.toString() + ".." + (existing.stop-1).toString());
			}
		}
		if (names.length > 1) {
			return "{" + names.join(", ") + "}";
		} else {
			return names[0];
		}
	}

	toTokenString(literalNames, symbolicNames) {
		const names = [];
		for (let i = 0; i < this.intervals.length; i++) {
			const existing = this.intervals[i];
			for (let j = existing.start; j < existing.stop; j++) {
				names.push(this.elementName(literalNames, symbolicNames, j));
			}
		}
		if (names.length > 1) {
			return "{" + names.join(", ") + "}";
		} else {
			return names[0];
		}
	}

	elementName(literalNames, symbolicNames, token) {
		if (token === Token.EOF) {
			return "<EOF>";
		} else if (token === Token.EPSILON) {
			return "<EPSILON>";
		} else {
			return literalNames[token] || symbolicNames[token];
		}
	}

	get length(){
		return this.intervals.map( interval => interval.length ).reduce((acc, val) => acc + val);
	}
}

module.exports = {
	Interval,
	IntervalSet
};
