/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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 org.openide.filesystems;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.openide.util.NbCollections;
import org.openide.util.TopologicalSortException;
import org.openide.util.BaseUtilities;

/**
 * Implements folder ordering logic in {@link FileUtil}.
 */
class Ordering {

    private Ordering() {}

    private static final Logger LOG = Logger.getLogger(Ordering.class.getName());
    private static final String ATTR_POSITION = "position"; // NOI18N

    static List<FileObject> getOrder(Collection<FileObject> children, final boolean logWarnings) throws IllegalArgumentException {
        LOG.log(Level.FINE, "getOrder for {0}", children); // NOI18N
        Iterator<FileObject> it = children.iterator();
        if (!it.hasNext()) {
            return Collections.emptyList();
        }
        int unordered = 0;
        int ordered = 0;
        Map<String,FileObject> childrenByName = new HashMap<String,FileObject>();
        class ChildAndPosition implements Comparable<ChildAndPosition> {
            ChildAndPosition(FileObject child, Number position) {
                this.child = child;
                this.position = position;
            }
            final FileObject child;
            private final Number position;
            @Override
            public int compareTo(ChildAndPosition o) {
                int res;
                if (position instanceof Float || position instanceof Double || o.position instanceof Float || o.position instanceof Double) {
                    res = Double.compare(position.doubleValue(), o.position.doubleValue());
                } else {
                    long v1 = position.longValue();
                    long v2 = o.position.longValue();
                    res = v1 < v2 ? -1 : (v1 == v2 ? 0 : 1);
                }
                if (res != 0) {
                    return res;
                } else {
                    if (logWarnings && o != this && !position.equals(0)) {
                        LOG.log(Level.WARNING, "Found same position {0} for both {1} and {2}", new Object[]{position, o.child.getPath(), child.getPath()});
                    }
                    return child.getNameExt().compareTo(o.child.getNameExt());
                }
            }
        }
        SortedSet<ChildAndPosition> childrenByPosition = new TreeSet<ChildAndPosition>();
        FileObject parent = null;
        while (it.hasNext()) {
            FileObject child = it.next();
            if (childrenByName.put(child.getNameExt(), child) != null) {
                throw new IllegalArgumentException("Duplicate in children list: " + child.getPath() + "\nChildren: " + children); // NOI18N
            }
            Object pos = child.getAttribute(ATTR_POSITION);
            if (pos instanceof Number) {
                childrenByPosition.add(new ChildAndPosition(child, (Number) pos));
                ordered |= child.isFolder() ? 1 : 2;
            } else if (logWarnings && pos != null) {
                LOG.log(Level.WARNING, "Encountered nonnumeric position attribute {0} of {1} for {2}\nChildren: {3}", new Object[]{pos, pos.getClass(), child.getPath(), children});
            }
            if (parent == null) {
                parent = child.getParent();
            } else {
                if (child.getParent() != parent) {
                    throw new IllegalArgumentException("All children must have the same parent: " + child.getParent().getPath() + " vs. " + parent.getPath() + "\nChildren: " + children); // NOI18N
                }
            }
            if (pos == null) {
                unordered |= child.isFolder() ? 1 : 2;
            }
        }
        Map<FileObject,Set<FileObject>> edges = new HashMap<FileObject,Set<FileObject>>();
        for (String attr : NbCollections.iterable(parent.getAttributes())) {
            if (LOG.isLoggable(Level.FINEST)) {
                LOG.log(Level.FINEST, "  attr found {0}({1})", new Object[]{parent, attr}); // NOI18N
            }
            int slash = attr.indexOf('/');
            if (slash == -1) {
                continue;
            }
            Object val = parent.getAttribute(attr);
            if (LOG.isLoggable(Level.FINE)) {
                LOG.log(Level.FINE, "  reading attribute {0}({1}) -> {2}", new Object[] {parent, attr, val}); // NOI18N
            }
            if (!Boolean.TRUE.equals(val)) {
                if (logWarnings && /* somehow this can happen, not sure how... */ val != null && !(val instanceof Boolean)) {
                    LOG.log(Level.WARNING, "Encountered non-boolean relative ordering attribute {0} from {1} on {2}", new Object[]{val, attr, parent.getPath()});
                }
                continue;
            }
            FileObject f1 = childrenByName.get(attr.substring(0, slash));
            FileObject f2 = childrenByName.get(attr.substring(slash + 1));
            if (f1 != null && f2 != null) {
                Set<FileObject> edge = edges.get(f1);
                if (edge == null) {
                    edges.put(f1, edge = new HashSet<FileObject>());
                }
                edge.add(f2);
                if (logWarnings) {
                    LOG.log(
                        Level.WARNING, "Relative ordering attribute {0} on {1} is deprecated in favor of numeric position attributes",
                        new Object[]{attr, parent.getPath()}
                    );
                }
            } else if (logWarnings) {
                LOG.log(
                    Level.WARNING, "Could not find both sides of relative ordering attribute {0} on {1}",
                    new Object[]{attr, parent.getPath()}
                );
            }
        }
        if (LOG.isLoggable(Level.FINEST)) {
            LOG.log(Level.FINEST, "  no more attribs {0}", parent); // NOI18N
        }
        Iterator<ChildAndPosition> it2 = childrenByPosition.iterator();
        if (it2.hasNext()) {
            FileObject previousChild = it2.next().child;
            while (it2.hasNext()) {
                FileObject subsequentChild = it2.next().child;
                Set<FileObject> edge = edges.get(previousChild);
                if (edge == null) {
                    edges.put(previousChild, edge = new HashSet<FileObject>());
                }
                edge.add(subsequentChild);
                previousChild = subsequentChild;
            }
        }
        boolean shouldLog = logWarnings && !childrenByPosition.isEmpty() && childrenByPosition.size() < children.size();
        if (shouldLog) {
            // exceptions:  See Bugzilla#201893 
            if (parent.getPath().matches("Projects/.+/Lookup")) {
                // do not report any order issues for Projects/Lookup, even between files, or between folders.
                shouldLog = false;
            } else if (FileUtil.isParentOf(FileUtil.getConfigRoot(), parent) && ((ordered & unordered) == 0)) {
                // do not report folder / file mismatch on configfs, but DO report mismatch inside folder/file category.
                shouldLog = false;
            }
        }
        if (shouldLog) {
            List<FileObject> missingPositions = new ArrayList<FileObject>(children);
            for (ChildAndPosition cap : childrenByPosition) {
                missingPositions.remove(cap.child);
            }
            for (Iterator<FileObject> mis = missingPositions.iterator(); mis.hasNext();) {
                FileObject fileObject = mis.next();
                if (fileObject.getExt().endsWith("_hidden")) { // NOI18N
                    mis.remove();
                }
            }
            IGNORE_ERGO: if (!missingPositions.isEmpty()) {
                List<String> missingNames = new ArrayList<String>(missingPositions.size());
                for (FileObject f : missingPositions) {
                    final String n = f.getNameExt();
                    if (n.contains("ergonomics")) { // NOI18N
                        break IGNORE_ERGO;
                    }
                    missingNames.add(n);
                }
                List<String> presentNames = new ArrayList<String>(childrenByPosition.size());
                for (ChildAndPosition cap : childrenByPosition) {
                    final String n = cap.child.getNameExt();
                    if (n.contains("ergonomics")) { // NOI18N
                        break IGNORE_ERGO;
                    }
                    presentNames.add(n);
                }
                LOG.log(
                    Level.WARNING, "Not all children in {0}/ marked with the position attribute: {1}, but some are: {2}",
                    new Object[]{parent.getPath(), missingNames, presentNames}
                );
            }
        }
        if (edges.isEmpty()) {
            // Shortcut.
            return new ArrayList<FileObject>(children);
        } else {
            try {
                return BaseUtilities.topologicalSort(children, edges);
            } catch (TopologicalSortException x) {
                if (logWarnings) {
                    LOG.log(Level.WARNING, "Contradictory partial ordering in " + parent.getPath(), x);
                }
                return NbCollections.checkedListByCopy(x.partialSort(), FileObject.class, true);
            }
        }
    }

    static void setOrder(List<FileObject> children) throws IllegalArgumentException, IOException {
        boolean oneNewChild = false;
        boolean fullySpecified = true;
        for (FileObject f : children) {
            if (findPosition(f) == null) {
                fullySpecified = false;
                break;
            }
        }
        FileObject toBeMoved = null, before = null, after = null;
        if (fullySpecified) {
            List<FileObject> oldOrder = getOrder(children, false);
            if (children.equals(oldOrder)) {
                // Nothing to do.
                return;
            }
            // First check to see if the change can be represented as a single move.
            // If so, we prefer to change just one position attribute.
            int length = children.size();
            int start = 0;
            while (start < length && children.get(start).equals(oldOrder.get(start))) {
                start++;
            }
            int end = length - 1;
            while (end >= 0 && children.get(end).equals(oldOrder.get(end))) {
                end--;
            }
            int rangeLength = end - start + 1;
            if (rangeLength > 2) {
                // Check if the permutation within this range is just a rotation by one element.
                if (children.get(end).equals(oldOrder.get(start)) && children.subList(start, end).equals(oldOrder.subList(start + 1, end + 1))) {
                    // Left rotation.
                    toBeMoved = children.get(end);
                    before = children.get(end - 1);
                    after = end + 1 < length ? children.get(end + 1) : null;
                } else if (children.get(start).equals(oldOrder.get(end)) && children.subList(start + 1, end + 1).equals(oldOrder.subList(start, end))) {
                    // Right rotation.
                    toBeMoved = children.get(start);
                    before = start - 1 >= 0 ? children.get(start - 1) : null;
                    after = children.get(start + 1);
                }
            } else if (rangeLength == 2) {
                // Adjacent swap.
                if (start == 0) {
                    // Use space on the left.
                    toBeMoved = children.get(start);
                    after = children.get(end);
                } else if (end == length - 1) {
                    // Use space on the right.
                    toBeMoved = children.get(end);
                    before = children.get(start);
                } else {
                    // Prefer to move the one which is closer to its outside neighbor.
                    Float outLeft = findPosition(children.get(start - 1));
                    Float outRight = findPosition(children.get(end + 1));
                    Float left = findPosition(children.get(start));
                    Float right = findPosition(children.get(end));
                    if (outLeft != null && outRight != null && left != null && right != null) {
                        if (left - outLeft < outRight - right) {
                            toBeMoved = children.get(end);
                            before = children.get(start);
                            after = children.get(end + 1);
                        } else {
                            toBeMoved = children.get(start);
                            before = children.get(start - 1);
                            after = children.get(end);
                        }
                    }
                }
            } else {
                assert rangeLength == 0 : oldOrder + " => " + children;
            }
        } else if (children.size() > 1) {
            // #110981: check to see if just one is new.
            FileObject nue = null;
            for (FileObject f : children) {
                if (findPosition(f) == null) {
                    if (nue == null) {
                        nue = f;
                    } else {
                        // More than one, skip.
                        nue = null;
                        break;
                    }
                }
            }
            if (nue != null) {
                oneNewChild = true;
                toBeMoved = nue;
                int idx = children.indexOf(nue);
                before = (idx == 0) ? null : children.get(idx - 1);
                after = (idx == children.size() - 1) ? null : children.get(idx + 1);
            }
        }
        if (toBeMoved != null) {
            // Do the swap.
            if (before == null) {
                toBeMoved.setAttribute(ATTR_POSITION, Math.round(findPosition(after) - 100));
            } else if (after == null) {
                toBeMoved.setAttribute(ATTR_POSITION, Math.round(findPosition(before) + 100));
            } else {
                Float beforePos = findPosition(before);
                Float afterPos = findPosition(after);
                int proposed = Math.round(beforePos + afterPos) / 2;
                if (beforePos < proposed && proposed < afterPos) {
                    toBeMoved.setAttribute(ATTR_POSITION, proposed);
                } else {
                    toBeMoved = null; // #115343
                }
            }
        }
        if (toBeMoved == null) {
            // More complex rearrangement. Fall back to a crude but correct behavior.
            int pos = 100;
            for (FileObject f : children) {
                f.setAttribute(ATTR_POSITION, pos);
                pos += 100;
            }
        }
        if(oneNewChild && toBeMoved != null) {
            // #131021 - If just one new child added and its position attr is set,
            // call setOrder again to potentially reorder others.
            setOrder(children);
            return;
        }
        // Kill off any old relative ordering attributes.
        FileObject d = children.get(0).getParent();
        for (String attr : NbCollections.iterable(d.getAttributes())) {
            if (attr.indexOf('/') != -1 && d.getAttribute(attr) instanceof Boolean) {
                d.setAttribute(attr, null);
            }
        }
        boolean asserts = false;
        assert asserts = true;
        if (asserts) {
            List<FileObject> actual = getOrder(children, false);
            assert actual.equals(children) : "setOrder(" + children + ") -> " + actual;
        }
    }

    private static Float findPosition(FileObject f) {
        Object o = f.getAttribute(ATTR_POSITION);
        if (o instanceof Number) {
            return ((Number) o).floatValue();
        } else {
            return null;
        }
    }

    static boolean affectsOrder(FileAttributeEvent event) {
        String name = event.getName();
        if (name == null) {
            // Unknown attrs changed. Conservatively assume it might affect order.
            return true;
        }
        return name.equals(ATTR_POSITION) || (event.getFile().isFolder() && name.indexOf('/') != -1);
    }

}
