/*
    * 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.notes;
  
  import static org.eclipse.jgit.lib.Constants.OBJECT_ID_STRING_LENGTH;
  import static org.eclipse.jgit.lib.FileMode.REGULAR_FILE;
  
  import java.io.IOException;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  import org.eclipse.jgit.lib.AnyObjectId;
  import org.eclipse.jgit.lib.ObjectId;
  import org.eclipse.jgit.lib.ObjectInserter;
  import org.eclipse.jgit.lib.ObjectInserter.Formatter;
  import org.eclipse.jgit.lib.ObjectReader;
  import org.eclipse.jgit.lib.TreeFormatter;
  
  /**
   * A note tree holding only notes, with no subtrees.
   *
   * The leaf bucket contains on average less than 256 notes, all of whom share
   * the same leading prefix. If a notes branch has less than 256 notes, the top
   * level tree of the branch should be a LeafBucket. Once a notes branch has more
   * than 256 notes, the root should be a {@link FanoutBucket} and the LeafBucket
   * will appear only as a cell of a FanoutBucket.
   *
   * Entries within the LeafBucket are stored sorted by ObjectId, and lookup is
   * performed using binary search. As the entry list should contain fewer than
   * 256 elements, the average number of compares to find an element should be
   * less than 8 due to the O(log N) lookup behavior.
   *
   * A LeafBucket must be parsed from a tree object by {@link NoteParser}.
   */
  class LeafBucket extends InMemoryNoteBucket {
  	static final int MAX_SIZE = 256;
  
  	/** All note blobs in this bucket, sorted sequentially. */
  	private Note[] notes;
  
  	/** Number of items in {@link #notes}. */
  	private int cnt;
  
  	LeafBucket(int prefixLen) {
  		super(prefixLen);
  		notes = new Note[4];
  	}
  
  	private int search(AnyObjectId objId) {
  		int low = 0;
  		int high = cnt;
  		while (low < high) {
  			int mid = (low + high) >>> 1;
  			int cmp = objId.compareTo(notes[mid]);
  			if (cmp < 0)
  				high = mid;
  			else if (cmp == 0)
  				return mid;
 			else
 				low = mid + 1;
 		}
 		return -(low + 1);
 	}
 
 	@Override
 	Note getNote(AnyObjectId objId, ObjectReader or) {
 		int idx = search(objId);
 		return 0 <= idx ? notes[idx] : null;
 	}
 
 	Note get(int index) {
 		return notes[index];
 	}
 
 	int size() {
 		return cnt;
 	}
 
 	@Override
 	Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader) {
 		return new Iterator<Note>() {
 			private int idx;
 
 			public boolean hasNext() {
 				return idx < cnt;
 			}
 
 			public Note next() {
 				if (hasNext())
 					return notes[idx++];
 				else
 					throw new NoSuchElementException();
 			}
 
 			public void remove() {
 				throw new UnsupportedOperationException();
 			}
 		};
 	}
 
 	@Override
 	int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
 		return cnt;
 	}
 
 	InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
 			ObjectReader or) throws IOException {
 		int p = search(noteOn);
 		if (0 <= p) {
 			if (noteData != null) {
 				notes[p].setData(noteData.copy());
 				return this;
 
 			} else {
 				System.arraycopy(notes, p + 1, notes, p, cnt - p - 1);
 				cnt--;
 				return 0 < cnt ? this : null;
 			}
 
 		} else if (noteData != null) {
 			if (shouldSplit()) {
 				return split().set(noteOn, noteData, or);
 
 			} else {
 				growIfFull();
 				p = -(p + 1);
 				if (p < cnt)
 					System.arraycopy(notes, p, notes, p + 1, cnt - p);
 				notes[p] = new Note(noteOn, noteData.copy());
 				cnt++;
 				return this;
 			}
 
 		} else {
 			return this;
 		}
 	}
 
 	@Override
 	ObjectId writeTree(ObjectInserter inserter) throws IOException {
 		return inserter.insert(build());
 	}
 
 	@Override
 	ObjectId getTreeId() {
 		try (Formatter f = new ObjectInserter.Formatter()) {
 			return f.idFor(build());
 		}
 	}
 
 	private TreeFormatter build() {
 		byte[] nameBuf = new byte[OBJECT_ID_STRING_LENGTH];
 		int nameLen = OBJECT_ID_STRING_LENGTH - prefixLen;
 		TreeFormatter fmt = new TreeFormatter(treeSize(nameLen));
 		NonNoteEntry e = nonNotes;
 
 		for (int i = 0; i < cnt; i++) {
 			Note n = notes[i];
 
 			n.copyTo(nameBuf, 0);
 
 			while (e != null
 					&& e.pathCompare(nameBuf, prefixLen, nameLen, REGULAR_FILE) < 0) {
 				e.format(fmt);
 				e = e.next;
 			}
 
 			fmt.append(nameBuf, prefixLen, nameLen, REGULAR_FILE, n.getData());
 		}
 
 		for (; e != null; e = e.next)
 			e.format(fmt);
 		return fmt;
 	}
 
 	private int treeSize(final int nameLen) {
 		int sz = cnt * TreeFormatter.entrySize(REGULAR_FILE, nameLen);
 		for (NonNoteEntry e = nonNotes; e != null; e = e.next)
 			sz += e.treeEntrySize();
 		return sz;
 	}
 
 	void parseOneEntry(AnyObjectId noteOn, AnyObjectId noteData) {
 		growIfFull();
 		notes[cnt++] = new Note(noteOn, noteData.copy());
 	}
 
 	@Override
 	InMemoryNoteBucket append(Note note) {
 		if (shouldSplit()) {
 			return split().append(note);
 
 		} else {
 			growIfFull();
 			notes[cnt++] = note;
 			return this;
 		}
 	}
 
 	private void growIfFull() {
 		if (notes.length == cnt) {
 			Note[] n = new Note[notes.length * 2];
 			System.arraycopy(notes, 0, n, 0, cnt);
 			notes = n;
 		}
 	}
 
 	private boolean shouldSplit() {
 		return MAX_SIZE <= cnt && prefixLen + 2 < OBJECT_ID_STRING_LENGTH;
 	}
 
 	FanoutBucket split() {
 		FanoutBucket n = new FanoutBucket(prefixLen);
 		for (int i = 0; i < cnt; i++)
 			n.append(notes[i]);
 		n.nonNotes = nonNotes;
 		return n;
 	}
 }