`NonEmptySet` and `NonEmptyMap`¶

Four types hold at least one element, as NonEmptyVector does for sequences:

Type	Holds	Order	Total `head` and `last`
`NonEmptySet<A>`	a `HashSet`	not defined	no
`NonEmptySortedSet<A>`	a `TreeSet`	the comparator's	yes
`NonEmptyMap<K, V>`	a `HashMap`	not defined	no
`NonEmptySortedMap<K, V>`	a `TreeMap`	the comparator's, on the keys	yes

Each has every operation of the type it holds, under the same names, and the same costs. The exceptions are the operations that mean nothing on a non-empty collection:

isEmpty, nonEmpty, orElse and toNonEmptySet (or toNonEmptyMap, and so on), which would always give the same answer;
the Option forms of what is total here: reduceOption, singleOption, and on the sorted ones headOption, lastOption, tailOption and initOption.

Total operations¶

On a HashSet, max and reduce return an Option or fail, because the set may be empty. Here they return the value itself. The same holds for min, maxBy, minBy, average on the sets, and head and last on the sorted variants.

var tags    = NonEmptySet.of("java", "scala", "java");
var longest = tags.maxBy(String::length);                    // String
var total   = NonEmptySet.of(1, 2, 3).reduce(Integer::sum);  // Integer
// scala, 6

A hash set has no order, so NonEmptySet and NonEmptyMap have no head. On the sorted variants, head and last follow the comparator, while min and max use the natural order of the elements, as on every set.

The return-type contract¶

The return type tells you whether the result can be empty:

Returns	When	For example
the non-empty type	the operation cannot remove every element	`add`, `addAll`, `union`, `map`, `put`, `putAll`, `merge`, `mapValues`, `replace`
the plain type	the operation may remove elements	`filter`, `remove`, `updateWith`, `intersect`, `diff`, `take`, `drop`, `tail`, `rangeFrom`
`Option`	you ask for a part that may not exist	`find`, `get`, `tailNonEmpty()`, `initNonEmpty()`, `minAfter`, `maxBefore`

addAll, union, putAll and merge accept a collection that may be empty and still return the non-empty type. map on a set may merge equal results, and map on a map equal keys, but never down to nothing.

On a map, keySet() returns a NonEmptySet (a NonEmptySortedSet on a NonEmptySortedMap) and values() a NonEmptyVector. groupBy returns a NonEmptyMap whose values are non-empty, and on the sorted variants grouped, sliding and slideBy return a Vector of them. toMap returns a NonEmptyMap and toSortedMap a NonEmptySortedMap, on these types and on NonEmptyVector: a non-empty source gives at least one entry.

groupMap returns a NonEmptyMap too, of non-empty groups: a NonEmptySet of the values on the sets, a NonEmptyVector on the maps. groupMapReduce returns a NonEmptyMap of one value per group.

// NonEmptyMap<Integer, NonEmptySet<String>>
var byLength = NonEmptySet.of("a", "bb", "cc").groupBy(String::length);
// NonEmptyMap<Integer, String>
var index = NonEmptyVector.of("a", "bb").toMap(String::length, word -> word);
// byLength maps 1 to a set of a, and 2 to a set of bb and cc; index is NonEmptyMap((1, a), (2, bb))

var prices = NonEmptySortedMap.of(Tuple.of("pear", 3), Tuple.of("apple", 2));
var first  = prices.head();                            // Tuple2<String, Integer>
var names  = prices.keySet();                          // NonEmptySortedSet<String>
var cheap  = prices.filterValues(price -> price < 3);  // TreeMap<String, Integer>
// (apple, 2), NonEmptySortedSet(apple, pear), TreeMap((apple, 2))

flatMap takes a function that returns the non-empty type, and keeps the result non-empty. flatMapAll takes a function that returns any Iterable, and returns the plain type.

Construction¶

Constructor	Returns
`NonEmptySet.of(head, rest...)`, `single(a)`, `fromIterable(head, Iterable tail)`	`NonEmptySet<A>`
`NonEmptyMap.single(key, value)`, `of(entry, entries...)`, `fromIterable(entry, Iterable entries)`	`NonEmptyMap<K, V>`
`fromSet(HashSet)`, `fromMap(HashMap)`, `fromIterable(Iterable)`	an `Option`
`HashSet.toNonEmptySet()`, `HashMap.toNonEmptyMap()`	an `Option`
`unsafeFromSet(HashSet)`, `unsafeFromMap(HashMap)`	the non-empty type, or `IllegalArgumentException` when empty

The sorted variants have the same constructors, each in two forms: one for the natural order and one that takes a Comparator first. They wrap a TreeSet or a TreeMap with fromSortedSet, fromSortedMap, TreeSet.toNonEmptySortedSet() and TreeMap.toNonEmptySortedMap().

var fromInput   = HashMap.of("a", 1).toNonEmptyMap();       // Option<NonEmptyMap<String, Integer>>
var fromNothing = HashSet.<String>empty().toNonEmptySet();  // Option<NonEmptySet<String>>
// Some(NonEmptyMap((a, 1))), None

toSet(), toSortedSet(), toMap() and toSortedMap() without arguments return the collection held, without copying.

Costs¶

NonEmptySetNonEmptySortedSetNonEmptyMapNonEmptySortedMap

Operation	Cost	Note
`contains`	effectively O(1)	effectively O(1), as HashSet.contains.
`add`	effectively O(1)	effectively O(1), as HashSet.add.
`remove`	effectively O(1)	effectively O(1), as HashSet.remove.
`union`	O(m)	O(m) for a set of m elements, each an effectively O(1) insertion, as HashSet.union.
`intersect`	O(n + m)	O(n + m) for a set of m elements, as HashSet.intersect.
`diff`	O(m)	O(m) for a set of m elements; O(n) for a LinkedHashSet larger than this set, as HashSet.diff.
`min`	O(n)	O(n), every element compared once.
`max`	O(n)	O(n), every element compared once.

Operation	Cost	Note
`contains`	O(log n)	O(log n), as TreeSet.contains.
`add`	O(log n)	O(log n), as TreeSet.add.
`remove`	O(log n)	O(log n), as TreeSet.remove.
`union`	O(m log(n + m))	O(m log(n + m)) for a set of m elements, as TreeSet.union.
`intersect`	O(n + m log n)	O(n + m log n) for a set of m elements, as TreeSet.intersect.
`diff`	O(n + m log n)	O(n + m log n) for a set of m elements, as TreeSet.diff.
`min`	O(n)	O(n), every element compared once.
`max`	O(n)	O(n), every element compared once.
`head`	O(log n)	O(log n), as TreeSet.head.
`take`	O(log n)	O(log n), as TreeSet.take.
`drop`	O(log n)	O(log n), as TreeSet.drop.

Operation	Cost	Note
`get`	effectively O(1)	effectively O(1), as HashMap.get.
`containsKey`	effectively O(1)	effectively O(1), as HashMap.containsKey.
`put`	effectively O(1)	effectively O(1), as HashMap.put.
`putAll`	O(m)	O(m) for m entries, as HashMap.putAll; O(n + m) when they are a HashMap, merged part by part.
`remove`	effectively O(1)	effectively O(1), as HashMap.remove.
`updateWith`	effectively O(1)	effectively O(1), as HashMap.updateWith.
`keySet`	O(n)	O(n), with no hashing and no key comparison, as HashMap.keySet.
`values`	O(n)	O(n), as HashMap.values.

Operation	Cost	Note
`get`	O(log n)	O(log n), as TreeMap.get.
`containsKey`	O(log n)	O(log n), as TreeMap.containsKey.
`put`	O(log n)	O(log n), as TreeMap.put.
`putAll`	O(m log(n + m))	O(m log(n + m)) for m entries, as TreeMap.putAll.
`remove`	O(log n)	O(log n), as TreeMap.remove.
`updateWith`	O(log n)	O(log n), as TreeMap.updateWith.
`keySet`	O(n)	O(n), with no key comparison, as TreeMap.keySet.
`values`	O(n)	O(n), as TreeMap.values.
`head`	O(log n)	O(log n), as TreeMap.head.
`take`	O(log n)	O(log n), as TreeMap.take.
`drop`	O(log n)	O(log n), as TreeMap.drop.

Every method: complexity page.

Sharp edges¶

A non-empty set is not a Set and is not equal to one with the same elements; compare through toSet() or toSortedSet(). The same goes for the maps. A NonEmptySet and a NonEmptySortedSet with the same elements are equal, as sets are: the elements are compared with their own equals, whatever the comparator, so a.equals(b) and b.equals(a) always agree. With a case-insensitive order, a NonEmptySortedSet of "a" equals a NonEmptySet of "a", not one of "A".
They are Iterable, but not Traversable. union, intersect and diff take a Set; to pass a non-empty set, use addAll, retainAll and removeAll, which take any Iterable.
reduce and fold on a NonEmptySet or a NonEmptyMap see the elements in hash order: give them an operation where the order does not matter.

NonEmptySet and NonEmptyMap¶