An abstract data type (ADT) describes what values are legal, which operations are available, and what those operations do—before choosing how to store the data. The practical question is: what should callers be able to ask for, without knowing how the answer is produced? section 2.2
Design an ADT from the outside in:
- List the operations callers need, including queries such as IsEmpty and ways to enumerate values. section 2.2 section 3.1
- Specify behavior and constraints. An immutable Push returns a new stack or deque; peeking or popping an empty stack is invalid. For a deque, operations at either end should remain cheap as it grows. section 2.2 section 3.1
- Express the contract as an interface, then choose a data structure and examine its performance. The interface need not dictate whether an implementation uses a separate class or some particular storage layout. section 2.2
One contract, different design pressures
An immutable stack needs Push, Peek, Pop, IsEmpty, and enumeration. A deque adds operations at both ends and chooses left-to-right enumeration. A mutable Life engine instead needs Clear, cell access, and Step(speed). The ADT follows the problem; immutability is not a requirement of the term. section 2.2 section 3.1 section 4.2
Why hide the storage?
A word-list ADT supports enumeration, membership tests, and prefix searches; it does not require callers to know which search structure holds the words. Likewise, an undirected graph should expose nodes and edges rather than dictionary keys and values. Its wrapper can enforce graph rules while leaving room to replace its multidictionary with an adjacency matrix without rewriting callers. section 5.1 section 8.3
Listing 8.2 An immutable undirected graph wrapping a multidictionary
readonly struct ImGraph<N> where N : notnull
{
public static ImGraph<N> Empty = new(ImMulti<N, N>.Empty);
private readonly ImMulti<N, N> nodes;
private ImGraph(ImMulti<N, N> ns) => this.nodes = ns;
public bool IsEmpty => nodes.IsEmpty;
public bool HasNode(N n) => nodes.ContainsKey(n);
public bool HasEdge(N n1, N n2) => nodes.HasValue(n1, n2);
public IEnumerable<N> Nodes => nodes.Keys;
public ImmutableHashSet<N> Edges(N n) => nodes[n];
public ImGraph<N> AddNode(N n) =>
HasNode(n) ?
this :
new(nodes.SetItem(n, ImmutableHashSet<N>.Empty));
public ImGraph<N> AddEdge(N n1, N n2) =>
new(nodes.Add(n1, n2).Add(n2, n1));
public ImGraph<N> RemoveEdge(N n1, N n2) =>
new(nodes.Remove(n1, n2).Remove(n2, n1));
public ImGraph<N> RemoveNode(N n)
{
var result = this;
foreach (var n2 in Edges(n))
result = result.RemoveEdge(n, n2);
return new(result.nodes.Remove(n));
}
public ImGraph<N> AddEdges(N n1, IEnumerable<N> ns)
{
var result = this;
foreach (var n2 in ns)
result = result.AddEdge(n1, n2);
return result;
}
public ImGraph<N> AddClique(IList<N> ns)
{
var result = this;
for(int i = 0; i < ns.Count; i += 1)
for(int j = i + 1 ; j < ns.Count; j += 1)
result = result.AddEdge(ns[i], ns[j]);
return result;
}
}
The graph implementation makes the distinction visible: its public members speak in nodes and edges, while a private multidictionary supplies the storage. section 8.3
