netaddr/v2/netaddr_setoid.go

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

package netaddr

import (
	"fmt"
	"sort"
	"strings"
)

func insert(s []*NetAddr, i int, e *NetAddr) []*NetAddr {
	i = clamp(i, 0, len(s))
	s = append(s, e)
	copy(s[i+1:], s[i:])
	s[i] = e
	return s
}

func remove(s []*NetAddr, i int) []*NetAddr {
	i = clamp(i, 0, len(s)-1)
	copy(s[i:], s[i+1:])
	return s[:len(s)-1]
}

/*
Create a new NetAddrSetoid.

Pass an empty slice to create an empty setoid.
*/
func NewNetAddrSetoid(ps []*NetAddr) *NetAddrSetoid {
	set := &NetAddrSetoid{make([]*NetAddr, 0, len(ps))}
	for _, p := range ps {
		set = set.Insert(p)
	}
	return set
}

/*
NetAddrSetoid is a dynamic collection of NetAddrs.

It is often advantageous to describe a set of addresses
using the fewest prefixes possible. In essence, this is the
smallest bitwise partition on the set. There is a sense in
which this partition acts as a witness for an equivalence
relation on the underlying set of addresses, and this set,
together with said equivalence relation, is called a setoid.

As addresses are added to and deleted from NetAddrSetoid,
the implementation maintains a minimal set of prefixes. This
effectively amortizes the work of efficiently extracting
such a partition, post hoc.
*/
type NetAddrSetoid struct {
	elems []*NetAddr
}

/* Clone returns a new (deep) copy of NetAddrSetoid. */
func (s *NetAddrSetoid) Clone() *NetAddrSetoid {
	next := &NetAddrSetoid{make([]*NetAddr, len(s.elems))}
	for i, e := range s.elems {
		next.elems[i] = e.Clone()
	}
	return next
}

func (s *NetAddrSetoid) getIndex(
	na *NetAddr,
	equiv func(*NetAddr, *NetAddr) bool,
) int {
	return sort.Search(len(s.elems), func(i int) bool {
		ei := s.elems[i]
		return !LessThan(ei, na) || equiv(ei, na)
	})
}

func (s *NetAddrSetoid) findEquivalent(
	na *NetAddr,
	equiv func(*NetAddr, *NetAddr) bool,
) (found *NetAddr, err error) {
	i := s.getIndex(na, equiv)
	if i == len(s.elems) {
		err = fmt.Errorf("netaddr setoid: find equivalent: none found")
		return
	}
	ei := s.elems[i]
	if equiv(ei, na) {
		found = ei
		return
	}
	err = fmt.Errorf("netaddr setoid: find equivalent: none found")
	return
}

/*
Blocks returns a slice of NetAddrs representing the minimum
set of prefixes that contains the underlying set of
addresses. This is just the quotient set of the setoid.

The returned slice is the result of a deep copy.
*/
func (s *NetAddrSetoid) Blocks() []*NetAddr {
	c := s.Clone()
	return c.elems
}

/*
Cardinality returns the number of prefixes (blocks) in the
setoid's quotient set.
*/
func (s *NetAddrSetoid) Cardinality() int {
	return len(s.elems)
}

/*
String returns a string representation of the prefixes
(blocks) in the setoid's quotient set.
*/
func (s *NetAddrSetoid) String() string {
	var b strings.Builder
	b.WriteString("{")
	for _, e := range s.elems {
		fmt.Fprintf(&b, "%s,", e.String())
	}
	return strings.TrimSuffix(b.String(), ",") + "}"
}

/*
Insert adds the set of addresses represented by na to
the setoid.
*/
func (s *NetAddrSetoid) Insert(
	na *NetAddr,
) *NetAddrSetoid {
	/* na may be one of

	* disjoint, left contiguous
	* disjoint, right contiguous
	* subset
	* proper superset
	* disjoint, discontiguous

	but na will never be a cover of two, four, etc.
	contiguous prefixes, as these will already have been
	coalesced into a single prefix.
	*/
	idx := s.getIndex(na, NetAddrContains)
	if idx == len(s.elems) { // disjoint
		s.elems = append(s.elems, na.FirstAddress())
	}
	for {
		cur := s.elems[idx]
		if 0 <= idx-1 {
			left := s.elems[idx-1]
			if Contiguous(left, cur) &&
				LeftAdjacent(left, cur) { // left contiguous
				s.elems[idx-1] =
					left.
						SetLength(left.Length() - 1).
						FirstAddress()
				s.elems = remove(s.elems, idx)
				idx-- // cur is gone: cur <- left
				continue
			}
		}
		if idx+1 < len(s.elems) {
			right := s.elems[idx+1]
			if Contiguous(cur, right) &&
				LeftAdjacent(cur, right) { // right contiguous
				s.elems[idx] =
					cur.
						SetLength(cur.Length() - 1).
						FirstAddress()
				s.elems = remove(s.elems, idx+1)
				// cur is unchanged: cur <- cur
				continue
			}
		}
		if NetAddrContains(cur, na) { // subset
			return s
		}
		// Since the above `contains` was false, na < e[i].
		// But then e[i-1] <~ na; check whether ~ or <.
		if 0 <= idx-1 {
			left := s.elems[idx-1]
			if NetAddrContains(na, left) { // proper superset
				s.elems = remove(s.elems, idx-1)
				idx-- // cur has moved: cur <- cur
				continue
			}
		}
		// disjoint, discontiguous
		s.elems = insert(s.elems, idx, na)
	}
}

/*
Delete removes the set of addresses represented by na
from the setoid.
*/
func (s *NetAddrSetoid) Delete(
	na *NetAddr,
) *NetAddrSetoid {
	idx := s.getIndex(na, NetAddrContains)
	if idx == len(s.elems) {
		return s
	}
	for na.Contains(s.elems[idx]) {
		s.elems = remove(s.elems, idx)
	}
	next := s.elems[idx]
	for next.Contains(na) {
		l, r := Split(next)
		if l.IsEqual(na) {
			s.elems[idx] = r
			return s
		}
		s.elems[idx] = l
		if r.IsEqual(na) {
			return s
		}
		s.elems = insert(s.elems, idx+1, r)
		switch {
		case l.Contains(na):
			next = l
		case r.Contains(na):
			next = r
			idx++
		}
	}
	return s
}

/*
FindSuperset returns a prefix wholly containing the given
NetAddr.  If none can be found, an error is provided.
*/
func (s *NetAddrSetoid) FindSuperset(
	na *NetAddr,
) (*NetAddr, error) {
	return s.findEquivalent(na, NetAddrContains)
}

/*
Includes returns true when the setoid contains all of the
given NetAddr.
*/
func (s *NetAddrSetoid) Includes(na *NetAddr) bool {
	_, err := s.FindSuperset(na)
	return err != nil
}

/*
FindOverlapping returns the largest (shortest) prefix that
contains, or is contained by, the given NetAddr.
*/
func (s *NetAddrSetoid) FindOverlapping(
	na *NetAddr,
) (*NetAddr, error) {
	return s.findEquivalent(na, NetAddrOverlaps)
}

/*
Overlaps returns true when the setoid and the given NetAddr
have addresses in common.
*/
func (s *NetAddrSetoid) Overlaps(na *NetAddr) bool {
	_, err := s.FindOverlapping(na)
	return err != nil
}

/*
IsEqual returns true if both setoids contain precisely the
same addresses.
*/
func (s1 *NetAddrSetoid) IsEqual(
	s2 *NetAddrSetoid,
) bool {
	if s1.Cardinality() != s2.Cardinality() {
		return false
	}
	for i := 0; i < len(s1.elems); i++ {
		if !NetAddrIsEqual(s1.elems[i], s2.elems[i]) {
			return false
		}
	}
	return true
}

/*
Union returns the set union of both setoids' underlying
sets.

The resulting setoid is a deep copy.
*/
func Union(s1, s2 *NetAddrSetoid) *NetAddrSetoid {
	next := s1.Clone()
	for _, e := range s2.elems {
		next.Insert(e)
	}
	return next
}

/*
RelComp returns a setoid whose underlying set is the set
difference s1 - s2.

The resulting setoid is a deep copy.
*/
func RelComp(s1, s2 *NetAddrSetoid) *NetAddrSetoid {
	next := s1.Clone()
	for _, e := range s2.elems {
		next.Delete(e)
	}
	return next
}