func initLookupCell(level, i, j, origOrientation, pos, orientation int) {
	if level == lookupBits {
		ij := (i << lookupBits) + j
		lookupPos[(ij<<2)+origOrientation] = (pos << 2) + orientation
		lookupIJ[(pos<<2)+origOrientation] = (ij << 2) + orientation
		return
	}
	level++
	i <<= 1
	j <<= 1
	pos <<= 2
	r := posToIJ[orientation]
	initLookupCell(level, i+(r[0]>>1), j+(r[0]&1), origOrientation, pos, orientation^posToOrientation[0])
	initLookupCell(level, i+(r[1]>>1), j+(r[1]&1), origOrientation, pos+1, orientation^posToOrientation[1])
	initLookupCell(level, i+(r[2]>>1), j+(r[2]&1), origOrientation, pos+2, orientation^posToOrientation[2])
	initLookupCell(level, i+(r[3]>>1), j+(r[3]&1), origOrientation, pos+3, orientation^posToOrientation[3])
}
initLookupCell initializes the lookupIJ table at init time.
package s2
import (
	"bytes"
	"fmt"
	"io"
	"math"
	"sort"
	"strconv"
	"strings"
	"github.com/golang/geo/r1"
	"github.com/golang/geo/r2"
	"github.com/golang/geo/r3"
	"github.com/golang/geo/s1"
)
type CellID uint64
const SentinelCellID = CellID(^uint64(0))
func sortCellIDs(ci []CellID) {
	sort.Sort(cellIDs(ci))
}
type cellIDs []CellID
func (c cellIDs) Len() int           { return len(c) }
func (c cellIDs) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
func (c cellIDs) Less(i, j int) bool { return c[i] < c[j] }
const (
	faceBits = 3
	numFaces = 6
	maxLevel = 30
	posBits = 2*maxLevel + 1
	maxSize = 1 << maxLevel
	wrapOffset = uint64(numFaces) << posBits
)
func CellIDFromFacePosLevel(face int, pos uint64, level int) CellID {
	return CellID(uint64(face)<<posBits + pos | 1).Parent(level)
}
func CellIDFromFace(face int) CellID {
	return CellID((uint64(face) << posBits) + lsbForLevel(0))
}
func CellIDFromLatLng(ll LatLng) CellID {
	return cellIDFromPoint(PointFromLatLng(ll))
}
func CellIDFromToken(s string) CellID {
	if len(s) > 16 {
		return CellID(0)
	}
	n, err := strconv.ParseUint(s, 16, 64)
	if err != nil {
		return CellID(0)
	}
	if len(s) < 16 {
		n = n << (4 * uint(16-len(s)))
	}
	return CellID(n)
}
func (ci CellID) ToToken() string {
	s := strings.TrimRight(fmt.Sprintf("%016x", uint64(ci)), "0")
	if len(s) == 0 {
		return "X"
	}
	return s
}
func (ci CellID) IsValid() bool {
	return ci.Face() < numFaces && (ci.lsb()&0x1555555555555555 != 0)
}
func (ci CellID) Face() int { return int(uint64(ci) >> posBits) }
func (ci CellID) Pos() uint64 { return uint64(ci) & (^uint64(0) >> faceBits) }
func (ci CellID) Level() int {
	return maxLevel - findLSBSetNonZero64(uint64(ci))>>1
}
func (ci CellID) IsLeaf() bool { return uint64(ci)&1 != 0 }
func (ci CellID) ChildPosition(level int) int {
	return int(uint64(ci)>>uint64(2*(maxLevel-level)+1)) & 3
}
func lsbForLevel(level int) uint64 { return 1 << uint64(2*(maxLevel-level)) }
func (ci CellID) Parent(level int) CellID {
	lsb := lsbForLevel(level)
	return CellID((uint64(ci) & -lsb) | lsb)
}
func (ci CellID) immediateParent() CellID {
	nlsb := CellID(ci.lsb() << 2)
	return (ci & -nlsb) | nlsb
}
func (ci CellID) isFace() bool { return uint64(ci)&(lsbForLevel(0)-1) == 0 }
func (ci CellID) lsb() uint64 { return uint64(ci) & -uint64(ci) }
func (ci CellID) Children() [4]CellID {
	var ch [4]CellID
	lsb := CellID(ci.lsb())
	ch[0] = ci - lsb + lsb>>2
	lsb >>= 1
	ch[1] = ch[0] + lsb
	ch[2] = ch[1] + lsb
	ch[3] = ch[2] + lsb
	return ch
}
func sizeIJ(level int) int {
	return 1 << uint(maxLevel-level)
}
func (ci CellID) EdgeNeighbors() [4]CellID {
	level := ci.Level()
	size := sizeIJ(level)
	f, i, j, _ := ci.faceIJOrientation()
	return [4]CellID{
		cellIDFromFaceIJWrap(f, i, j-size).Parent(level),
		cellIDFromFaceIJWrap(f, i+size, j).Parent(level),
		cellIDFromFaceIJWrap(f, i, j+size).Parent(level),
		cellIDFromFaceIJWrap(f, i-size, j).Parent(level),
	}
}
func (ci CellID) VertexNeighbors(level int) []CellID {
	halfSize := sizeIJ(level + 1)
	size := halfSize << 1
	f, i, j, _ := ci.faceIJOrientation()
	var isame, jsame bool
	var ioffset, joffset int
	if i&halfSize != 0 {
		ioffset = size
		isame = (i + size) < maxSize
	} else {
		ioffset = -size
		isame = (i - size) >= 0
	}
	if j&halfSize != 0 {
		joffset = size
		jsame = (j + size) < maxSize
	} else {
		joffset = -size
		jsame = (j - size) >= 0
	}
	results := []CellID{
		ci.Parent(level),
		cellIDFromFaceIJSame(f, i+ioffset, j, isame).Parent(level),
		cellIDFromFaceIJSame(f, i, j+joffset, jsame).Parent(level),
	}
	if isame || jsame {
		results = append(results, cellIDFromFaceIJSame(f, i+ioffset, j+joffset, isame && jsame).Parent(level))
	}
	return results
}
func (ci CellID) AllNeighbors(level int) []CellID {
	var neighbors []CellID
	face, i, j, _ := ci.faceIJOrientation()
	size := sizeIJ(ci.Level())
	i &= -size
	j &= -size
	nbrSize := sizeIJ(level)
	for k := -nbrSize; ; k += nbrSize {
		var sameFace bool
		if k < 0 {
			sameFace = (j+k >= 0)
		} else if k >= size {
			sameFace = (j+k < maxSize)
		} else {
			sameFace = true
			neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+k, j-nbrSize,
				j-size >= 0).Parent(level))
			neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+k, j+size,
				j+size < maxSize).Parent(level))
		}
		neighbors = append(neighbors, cellIDFromFaceIJSame(face, i-nbrSize, j+k,
			sameFace && i-size >= 0).Parent(level))
		neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+size, j+k,
			sameFace && i+size < maxSize).Parent(level))
		if k >= size {
			break
		}
	}
	return neighbors
}
func (ci CellID) RangeMin() CellID { return CellID(uint64(ci) - (ci.lsb() - 1)) }
func (ci CellID) RangeMax() CellID { return CellID(uint64(ci) + (ci.lsb() - 1)) }
func (ci CellID) Contains(oci CellID) bool {
	return uint64(ci.RangeMin()) <= uint64(oci) && uint64(oci) <= uint64(ci.RangeMax())
}
func (ci CellID) Intersects(oci CellID) bool {
	return uint64(oci.RangeMin()) <= uint64(ci.RangeMax()) && uint64(oci.RangeMax()) >= uint64(ci.RangeMin())
}
func (ci CellID) String() string {
	if !ci.IsValid() {
		return "Invalid: " + strconv.FormatInt(int64(ci), 16)
	}
	var b bytes.Buffer
	b.WriteByte("012345"[ci.Face()])  
	b.WriteByte('/')
	for level := 1; level <= ci.Level(); level++ {
		b.WriteByte("0123"[ci.ChildPosition(level)])
	}
	return b.String()
}
func cellIDFromString(s string) CellID {
	level := len(s) - 2
	if level < 0 || level > maxLevel {
		return CellID(0)
	}
	face := int(s[0] - '0')
	if face < 0 || face > 5 || s[1] != '/' {
		return CellID(0)
	}
	id := CellIDFromFace(face)
	for i := 2; i < len(s); i++ {
		childPos := s[i] - '0'
		if childPos < 0 || childPos > 3 {
			return CellID(0)
		}
		id = id.Children()[childPos]
	}
	return id
}
func (ci CellID) Point() Point { return Point{ci.rawPoint().Normalize()} }
func (ci CellID) LatLng() LatLng { return LatLngFromPoint(Point{ci.rawPoint()}) }
func (ci CellID) ChildBegin() CellID {
	ol := ci.lsb()
	return CellID(uint64(ci) - ol + ol>>2)
}
func (ci CellID) ChildBeginAtLevel(level int) CellID {
	return CellID(uint64(ci) - ci.lsb() + lsbForLevel(level))
}
func (ci CellID) ChildEnd() CellID {
	ol := ci.lsb()
	return CellID(uint64(ci) + ol + ol>>2)
}
func (ci CellID) ChildEndAtLevel(level int) CellID {
	return CellID(uint64(ci) + ci.lsb() + lsbForLevel(level))
}
func (ci CellID) Next() CellID {
	return CellID(uint64(ci) + ci.lsb()<<1)
}
func (ci CellID) Prev() CellID {
	return CellID(uint64(ci) - ci.lsb()<<1)
}
func (ci CellID) NextWrap() CellID {
	n := ci.Next()
	if uint64(n) < wrapOffset {
		return n
	}
	return CellID(uint64(n) - wrapOffset)
}
func (ci CellID) PrevWrap() CellID {
	p := ci.Prev()
	if uint64(p) < wrapOffset {
		return p
	}
	return CellID(uint64(p) + wrapOffset)
}
func (ci CellID) AdvanceWrap(steps int64) CellID {
	if steps == 0 {
		return ci
	}
	shift := uint(2*(maxLevel-ci.Level()) + 1)
	if steps < 0 {
		if min := -int64(uint64(ci) >> shift); steps < min {
			wrap := int64(wrapOffset >> shift)
			steps %= wrap
			if steps < min {
				steps += wrap
			}
		}
	} else {
		if max := int64((wrapOffset - uint64(ci)) >> shift); steps > max {
			wrap := int64(wrapOffset >> shift)
			steps %= wrap
			if steps > max {
				steps -= wrap
			}
		}
	}
	return CellID(uint64(ci) + (uint64(steps) << shift))
}
func (ci CellID) Encode(w io.Writer) error {
	e := &encoder{w: w}
	ci.encode(e)
	return e.err
}
func (ci CellID) encode(e *encoder) {
	e.writeUint64(uint64(ci))
}
func (ci *CellID) Decode(r io.Reader) error {
	d := &decoder{r: asByteReader(r)}
	ci.decode(d)
	return d.err
}
func (ci *CellID) decode(d *decoder) {
	*ci = CellID(d.readUint64())
}
func (ci CellID) distanceFromBegin() int64 {
	return int64(ci >> uint64(2*(maxLevel-ci.Level())+1))
}
func (ci CellID) rawPoint() r3.Vector {
	face, si, ti := ci.faceSiTi()
	return faceUVToXYZ(face, stToUV((0.5/maxSize)*float64(si)), stToUV((0.5/maxSize)*float64(ti)))
}
func (ci CellID) faceSiTi() (face int, si, ti uint32) {
	face, i, j, _ := ci.faceIJOrientation()
	delta := 0
	if ci.IsLeaf() {
		delta = 1
	} else {
		if (i^(int(ci)>>2))&1 != 0 {
			delta = 2
		}
	}
	return face, uint32(2*i + delta), uint32(2*j + delta)
}
func (ci CellID) faceIJOrientation() (f, i, j, orientation int) {
	f = ci.Face()
	orientation = f & swapMask
	nbits := maxLevel - 7*lookupBits  
	for k := 7; k >= 0; k-- {
		orientation += (int(uint64(ci)>>uint64(k*2*lookupBits+1)) & ((1 << uint(2*nbits)) - 1)) << 2
		orientation = lookupIJ[orientation]
		i += (orientation >> (lookupBits + 2)) << uint(k*lookupBits)
		j += ((orientation >> 2) & ((1 << lookupBits) - 1)) << uint(k*lookupBits)
		orientation &= (swapMask | invertMask)
		nbits = lookupBits  
	}
	if ci.lsb()&0x1111111111111110 != 0 {
		orientation ^= swapMask
	}
	return
}
func cellIDFromFaceIJ(f, i, j int) CellID {
	n := uint64(f) << (posBits - 1)
	bits := f & swapMask
	for k := 7; k >= 0; k-- {
		mask := (1 << lookupBits) - 1
		bits += ((i >> uint(k*lookupBits)) & mask) << (lookupBits + 2)
		bits += ((j >> uint(k*lookupBits)) & mask) << 2
		bits = lookupPos[bits]
		n |= uint64(bits>>2) << (uint(k) * 2 * lookupBits)
		bits &= (swapMask | invertMask)
	}
	return CellID(n*2 + 1)
}
func cellIDFromFaceIJWrap(f, i, j int) CellID {
	i = clampInt(i, -1, maxSize)
	j = clampInt(j, -1, maxSize)
	const scale = 1.0 / maxSize
	limit := math.Nextafter(1, 2)
	u := math.Max(-limit, math.Min(limit, scale*float64((i<<1)+1-maxSize)))
	v := math.Max(-limit, math.Min(limit, scale*float64((j<<1)+1-maxSize)))
	f, u, v = xyzToFaceUV(faceUVToXYZ(f, u, v))
	return cellIDFromFaceIJ(f, stToIJ(0.5*(u+1)), stToIJ(0.5*(v+1)))
}
func cellIDFromFaceIJSame(f, i, j int, sameFace bool) CellID {
	if sameFace {
		return cellIDFromFaceIJ(f, i, j)
	}
	return cellIDFromFaceIJWrap(f, i, j)
}
func ijToSTMin(i int) float64 {
	return float64(i) / float64(maxSize)
}
func stToIJ(s float64) int {
	return clampInt(int(math.Floor(maxSize*s)), 0, maxSize-1)
}
func cellIDFromPoint(p Point) CellID {
	f, u, v := xyzToFaceUV(r3.Vector{p.X, p.Y, p.Z})
	i := stToIJ(uvToST(u))
	j := stToIJ(uvToST(v))
	return cellIDFromFaceIJ(f, i, j)
}
func ijLevelToBoundUV(i, j, level int) r2.Rect {
	cellSize := sizeIJ(level)
	xLo := i & -cellSize
	yLo := j & -cellSize
	return r2.Rect{
		X: r1.Interval{
			Lo: stToUV(ijToSTMin(xLo)),
			Hi: stToUV(ijToSTMin(xLo + cellSize)),
		},
		Y: r1.Interval{
			Lo: stToUV(ijToSTMin(yLo)),
			Hi: stToUV(ijToSTMin(yLo + cellSize)),
		},
	}
}
const (
	lookupBits = 4
	swapMask   = 0x01
	invertMask = 0x02
)
var (
	ijToPos = [4][4]int{
		{0, 1, 3, 2},  
		{0, 3, 1, 2},  
		{2, 3, 1, 0},  
		{2, 1, 3, 0},  
	}
	posToIJ = [4][4]int{
		{0, 1, 3, 2},  
		{0, 2, 3, 1},  
		{3, 2, 0, 1},  
		{3, 1, 0, 2},  
	}
	posToOrientation = [4]int{swapMask, 0, 0, invertMask | swapMask}
	lookupIJ         [1 << (2*lookupBits + 2)]int
	lookupPos        [1 << (2*lookupBits + 2)]int
)
func init() {
	initLookupCell(0, 0, 0, 0, 0, 0)
	initLookupCell(0, 0, 0, swapMask, 0, swapMask)
	initLookupCell(0, 0, 0, invertMask, 0, invertMask)
	initLookupCell(0, 0, 0, swapMask|invertMask, 0, swapMask|invertMask)
}