/*
 * Copyright (c) 2007-2010 by The Broad Institute, Inc. and the Massachusetts Institute of Technology.
 * All Rights Reserved.
 *
 * This software is licensed under the terms of the GNU Lesser General Public License (LGPL), Version 2.1 which
 * is available at http://www.opensource.org/licenses/lgpl-2.1.php.
 *
 * THE SOFTWARE IS PROVIDED "AS IS." THE BROAD AND MIT MAKE NO REPRESENTATIONS OR WARRANTIES OF
 * ANY KIND CONCERNING THE SOFTWARE, EXPRESS OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, NONINFRINGEMENT, OR THE ABSENCE OF LATENT
 * OR OTHER DEFECTS, WHETHER OR NOT DISCOVERABLE.  IN NO EVENT SHALL THE BROAD OR MIT, OR THEIR
 * RESPECTIVE TRUSTEES, DIRECTORS, OFFICERS, EMPLOYEES, AND AFFILIATES BE LIABLE FOR ANY DAMAGES OF
 * ANY KIND, INCLUDING, WITHOUT LIMITATION, INCIDENTAL OR CONSEQUENTIAL DAMAGES, ECONOMIC
 * DAMAGES OR INJURY TO PROPERTY AND LOST PROFITS, REGARDLESS OF WHETHER THE BROAD OR MIT SHALL
 * BE ADVISED, SHALL HAVE OTHER REASON TO KNOW, OR IN FACT SHALL KNOW OF THE POSSIBILITY OF THE
 * FOREGOING.
 */
package org.broad.igv.track;

import org.apache.log4j.Logger;
import org.broad.igv.Globals;
import org.broad.igv.PreferenceManager;
import org.broad.igv.feature.*;
import org.broad.igv.renderer.*;
import org.broad.igv.session.ViewContext;
import org.broad.igv.ui.IGVMainFrame;
import org.broad.igv.ui.UIConstants;
import org.broad.igv.ui.WaitCursorManager;
import org.broad.igv.ui.util.MessageUtils;
import org.broad.igv.util.BrowserLauncher;
import org.broad.igv.util.LongRunningTask;
import org.broad.igv.util.NamedRunnable;
import org.broad.igv.util.ResourceLocator;

import java.awt.*;
import java.awt.event.MouseEvent;
import java.io.IOException;
import java.net.URLEncoder;
import java.util.*;
import java.util.List;

/**
 * @author jrobinso
 */
public class FeatureTrack extends AbstractTrack {

    private static Logger log = Logger.getLogger(FeatureTrack.class);
    static int maxLevels = 200;

    private boolean expanded;
    private List<Rectangle> featureRects = new ArrayList();
    private PackedFeatures packedFeatures;

    private FeatureRenderer renderer;
    private DataRenderer coverageRenderer;

    // true == features,  false =  coverage
    private boolean showFeatures = true;

    protected FeatureSource source;
    private static final int MINIMUM_FEATURE_SPACING = 1;
    private int visibilityWindow = -1;

    private Rectangle expandButtonRect = expandButtonRect = new Rectangle();
    private static final int EXPAND_ICON_BUFFER_WIDTH = 17;
    private static final int EXPAND_ICON_BUFFER_HEIGHT = 17;
    public static final int MARGIN = 5;
    public static final String FEATURE_VISIBILITY_WINDOW = "featureVisibilityWindow";


    public FeatureTrack(String id, FeatureSource source) {
        super(id);
        init(source);
    }


    public FeatureTrack(ResourceLocator locator, FeatureSource source) {
        super(locator);
        init(source);
        this.getMinimumHeight();
    }

    private void init(FeatureSource source) {
        this.expanded = PreferenceManager.getInstance().isExpandTracks();
        this.source = source;
        setMinimumHeight(10);
        setColor(Color.blue.darker());
        coverageRenderer = new HeatmapRenderer();

        if (source.getBinSize() > 0) {
            visibilityWindow = source.getBinSize();
        }
    }

    @Override
    public void setTrackProperties(TrackProperties trackProperties) {
        super.setTrackProperties(trackProperties);

        if (trackProperties.getFeatureVisibilityWindow() >= 0) {
            setVisibilityWindow(trackProperties.getFeatureVisibilityWindow());
        }

    }

    @Override
    public int getHeight() {

        if (false == isVisible()) {
            return 0;
        }
        return super.getHeight() * Math.max(1, getNumberOfFeatureLevels());
    }

    public int getNumberOfFeatureLevels() {

        return expanded ? (packedFeatures == null ? 1 : packedFeatures.getRowCount()) : 1;
    }

    /**
     * Return a score over the interval.  This is required by the track interface to support sorting.
     *
     * @param chr   ignored
     * @param start ignored
     * @param end   ignored
     * @param zoom  ignored
     * @param type  ignored
     * @return 0
     */
    public float getRegionScore(String chr, int start, int end, int zoom, RegionScoreType type) {
        return -Float.MAX_VALUE;
    }


    public FeatureRenderer getRenderer() {
        if (renderer == null) {
            setRendererClass(BasicFeatureRenderer.class);
        }
        return renderer;
    }

    /**
     * Return a string for popup text.
     *
     * @param chr
     * @param position -- 1 relative coordinates
     * @param y
     * @return
     */
    public String getValueStringAt(String chr, double position, int y) {


        if (showFeatures) {
            // Reverse lookup, get mouse X position from mouse.  Consider refactoring to get it directly
            double scale = ViewContext.getInstance().getScale();
            double origin = ViewContext.getInstance().getOrigin();
            int x = (int) ((position - origin) / scale);
            if (x < EXPAND_ICON_BUFFER_WIDTH) {
                if (expandButtonRect.contains(x, y)) {
                    return "<b><strong>Click to " + (isExpanded() ? " collapse track " : " expand track</strong></b>");
                } else {
                    return "";
                }
            }


            Feature feature = getFeatureAt(chr, position, y);

            //getRenderer().setHighlightFeature(feature);

            return (feature == null) ? null : feature.getValueString(position, null);
        } else {
            int zoom = Math.max(0, ViewContext.getInstance().getZoom());
            List<LocusScore> scores = source.getCoverageScores(chr, (int) position - 10, (int) position + 10, zoom);

            if (scores == null) {
                return "";
            } else {
                // give a 2 pixel window, otherwise very narrow features will be missed.
                double bpPerPixel = ViewContext.getInstance().getScale();
                double minWidth = MINIMUM_FEATURE_SPACING * bpPerPixel;    /* * */
                LocusScore score = (LocusScore) FeatureUtils.getFeatureAt(position, minWidth, scores);
                return score == null ? "" : "Mean count: " + score.getScore();
            }

        }
    }

    private Feature getFeatureAt(String chr, double position, int y) {

        if (packedFeatures == null) {
            return null;
        }

        Feature feature = null;
        // Determine the level number (for expanded tracks.
        int levelNumber = 0;
        if (featureRects != null) {
            for (int i = 0; i < featureRects.size(); i++) {
                Rectangle r = featureRects.get(i);
                if ((y >= r.y) && (y <= r.getMaxY())) {
                    levelNumber = i;
                    break;
                }
            }
        }

        int nLevels = this.getNumberOfFeatureLevels();
        List<Feature> features = null;
        if ((nLevels > 1) && (levelNumber < nLevels)) {
            features = packedFeatures.rows.get(levelNumber).features;
        } else {
            features = packedFeatures.features;
        }
        if (features != null) {

            // give a 2 pixel window, otherwise very narrow features will be missed.
            double bpPerPixel = ViewContext.getInstance().getScale();
            double minWidth = MINIMUM_FEATURE_SPACING * bpPerPixel;
            feature = (Feature) FeatureUtils.getFeatureAt(position, minWidth, features);
        }
        return feature;
    }

    public WindowFunction getWindowFunction() {
        return WindowFunction.count;
    }

    @Override
    public boolean handleClick(MouseEvent e) {

        if (e.getClickCount() == 1 && !e.isShiftDown() && !e.isPopupTrigger() && e.getButton() == MouseEvent.BUTTON1) {
            if (e.getX() < EXPAND_ICON_BUFFER_WIDTH) {
                if (expandButtonRect.contains(e.getPoint())) {
                    setExpanded(!expanded);
                    IGVMainFrame.getInstance().doResizeTrackPanels();
                    IGVMainFrame.getInstance().doRefresh();
                }
                return true;
            }


            Feature f = getFeatureAtMousePosition(e);

            if (f != null) {
                String url = f.getURL();
                if (url == null) {
                    String trackURL = getUrl();
                    if (trackURL != null && f.getIdentifier() != null) {
                        String encodedID = URLEncoder.encode(f.getIdentifier());
                        url = trackURL.replaceAll("\\$\\$", encodedID);
                    }
                }
                // A scheduler is used so that the browser opening can be canceled in the event of a double
                // click.  In that case the first click will schedule the browser opening, but it is delayed
                // long enough to enable the second click to cancel it.
                if (url != null) {
                    scheduleBrowserTask(url, UIConstants.getDoubleClickInterval());
                    e.consume();
                    return true;
                }
            }

        } else

        {
            // This call will cancel opening a browser in the event of a double click
            cancelBrowserTask();
        }

        return false;
    }

    public Feature getFeatureAtMousePosition(MouseEvent e) {
        double location = getViewContext().getChromosomePosition(e.getX());
        double displayLocation = location + 1;
        Feature f = getFeatureAt(getViewContext().getChrName(), displayLocation, e.getY());
        return f;
    }


    @Override
    public boolean isExpanded() {
        return expanded;
    }

    /**
     * Required by the interface, really not applicable to feature tracks
     */
    public boolean isLogNormalized() {
        return true;
    }


    public void overlay(RenderContext context, Rectangle rect) {
        getRenderer().setOverlayMode(true);
        renderFeatures(context, rect);
    }

    public void render(RenderContext context, Rectangle rect) {
        getRenderer().setOverlayMode(false);
        Rectangle renderRect = new Rectangle(rect);
        renderRect.y = renderRect.y + MARGIN;
        renderRect.height -= MARGIN;


        double windowSize = rect.width * context.getScale();

        int vw = getVisibilityWindow();
        showFeatures = true;
        if (vw == 0) {
            showFeatures = !context.getChr().equals(Globals.CHR_ALL);
        } else if (vw > 0) {
            showFeatures = !context.getChr().equals(Globals.CHR_ALL) && windowSize <= vw;
        }

        if (showFeatures) {
            renderFeatures(context, renderRect);
        } else {
            renderCoverage(context, renderRect);
        }
        boolean showIcon = PreferenceManager.getInstance().getBooleanPreference(PreferenceManager.SHOW_EXPAND_ICON, true);
        if (showIcon && !IGVMainFrame.getInstance().isExportingSnapshot()) {
            renderExpandTool(context, rect);
        }
    }

    private void renderCoverage(RenderContext context, Rectangle inputRect) {
        List<LocusScore> scores = source.getCoverageScores(context.getChr(), (int) context.getOrigin(),
                (int) context.getEndLocation(), context.getZoom());
        if (scores == null) {
            Graphics2D g = context.getGraphic2DForColor(Color.gray);
            Rectangle textRect = new Rectangle(inputRect);

            // Keep text near the top of the track rectangle
            textRect.height = Math.min(inputRect.height, 20);
            String message = context.getChr().equals(Globals.CHR_ALL) ? "Zoom in to see features." :
                    "Zoom in to see features, or right-click to increase Feature Visibility Window.";
            GraphicUtils.drawCenteredText(message, textRect, g);
        } else {
            float max = getMaxEstimate(scores);
            ContinuousColorScale cs = getColorScale();
            if (cs != null) {
                cs.setPosEnd(max);
            }
            setDataRange(new DataRange(0, 0, max));
            coverageRenderer.render(this, scores, context, inputRect);
        }
    }


    private float getMaxEstimate(List<LocusScore> scores) {
        float max = 0;
        int n = Math.min(200, scores.size());
        for (int i = 0; i < n; i++) {
            max = Math.max(max, scores.get(i).getScore());
        }
        return max;
    }


    private boolean featuresLoading = false;


    private int[] p1 = new int[3];
    private int[] p2 = new int[3];

    private void renderExpandTool(RenderContext contect, Rectangle rect) {

        if (packedFeatures == null || packedFeatures.getRowCount() <= 1) {
            return;
        }

        Graphics2D g2d = contect.getGraphic2DForColor(Color.DARK_GRAY);
        int levelHeight = getHeight() / this.getNumberOfFeatureLevels() + 1;

        g2d.clearRect(rect.x, rect.y, EXPAND_ICON_BUFFER_WIDTH, levelHeight);

        expandButtonRect.x = rect.x + 3;
        expandButtonRect.y = rect.y + MARGIN + 4;
        expandButtonRect.width = 10;
        expandButtonRect.height = 10;

        if (expanded) {
            p1[0] = expandButtonRect.x;
            p1[1] = expandButtonRect.x + 8;
            p1[2] = expandButtonRect.x + 4;
            p2[0] = expandButtonRect.y;
            p2[1] = expandButtonRect.y;
            p2[2] = expandButtonRect.y + 8;
            g2d.fillPolygon(p1, p2, 3);

        } else {
            p1[0] = expandButtonRect.x;
            p1[1] = expandButtonRect.x + 8;
            p1[2] = expandButtonRect.x;
            p2[0] = expandButtonRect.y;
            p2[1] = expandButtonRect.y + 4;
            p2[2] = expandButtonRect.y + 8;
            g2d.fillPolygon(p1, p2, 3);
        }

    }


    // Render features in the given input rectangle.

    private void renderFeatures(RenderContext context, Rectangle inputRect) {

        if (featuresLoading) {
            return;
        }

        //if (log.isDebugEnabled()) {
        //    log.debug("renderFeatures: " + getName());
        //}

        String chr = context.getChr();
        int start = (int) context.getOrigin();
        int end = (int) context.getEndLocation() + 1;
        if (packedFeatures == null || !packedFeatures.containsInterval(chr, start, end)) {
            featuresLoading = true;
            int maxEnd = end;
            Genome genome = ViewContext.getInstance().getGenome();
            if (genome != null) {
                Chromosome c = genome.getChromosome(chr);
                if (c != null) maxEnd = Math.max(c.getLength(), end);
            }
            int delta = (end - start) / 2;
            int expandedStart = Math.max(0, start - delta);
            int expandedEnd = Math.min(maxEnd, end + delta);

            loadFeatures(chr, expandedStart, expandedEnd);

            if (!IGVMainFrame.getInstance().isExportingSnapshot()) {
                return;
            }
        }


        if (expanded) {
            List<FeatureRow> rows = packedFeatures.rows;
            if (rows != null && rows.size() > 0) {

                int nLevels = rows.size();
                synchronized (featureRects) {

                    featureRects.clear();

                    // Divide rectangle into equal height levels
                    double h = inputRect.getHeight() / nLevels;
                    Rectangle rect = new Rectangle(inputRect.x, inputRect.y, inputRect.width, (int) h);
                    for (FeatureRow row : rows) {
                        featureRects.add(new Rectangle(rect));
                        getRenderer().renderFeatures(row.features, context, rect, this);
                        rect.y += h;
                    }
                }
            }
        } else {
            List<Feature> features = packedFeatures.features;
            if (features != null) {
                getRenderer().renderFeatures(features, context, inputRect, this);
            }
        }


    }

    /**
     * Loads and segregates features into rows such that they do not overlap.  Loading is done in a background
     * thread.
     *
     * @param chr
     * @param start
     * @param end
     */
    private void loadFeatures(final String chr, final int start, final int end) {

        NamedRunnable runnable = new NamedRunnable() {
            public void run() {
                try {

                    // TODO -- implement source to return iterators
                    Iterator<Feature> iter = source.getFeatures(chr, start, end);
                    if (iter == null) {
                        packedFeatures = new PackedFeatures(chr, start, end);
                    } else {
                        packedFeatures = new PackedFeatures(chr, start, end, iter, getName());
                    }

                    IGVMainFrame.getInstance().repaint();
                } catch (Throwable e) {
                    // Mark the interval with an empty feature list to prevent an endless loop of load
                    // attempts.
                    packedFeatures = new PackedFeatures(chr, start, end);
                    String msg = "Error loading features for interval: " +
                            chr + ":" + start + "-" + end + " <br>" + e.toString();
                    MessageUtils.showMessage(msg);
                    log.error(msg, e);
                }

                finally {
                    featuresLoading = false;
                    if (log.isDebugEnabled()) {
                        log.debug("features loaded");
                    }
                }
            }

            public String getName() {
                return "Load features: " + FeatureTrack.this.getName();
            }
        };

        LongRunningTask.submit(runnable);
    }


    @Override
    public void setExpanded(boolean value) {
        expanded = value;
    }

    @Override
    public void setHeight(int newHeight) {

        int levelCount = this.getNumberOfFeatureLevels();
        super.setHeight(Math.max(getMinimumHeight(), newHeight / levelCount));
    }

    public void setRendererClass(Class rc) {
        try {
            renderer = (FeatureRenderer) rc.newInstance();
        } catch (Exception ex) {
            log.error("Error instatiating renderer ", ex);
        }
    }

    public void setStatType(WindowFunction type) {
    }

    /**
     * Method description
     *
     * @param zoom
     */
    public void setZoom(int zoom) {
    }

    /**
     * A timer task is used for opening web links to distinguish a click from a double click.
     */
    private TimerTask currentBrowserTask = null;

    private void cancelBrowserTask() {
        if (currentBrowserTask != null) {
            currentBrowserTask.cancel();
            currentBrowserTask = null;
        }
    }

    private void scheduleBrowserTask(final String url, int delay) {
        cancelBrowserTask();
        currentBrowserTask = new TimerTask() {
            public void run() {
                try {
                    BrowserLauncher.openURL(url);
                } catch (IOException e1) {
                    log.error("Error opening url: " + url);
                }
            }
        };
        (new java.util.Timer()).schedule(currentBrowserTask, delay);
    }


    /**
     * Return the nextLine or previous feature relative to the center location.
     * TODO -- investigate delegating this method to FeatureSource, where it might be possible to simplify the implementation
     *
     * @param chr
     * @param center
     * @param forward
     * @return
     * @throws IOException
     */
    public Feature nextFeature(String chr, double center, boolean forward) throws IOException {

        Feature f = null;
        ViewContext vc = ViewContext.getInstance();
        boolean canScroll = (forward && !vc.windowAtEnd()) ||
                (!forward && vc.getOrigin() > 0);

        if (packedFeatures != null && packedFeatures.containsInterval(chr, (int) center - 1, (int) center + 1)) {
            if (packedFeatures.features.size() > 0 && canScroll) {
                f = (Feature)
                        (forward ? FeatureUtils.getFeatureAfter(center + 1, packedFeatures.features) :
                                FeatureUtils.getFeatureBefore(center - 1, packedFeatures.features));
            }

            if (f == null) {
                int binSize = source.getBinSize();

                if (forward == true) {
                    // Forward
                    int nextStart = packedFeatures.end;
                    String nextChr = chr;
                    while (nextChr != null) {
                        int chrLength = vc.getGenome().getChromosome(nextChr).getLength();
                        while (nextStart < chrLength) {
                            int nextEnd = binSize > 0 ? nextStart + source.getBinSize() : chrLength;
                            Iterator<Feature> iter = source.getFeatures(nextChr, nextStart, nextEnd);

                            // The check on position should not be neccessary, but not all implementations of getFeatures
                            // obey the contract to return features only in the interval.
                            if (iter != null) {
                                while (iter.hasNext()) {
                                    Feature feat = iter.next();
                                    if (feat.getStart() > nextStart) {
                                        return feat;
                                    }
                                }
                            }
                            nextStart = nextEnd;
                        }
                        nextChr = vc.getNextChrName(nextChr);
                        nextStart = 0;
                    }
                } else {
                    // Reverse
                    int nextEnd = packedFeatures.start;
                    String nextChr = chr;
                    while (nextChr != null) {
                        while (nextEnd > 0) {
                            int nextStart = binSize > 0 ? Math.max(0, nextEnd - source.getBinSize()) : 0;
                            Iterator<Feature> iter = source.getFeatures(nextChr, nextStart, nextEnd);
                            if (iter != null && iter.hasNext()) {
                                Feature prevFeature = null;
                                while (iter.hasNext()) {
                                    Feature feat = iter.next();
                                    if (feat.getStart() < nextEnd) {
                                        prevFeature = feat;
                                    }
                                }
                                if (prevFeature != null) {
                                    return prevFeature;
                                }
                            }
                            nextEnd = nextStart;
                        }
                        nextChr = vc.getPrevChrName(nextChr);
                        if (nextChr != null) {
                            nextEnd = vc.getGenome().getChromosome(nextChr).getLength();
                        }
                    }
                }
            }
        }

        return f;
    }

    public int getVisibilityWindow() {
        return visibilityWindow;
    }

    public void setVisibilityWindow(int windowSize) {
        this.visibilityWindow = windowSize;
        source.setBinSize(visibilityWindow);
    }

    @Override
    public void restorePersistentState(Map<String, String> attributes) {
        super.restorePersistentState(attributes);    //To change body of overridden methods use File | Settings | File Templates.

        String fvw = attributes.get(FEATURE_VISIBILITY_WINDOW);
        if (fvw != null) {
            try {
                visibilityWindow = Integer.parseInt(fvw);
            } catch (NumberFormatException e) {
                log.error("Error restoring visibilityWindow: " + fvw);
            }
        }

    }

    @Override
    public Map<String, String> getPersistentState() {
        Map<String, String> stateMap = super.getPersistentState();
        stateMap.put(FEATURE_VISIBILITY_WINDOW, String.valueOf(visibilityWindow));
        return stateMap;

    }

    //public Feature nextFeature(String chr, double position, boolean forward) {
//
//    return source.nextFeature(chr, position, forward);
//}


    static class FeatureRow {
        int start;
        int end;
        List<Feature> features;

        FeatureRow() {
            this.features = new ArrayList(100);
        }

        void addFeature(Feature feature) {
            if (features.isEmpty()) {
                this.start = feature.getStart();
            }
            features.add(feature);
            end = feature.getEnd();
        }
    }


    static class PackedFeatures {
        private String trackName;
        private String chr;
        private int start;
        private int end;
        private List<Feature> features;
        private List<FeatureRow> rows;

        PackedFeatures(String chr, int start, int end) {
            this.chr = chr;
            this.start = start;
            this.end = end;
            features = Collections.emptyList();
            rows = Collections.emptyList();
        }

        PackedFeatures(String chr, int start, int end, Iterator<Feature> iter, String trackName) {
            this.trackName = trackName;
            this.chr = chr;
            this.start = start;
            this.end = end;
            features = new ArrayList(1000);
            rows = packFeatures(iter);
        }

        int getRowCount() {
            return rows.size();
        }

        boolean containsInterval(String chr, int start, int end) {
            return this.chr.equals(chr) && start >= this.start && end <= this.end;
        }

        /**
         * Allocates each alignment to the rows such that there is no overlap.
         *
         * @param iter TabixLineReader wrapping the collection of alignments
         */
        List<FeatureRow> packFeatures(Iterator<Feature> iter) {

            List<FeatureRow> rows = new ArrayList(10);
            if (iter == null || !iter.hasNext()) {
                return rows;
            }


            // Compares 2 alignments by length.
            Comparator lengthComparator = new Comparator<Feature>() {
                public int compare(Feature row1, Feature row2) {
                    return (row2.getEnd() - row2.getStart()) - (row1.getEnd() - row2.getStart());
                }
            };

            Feature firstFeature = iter.next();
            features.add(firstFeature);
            int totalCount = 1;

            LinkedHashMap<Integer, PriorityQueue<Feature>> bucketArray = new LinkedHashMap();

            while (iter.hasNext()) {
                Feature feature = iter.next();
                features.add(feature);

                int bucketNumber = feature.getStart();

                PriorityQueue bucket = bucketArray.get(bucketNumber);
                if (bucket == null) {
                    bucket = new PriorityQueue(5, lengthComparator);
                    bucketArray.put(bucketNumber, bucket);
                }
                bucket.add(feature);
                totalCount++;

            }

            // Allocate alignments to rows
            FeatureRow currentRow = new FeatureRow();
            currentRow.addFeature(firstFeature);
            int allocatedCount = 1;
            int nextStart = currentRow.end + MINIMUM_FEATURE_SPACING;


            int lastKey = 0;
            int lastAllocatedCount = 0;
            while (allocatedCount < totalCount && rows.size() < maxLevels) {

                // Check to prevent infinite loops
                if (lastAllocatedCount == allocatedCount) {
                    String msg = "Infinite loop detected while packing features for track: " + trackName +
                            ".<br>Not all features will be shown." +
                            "<br>Please contact igv-help@broadinstitute.org";

                    log.error(msg);
                    MessageUtils.showMessage(msg);
                    break;
                }
                lastAllocatedCount = allocatedCount;

                // Next row Loop through alignments until we reach the end of the interval

                PriorityQueue<Feature> bucket = null;
                // Advance to nextLine occupied bucket

                ArrayList<Integer> emptyBucketKeys = new ArrayList();
                for (Integer key : bucketArray.keySet()) {
                    //if (key < lastKey) {
                    //    String msg = "Features from track: " + trackName + " are not sorted.  Some features might not be shown.<br>" +
                    //            "Please notify igv-help@broadinstitute.org";
                    //    MessageUtils.showMessage(msg);
                    //}
                    lastKey = key;
                    if (key >= nextStart) {
                        bucket = bucketArray.get(key);

                        Feature feature = bucket.poll();

                        if (bucket.isEmpty()) {
                            emptyBucketKeys.add(key);
                        }
                        currentRow.addFeature(feature);
                        nextStart = currentRow.end + MINIMUM_FEATURE_SPACING;
                        allocatedCount++;
                    }
                }
                for (Integer key : emptyBucketKeys) {
                    bucketArray.remove(key);
                }


                // We've reached the end of the interval,  start a new row
                if (currentRow.features.size() > 0) {
                    rows.add(currentRow);
                    lastAllocatedCount = 0;
                }
                currentRow = new FeatureRow();
                nextStart = 0;
                lastKey = 0;


            }
            // Add the last row
            if (currentRow.features.size() > 0) {
                rows.add(currentRow);
            }

            return rows;
        }
    }
}

