package org.simantics.scl.compiler.internal.parsing.utils;

import gnu.trove.list.array.TIntArrayList;

public class LineLocators {

    private static class ByteArrayLineLocator extends LineLocator {
        private final byte[] lineNumbers;
        private final int maxLine;
        
        public ByteArrayLineLocator(int[] rowStarts) {
            super(rowStarts);
            int lastRow = rowStarts.length-1;
            this.lineNumbers = new byte[rowStarts[lastRow]];
            this.maxLine = rowStarts.length-1;
            
            int position = 0;
            int line = 0;
            while(line < maxLine) {
                int endPosition = rowStarts[line+1];
                while(position < endPosition)
                    lineNumbers[position++] = (byte)line;
                ++line;
            }
        }
        
        @Override
        public int lineNumberFromPosition(int position) {
            if(position <= 0)
                return 0;
            if(position >= lineNumbers.length)
                return maxLine;
            return (int)lineNumbers[position];
        }
    }
    
    private static class CharArrayLineLocator extends LineLocator {
        private final char[] lineNumbers;
        private final int maxLine;
        
        public CharArrayLineLocator(int[] rowStarts) {
            super(rowStarts);
            int lastRow = rowStarts.length-1;
            this.lineNumbers = new char[rowStarts[lastRow]];
            this.maxLine = rowStarts.length-1;
            
            int position = 0;
            int line = 0;
            while(line < maxLine) {
                int endPosition = rowStarts[line+1];
                while(position < endPosition)
                    lineNumbers[position++] = (char)line;
                ++line;
            }
        }
        
        @Override
        public int lineNumberFromPosition(int position) {
            if(position <= 0)
                return 0;
            if(position >= lineNumbers.length)
                return maxLine;
            return (int)lineNumbers[position];
        }
    }
    
    private static class IntArrayLineLocator extends LineLocator {
        private final int[] lineNumbers;
        private final int maxLine;
        
        public IntArrayLineLocator(int[] rowStarts) {
            super(rowStarts);
            int lastRow = rowStarts.length-1;
            this.lineNumbers = new int[rowStarts[lastRow]];
            this.maxLine = rowStarts.length-1;
            
            int position = 0;
            int line = 0;
            while(line < maxLine) {
                int endPosition = rowStarts[line+1];
                while(position < endPosition)
                    lineNumbers[position++] = line;
                ++line;
            }
        }
        
        @Override
        public int lineNumberFromPosition(int position) {
            if(position <= 0)
                return 0;
            if(position >= lineNumbers.length)
                return maxLine;
            return lineNumbers[position];
        }
    }
    
    private static class BinarySearchLineLocator extends LineLocator {
        public BinarySearchLineLocator(int[] rowStarts) {
            super(rowStarts);
        }

        @Override
        public int lineNumberFromPosition(int position) {
            if(position <= 0)
                return 0;
            if(position >= rowStarts[rowStarts.length-1])
                return rowStarts.length-1;
            int low = 0;
            int high = rowStarts.length-1;
            // invariant, low <= lineNumber < high
            while(low < high-1) {
                int middle = (low+high) / 2;
                if(position < rowStarts[middle])
                    high = middle;
                else
                    low = middle;
            }
            return low;
        }
    }
    
    private static class InterpolationSearchLineLocator extends LineLocator {
        public InterpolationSearchLineLocator(int[] rowStarts) {
            super(rowStarts);
        }

        @Override
        public int lineNumberFromPosition(int position) {
            if(position <= 0)
                return 0;
            if(position >= rowStarts[rowStarts.length-1])
                return rowStarts.length-1;
            int low = 0;
            int lowPosition = 0;
            int high = rowStarts.length-1;
            int highPosition = rowStarts[high];
            // invariant, low <= lineNumber < high
            while(low < high-1) {
                int delta = (int)((long)(high - low) * (position - lowPosition) / (highPosition - lowPosition));
                int middle = low + delta;
                if(middle == low)
                    ++middle;
                if(position < rowStarts[middle]) {
                    high = middle;
                    highPosition = rowStarts[high];
                }
                else {
                    low = middle;
                    lowPosition = rowStarts[low];
                }
            }
            return low;
        }
    }

    public static final LineLocator DUMMY_LOCATOR = new LineLocator(new int[] {0}) {
        @Override
        public int lineNumberFromPosition(int position) {
            return 0;
        }
    };
    
    private static int[] findRowStarts(String source) {
        TIntArrayList rowStarts = new TIntArrayList();
        rowStarts.add(0);

        int length = source.length();
        for(int i=0;i<length;++i) {
            char c = source.charAt(i);
            if(c == '\n')
                rowStarts.add(i+1);
        }
        return rowStarts.toArray();
    }

    public static LineLocator createLineLocator(String source) {
        int[] rowStarts = findRowStarts(source);
        if(rowStarts.length <= Byte.MAX_VALUE)
            return new ByteArrayLineLocator(rowStarts);
        else if(rowStarts.length <= Character.MAX_VALUE)
            return new CharArrayLineLocator(rowStarts);
        else
            return new InterpolationSearchLineLocator(rowStarts);
    }
}