Skip to content

Ghidra is a software reverse engineering (SRE) framework

29.8 KB
Raw Blame
/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package generic;

import java.util.*;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.stream.Collectors;

import generic.ULongSpan.*;

/**
 * A (closed) interval
 *
 * <p>
 * An interval-like type may implement this interface in order to obtain a near out-of-box
 * implementation of a map and/or set of spans. Common operations, such as computing intersections
 * and bounds, are provided. Similarly, spans are automatically coalesced when present in sets and
 * maps. The main requirement is that the span define the domain of its endpoints. The domain can
 * impose behaviors and properties that aren't otherwise present on the type of endpoints. For
 * example, the domain may be {@link Long}s, but using unsigned attributes. The domain also provides
 * a factory for new spans. While nominally, this only supports closed intervals, the domain can
 * define a custom endpoint type to obtain mixed intervals.
 *
 * @param <N> the type of endpoints
 * @param <S> the type of spans (recursive)
 */
public interface Span<N, S extends Span<N, S>> extends Comparable<S> {
	/**
	 * The (discrete) domain of endpoints for a span
	 *
	 * <p>
	 * This defines the domain, which may introduce behaviors different than those naturally
	 * acquired from the type. For example, a domain may impose unsigned comparison on a (boxed)
	 * primitive type.
	 *
	 * @implNote each domain should be a singleton class
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 */
	public interface Domain<N, S extends Span<N, S>> {
		/**
		 * Create a new span with the given endpoints, inclusive.
		 * 
		 * @param min the lower endpoint
		 * @param max the upper endpoint
		 * @return the span
		 * @throws IllegalArgumentException if max is less than min
		 */
		default S closed(N min, N max) {
			if (compare(min, max) > 0) {
				throw new IllegalArgumentException("min > max: min=" + min + ",max=" + max);
			}
			return newSpan(min, max);
		}

		/**
		 * Factory method for a new span after arguments are validated
		 * 
		 * @param min the lower endpoint
		 * @param max the upper endpoint
		 * @return the span
		 */
		S newSpan(N min, N max);

		/**
		 * Construct a span containing only the given value
		 * 
		 * @param n the value
		 * @return the span
		 */
		default S value(N n) {
			return closed(n, n);
		}

		/**
		 * Construct a new span with the given upper endpoint, inclusive.
		 * 
		 * <p>
		 * The lower endpoint becomes the minimum value in the domain
		 * 
		 * @param max the upper endpoint
		 * @return the span
		 */
		default S atMost(N max) {
			return closed(min(), max);
		}

		/**
		 * Construct a new span with the given lower endpoint, inclusive.
		 * 
		 * <p>
		 * The upper endpoint becomes the maximum value in the domain
		 * 
		 * @param min the lower endpoint
		 * @return the span
		 */
		default S atLeast(N min) {
			return closed(min, max());
		}

		/**
		 * Get the span containing all values in the domain
		 * 
		 * @implNote It is recommended to return a static object
		 * @return the span
		 */
		S all();

		/**
		 * Get the span that contains no value, nor has any endpoints
		 * 
		 * <p>
		 * This span is returned when the result doesn't exist, e.g., when finding the intersection
		 * of spans which do not intersect.
		 * 
		 * @implNote It is recommended to implement {@link Empty} as a singleton class and return
		 *           its instance
		 * @return the empty span
		 */
		S empty();

		/**
		 * Render the given value as a string
		 * 
		 * @param n the value
		 * @return the string
		 */
		default String toString(N n) {
			return n.toString();
		}

		/**
		 * Render the given span as a string
		 * 
		 * @param s the span
		 * @return the string
		 */
		default String toString(S s) {
			return toString(s, this::toString);
		}

		/**
		 * Render the given span as a string
		 * 
		 * @param s the span
		 * @param nToString a function to convert n to a string
		 * @return the string
		 */
		default String toString(S s, Function<? super N, String> nToString) {
			return s.isEmpty() ? "(empty)"
					: toMinString(s.min(), nToString) + ".." + toMaxString(s.max(), nToString);
		}

		/**
		 * Render the lower bound of a span
		 * 
		 * @param min the lower bound
		 * @param nToString a function to convert n to a string
		 * @return the string
		 */
		default String toMinString(N min, Function<? super N, String> nToString) {
			return min().equals(min) ? "(-inf" : ("[" + nToString.apply(min));
		}

		/**
		 * Render the upper bound of a span
		 * 
		 * @param max the upper bound
		 * @param nToString a function to convert n to a string
		 * @return the string
		 */
		default String toMaxString(N max, Function<? super N, String> nToString) {
			return max().equals(max) ? "+inf)" : (nToString.apply(max) + "]");
		}

		/**
		 * Compare two values
		 * 
		 * @param n1 a value
		 * @param n2 another value
		 * @return the result, as in {@link Comparator#compare(Object, Object)}
		 */
		int compare(N n1, N n2);

		/**
		 * Get the minimum value in the domain
		 * 
		 * <p>
		 * This value can also represent negative infinity.
		 * 
		 * @return the minimum value
		 */
		N min();

		/**
		 * Get the maximum value in the domain
		 * 
		 * <p>
		 * This value can also represent positive infinity.
		 * 
		 * @return the maximum value
		 */
		N max();

		/**
		 * Get a given value, incremented by 1
		 * 
		 * <p>
		 * If the resulting value would exceed {@link #max()}, this should wrap to {@link #min()}.
		 * 
		 * @param n the value
		 * @return the value incremented
		 */
		N inc(N n);

		/**
		 * Get a given value, decremented by 1
		 * 
		 * <p>
		 * If the resulting value would exceed {@link #min()}, this should wrap to {@link #max()}.
		 * 
		 * @param n the value
		 * @return the value decremented
		 */
		N dec(N n);

		/**
		 * Get the lesser of two values
		 * 
		 * <p>
		 * If the values are equal, then either may be chosen
		 * 
		 * @param n1 a value
		 * @param n2 another value
		 * @return the lesser
		 */
		default N min(N n1, N n2) {
			return compare(n1, n2) < 0 ? n1 : n2;
		}

		/**
		 * Get the greater of two values
		 * 
		 * <p>
		 * If the values are equal, then either may be chosen
		 * 
		 * @param n1 a value
		 * @param n2 another value
		 * @return the greater
		 */
		default N max(N n1, N n2) {
			return compare(n1, n2) < 0 ? n2 : n1;
		}

		/**
		 * Compute the intersection of two spans
		 * 
		 * @param s1 a span
		 * @param s2 another span
		 * @return the intersection, possibly empty
		 */
		default S intersect(S s1, S s2) {
			if (!intersects(s1, s2)) {
				return empty();
			}
			return closed(max(s1.min(), s2.min()), min(s1.max(), s2.max()));
		}

		/**
		 * Check if two spans intersect
		 * 
		 * @param s1 a span
		 * @param s2 another span
		 * @return true if they intersect
		 */
		default boolean intersects(S s1, S s2) {
			if (s1.isEmpty() || s2.isEmpty()) {
				return false;
			}
			return compare(s1.max(), s2.min()) >= 0 && compare(s2.max(), s1.min()) >= 0;
		}

		/**
		 * Check if one span encloses another
		 * 
		 * @param s1 a span
		 * @param s2 another span
		 * @return true if s1 encloses s2
		 */
		default boolean encloses(S s1, S s2) {
			if (s1.isEmpty()) {
				return false;
			}
			if (s2.isEmpty()) {
				return true;
			}
			return compare(s1.min(), s2.min()) <= 0 && compare(s1.max(), s2.max()) >= 0;
		}

		/**
		 * Compute the smallest span which contains two spans
		 * 
		 * @param s1 a span
		 * @param s2 another span
		 * @return the bounding span
		 */
		default S bound(S s1, S s2) {
			if (s1.isEmpty()) {
				return s2;
			}
			if (s2.isEmpty()) {
				return s1;
			}
			return closed(min(s1.min(), s2.min()), max(s1.max(), s2.max()));
		}

		/**
		 * Subtract two spans
		 * 
		 * <p>
		 * If the first span is empty, this returns 0 spans.
		 * 
		 * @param s1 a span
		 * @param s2 another span
		 * @return 0, 1, or 2 spans
		 */
		default List<S> subtract(S s1, S s2) {
			if (s1.isEmpty()) {
				return List.of();
			}
			if (s2.isEmpty()) {
				return List.of(s1);
			}
			if (compare(s1.max(), s2.min()) < 0 || compare(s2.max(), s1.min()) < 0) {
				return List.of(s1);
			}
			if (compare(s1.min(), s2.min()) < 0) {
				if (compare(s1.max(), s2.max()) > 0) {
					return List.of(
						closed(s1.min(), dec(s2.min())),
						closed(inc(s2.max()), s1.max()));
				}
				return List.of(closed(s1.min(), dec(s2.min())));
			}
			if (compare(s1.max(), s2.max()) > 0) {
				return List.of(closed(inc(s2.max()), s1.max()));
			}
			return List.of();
		}
	}

	/**
	 * A mix-in interface for empty spans
	 *
	 * @implNote It is recommended to implement this as a singleton class
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 */
	public interface Empty<N, S extends Span<N, S>> extends Span<N, S> {
		@Override
		default N min() {
			throw new NoSuchElementException();
		}

		@Override
		default N max() {
			throw new NoSuchElementException();
		}

		@Override
		default boolean isEmpty() {
			return true;
		}

		@Override
		default boolean contains(N c) {
			return false;
		}
	}

	/**
	 * An abstract interface for an immutable map of spans to values
	 * 
	 * <p>
	 * Spans are not allowed to overlap, and connected spans are automatically coalesced when mapped
	 * to the same value. For example, the entries {@code [1..5]='A'} and {@code [6..10]='A'} become
	 * one entry {@code [1..10]='A'}. When an entry is added that overlaps other entries, the
	 * existing entries are truncated or deleted (or coalesced if they share the same value as the
	 * new entry) so that the new entry can fit.
	 * 
	 * @implNote It is recommended to create an interface (having only the {@code <V>} parameter)
	 *           extending this one specific to your domain and span type, then implement it using
	 *           an extension of {@link DefaultSpanMap}. See {@link ULongSpanMap} for an example.
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 * @param <V> the type of values
	 */
	public interface SpanMap<N, S extends Span<N, S>, V> {
		/**
		 * Check if this map has any entries
		 * 
		 * @return true if empty
		 */
		boolean isEmpty();

		/**
		 * Get the spans in this map
		 * 
		 * <p>
		 * Note that the behavior regarding a copy versus a view is not specified. Clients should
		 * not rely on one or the other.
		 * 
		 * @return the set of spans
		 */
		NavigableSet<S> spans();

		/**
		 * Get the values in this map
		 * 
		 * <p>
		 * Note that the behavior regarding a copy versus a view is not specified. Clients should
		 * not rely on one of the other.
		 * 
		 * @return the collection of values
		 */
		Collection<V> values();

		/**
		 * Get a span which encloses all spans in the map
		 * 
		 * @return the bounding span
		 */
		S bound();

		/**
		 * Get the entries in this map
		 * <p>
		 * Note that the behavior regarding a copy versus a view is not specified. Clients should
		 * not rely on one or the other.
		 * 
		 * @return the set of entries
		 */
		Set<Map.Entry<S, V>> entries();

		/**
		 * Get the entry whose span contains the given key
		 * 
		 * @param n the key
		 * @return the entry, or null
		 */
		Map.Entry<S, V> getEntry(N n);

		/**
		 * Get the value of the given key
		 * 
		 * <p>
		 * Note that a null return could indicate either that no entry has a span containing the
		 * given key, or that the entry whose span contains it has the null value. To distinguish
		 * the two, consider using {@link #getEntry(Object)}.
		 * 
		 * @param n the key
		 * @return the value, or null
		 */
		V get(N n);

		/**
		 * Iterate over all entries whose spans intersect the given span
		 * 
		 * @param s the span
		 * @return an iterable of entries
		 */
		Iterable<Map.Entry<S, V>> intersectingEntries(S s);

		/**
		 * Iterate over all spans in the map that intersect the given span
		 * 
		 * @param s the span
		 * @return an iterable of spans
		 */
		Iterable<S> intersectingSpans(S s);

		/**
		 * Check if any span in the map intersects the given span
		 * 
		 * @param s the span
		 * @return true if any span in the map intersects it
		 */
		boolean intersects(S s);
	}

	/**
	 * An abstract interface for a mutable {@link SpanMap}
	 *
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 * @param <V> the type of values
	 */
	public interface MutableSpanMap<N, S extends Span<N, S>, V> extends SpanMap<N, S, V> {
		/**
		 * Put an entry, mapping all keys contains in the span to the given value
		 * 
		 * <p>
		 * Each key can only be mapped to a single value. Thus existing entries having the same
		 * value may be coalesced to this new entry. Existing entries having a different value will
		 * be truncated or deleted to make room for this entry.
		 * 
		 * @param s the span
		 * @param v the value
		 */
		void put(S s, V v);

		/**
		 * Copy all entries from the given map into this one
		 * 
		 * <p>
		 * The entries from both maps may be coalesced when entered into this one. (The given map
		 * remains unmodified.) The entries in this map may be truncated or deleted to make room for
		 * those in the given map.
		 * 
		 * @param map the other map
		 */
		void putAll(SpanMap<N, S, V> map);

		/**
		 * Delete all keys in the given span
		 * 
		 * <p>
		 * Entries which intersect the given span are truncated. Entries which are enclosed are
		 * deleted, such that every key in the given span is no longer mapped to a value.
		 * 
		 * @param s the span
		 */
		void remove(S s);

		/**
		 * Remove all entries from the map
		 */
		void clear();
	}

	/**
	 * An abstract interface for a set of spans
	 *
	 * <p>
	 * Connected spans in the set are automatically coalesced. For example, the set
	 * {@code [[0..5],[6..10]]} becomes {@code [[0..10]]}.
	 * 
	 * @implNote It is recommended to create an unparameterized interface extending this one
	 *           specific to your domain and span type, then implement it using an extension of
	 *           {@link DefaultSpanSet}. See {@link ULongSpanSet} for an example.
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 */
	public interface SpanSet<N, S extends Span<N, S>> {
		/**
		 * Check if this set has any spans
		 * 
		 * @return true if empty
		 */
		boolean isEmpty();

		/**
		 * Render this set as a string, using the given endpoint-to-string function
		 * 
		 * @param nToString the endpoint-to-string function
		 * @return the string
		 */
		String toString(Function<? super N, String> nToString);

		/**
		 * Iterate the spans in this set
		 * 
		 * @return the iterable
		 */
		NavigableSet<S> spans();

		/**
		 * Get a span which encloses all spans in the set
		 * 
		 * @return the bounding span
		 */
		S bound();

		/**
		 * Check if the set contains the given value
		 * 
		 * @param n the value
		 * @return true if contained by any span in the set
		 */
		boolean contains(N n);

		/**
		 * Get the span containing the given value
		 * 
		 * @param n the value
		 * @return the span or null
		 */
		S spanContaining(N n);

		/**
		 * Iterate over all spans in the set that intersect the given span
		 * 
		 * @param s the span
		 * @return the iterable of spans
		 */
		Iterable<S> intersecting(S s);

		/**
		 * Iterate over the spans which are absent from the set but enclosed by the given span
		 * 
		 * @param s the span
		 * @return the iterable of spans
		 */
		default Iterable<S> complement(S s) {
			Domain<N, S> dom = s.domain();
			N min = s.min();
			List<S> result = new ArrayList<>();
			for (S i : intersecting(s)) {
				if (dom.compare(i.min(), min) > 0) {
					result.add(dom.closed(min, dom.dec(i.min())));
				}
				if (!i.maxIsFinite()) {
					return result;
				}
				min = dom.inc(i.max());
			}
			if (dom.compare(min, s.max()) <= 0) {
				result.add(dom.closed(min, s.max()));
			}
			return result;
		}

		/**
		 * Check if any span in the set intersects the given span
		 * 
		 * @param s the span
		 * @return true if any span in the set intersects it
		 */
		boolean intersects(S s);

		/**
		 * Check if any span in the set encloses the given span
		 * 
		 * @param s the span
		 * @return true if any span in the set encloses it
		 */
		default boolean encloses(S s) {
			S c = spanContaining(s.min());
			if (c == null) {
				return false;
			}
			return c.contains(s.max());
		}
	}

	/**
	 * An abstract interface for a mutable {@link SpanSet}
	 *
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 */
	public interface MutableSpanSet<N, S extends Span<N, S>> extends SpanSet<N, S> {
		/**
		 * Add a span to the set
		 * 
		 * <p>
		 * Any connected spans will be coalesced.
		 * 
		 * @param s the span
		 */
		void add(S s);

		/**
		 * Add all spans from the given set into this one
		 * 
		 * <p>
		 * The spans from both maps amy be coalesced when entered into this one. (The given map
		 * remains unmodified.)
		 * 
		 * @param set the other set
		 */
		void addAll(SpanSet<N, S> set);

		/**
		 * Remove a span from the set
		 * 
		 * <p>
		 * Spans which intersect the given span are truncated. Spans which are enclosed are deleted,
		 * such that no value in the given span remains in the set.
		 * 
		 * @param s the span
		 */
		void remove(S s);

		/**
		 * Remove all spans from the set
		 */
		void clear();
	}

	/**
	 * A partial implementation of {@link RangeMapSetter} for {@link Span}s.
	 *
	 * @param <E> the type of entries in the {@link SpanMap} implementation
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 * @param <V> the type of values
	 */
	abstract class SpanMapSetter<E, N, S extends Span<N, S>, V>
			extends RangeMapSetter<E, N, S, V> {

		/**
		 * Get the domain of the spans
		 * 
		 * @return the domain
		 */
		protected abstract Domain<N, S> domain();

		@Override
		protected int compare(N d1, N d2) {
			return domain().compare(d1, d2);
		}

		@Override
		protected N getLower(S range) {
			return range.min();
		}

		@Override
		protected N getUpper(S range) {
			return range.max();
		}

		@Override
		protected S toSpan(N lower, N upper) {
			return domain().closed(lower, upper);
		}

		@Override
		protected N getPrevious(N d) {
			if (domain().min().equals(d)) {
				return null;
			}
			return domain().dec(d);
		}

		@Override
		protected N getNext(N d) {
			if (domain().max().equals(d)) {
				return null;
			}
			return domain().inc(d);
		}
	}

	/**
	 * The default implementation of {@link SpanMap} and {@link MutableSpanMap} using an interval
	 * tree
	 *
	 * <p>
	 * The interfaces can prevent accidental mutation of a map where it shouldn't be allowed;
	 * however, nothing prevents a client from casting to the mutable interface. If proper
	 * immutability is required, this will need to be wrapped or extended to prevent mutation.
	 *
	 * @implNote While this map is concrete and can be used as is for spans in the given domain, it
	 *           is recommended to create your own extension implementing an interface specific to
	 *           your span type and domain.
	 *
	 * @param <N> the type of endpoints
	 * @param <S> the type of spans
	 * @param <V> the type of values
	 */
	public class DefaultSpanMap<N, S extends Span<N, S>, V> implements MutableSpanMap<N, S, V> {
		/**
		 * The setter, which handles coalescing and truncating entries
		 */
		private class Setter extends SpanMapSetter<Entry<N, Entry<S, V>>, N, S, V> {
			private final Domain<N, S> domain;

			/**
			 * Create a setter for the given domain
			 * 
			 * @param domain the domain
			 */
			public Setter(Domain<N, S> domain) {
				this.domain = domain;
			}

			@Override
			protected Domain<N, S> domain() {
				return domain;
			}

			@Override
			protected S getRange(Entry<N, Entry<S, V>> entry) {
				return entry.getValue().getKey();
			}

			@Override
			protected V getValue(Entry<N, Entry<S, V>> entry) {
				return entry.getValue().getValue();
			}

			@Override
			protected void remove(Entry<N, Entry<S, V>> entry) {
				spanTree.remove(entry.getKey());
			}

			@Override
			protected Iterable<Entry<N, Entry<S, V>>> getIntersecting(N lower, N upper) {
				return subMap(lower, upper).entrySet();
			}

			@Override
			protected Entry<N, Entry<S, V>> put(S range, V value) {
				if (value != null) {
					spanTree.put(range.min(), Map.entry(range, value));
				}
				return null;
			}
		}

		private final Domain<N, S> domain;
		private final DefaultSpanMap<N, S, V>.Setter setter;
		private final NavigableMap<N, Entry<S, V>> spanTree;

		/**
		 * Create a span map on the given domain
		 * 
		 * <p>
		 * Extensions should invoke this as a super constructor with a fixed domain. See
		 * {@link DefaultULongSpanMap} for an example.
		 * 
		 * @param domain the domain
		 */
		public DefaultSpanMap(Domain<N, S> domain) {
			this.domain = domain;
			this.setter = new Setter(domain);
			this.spanTree = new TreeMap<>(domain::compare);
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (!(obj instanceof DefaultSpanMap that)) {
				return false;
			}
			if (this.domain != that.domain) {
				return false;
			}
			if (!Objects.equals(this.spanTree, that.spanTree)) {
				return false;
			}
			return true;
		}

		public String toString(Function<? super N, String> nToString) {
			return spanTree.values()
					.stream()
					.map(e -> domain.toString(e.getKey(), nToString) + '=' + e.getValue())
					.collect(Collectors.joining(",", "{", "}"));
		}

		@Override
		public String toString() {
			return toString(domain::toString);
		}

		@Override
		public boolean isEmpty() {
			return spanTree.isEmpty();
		}

		@Override
		public NavigableSet<S> spans() {
			// Make this a view?
			return spanTree.values()
					.stream()
					.map(e -> e.getKey())
					.collect(Collectors.toCollection(TreeSet::new));
		}

		@Override
		public S bound() {
			if (spanTree.isEmpty()) {
				return domain.empty();
			}
			S first = spanTree.firstEntry().getValue().getKey();
			S last = spanTree.lastEntry().getValue().getKey();
			return first.bound(last);
		}

		@Override
		public Collection<V> values() {
			return spanTree.values().stream().map(e -> e.getValue()).collect(Collectors.toSet());
		}

		@Override
		public Set<Entry<S, V>> entries() {
			return Set.copyOf(spanTree.values());
		}

		@Override
		public Entry<S, V> getEntry(N n) {
			Entry<N, Entry<S, V>> floor = spanTree.floorEntry(n);
			if (floor == null) {
				return null;
			}
			Entry<S, V> ent = floor.getValue();
			if (!ent.getKey().contains(n)) {
				return null;
			}
			return ent;
		}

		@Override
		public V get(N n) {
			Entry<S, V> ent = getEntry(n);
			return ent == null ? null : ent.getValue();
		}

		/**
		 * Get the portion of the interval tree whose entries intersect the given span
		 * 
		 * @param min the lower endpoint of the span
		 * @param max the upper endpoint of the span
		 * @return the sub map
		 */
		protected NavigableMap<N, Entry<S, V>> subMap(N min, N max) {
			Entry<N, Entry<S, V>> adjEnt = spanTree.floorEntry(min);
			if (adjEnt != null && adjEnt.getValue().getKey().contains(min)) {
				min = adjEnt.getKey();
			}
			return spanTree.subMap(min, true, max, true);
		}

		@Override
		public Collection<Entry<S, V>> intersectingEntries(S s) {
			return subMap(s.min(), s.max()).values();
		}

		@Override
		public Iterable<S> intersectingSpans(S s) {
			return intersectingEntries(s).stream()
					.map(e -> e.getKey())
					.collect(Collectors.toList());
		}

		@Override
		public boolean intersects(S s) {
			Entry<N, Entry<S, V>> entry = spanTree.floorEntry(s.max());
			return entry != null && entry.getValue().getKey().intersects(s);
		}

		@Override
		public void put(S s, V v) {
			if (s.isEmpty()) {
				return;
			}
			setter.set(s, v);
		}

		@Override
		public void putAll(SpanMap<N, S, V> map) {
			for (Entry<S, V> entry : map.entries()) {
				put(entry.getKey(), entry.getValue());
			}
		}

		@Override
		public void remove(S s) {
			setter.set(s, null);
		}

		@Override
		public void clear() {
			spanTree.clear();
		}
	}

	/**
	 * The default implementation of {@link SpanSet} and {@link MutableSpanSet} using an interval
	 * tree
	 * 
	 * @param <N> the type of endpoints
	 * @param <S> the type of values
	 */
	public class DefaultSpanSet<N, S extends Span<N, S>> implements MutableSpanSet<N, S> {
		private final MutableSpanMap<N, S, Boolean> map;
		private final Domain<N, S> domain;

		/**
		 * Create a span set on the given domain
		 * 
		 * <p>
		 * Extensions should invoke this as a super constructor with a fixed domain. See
		 * {@link DefaultULongSpanSet} for an example.
		 * 
		 * @param domain the domain
		 */
		public DefaultSpanSet(Domain<N, S> domain) {
			this.map = newSpanMap(domain);
			this.domain = domain;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (!(obj instanceof DefaultSpanSet that)) {
				return false;
			}
			if (!Objects.equals(this.map, that.map)) {
				return false;
			}
			return true;
		}

		@Override
		public String toString(Function<? super N, String> nToString) {
			return map.spans()
					.stream()
					.map(s -> domain.toString(s, nToString))
					.collect(Collectors.joining(",", "[", "]"));
		}

		@Override
		public String toString() {
			return toString(domain::toString);
		}

		/**
		 * Factory method for the span map backing this span set
		 * 
		 * @param domain the domain
		 * @return the map
		 */
		protected MutableSpanMap<N, S, Boolean> newSpanMap(Domain<N, S> domain) {
			return new DefaultSpanMap<>(domain);
		}

		@Override
		public boolean isEmpty() {
			return map.isEmpty();
		}

		@Override
		public NavigableSet<S> spans() {
			return map.spans();
		}

		@Override
		public S bound() {
			return map.bound();
		}

		@Override
		public boolean contains(N n) {
			return Boolean.TRUE.equals(map.get(n));
		}

		@Override
		public S spanContaining(N n) {
			Entry<S, Boolean> entry = map.getEntry(n);
			return entry == null ? null : entry.getKey();
		}

		@Override
		public Iterable<S> intersecting(S s) {
			return map.intersectingSpans(s);
		}

		@Override
		public boolean intersects(S s) {
			return map.intersects(s);
		}

		@Override
		public void add(S s) {
			map.put(s, true);
		}

		@Override
		public void addAll(SpanSet<N, S> set) {
			// TODO: May not be the most efficient. A linear merge algorithm may do better....
			for (S s : set.spans()) {
				add(s);
			}
		}

		@Override
		public void remove(S s) {
			map.remove(s);
		}

		@Override
		public void clear() {
			map.clear();
		}
	}

	/**
	 * Provides a default {@link Object#toString} implementation
	 * 
	 * @param nToString the endpoint-to-string function
	 * @return the string
	 */
	@SuppressWarnings("unchecked")
	default String toString(Function<? super N, String> nToString) {
		return domain().toString((S) this, nToString);
	}

	/**
	 * Get the domain of this span's endpoints
	 * 
	 * @implNote a span implementation should probably return a fixed singleton instance for its
	 *           domain.
	 * @return the domain
	 */
	Domain<N, S> domain();

	/**
	 * Get the lower enpdoint
	 * 
	 * @return the lower endpoint
	 * @throws NoSuchElementException if the span is empty
	 * @see #isEmpty()
	 */
	N min();

	/**
	 * Get the upper endpoint
	 * 
	 * @return the upper endpoint
	 * @throws NoSuchElementException if the span is empty
	 * @see #isEmpty()
	 */
	N max();

	/**
	 * Check if the lower endpoint excludes the domain minimum
	 * 
	 * @return true if min is not the domain min
	 */
	default boolean minIsFinite() {
		return !min().equals(domain().min());
	}

	/**
	 * Check if the upper endpoint excludes the domain maximum
	 * 
	 * @return true if max is not the domain max
	 */
	default boolean maxIsFinite() {
		return !max().equals(domain().max());
	}

	/**
	 * Check if this span is empty
	 * 
	 * @return true if empty
	 */
	default boolean isEmpty() {
		return false;
	}

	/**
	 * Check if this span contains the given value
	 * 
	 * @param n the value
	 * @return true if n is contained in this span
	 */
	default boolean contains(N n) {
		return domain().compare(min(), n) <= 0 && domain().compare(n, max()) <= 0;
	}

	/**
	 * Compute the intersection of this span and another
	 * 
	 * @param s another span
	 * @return the intersection, possibly empty
	 * @see Domain#intersect(Span, Span)
	 */
	@SuppressWarnings("unchecked")
	default S intersect(S s) {
		return domain().intersect((S) this, s);
	}

	/**
	 * Check if this span intersects a given span
	 * 
	 * @param s another span
	 * @return true if they intersect
	 * @see Domain#intersects(Span, Span)
	 */
	@SuppressWarnings("unchecked")
	default boolean intersects(S s) {
		return domain().intersects((S) this, s);
	}

	/**
	 * Check if this span encloses a given span
	 * 
	 * @param s another span
	 * @return true if this encloses the given span
	 */
	@SuppressWarnings("unchecked")
	default boolean encloses(S s) {
		return domain().encloses((S) this, s);
	}

	/**
	 * Compute the bound of this span and another
	 * 
	 * @param s another span
	 * @return the bound
	 * @see Domain#bound(Span, Span)
	 */
	@SuppressWarnings("unchecked")
	default S bound(S s) {
		return domain().bound((S) this, s);
	}

	/**
	 * Subtract a span from this span
	 * 
	 * @param s the span to subtract
	 * @return 0, 1, or 2 spans resulting from the subtraction
	 */
	@SuppressWarnings("unchecked")
	default List<S> subtract(S s) {
		return domain().subtract((S) this, s);
	}

	@Override
	default int compareTo(S that) {
		if (this.isEmpty()) {
			if (that.isEmpty()) {
				return 0;
			}
			return -1;
		}
		if (that.isEmpty()) {
			return 1;
		}
		int result;
		result = domain().compare(this.min(), that.min());
		if (result != 0) {
			return result;
		}
		result = domain().compare(this.max(), that.max());
		if (result != 0) {
			return result;
		}
		return 0;
	}
}