in uimaj-core/src/main/java/org/apache/uima/internal/util/OrderedFsSet_array2.java [478:679]
private void doProcessBatch() {
synchronized (batch) {
int batchSize = batch.size();
if ((batchSize == 0) || doingBatchAdds) {
return; // bypass recursive calls from Eclipse IDE on same thread,
// when its toString methods invoke this recursively to update the
// debug UI for instance, while single stepping.
}
try {
// validateA();
// debug
// assert (lastRemovedPos != -1) ? a[lastRemovedPos] == null : true;
doingBatchAdds = true;
if (MEASURE) {
batchAddCount++;
batchAddTotal += batchSize;
batchCountHistogram[31 - Integer.numberOfLeadingZeros(batchSize)]++;
}
// @formatter:off
/* the number of new empty slots created,
* may end up being larger than actually used because some of the items
* being inserted may already be in the array
* - decreases as each item is actually inserted into the array
*/
// @formatter:on
int nbrNewSlots = 1; // start at one, may increase
if (batchSize > 1) {
// Sort the items to add
batch.sort(comparatorWithID);
TOP prev = batch.get(batchSize - 1);
// nbrNewSlots = batch.size();
// count dups (to reduce excess allocations)
// deDups done using the comparatorWithID
final boolean useEq = comparatorWithID != comparatorWithoutID; // true for Sorted, false
// for set
for (int i = batchSize - 2; i >= 0; i--) {
TOP item = batch.get(i);
if (useEq ? (item == prev) : (comparatorWithID.compare(item, prev) == 0)) {
batch.set(i + 1, null); // need to do this way so the order of adding is the same as
// v2
if (i + 1 == batchSize - 1) {
batchSize--; // start with non-null when done
}
} else {
prev = item;
nbrNewSlots++; // count of items that will actually be added; skips the duplicates
}
}
}
int i_batch = batchSize - 1;
int insertPosOfAddedSpace = 0;
TOP itemToAdd;
// skip entries already found
itemToAdd = batch.get(i_batch);
while (itemToAdd == null || (insertPosOfAddedSpace = find(itemToAdd)) >= 0) {
// skip any entries at end of list if they're already in the set
i_batch--;
nbrNewSlots--;
if (i_batch < 0) {
batch.clear();
return; // all were already in the index
}
itemToAdd = batch.get(i_batch);
}
// assert nbrNewSlots > 0; // otherwise batch would be empty and would have returned before
// insertPosOfAddedSpace is index to non-null item that is > itemToAdd
// or points to 1 beyond current size
insertPosOfAddedSpace = (-insertPosOfAddedSpace) - 1;
// insertPos is insert point, i_batch is index of first batch element to insert
// there may be other elements in batch that duplicate; these won't be inserted, but
// there will be space lost in this case
int indexOfNewItem = insertSpace(insertPosOfAddedSpace, nbrNewSlots) // returns index of a
// non-null item
// the new item goes one spot to the left of this
- 1; // inserts nulls at the insert point, shifting other cells down
assert nbrNewSlots == nullBlockEnd - nullBlockStart;
int nbrNewSlotsRemaining = nbrNewSlots; // will be decremented as slots are used
// process first item
if (indexOfNewItem >= nullBlockStart) {
nbrNewSlotsRemaining--;
} // else, don't decr because we're using existing nulls
// debug
// assert (nbrNewSlotsRemaining > 0) ? indexOfNewItem != nullBlockStart : true;
// assert (nbrNewSlotsRemaining > 0) ? nullBlockEnd - 1 > nullBlockStart : true;
insertItem(indexOfNewItem, itemToAdd);
// TOP prevItem = itemToAdd;
if (indexOfNewItem + 1 == a_nextFreeslot) {
highest = itemToAdd;
}
// debug
// assert (nbrNewSlotsRemaining > 0) ? nullBlockStart != -1 : true;
int bPos = i_batch - 1; // next after first one from end
for (; bPos >= 0; bPos--) {
itemToAdd = batch.get(bPos);
if (null == itemToAdd) {
continue; // skipping a duplicate
}
int pos = findRemaining(itemToAdd); // search limited, ends at nullBlockstart
if (pos >= 0) {
continue; // already in the list
}
pos = (-pos) - 1; // pos is the insert point
// new item goes 1 to left of this
assert a[pos] != null;
indexOfNewItem = pos - 1; // where the new item goes, 1 to left of insert point
if (nullBlockStart == 0) {
// this and all the rest of the elements are lower, insert in bulk
// because all are lower, none are in the array, so don't need the compare check
insertItem(indexOfNewItem--, itemToAdd);
nbrNewSlotsRemaining--;
bPos--;
for (; bPos >= 0; bPos--) {
itemToAdd = batch.get(bPos);
if (itemToAdd == null) {
continue;
}
insertItem(indexOfNewItem--, itemToAdd);
nbrNewSlotsRemaining--; // do this way to respect skipped items due to == to prev
}
break;
}
// validateA();
// boolean debugdidshift = false;
if (indexOfNewItem == -1 || null != a[indexOfNewItem]) {
// debugdidshift = true;
indexOfNewItem = shiftFreespaceDown(pos, nbrNewSlotsRemaining) - 1; // results in null
// being available
// at pos - 1
assert nbrNewSlotsRemaining == nullBlockEnd - nullBlockStart;
nbrNewSlotsRemaining--; // only decr if using a new slot, skip if filling in a null
} else {
// there was a null in the spot to insert
// two cases: if the spot is within the nullBlock, need to decr nbrNewSlots
if (indexOfNewItem < nullBlockEnd && indexOfNewItem >= nullBlockStart) {
nbrNewSlotsRemaining--; // the insertItem will adjust nullBlock start/end
}
}
// //debug
// assert (nbrNewSlotsRemaining > 0) ? nullBlockStart != -1 : true;
insertItem(indexOfNewItem, itemToAdd);
// //debug
// assert nbrNewSlotsRemaining == nullBlockEnd - nullBlockStart;
// assert (nbrNewSlotsRemaining > 0) ? nullBlockStart != -1 : true;
}
if (nbrNewSlotsRemaining > 0) {
// have extra space left over due to dups not being added
// If this space is not at beginning, move space to beginning or end (whichever is closer)
// if (indexOfNewItem - nbrNewSlotsRemaining > 0) {
if (nullBlockEnd != a_firstUsedslot) {
// space is not at beginning
assert nbrNewSlotsRemaining == nullBlockEnd - nullBlockStart;
int nullBlockEnd_end = a_nextFreeslot - nullBlockEnd;
int nullBlockStart_start = nullBlockStart - a_firstUsedslot;
assert nullBlockEnd_end > 0;
assert nullBlockStart_start > 0;
if (nullBlockStart_start <= nullBlockEnd_end) {
shiftFreespaceDown(a_firstUsedslot, nbrNewSlotsRemaining);
// System.arraycopy(a, indexOfNewItem - nbrNewSlots, a, 0, nbrNewSlots);
// a_firstUsedslot += nbrNewSlots;
// validateA();
} else {
shiftFreespaceUp(a_nextFreeslot, nbrNewSlotsRemaining);
a_nextFreeslot -= nbrNewSlotsRemaining;
// // move to end
// System.arraycopy(a, indexOfNewItem, a, indexOfNewItem - nbrNewSlots, a_nextFreeslot
// - indexOfNewItem);
// Arrays.fill(a, a_nextFreeslot - nbrNewSlots, a_nextFreeslot, null);
// a_nextFreeslot -= nbrNewSlots;
// validateA();
}
}
}
nullBlockStart = nullBlockEnd = -1;
// validateA();
batch.clear();
} finally {
doingBatchAdds = false;
// //debug
// assert (lastRemovedPos != -1) ? a[lastRemovedPos] == null : true;
}
}
}