“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

In normal development, sets and sums are often used, but without a systematic comb, this article begins with a brief look at them.

The code version for Kotlin is 1.5.20 and the code version for Java is 1.8.

The body of the

Let’s take a look at what interfaces we inherit from the set and set that we normally use.

Top level interface carding

The Kotlin interface is slightly different from the Java interface. In Kotlin, there is a distinction between mutable and immutable variables, like val and var. These interfaces are named MutableXXX.

  • Iterator: Iterator interface. This is an Iterator interface. What is an Iterator? Under its interface, there are two most common iterator interfaces, one is a variable iterator interface, which means that the data set can be modified when iterating. One is ListIterator, which here can be understood as an ordered linear iterator interface.

  • Iterable: An Iterable interface. A class that implements this interface must implement the ability to iterate over data, usually through iterators.

  • Map interface: dedicated to key and value pairs. Note that the Map interface is not the base Iterable interface, but we can also iterate over a Map. Why not inherit from Iterable?

Subdivision interface carding

If you don’t quite understand why interfaces are designed this way, let’s take a look at what they mean.

可迭代

Means that the class is iterable, and how to iterate is by iterator. So this interface is very simple, and it just needs to return an iterator.

MutableIterable

The data set that Kotlin holds can not only be traversed, but can also be added, deleted, or modified by returning a variable iterator, so the interface requires a variable iterator.

Collection

The iterable class has been mentioned before, so this Collection class can be regarded as the concept of set sum, which is also referred to as set sum in ordinary times. It has an important feature that is a set of data of the same type. We think it is Collection, namely set sum.

So a Collection has some primitive functions for sets and sums, such as whether it is empty, how many elements it has, and so on.

MutableCollection

The MutableCollection interface has add and remove methods to add and remove elements, and the variable iterators returned by them can also add and remove elements. There are differences between these two methods, which we will discuss later.

List

The original design of the List interface is ordered, positioning is to deal with ordered sets and, so each element in the List has its own index, that is, the position coordinate, to express its order, it is the number, so the List interface has more methods about index.

Set

The positioning of a Set is de-duplication and unordering, that is, you can use a Set when you need to ensure that elements are not duplicated, but it is unordered and has no concept of subscripts, so its interface definition is relatively simple.

Map

When using Map to save and process key-value pairs, it has a requirement that the keys should not be repeated. According to the previous study, the keys should be stored with Set, and the values should be stored with List. This explains why Map sets and values do not need to be inherited from Collection, because it is a combination of Set and List, so its method is not complicated.

MutableList

As the name implies, this is a mutable List, because List is ordered with the concept of off-duty index, all additions, deletions, changes and searches can be indexed with index.

MutalbeSet

Mutable sets, which are unordered and repetitive, are deleted directly based on their elements.

MutableMap

Mutable Map. Because the keys in a Map are unique, operations are performed on unique keys.

Having said the set and part interfaces, iterator interfaces are certainly not missing, so we continue to comb through them.

Iterator

As mentioned earlier, the key to a set and iteration is to have iterators, so the basic function of an iterator is to iterate through the iteration and get the current element.

MutableIterator

Mutable iterators, which delete elements while iterating over data.

ListIterator

Just like the List concept, the ListIterator differs from the ordinary iterator in that it has the concept of order, which is the index index, so its design has a method for index.

MutableListIterator

Mutable List iterators, with added, subtracted, and modified functions that allow element processing in the iterator.

Other Abstract classes

Having said that, many of these methods are easy to implement, so in order to reduce the number of lines of code to implement concrete sets and sums, there are some base class abstract classes, let’s also take a brief look at them.

AbstractCollection

Abstract skeleton Collection column, a simple implementation of some interfaces:

  1. This contains method is implemented directly using an extension function, which is an extension of the Iterable class, directly look at the source code:
public inline fun  Iterable.any(predicate: (T) -> Boolean) :Boolean {
    if (this is Collection && isEmpty()) return false
    for (element in this) if (predicate(element)) return true
    return false
}
Copy the code

There are a lot of extension functions on the collection, when the specific use of the first to look for, do not implement their own, at the same time, if you want to implement, add extension functions on the collection is also a good example.

It also uses a quick for loop, which is really an operator overload of the iterator, and without the iterator, this quick for loop wouldn’t work either.

  1. The toArray method’s copyToArrayImpl implementation is decorated with Expect:
internal expect fun  copyToArrayImpl(collection: Collection<*>, array: Array) :Array
Copy the code

What does this mean? This method is defined in Kotlin, and is expected to be implemented on multiple platforms. This reflects kotlin’s cross-platform nature, which can be found in JVM implementations:

internal actual inline fun copyToArrayImpl(collection: Collection<*>): Array =
    kotlin.jvm.internal.collectionToArray(collection)
Copy the code
AbstractList

Abstract skeleton List, this class is for the concrete List to do some simple encapsulation, so that the concrete List implement fewer methods.

For the abstract List, there are also methods that can be implemented. The main points have been marked in the diagram.

  1. Since the List already has an order, the index method here can be implemented, again using extension functions.

  2. ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator: ListIterator

// Returns an iterator instance. The constructor takes the argument 0
override fun listIterator(): ListIterator = ListIteratorImpl(0)

private open inner class ListIteratorImpl(index: Int) : IteratorImpl(), ListIterator {

    // Maintain an internal index. This index is the real index of the external List
    init {
        checkPositionIndex(index, this@AbstractList.size)
        this.index = index
    }
    // If there is a front node, check whether index is greater than 0
    override fun hasPrevious(): Boolean = index > 0
    override fun nextIndex(): Int = index
    override fun previous(): E {
        if(! hasPrevious())throw NoSuchElementException()
        return get(--index)
    }
    override fun previousIndex(): Int = index - 1
}
Copy the code

You’ll see how simple this ListIterator implementation is.

3.SubList is interesting, which means to intercept the list, but its implementation principle is not to create a new list, but to use the original list data, modify the get method to achieve. So using SubList to intercept the SubList will also affect the original List.

// Where parameters are source List, start and end index respectively
private class SubList<out E> (private val list: AbstractList<E>, 
    private val fromIndex: Int.toIndex: Int) :
     AbstractList<E> (),RandomAccess {
        private var _size: Int = 0

        init {
            checkRangeIndexes(fromIndex, toIndex, list.size)
            this._size = toIndex - fromIndex
        }
        // The value obtained by the get method is the source List principality subscript
        override fun get(index: Int): E {
            checkElementIndex(index, _size)

            return list[fromIndex + index]
        }

        override val size: Int get() = _size
    }
Copy the code

4. In the case of hashCode, the equals and hashCode methods, since they are a List, must involve each element, so the order and values of the elements must be the same.

override fun equals(other: Any?) :Boolean {
        if (other === this) return true
        if(other ! is List<*>)return false
        // Check equals one by one
        return orderedEquals(this, other)
    }
Copy the code
internal fun orderedEquals(c: Collection<*>, other: Collection<*>): Boolean {
            if(c.size ! = other.size)return false

            val otherIterator = other.iterator()
            for (elem in c) {
                val elemOther = otherIterator.next()
                if(elem ! = elemOther) {return false}}return true
        }
Copy the code
override fun hashCode(): Int = orderedHashCode(this)
// Calculate hashCode, every element has to participate
internal fun orderedHashCode(c: Collection<*>): Int {
            var hashCode = 1
            for (e in c) {
                hashCode = 31* hashCode + (e? .hashCode() ? :0)}return hashCode
        }
Copy the code

conclusion

This chapter is just an introduction to interfaces, and the specific sets will be covered later.