func (ci CellID) Next() CellID {
	return CellID(uint64(ci) + ci.lsb()<<1)
}
Next returns the next cell along the Hilbert curve.
This is expected to be used with ChildBegin and ChildEnd,
or ChildBeginAtLevel and ChildEndAtLevel.
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))
}