Todo List

Class <CHSortedSet>

Add more operations similar to those supported by NSSet and NSMutableSet, such as:

• - (NSArray*) allObjectsFilteredUsingPredicate:
• - (void) filterUsingPredicate:
• - (BOOL) isEqualToSortedSet:
• - (BOOL) isSubsetOfSortedSet:
• - (BOOL) intersectsSet:
• - (void) intersectSet:
• - (void) minusSet:
• - (void) unionSet:

Consider adding other possible sorted set implementations, such as skip lists, sorted linear hash sets, and sorted lists.

Member [CHMultiDictionary objectEnumerator]

Refine with custom enumerator for greater efficiency?

Member [CHRedBlackTree removeObject:]

Speed up red-black removal. The EternallyConfuzzled.com tutorial opts to push a red node down the tree using rotations and flips to avoid a nasty case of deleting a black node. This is almost certainly what causes the performance problems.

Class CHLockableDictionary

Implement -copy and -mutableCopy differently (so users can actually obtain an immutable copy) and make mutation methods aware of immutability?

Class CHMultiDictionary

Combine -addObject:forKey: and -addObjects:forKey: into a single method that accepts an NSArray, NSSet, or generic object, then wraps in a mutable set?

Class CHOrderedSet

Allow setting a maximum size, and either reject additions or evict the "oldest" item when the limit is reached? (Perhaps this would be better done by the user...)

Class CHSortedDictionary

Document CHSortedDictionary

Class CHTreap

Examine performance issues (treaps are often the slowest balanced tree).

page Overview

Add support for NSSortDescriptor for comparator-style sorting. (Currently, all implementations use -compare: for sorting.)

Consider implementing "versionable" persistent data structures, wherein concurrent enumeration and modification are supported via tagged versions of the structure. (An example of this for red-black trees is an exercise for the reader in "Introduction to Algorithms, 2nd Edition" (ISBN: 9780262032933) in problem 13.1, pages 294-295.) The best candidates are probably queues, heaps, and search trees (sorted sets).

Look at adding -filterUsingPredicate: to all data structures. This would allow applying an NSPredicate and removing only objects that don't match. Also add copying variants (-filteredQueueUsingPredicate:, -filteredSortedSetUsingPredicate:, etc.) to avoid the overhead of a full copy before filtering.

Examine feasibility and utility of implementing key-value observing/coding/binding.