/*
 * Copyright 2013 Yuichiro Moriguchi
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.morilib.sh.builtin;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import net.morilib.sh.ShEnvironment;
import net.morilib.sh.ShFileSystem;
import net.morilib.sh.ShProcess;
import net.morilib.unix.misc.OptionIterator;

public class ShSort implements ShProcess {

	private static class S1 {
		private int flags;
		private List<S2> fields = new ArrayList<S2>();
		private String ofile = null;
		private int sep = ' ';
	}

	private static class S2 {

		int fs, ch, fe;

		S2(int fs, int ch, int fe) {
			this.fs = fs;
			this.ch = ch;
			this.fe = fe;
		}

	}

	private static class CNum implements Comparator<String> {

		private S1 f;

		CNum(S1 f) {
			this.f = f;
		}

		public int compare(String s, String t) {
			String[] a, b;
			String v, w;
			int r;

			a = _split(f, s);  b = _split(f, t);
			for(S2 x : f.fields) {
				for(int i = x.fs; i < x.fe; i++) {
					if(i >= a.length && i >= b.length) {
						break;
					} else if(i < a.length && i >= b.length) {
						return 1;
					} else if(i >= a.length && i < b.length) {
						return -1;
					} else {
						if(x.ch > 0) {
							v = x.ch < a[i].length() ?
									a[i].substring(0, x.ch) : a[i];
							w = x.ch < b[i].length() ?
									b[i].substring(0, x.ch) : b[i];
						} else {
							v = a[i];  w = b[i];
						}
						if((r = cmpnum(f, v, w)) != 0)  return r;
					}
				}
			}
			return 0;
		}

	}

	private static class CStr implements Comparator<String> {

		private S1 f;

		CStr(S1 f) {
			this.f = f;
		}

		public int compare(String s, String t) {
			String[] a, b;
			String v, w;
			int r;

			a = _split(f, s);  b = _split(f, t);
			for(S2 x : f.fields) {
				for(int i = x.fs; i < x.fe; i++) {
					if(i >= a.length && i >= b.length) {
						break;
					} else if(i < a.length && i >= b.length) {
						return 1;
					} else if(i >= a.length && i < b.length) {
						return -1;
					} else {
						if(x.ch > 0) {
							v = x.ch < a[i].length() ?
									a[i].substring(0, x.ch) : a[i];
							w = x.ch < b[i].length() ?
									b[i].substring(0, x.ch) : b[i];
						} else {
							v = a[i];  w = b[i];
						}
						if((r = cmpstr(f, v, w)) != 0)  return r;
					}
				}
			}
			return 0;
		}
		
	}

	private static final String STDIN = "(stdin)";
	private static final int MAX_FIELDS = 1000000;
	private static final Pattern OBS =
			Pattern.compile("\\+([0-9]+(\\.[0-9]*[1-9])?)");
	private static final Pattern OB2 =
			Pattern.compile("-([0-9]+)");
	private static final Pattern NEW =
			Pattern.compile(
					"([0-9]*[1-9](\\.[0-9]*[1-9])?)(,([0-9]*[1-9]))?");
	private static final Pattern NUM =
			Pattern.compile("\\p{Space}*(-?)([0-9]*)\\.?");
	private static final Pattern SPC = Pattern.compile("\\p{Space}*");
	private static final Pattern ASP = Pattern.compile(" +");
	private static final Pattern POS =
			Pattern.compile("([0-9]+)(\\.([0-9]*[1-9]))?");
	private static final String ALS = "[^\\p{Alnum}\\p{Space}]+";
	private static final String ASC = "[^\\p{ASCII}]+";

	private static final int CHECK_SORTED = 1;
	private static final int MERGE = 2;
	private static final int IGNORE_SPACES = 4;
	private static final int USE_ALNUM_SPACES = 8;
	private static final int IGNORE_CASE = 16;
	private static final int USE_ASCII = 32;
	private static final int SORT_MONTHS = 64;
	private static final int SORT_NUMBERS = 128;
	private static final int REVERSE = 256;
	private static final int SUPPRESS_DUPLICATE = 512;

	private static void perror(PrintStream err, String n, String s) {
		err.print(n);
		err.print(": ");
		err.println(s);
	}

	private static int comparerev(String s, String t) {
		if(s.length() < t.length()) {
			return -1;
		} else if(s.length() > t.length()) {
			return 1;
		} else {
			return s.compareTo(t);
		}
	}

	private static int cmpstr(S1 f, String s1, String s2) {
		String s = s1, t = s2;
		Matcher m, n;
		int z;

		if((f.flags & IGNORE_SPACES) != 0) {
			m = SPC.matcher(s);  m.lookingAt();
			n = SPC.matcher(t);  n.lookingAt();
			s = s.substring(m.end());
			t = t.substring(n.end());
		}

		if((f.flags & USE_ASCII) != 0) {
			s = s.replaceAll(ASC, "");
			t = t.replaceAll(ASC, "");
		}

		if((f.flags & USE_ALNUM_SPACES) != 0) {
			s = s.replaceAll(ALS, "");
			t = t.replaceAll(ALS, "");
		}

		if((f.flags & IGNORE_CASE) != 0) {
			z = s.compareToIgnoreCase(t);
		} else {
			z = s.compareTo(t);
		}
		return ((f.flags & REVERSE) != 0) ? -z : z;
	}

	private static int cmpnum(S1 f, String s, String t) {
		String a1, b1, a2, b2;
		Matcher x, y;
		int z;

		x  = NUM.matcher(s);  y  = NUM.matcher(t);
		x.lookingAt();        y.lookingAt();
		a1 = x.group(1);      b1 = y.group(1);
		a2 = x.group(2);      b2 = y.group(2);
		if(a1.equals("") && b1.equals("-")) {
			z = 1;
		} else if(a1.equals("-") && b1.equals("")) {
			z = -1;
		} else if((z = comparerev(a2, b2)) != 0) {
			z = a1.equals("-") ? -z : z;
		} else {
			s = s.substring(x.end());
			t = t.substring(y.end());
			z = cmpstr(f, s, t);
		}
		return ((f.flags & REVERSE) != 0) ? -z : z;
	}

	private static String[] _split(S1 f, String s) {
		List<String> l = new ArrayList<String>();
		Matcher m;
		int k = 0;

		if(f.sep == ' ') {
			m = ASP.matcher(s);
			if(!m.lookingAt())  m.reset();
			while(m.find()) {
				l.add(s.substring(k, m.start()));
				k = m.end();
			}
			l.add(s.substring(k));
			return l.toArray(new String[0]);
		} else {
			return s.split("\\" + (char)f.sep);
		}
	}

	private Comparator<String> getcmp(S1 f) {
		return ((f.flags & SORT_NUMBERS) != 0) ?
				new CNum(f) : new CStr(f);
	}

	private S2 _pos1(String s) {
		S2 r = new S2(0, 0, MAX_FIELDS);
		Matcher m = POS.matcher(s);

		m.matches();
		r.fs = Integer.parseInt(m.group(1));
		if(m.group(3) != null) {
			r.ch = Integer.parseInt(m.group(3));
		}
		return r;
	}

	private S2 _pos2(String s, String t) {
		Matcher m = POS.matcher(s);
		S2 r = new S2(0, 0, 0);

		m.matches();
		r.fs = Integer.parseInt(m.group(1)) - 1;
		r.fe = t != null ? Integer.parseInt(t) : MAX_FIELDS;
		if(m.group(3) != null) {
			r.ch = Integer.parseInt(m.group(3));
		}
		return r;
	}

	int _check(S1 f, InputStream in, String n,
			Charset cset) throws IOException {
		Comparator<String> p = getcmp(f);
		BufferedReader rd;
		String s = null, t;

		rd = new BufferedReader(new InputStreamReader(in, cset));
		for(; (t = rd.readLine()) != null; s = t) {
			if(s != null && p.compare(s, t) > 0) {
				return 1;
			}
		}
		return 0;
	}

	boolean notnil(String[] ss) throws IOException {
		for(String s : ss) {
			if(s != null)  return true;
		}
		return false;
	}

	int _min(Comparator<String> p, String[] ss) {
		int k = 0;

		for(; k < ss.length && ss[k] == null; k++);
		for(int i = k + 1; i < ss.length; i++) {
			if(ss[i] == null)  continue;
			k = p.compare(ss[k], ss[i]) > 0 ? i : k;
		}
		return k;
	}

	int _merge(S1 f, ShFileSystem fs, PrintStream out,
			Charset cset, String... fls) throws IOException {
		BufferedReader[] rs = new BufferedReader[fls.length];
		String[] ss = new String[fls.length];
		Comparator<String> p = getcmp(f);
		int z;

		Arrays.fill(rs, null);
		try {
			for(int i = 0; i < fls.length; i++) {
				rs[i] = new BufferedReader(new InputStreamReader(
						fs.getFile(fls[i]).getInputStream(), cset));
				ss[i] = rs[i].readLine();
			}

			while(notnil(ss)) {
				z = _min(p, ss);
				out.println(ss[z]);
				ss[z] = rs[z].readLine();
			}
			return 0;
		} finally {
			for(int i = 0; i < fls.length; i++) {
				if(rs[i] != null)  rs[i].close();
			}
		}
	}

	int _sort(S1 f, List<String> l, InputStream in,
			String n, Charset cset) throws IOException {
		BufferedReader rd;
		String t;

		if((f.flags & CHECK_SORTED) != 0) {
			return _check(f, in, n, cset);
		}
		rd = new BufferedReader(new InputStreamReader(in, cset));
		while((t = rd.readLine()) != null)  l.add(t);
		return 0;
	}

	void _execsort(S1 f, List<String> l, PrintStream out) {
		Comparator<String> p = getcmp(f);
		String[] a;

		a  = l.toArray(new String[0]);
		Arrays.sort(a, p);
		for(int i = 0; i < a.length; i++) {
			if((f.flags & SUPPRESS_DUPLICATE) == 0 ||
					i == 0 || p.compare(a[i - 1], a[i]) != 0) {
				out.println(a[i]);
			}
		}
	}

	public int main(ShEnvironment env, ShFileSystem fs, InputStream in,
			PrintStream out, PrintStream err,
			String... args) throws IOException {
		String[] a = new String[args.length - 1];
		Charset cset = env.getCharset();
		InputStream ins = null;
		PrintStream ous = out;
		Iterator<String> q;
		OptionIterator o;
		S1 f = new S1();
		List<String> l;
		Matcher m;
		String s;
		int z;
		S2 x;

		System.arraycopy(args, 1, a, 0, a.length);
		o = new OptionIterator("1234567890.cmut:o:bdfiMnrk:",
				true, a);
		while(o.hasNext()) {
			if((m = OBS.matcher(s = o.getLookahead())).matches()) {
				f.fields.add(_pos1(m.group(1)));
				o.skip();
			} else if((m = OB2.matcher(s)).matches()) {
				if(f.fields.size() > 0) {
					f.fields.get(f.fields.size() - 1).fe =
							Integer.parseInt(m.group(1));
				} else {
					f.fields.add(new S2(
							0, 0, Integer.parseInt(m.group(1))));
				}
				o.skip();
			} else {
				switch(o.nextChar()) {
				case 'c':  f.flags |= CHECK_SORTED;  break;
				case 'm':  f.flags |= MERGE;  break;
				case 'u':  f.flags |= SUPPRESS_DUPLICATE;  break;
				case 't':
					if(o.getArgument().length() > 0) {
						f.sep = o.getArgument().charAt(0);
					}
					break;
				case 'o':  f.ofile = o.getArgument();  break;
				case 'b':  f.flags |= IGNORE_SPACES;  break;
				case 'd':  f.flags |= USE_ALNUM_SPACES;  break;
				case 'f':  f.flags |= IGNORE_CASE;  break;
				case 'i':  f.flags |= USE_ASCII;  break;
				case 'M':
					f.flags |= SORT_MONTHS;
					err.print(args[0]);
					err.print(": warning: ");
					err.print("option M is not supported");
					err.println(" in this version.");
					break;
				case 'n':  f.flags |= SORT_NUMBERS;  break;
				case 'r':  f.flags |= REVERSE;  break;
				case 'k':
					if(!(m = NEW.matcher(o.getArgument())).matches()) {
						perror(err, args[0], "invalid field");
						return 2;
					}
					f.fields.add(x = _pos2(m.group(1), m.group(4)));
					if(x.fs >= x.fe) {
						perror(err, args[0], "invalid field");
						return 2;
					}
					break;
				default:
					perror(err, args[0], "invalid argument");
					return 2;
				}
			}
		}

		try {
			if(f.ofile != null) {
				ous = fs.getFile(f.ofile).getPrintStream(false);
			}
			if(f.fields.isEmpty()) {
				f.fields.add(new S2(0, 0, MAX_FIELDS));
			}

			l = new ArrayList<String>();
			q = o.filenameIterator();
			if(!q.hasNext()) {
				if((z = _sort(f, l, in, STDIN, cset)) != 0)  return z;
			} else if((f.flags & MERGE) != 0) {
				l = new ArrayList<String>();
				while(q.hasNext())  l.add(q.next());
				return _merge(f, fs, ous, cset,
						l.toArray(new String[0]));
			} else {
				for(z = 0; q.hasNext();) {
					s = q.next();
					if(s.equals("-")) {
						z = _sort(f, l, in, STDIN, cset);
					} else {
						try {
							ins = fs.getFile(s).getInputStream();
							z = _sort(f, l, ins, s, cset);
						} finally {
							if(ins != null)  ins.close();
							ins = null;
						}
					}
					if(z != 0)  return z;
				}
			}
			_execsort(f, l, out);
			return z;
		} finally {
			if(ous != out)  ous.close();
		}
	}

}
