我有一个任务来实现一个通用的循环缓冲区。一切都很好,我只需要做一个sort
方法,但是我想不出一个解决方案来使它泛型。你能给我一个提示吗?谢谢!
public class CircularBuffer<T> {
public T[] elements = null;
private int capacity = 0;
private int dataStart = 0;
private int dataEnd = 0;
@SuppressWarnings("unchecked")
public CircularBuffer(int capacity) {
this.capacity = capacity;
this.elements = (T[]) new Object[capacity];
}
public boolean isEmpty() {
return dataStart == dataEnd;
}
public boolean isFull() {
if (dataStart == 0) {
return dataEnd == capacity - 1 ;
}
return dataStart - dataEnd == 1;
}
public int size() {
return dataEnd - dataStart;
}
public void put(T t) {
if (isFull()) {
throw new RuntimeException("Buffer is full");
}
if (dataEnd < capacity) {
elements[dataEnd] = t;
dataEnd++;
}
}
public T get() {
if (isEmpty()) {
throw new RuntimeException("Buffer is empty");
}
return elements[dataStart++];
}
public Object[] toObjectArray() {
Object[] newArray = new Object[size()];
for (int i = dataStart; i < dataEnd; i++) {
newArray[i] = elements[i];
}
return newArray;
}
@SuppressWarnings("unchecked")
public <Q> Q[] toArray(Q[] a) {
if (a.length < size())
return (Q[]) Arrays.copyOf(elements, size(), a.getClass());
System.arraycopy(elements, 0, a, 0, size());
return a;
}
public List<T> asList(List<T> a) {
List<T> list = new ArrayList<>(size());
for (int i = dataStart; i < dataEnd; i++) {
list.add(elements[i]);
}
return list;
}
public void addAll(List<? extends T> toAdd) {
if (toAdd.size() > capacity - size()) {
throw new RuntimeException("Not enough space to add all elements");
}
else {
for (int i = 0; i < toAdd.size(); i++) {
elements[dataEnd] = toAdd.get(i);
dataEnd++;
}
}
}
public void sort(Comparator<? super T> comparator) {
// TODO
}
}
发布于 2018-04-10 20:32:16
最简单的选择是将内容作为List
取出,对其进行排序,并替换现在排序的列表中的旧内容。
public void sort(Comparator<? super T> comparator) {
// Get them all out - not sure why you have a parameter to `asList`
List<T> all = asList(Collections.emptyList());
// Sort them.
Collections.<T>sort(all);
// Clear completely.
dataStart = dataEnd = 0;
addAll(all);
}
您需要更改类的签名以确保T
是可排序的。
public class CircularBuffer<T extends Comparable<T>> {
发布于 2018-04-10 20:17:10
井,
A)这不是循环的-当索引dataStart
和dataEnd
通过capacity
时,您应该重置它们。要做到这一点,一种简单的方法是替换以下内容:
dataEnd++;
通过以下方式:
dataEnd = (dataEnd + 1) % capacity;
B)一旦你这样做了,我猜你所谓的“排序”只是指dataStart
到dataEnd
之间的那部分。这并不是微不足道的,因为它是循环的。我认为你需要在你的循环缓冲区中实现一个排序。
发布于 2018-04-10 20:31:00
我会这样做:
public void sort(Comparator<? super T> comparator) {
if (dataStart > dataEnd) {
System.arraycopy(elements, dataStart, elements, dataEnd, capacity-dataStart);
dataEnd = dataEnd + capacity-dataStart;
dataStart = 0;
}
Arrays.sort(elements, dataStart, dataEnd, comparator);
}
https://stackoverflow.com/questions/49753173
复制相似问题