Guava TreeMultiSet實作原理分析

1 存儲模型

TreeMultiset本身實作了一棵平衡樹，并通過使用者定義的比對方式進行排序。使用者可以通過兩種方式定義比較器：資料類型實作Comparable，或者為Set注冊Comparator。和普通的Set相比，TreeMultiset允許多個資料在比較器比較結果是相等的。如果相等，則放在此節點下的一個清單中。

TreeMultiset定義了兩種查找方式：head和tail。和他們的名字相對應，head是從頭開始截取一部分資料集合，tail是從一個節點開始到尾部截取一部分資料集合。TreeMultiset并沒有定義equal的查詢方式，而是需要head和tail結合使用，完成equal的功能。當然，head和tail操作可以截取任何一段資料。

TreeMultiset的資料段采用GeneralRange模型來辨別。GeneralRange包含了資料段上下限的定義，比較器，以及上下限的開閉性質。

2 樹形結構

TreeMultiset本身是一個平衡二叉樹。樹節點的類型為AvlNode，通過left和right維護節點的左右子節點。

為了快速查詢周遊，樹上的每個節點通過深度優先搜尋的順序維護自己的上一個節點和下一個節點。如果不做此維護，那麼尋找下一節點的時間複雜度将有可能是O(log2n)。比如element4，他是根節點左子樹的最後一個節點，他的下個節點是根節點。不加pred和succ的情況下，需要層層遞歸，直到根節點。

3 head，tail

head操作，是通過條件找到資料段的終止節點，并封裝成新的TreeMultiset傳回。

@Override
  public SortedMultiset<E> headMultiset(@Nullable E upperBound, BoundType  boundType) {
    return new TreeMultiset<E>(
        rootReference,
        range.intersect(GeneralRange.upTo(comparator(), upperBound, boundType)),
        header);
  }
           

GeneralRange通過upTo()方法建立了一個執行個體，并通過此執行個體找出資料區間。

GeneralRange的構造函數對參數進行了校驗，如下圖。其中對輸入的查詢資訊進行了多次比對（lowerEndPoint，upperEndPoint），確定參數可比對以及參數的區間是存在的。

接下來，TreeMultiset的range将會和新的range進行交集計算，确定資料區間。

tail的實作方式和head類似。

4 iterator

TreeMultiset的iterator實際實作定義在Iterator<Entry> entryIterator()中，如下代碼。

疊代器實際上通過AvlNode的資訊進行周遊。本身存放目前的節點資訊。當調用next時，就傳回succ的節點資訊。

每傳回一個節點，都會先進行一次邊界比較。range.tooHigh()中将upperBound和current進行比對。如果超出upperBound，則認為到達邊界，結束周遊。

return new Iterator<Entry<E>>() {
      AvlNode<E> current = firstNode();
      @Nullable Entry<E> prevEntry;
      @Override
      public boolean hasNext() {
        if (current == null) {
          return false;
        } else if (range.tooHigh(current.getElement())) {
          current = null;
          return false;
        } else {
          return true;
        }
      }
      @Override
      public Entry<E> next() {
        if (!hasNext()) {
          throw new NoSuchElementException();
        }
        Entry<E> result = wrapEntry(current);
        prevEntry = result;
        if (current.succ == header) {
          current = null;
        } else {
          current = current.succ;
        }
        return result;
      }
      @Override
      public void remove() {
        checkRemove(prevEntry != null);
        setCount(prevEntry.getElement(), 0);
        prevEntry = null;
      }
    };