TreeMultiSet

TreeSet that supports repeatable elements based on TreeMap implementation

Anyone who has worked with Java knows TreeSet, but TreeSet does not support repeating elements. One might say, why not ArrayList or LinkedList? Indeed, arrayLists or LinkedLists are naturally unweighted and can meet the need to support repeating elements. However, NOT only do I need to support repeatable elements, but I also need the data to stay in order in real time.

Somebody here says again, isn’t order easy? After I insert the data into the ArrayList or LinkedList, I call sort and I’m done. Well, sure, if your List doesn’t change very often (sort is very, very rare), then you can certainly use List+sort. But what if the data is constantly changing? 【 References 】

If the data is constantly changing and you need to keep the data in order in real time (e.g., there are minimum and maximum requirements for real-time queries), the time complexity is very high if you use List+sort: So the single insertion time is O(n)O(n), and if you have n elements, you need O(n^2)O(n 2). So, if we want to reduce time complexity, we can’t use lists.

Then someone said, I just use TreeMap seems to be ok. The key of a TreeMap is an element, and the value is the number of occurrences of the element corresponding to the key. This satisfies the need for repeatable and ordered inserts. [Ref.] Indeed, this can meet the requirement of repeatable and ordered roughly. However, here are a few disadvantages of using TreeMap for repeatable and ordered requirements:

If we need to know the number of sets of repeatable elements (the number of repeating elements counts as multiple), we can’t get it immediately and within O(1)O(1) time using TreeMap. Instead, we need to loop through all keys and then compute the sum of all values. The general code is as follows:

 int size = 0;
    for (Integer num : treeMap.keySet()) {
        size += treeMap.get(num);
    }
Copy the code

Does that seem like a bit of a hassle? To get the number of sets, we should expect the following to be succinct:

    set.size();
Copy the code

If we need to iterate over all the elements in the collection, repeating elements need to be iterate over multiple times (similar to the list). Using TreeMap to do this requires a double loop, which is not intuitive. As follows:

    for (Integer num : treeMap.keySet()) {
        int count = treeMap.get(num);
        while ((count--) > 0) {
            // Use a loop to print num count timesSystem.out.println(num); }}Copy the code

Again, we should expect a repeat loop, like the following:

    for (Integer num : set) {
        System.out.println(num);
    }
Copy the code

If we need to delete a specified number of elements in the set. For example, set [1, 2, 2, 3, 3, 3]. I just want to delete two 3’s, TreeMap needs to do this:

    if (treeMap.containsKey(3)) {
        treeMap.put(2, treeMap.get(3) - 2);
    }
Copy the code

Again, we should expect something like this:

    set.remove(3.2); // The second argument represents the number of elements to delete
// If we need to add a specified number of elements to the collection. For example, set [1, 2, 2, 2, 4], we need to add two 4's, TreeMap needs to do this:
// Join Java development chat
    treeMap.put(4, treeMap.getOrDefault(4.0) + 2);
// Again, we should expect something like this:


    set.add(4.2); // The second argument represents the number of elements to be inserted
Copy the code

In addition, there are a few less elegant ways in which TreeMap implements the functionality of a repeatable TreeSet, which I won’t list here.

Hence, TreeMultiSet was born. (Just for the record: TreeMultiSet is mostly realized by referring to TreeSet, which is actually based on TreeMap, and the bottom layer of TreeMap is realized by red-black Tree. This is also the essential reason why TreeSet’s remove operation can achieve O(logN) time complexity.

How to use

gradle

Step 1. Add the JitPack repository in your root build.gradle at the end of repositories:


allprojects {
	repositories {
		...
		maven { url 'https://jitpack.io'}}}// Join Java development chat
Step 2. Add the dependency in your app build.gradle:


dependencies {
	implementation 'com. Making. Yuruiyin: TreeMultiSet: 1.0.1'
}
Copy the code

Feature list

Code demo

Here are a few ways to call some methods that I think are commonly used

1) Create a new TreeMultiSet for a custom comparator

    TreeMultiSet<Integer> set = new TreeMultiSet<>((o1, o2) -> o2 - o1); // Pass a big-to-small comparator
Copy the code

2) Foreach traverses all elements (including repeating elements)

    for (Integer num : set) {
        // TODO, which can output sequences like 2, 2, 2, 3
    }
Copy the code

3) Get forward iterators for all elements (including repeating elements)

    Iterator<Integer> iterator = set.iterator();
    while (iterator.hasNext()) {
        arr[i++] = iterator.next();
    }
Copy the code

4) Get forward iterators for different elements

    Iterator<Integer> diffIterator = set.diffIterator();
    while (diffIterator.hasNext()) {
        arr[i++] = diffIterator.next();
    }
Copy the code

5) Get the total number of elements (including duplicate elements)

    set.size();
Copy the code

6) Get the number of different elements

    set.diffElementSize();
Copy the code

7) Get the first and last element

    set.first();
    set.last();
Copy the code

Add a specified number of elements

    set.add(2.3); // Add 3 2's to the set
Copy the code

9) Set the number of specified elements

    set.setCount(2.3); // Set the number of 2's in the set to 3
Copy the code

10) Get the number of specified elements

    set.count(2); // Get the number of 2 in the set
Copy the code

11) Delete the specified number of elements

    set.remove(2.3); // Delete 3 2's
Copy the code

12) Delete the specified number of first elements

 set.pollFirst(2); // Delete 2 first elements. If the collection [1,1,1,2,2,3] executes this line of code and becomes [1,2,2,3]
Copy the code

13) Delete the last element of the specified number

    set.pollLast(1); // Delete 1 last element. If the collection [1,1,1,2,3,3] executes this line of code and becomes [1,1,1,2,2,3]
Copy the code

Unit testing

TreeMultiSetTest has been unit tested on all methods of TreeMultiSet, including constructors, with 100% test coverage.

Various set contrast

Note the complexity listed below refers to the time complexity. And the following insert and delete operations refer to operations on intermediate elements. At the same time, the insertion and deletion time complexity of the LinkedList takes into account the query time to the location to be inserted or deleted.

Mysql, Netty, Spring, thread, Spring Cloud, JVM, source code, algorithm, etc., also have a detailed learning plan map, interview questions, etc., need to obtain these contents of the friend please add Q: sample: 756584822