// Walk down the free list calling f() on the in-range portions, until
// f() returns true or we run out of free space.  Return true iff f() returned true
func (s *Space) walkFree(r address.Range, f func(address.Range) bool) bool {
	if r.Start >= r.End { // degenerate case
		return false
	}
	for i := 0; i < len(s.free); i += 2 {
		chunk := address.Range{Start: s.free[i], End: s.free[i+1]}
		if chunk.End <= r.Start { // this chunk comes before the range
			continue
		}
		if chunk.Start >= r.End {
			// all remaining free space is completely after range
			break
		}
		// at this point we know chunk.End>chunk.Start &&
		// chunk.End>r.Start && r.End>chunk.Start && r.End>r.Start
		// therefore max(start, r.Start) < min(end, r.End)
		// Restrict this block of free space to be in range
		if chunk.Start < r.Start {
			chunk.Start = r.Start
		}
		if chunk.End > r.End {
			chunk.End = r.End
		}
		// at this point we know start<end
		if f(chunk) {
			return true
		}
	}
	return false
}

func (alloc *Allocator) ownedInRange(ident string, r address.Range) (address.Address, bool) {
	for _, addr := range alloc.owned[ident] {
		if r.Contains(addr) {
			return addr, true
		}
	}
	return 0, false
}

func (alloc *Allocator) ownedInRange(ident string, r address.Range) []address.CIDR {
	var c []address.CIDR
	for _, cidr := range alloc.owned[ident].Cidrs {
		if r.Contains(cidr.Addr) {
			c = append(c, cidr)
		}
	}
	return c
}

func (alloc *Allocator) spaceRequestDenied(sender mesh.PeerName, r address.Range) {
	for i := 0; i < len(alloc.pendingClaims); {
		claim := alloc.pendingClaims[i].(*claim)
		if r.Contains(claim.addr) {
			claim.deniedBy(alloc, sender)
			alloc.pendingClaims = append(alloc.pendingClaims[:i], alloc.pendingClaims[i+1:]...)
			continue
		}
		i++
	}
}

// NewAllocator creates and initialises a new Allocator
func NewAllocator(ourName router.PeerName, ourUID router.PeerUID, ourNickname string, universe address.Range, quorum uint) *Allocator {
	return &Allocator{
		ourName:   ourName,
		universe:  universe,
		ring:      ring.New(universe.Start, address.Add(universe.Start, universe.Size()), ourName),
		owned:     make(map[string][]address.Address),
		paxos:     paxos.NewNode(ourName, ourUID, quorum),
		nicknames: map[router.PeerName]string{ourName: ourNickname},
		now:       time.Now,
	}
}