v1.0.1

Anatree

• Added use of C++20 concepts to ensure given template parameters indeed can be used as part of the Anatree.
• Switched the internal tree structure from using std::shared_ptr to std::unique_ptr. This should improve performance as reference counting now is omitted.

Contributors

• Steffan Sølvsten ( @SSoelvsten )

v1.0.0

Anatree

A data structure in which you can store a set of words, i.e. list of some type of elements, and is optimised to answer queries for words that are equal up to permutation (and removal) of elements

Operations

Many operations are not related to the size of the set N or the number of nodes in the tree n but rather only the size of a word w and the number of symbols used from the alphabet Σ.

• insert(w)
  Stores the word w.
  Time: O(w lg w + |Σ|)
• insert(begin, end)
  Stores each of the words provided by the iterator.
• contains(w)
  Whether the tree currently contains w.
  Time: O(w lg w + |Σ|)
• size()
  Obtain the number N of words stored.
  Time: O(1)
• empty()
  Obtain whether no words are stored.
  Time: O(1)
• tree_size()
  Obtain the number n of number of nodes in the tree (including leaves)
  Time: O(1)
• clear()
  Remove all the words stored.
  Time: O(n + N)
• keys()
  Obtain all words in the tree, excluding the ones that are a subanagram of another one returned.
  Time: O(n³)
• keys(word_length)
  Obtain all words in the tree of a certain length, excluding the ones that are an anagram of another one returned.
  Time: O(n²)
• anagrams_of(w)
  Obtain all words that are anagrams of w.
  Time: O(w lg w + |Σ| + T) where T is the output size.
• subanagrams_of(w)
  Obtain all words that are subanagrams of w.
  Time: O(w lg w + T (|Σ| + w)) where T is the output size.

Contributors

• Steffan Sølvsten ( @SSoelvsten )
• Andreas Hesselholt Høj Hansen ( @APersonH )