java - 按 "add() count"排序的集合

Question

我正在尝试实现一个按添加数量排序的 Set，如下所示:

public class App {
    public static void main(String args[]) {
        FrequencyOrderedTreeSet<String> set = new FrequencyOrderedTreeSet<String>();
        set.add("bar");
        set.add("foo");
        set.add("foo");
        Iterator<String> i = set.iterator();
        while (i.hasNext()) {
            System.out.print(i.next());
        }
        // prints "foobar"
    }
}

我创建了一个 protected class FrequencyOrderedTreeSet.Element它实现了 Comparable并有一个T entry和一个int frequency属性(property)和延伸TreeSet<FrequencyOrderedTreeSet.Element>与 FrequencyOrderedTreeSet<T>并覆盖 compareTo和equals Element 上的方法.

一个问题是，由于类型删除问题，我无法重写 add() 方法，而且我也无法调用 instanceof Element在 equals方法，因为如果给它的对象是一个 Element，我必须比较它们的条目，但如果不是，我必须将对象本身与 this.entry 进行比较.

在 add方法我创建一个新元素，找到集合中具有相同条目的元素，将新元素的频率设置为“旧+1”，删除旧元素并添加新元素。我什至不确定这是最好的方法，或者它是否有效，因为我描述了其他问题。

问题是:实现这种数据结构的最佳方法是什么？如果我在某种程度上走在正确的轨道上 - 我怎样才能避免上面提到的问题？

Answer 1

这是一个基本的实现。这不是最优的，如果您想实现完整的 Set 接口(interface)，还需要做更多的工作。

public class FrequencySet<T> implements Iterable<T>
{
    private TreeSet<T> set;
    private HashMap<T, Integer> elements = new HashMap<T, Integer>();

    public FrequencySet()
    {
        set = new TreeSet<T>(new Comparator<T>()
        {
            public int compare(T o1, T o2)
            {
                return elements.get(o2)-elements.get(o1);
            }
        });
    }

    public void add(T t)
    {
        Integer i = elements.get(t);
        elements.put(t, i == null ? 1 : i+1);
        set.remove(t);
        set.add(t);
    }

    public Iterator<T> iterator() {return set.iterator();}

    public static void main(String [] args)
    {
        FrequencySet<String> fset = new FrequencySet<String>();

        fset.add("foo");
        fset.add("bar");
        fset.add("foo");
        for (String s : fset)
            System.out.print(s);
        System.out.println();

        fset.add("bar");
        fset.add("bar");
        for (String s : fset)
            System.out.print(s);
    }
}

关键在add方法。我们更改给定对象的计数器(这会更改关系顺序)，将其从支持集中删除并将其放回。