代码之家 › 专栏 › 技术社区 › Kokufuu

Java通用循环缓冲区排序

circular-buffer generics sorting java

Kokufuu · 技术社区 · 7 年前

我有一个任务来实现一个通用的循环缓冲区。一切都很好,我只需要做一个 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
}

}

3 回复 | 直到 7 年前

OldCurmudgeon 7 年前

最简单的选择是将内容作为 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>> {

Roee Gavirel 7 年前

好
A) 这不是循环的-您应该重置索引 dataStart 和 dataEnd 当他们通过 capacity 。一种简单的方法是替换以下内容:

dataEnd++;

使用:

dataEnd = (dataEnd + 1) % capacity;

B) 一旦你这样做了,我猜你所说的“排序”只是指介于 数据启动 到 数据端 .这不是微不足道的,因为它是循环的。我认为您需要在循环缓冲区上实现其中一种排序。

Maurice Perry 7 年前

我会这样做:

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);
}