/*
 * Copyright (C) 2010, Google Inc.
 * and other copyright owners as documented in the project's IP log.
 *
 * This program and the accompanying materials are made available
 * under the terms of the Eclipse Distribution License v1.0 which
 * accompanies this distribution, is reproduced below, and is
 * available at http://www.eclipse.org/org/documents/edl-v10.php
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
 *
 * - Neither the name of the Eclipse Foundation, Inc. nor the
 *   names of its contributors may be used to endorse or promote
 *   products derived from this software without specific prior
 *   written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.eclipse.jgit.util;

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.function.BinaryOperator;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.lib.RefComparator;

Specialized Map to present a RefDatabase namespace. 
 Although not declared as a SortedMap, iterators from this map's projections always return references in RefComparator ordering. The map's internal representation is a sorted array of Ref objects, which means lookup and replacement is O(log N), while insertion and removal can be as expensive as O(N + log N) while the list expands or contracts. Since this is not a general map implementation, all entries must be keyed by the reference name. 
 This class is really intended as a helper for RefDatabase, which needs to perform a merge-join of three sorted RefLists in order to present the unified namespace of the packed-refs file, the loose refs/ directory tree, and the resolved form of any symbolic references. /**
 * Specialized Map to present a {@code RefDatabase} namespace.
 * <p>
 * Although not declared as a {@link java.util.SortedMap}, iterators from this
 * map's projections always return references in
 * {@link org.eclipse.jgit.lib.RefComparator} ordering. The map's internal
 * representation is a sorted array of {@link org.eclipse.jgit.lib.Ref} objects,
 * which means lookup and replacement is O(log N), while insertion and removal
 * can be as expensive as O(N + log N) while the list expands or contracts.
 * Since this is not a general map implementation, all entries must be keyed by
 * the reference name.
 * <p>
 * This class is really intended as a helper for {@code RefDatabase}, which
 * needs to perform a merge-join of three sorted
 * {@link org.eclipse.jgit.util.RefList}s in order to present the unified
 * namespace of the packed-refs file, the loose refs/ directory tree, and the
 * resolved form of any symbolic references.
 */
public class RefMap extends AbstractMap<String, Ref> {
	
Prefix denoting the reference subspace this map contains.

All reference names in this map must start with this prefix. If the
prefix is not the empty string, it must end with a '/'.
/**
	 * Prefix denoting the reference subspace this map contains.
	 * <p>
	 * All reference names in this map must start with this prefix. If the
	 * prefix is not the empty string, it must end with a '/'.
	 */
	final String prefix;

	
Immutable collection of the packed references at construction time. /** Immutable collection of the packed references at construction time. */
	RefList<Ref> packed;

	
Immutable collection of the loose references at construction time.
 If an entry appears here and in packed, this entry must take precedence, as its more current. Symbolic references in this collection are typically unresolved, so they only tell us who their target is, but not the current value of the target. /**
	 * Immutable collection of the loose references at construction time.
	 * <p>
	 * If an entry appears here and in {@link #packed}, this entry must take
	 * precedence, as its more current. Symbolic references in this collection
	 * are typically unresolved, so they only tell us who their target is, but
	 * not the current value of the target.
	 */
	RefList<Ref> loose;

	
Immutable collection of resolved symbolic references.
 This collection contains only the symbolic references we were able to resolve at map construction time. Other loose references must be read from loose. Every entry in this list must be matched by an entry in loose, otherwise it might be omitted by the map. /**
	 * Immutable collection of resolved symbolic references.
	 * <p>
	 * This collection contains only the symbolic references we were able to
	 * resolve at map construction time. Other loose references must be read
	 * from {@link #loose}. Every entry in this list must be matched by an entry
	 * in {@code loose}, otherwise it might be omitted by the map.
	 */
	RefList<Ref> resolved;

	int size;

	boolean sizeIsValid;

	private Set<Entry<String, Ref>> entrySet;

	
Construct an empty map with a small initial capacity.
/**
	 * Construct an empty map with a small initial capacity.
	 */
	public RefMap() {
		prefix = ""; //$NON-NLS-1$
		packed = RefList.emptyList();
		loose = RefList.emptyList();
		resolved = RefList.emptyList();
	}

	
Construct a map to merge 3 collections together.
Params:
prefix –  prefix used to slice the lists down. Only references whose names start with this prefix will appear to reside in the map. Must not be null, use "" (the empty string) to select all list items.
packed – 
           items from the packed reference list, this is the last list
           searched.
loose –  items from the loose reference list, this list overrides packed if a name appears in both.
resolved –  resolved symbolic references. This list overrides the prior list loose, if an item appears in both. Items in this list must also appear in loose./**
	 * Construct a map to merge 3 collections together.
	 *
	 * @param prefix
	 *            prefix used to slice the lists down. Only references whose
	 *            names start with this prefix will appear to reside in the map.
	 *            Must not be null, use {@code ""} (the empty string) to select
	 *            all list items.
	 * @param packed
	 *            items from the packed reference list, this is the last list
	 *            searched.
	 * @param loose
	 *            items from the loose reference list, this list overrides
	 *            {@code packed} if a name appears in both.
	 * @param resolved
	 *            resolved symbolic references. This list overrides the prior
	 *            list {@code loose}, if an item appears in both. Items in this
	 *            list <b>must</b> also appear in {@code loose}.
	 */
	@SuppressWarnings("unchecked")
	public RefMap(String prefix, RefList<? extends Ref> packed,
			RefList<? extends Ref> loose, RefList<? extends Ref> resolved) {
		this.prefix = prefix;
		this.packed = (RefList<Ref>) packed;
		this.loose = (RefList<Ref>) loose;
		this.resolved = (RefList<Ref>) resolved;
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public boolean containsKey(Object name) {
		return get(name) != null;
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public Ref get(Object key) {
		String name = toRefName((String) key);
		Ref ref = resolved.get(name);
		if (ref == null)
			ref = loose.get(name);
		if (ref == null)
			ref = packed.get(name);
		return ref;
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public Ref put(String keyName, Ref value) {
		String name = toRefName(keyName);

		if (!name.equals(value.getName()))
			throw new IllegalArgumentException();

		if (!resolved.isEmpty()) {
			// Collapse the resolved list into the loose list so we
			// can discard it and stop joining the two together.
			for (Ref ref : resolved)
				loose = loose.put(ref);
			resolved = RefList.emptyList();
		}

		int idx = loose.find(name);
		if (0 <= idx) {
			Ref prior = loose.get(name);
			loose = loose.set(idx, value);
			return prior;
		} else {
			Ref prior = get(keyName);
			loose = loose.add(idx, value);
			sizeIsValid = false;
			return prior;
		}
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public Ref remove(Object key) {
		String name = toRefName((String) key);
		Ref res = null;
		int idx;
		if (0 <= (idx = packed.find(name))) {
			res = packed.get(name);
			packed = packed.remove(idx);
			sizeIsValid = false;
		}
		if (0 <= (idx = loose.find(name))) {
			res = loose.get(name);
			loose = loose.remove(idx);
			sizeIsValid = false;
		}
		if (0 <= (idx = resolved.find(name))) {
			res = resolved.get(name);
			resolved = resolved.remove(idx);
			sizeIsValid = false;
		}
		return res;
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public boolean isEmpty() {
		return entrySet().isEmpty();
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public Set<Entry<String, Ref>> entrySet() {
		if (entrySet == null) {
			entrySet = new AbstractSet<Entry<String, Ref>>() {
				@Override
				public Iterator<Entry<String, Ref>> iterator() {
					return new SetIterator();
				}

				@Override
				public int size() {
					if (!sizeIsValid) {
						size = 0;
						Iterator<?> i = entrySet().iterator();
						for (; i.hasNext(); i.next())
							size++;
						sizeIsValid = true;
					}
					return size;
				}

				@Override
				public boolean isEmpty() {
					if (sizeIsValid)
						return 0 == size;
					return !iterator().hasNext();
				}

				@Override
				public void clear() {
					packed = RefList.emptyList();
					loose = RefList.emptyList();
					resolved = RefList.emptyList();
					size = 0;
					sizeIsValid = true;
				}
			};
		}
		return entrySet;
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public String toString() {
		StringBuilder r = new StringBuilder();
		boolean first = true;
		r.append('[');
		for (Ref ref : values()) {
			if (first)
				first = false;
			else
				r.append(", "); //$NON-NLS-1$
			r.append(ref);
		}
		r.append(']');
		return r.toString();
	}

	
Create a Collector for Ref. 
Params:
mergeFunction – 
Returns:
Collector for Ref
Since:
5.4/**
	 * Create a {@link Collector} for {@link Ref}.
	 *
	 * @param mergeFunction
	 * @return {@link Collector} for {@link Ref}
	 * @since 5.4
	 */
	public static Collector<Ref, ?, RefMap> toRefMap(
			BinaryOperator<Ref> mergeFunction) {
		return Collectors.collectingAndThen(RefList.toRefList(mergeFunction),
				(refs) -> new RefMap("", //$NON-NLS-1$
							refs, RefList.emptyList(),
						RefList.emptyList()));
	}

	private String toRefName(String name) {
		if (0 < prefix.length())
			name = prefix + name;
		return name;
	}

	String toMapKey(Ref ref) {
		String name = ref.getName();
		if (0 < prefix.length())
			name = name.substring(prefix.length());
		return name;
	}

	private class SetIterator implements Iterator<Entry<String, Ref>> {
		private int packedIdx;

		private int looseIdx;

		private int resolvedIdx;

		private Entry<String, Ref> next;

		SetIterator() {
			if (0 < prefix.length()) {
				packedIdx = -(packed.find(prefix) + 1);
				looseIdx = -(loose.find(prefix) + 1);
				resolvedIdx = -(resolved.find(prefix) + 1);
			}
		}

		@Override
		public boolean hasNext() {
			if (next == null)
				next = peek();
			return next != null;
		}

		@Override
		public Entry<String, Ref> next() {
			if (hasNext()) {
				Entry<String, Ref> r = next;
				next = peek();
				return r;
			}
			throw new NoSuchElementException();
		}

		public Entry<String, Ref> peek() {
			if (packedIdx < packed.size() && looseIdx < loose.size()) {
				Ref p = packed.get(packedIdx);
				Ref l = loose.get(looseIdx);
				int cmp = RefComparator.compareTo(p, l);
				if (cmp < 0) {
					packedIdx++;
					return toEntry(p);
				}

				if (cmp == 0)
					packedIdx++;
				looseIdx++;
				return toEntry(resolveLoose(l));
			}

			if (looseIdx < loose.size())
				return toEntry(resolveLoose(loose.get(looseIdx++)));
			if (packedIdx < packed.size())
				return toEntry(packed.get(packedIdx++));
			return null;
		}

		private Ref resolveLoose(Ref l) {
			if (resolvedIdx < resolved.size()) {
				Ref r = resolved.get(resolvedIdx);
				int cmp = RefComparator.compareTo(l, r);
				if (cmp == 0) {
					resolvedIdx++;
					return r;
				} else if (cmp > 0) {
					// WTF, we have a symbolic entry but no match
					// in the loose collection. That's an error.
					throw new IllegalStateException();
				}
			}
			return l;
		}

		private Ent toEntry(Ref p) {
			if (p.getName().startsWith(prefix))
				return new Ent(p);
			packedIdx = packed.size();
			looseIdx = loose.size();
			resolvedIdx = resolved.size();
			return null;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	private class Ent implements Entry<String, Ref> {
		private Ref ref;

		Ent(Ref ref) {
			this.ref = ref;
		}

		@Override
		public String getKey() {
			return toMapKey(ref);
		}

		@Override
		public Ref getValue() {
			return ref;
		}

		@Override
		public Ref setValue(Ref value) {
			Ref prior = put(getKey(), value);
			ref = value;
			return prior;
		}

		@Override
		public int hashCode() {
			return getKey().hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Map.Entry) {
				final Object key = ((Map.Entry) obj).getKey();
				final Object val = ((Map.Entry) obj).getValue();
				if (key instanceof String && val instanceof Ref) {
					final Ref r = (Ref) val;
					if (r.getName().equals(ref.getName())) {
						final ObjectId a = r.getObjectId();
						final ObjectId b = ref.getObjectId();
						if (a != null && b != null
								&& AnyObjectId.isEqual(a, b)) {
							return true;
						}
					}
				}
			}
			return false;
		}

		@Override
		public String toString() {
			return ref.toString();
		}
	}
}