package com.oracle.objectfile;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.NavigableSet;
import java.util.SortedSet;
import java.util.TreeSet;
import com.oracle.objectfile.ObjectFile.Element;
import com.oracle.objectfile.ObjectFile.Section;
public class ElementList implements List<Element> {
private List<Element> entries = new ArrayList<>();
protected final Map<String, Element> elementForName = new HashMap<>();
public Element forName(String name) {
return elementForName.get(name);
}
private NavigableSet<Integer> nonSectionElementIndices = new TreeSet<>();
private NavigableSet<Integer> sectionElementIndices = new TreeSet<>();
public int elementIndexToSectionIndex(int i) {
SortedSet<Integer> lowerNonSectionElements = nonSectionElementIndices.headSet(i);
return i - lowerNonSectionElements.size();
}
public int sectionIndexToElementIndex(int sectionIndex) {
int pivot = (sectionElementIndices.first() + sectionElementIndices.last()) / 2;
int leftOffset = 0;
SortedSet<Integer> leftSet = sectionElementIndices.headSet(pivot);
SortedSet<Integer> rightSet = sectionElementIndices.tailSet(pivot);
int rightHeadIndex = leftOffset + leftSet.size();
while (leftSet.size() + rightSet.size() > 1) {
if (rightHeadIndex > sectionIndex) {
if (leftSet.size() == 0) {
throw new IndexOutOfBoundsException();
}
pivot = (int) Math.floor((leftSet.first() + leftSet.last()) / 2.0);
SortedSet<Integer> newLeftSet = leftSet.headSet(pivot);
SortedSet<Integer> newRightSet = leftSet.tailSet(pivot);
assert !leftSet.equals(newLeftSet) || !rightSet.equals(newRightSet);
leftSet = newLeftSet;
rightSet = newRightSet;
} else {
if (rightSet.size() == 0) {
throw new IndexOutOfBoundsException();
}
pivot = (int) Math.ceil((rightSet.first() + rightSet.last()) / 2.0);
leftOffset += leftSet.size();
SortedSet<Integer> newLeftSet = rightSet.headSet(pivot);
SortedSet<Integer> newRightSet = rightSet.tailSet(pivot);
assert !leftSet.equals(newLeftSet) || !rightSet.equals(newRightSet);
leftSet = newLeftSet;
rightSet = newRightSet;
}
rightHeadIndex = leftOffset + leftSet.size();
}
if ((rightHeadIndex > sectionIndex && leftSet.size() == 0) || !(rightHeadIndex > sectionIndex) && rightSet.size() == 0) {
throw new IndexOutOfBoundsException();
}
int toReturn = (rightHeadIndex > sectionIndex) ? leftSet.last() : rightSet.first();
assert toReturn == sectionIndexToElementIndexNaive(sectionIndex);
return toReturn;
}
Section getSection(int sectionIndex) {
int elementIndex = sectionIndexToElementIndex(sectionIndex);
if (elementIndex == -1) {
return null;
}
Element found = get(elementIndex);
assert found instanceof Section;
return (Section) found;
}
public int sectionIndexToElementIndexNaive(int i) {
Section s = null;
int si = -1;
Iterator<Section> iter = sectionsIterator();
while (iter.hasNext()) {
Section cur = iter.next();
++si;
if (i == si) {
s = cur;
break;
}
}
if (s == null) {
assert i == sectionsCount();
return size();
}
assert s != null;
int ei = si;
while (get(ei) != s) {
++ei;
}
return ei;
}
public Iterator<Section> sectionsIterator() {
return entries.stream().filter(element -> element instanceof Section).map(element -> (Section) element).iterator();
}
public int sectionsCount() {
return sectionElementIndices.size();
}
public int nonSectionsCount() {
return nonSectionElementIndices.size();
}
private void decrementSectionCounters(Element removed, int pos) {
if (removed instanceof Section) {
sectionElementIndices.remove(pos);
} else {
nonSectionElementIndices.remove(pos);
}
}
private void incrementSectionCounters(Element added, int pos) {
if (added instanceof Section) {
sectionElementIndices.add(pos);
} else {
nonSectionElementIndices.add(pos);
}
}
@Override
public boolean add(Element arg) {
elementForName.put(arg.getName(), arg);
boolean changed = entries.add(arg);
if (changed) {
int pos = size() - 1;
incrementSectionCounters(arg, pos);
}
return changed;
}
@Override
public boolean addAll(Collection<? extends Element> arg) {
boolean changed = false;
for (Element e : arg) {
changed |= this.add(e);
}
return changed;
}
@Override
public void clear() {
entries.clear();
elementForName.clear();
sectionElementIndices.clear();
nonSectionElementIndices.clear();
}
@Override
public boolean contains(Object arg) {
return entries.contains(arg);
}
@Override
public boolean containsAll(Collection<?> arg) {
return entries.containsAll(arg);
}
@Override
public boolean isEmpty() {
return entries.isEmpty();
}
@Override
public Iterator<Element> iterator() {
return entries.iterator();
}
@Override
public boolean remove(Object arg) {
boolean ret = entries.remove(arg);
int pos = entries.indexOf(arg);
if (ret) {
decrementSectionCounters((Element) arg, pos);
adjustAllGE(nonSectionElementIndices, pos, -1);
adjustAllGE(sectionElementIndices, pos, -1);
elementForName.remove(((Element) arg).getName());
}
return ret;
}
@Override
public boolean removeAll(Collection<?> arg0) {
boolean removed = false;
for (Object o : arg0) {
removed |= this.remove(o);
}
return removed;
}
@Override
public boolean retainAll(Collection<?> arg0) {
boolean changed = false;
for (Element e : this) {
if (!arg0.contains(e)) {
changed |= this.remove(e);
}
}
return changed;
}
@Override
public int size() {
return entries.size();
}
@Override
public Object[] toArray() {
return entries.toArray();
}
@Override
public <T> T[] toArray(T[] arg) {
return entries.toArray(arg);
}
static void adjustAllGE(SortedSet<Integer> t, int pos, int diff) {
TreeSet<Integer> tmp = new TreeSet<>();
SortedSet<Integer> tailSet = t.tailSet(pos);
for (Integer i : tailSet) {
tmp.add(i + diff);
}
t.removeAll(tailSet);
t.addAll(tmp);
}
@Override
public void add(int pos, Element arg1) {
adjustAllGE(sectionElementIndices, pos, 1);
adjustAllGE(nonSectionElementIndices, pos, 1);
entries.add(pos, arg1);
((arg1 instanceof Section) ? sectionElementIndices : nonSectionElementIndices).add(pos);
elementForName.put(arg1.getName(), arg1);
}
@Override
public boolean addAll(int arg0, Collection<? extends Element> arg1) {
int pos = arg0;
boolean changed = false;
for (Element e : arg1) {
this.add(pos++, e);
changed = true;
}
return changed;
}
@Override
public boolean equals(Object arg0) {
return entries.equals(arg0);
}
@Override
public Element get(int arg0) {
return entries.get(arg0);
}
@Override
public int hashCode() {
return entries.hashCode();
}
@Override
public int indexOf(Object arg0) {
return entries.indexOf(arg0);
}
@Override
public int lastIndexOf(Object arg0) {
return entries.lastIndexOf(arg0);
}
@Override
public ListIterator<Element> listIterator() {
return entries.listIterator();
}
@Override
public ListIterator<Element> listIterator(int arg0) {
return entries.listIterator(arg0);
}
@Override
public Element remove(int arg0) {
adjustAllGE(sectionElementIndices, arg0, -1);
adjustAllGE(nonSectionElementIndices, arg0, -1);
Element e = entries.remove(arg0);
elementForName.remove(e.getName());
return e;
}
@Override
public Element set(int arg0, Element arg1) {
Element replaced = entries.set(arg0, arg1);
elementForName.remove(replaced.getName());
elementForName.put(arg1.getName(), arg1);
if (replaced instanceof Section) {
sectionElementIndices.remove(arg0);
} else {
nonSectionElementIndices.remove(arg0);
}
if (arg1 instanceof Section) {
sectionElementIndices.add(arg0);
} else {
nonSectionElementIndices.add(arg0);
}
return replaced;
}
@Override
public List<Element> subList(int arg0, int arg1) {
return entries.subList(arg0, arg1);
}
}