/*
    * Copyright (C) 2010, Google Inc. and others
    *
    * This program and the accompanying materials are made available under the
    * terms of the Eclipse Distribution License v. 1.0 which is available at
    * https://www.eclipse.org/org/documents/edl-v10.php.
    *
    * SPDX-License-Identifier: BSD-3-Clause
    */
  
  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<>() {
  			private int idx;
  
  			@Override
  			public boolean hasNext() {
  				return idx < cnt;
  			}
  
  			@Override
  			public Note next() {
  				if (hasNext()) {
 					return notes[idx++];
 				}
 				throw new NoSuchElementException();
 			}
 
 			@Override
 			public void remove() {
 				throw new UnsupportedOperationException();
 			}
 		};
 	}
 
 	@Override
 	int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
 		return cnt;
 	}
 
 	@Override
 	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;
 
 			}
 			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);
 			}
 			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(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);
 		}
 		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;
 	}
 }