func rotateLeft(x uint, k int) uint {
	if uintSize == 32 {
		return uint(rotateLeft32(uint32(x), k))
	}
	return uint(rotateLeft64(uint64(x), k))
}
rotateLeft returns the value of x rotated left by (k mod UintSize) bits.
To rotate x right by k bits, call RotateLeft(x, -k).
package antlr
import (
	"bytes"
	"errors"
	"fmt"
	"sort"
	"strconv"
	"strings"
)
func intMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}
type IntStack []int
var ErrEmptyStack = errors.New("Stack is empty")
func (s *IntStack) Pop() (int, error) {
	l := len(*s) - 1
	if l < 0 {
		return 0, ErrEmptyStack
	}
	v := (*s)[l]
	*s = (*s)[0:l]
	return v, nil
}
func (s *IntStack) Push(e int) {
	*s = append(*s, e)
}
type Set struct {
	data             map[int][]interface{}
	hashcodeFunction func(interface{}) int
	equalsFunction   func(interface{}, interface{}) bool
}
func NewSet(
	hashcodeFunction func(interface{}) int,
	equalsFunction func(interface{}, interface{}) bool) *Set {
	s := new(Set)
	s.data = make(map[int][]interface{})
	if hashcodeFunction != nil {
		s.hashcodeFunction = hashcodeFunction
	} else {
		s.hashcodeFunction = standardHashFunction
	}
	if equalsFunction == nil {
		s.equalsFunction = standardEqualsFunction
	} else {
		s.equalsFunction = equalsFunction
	}
	return s
}
func standardEqualsFunction(a interface{}, b interface{}) bool {
	ac, oka := a.(comparable)
	bc, okb := b.(comparable)
	if !oka || !okb {
		panic("Not Comparable")
	}
	return ac.equals(bc)
}
func standardHashFunction(a interface{}) int {
	if h, ok := a.(hasher); ok {
		return h.hash()
	}
	panic("Not Hasher")
}
type hasher interface {
	hash() int
}
func (s *Set) length() int {
	return len(s.data)
}
func (s *Set) add(value interface{}) interface{} {
	key := s.hashcodeFunction(value)
	values := s.data[key]
	if s.data[key] != nil {
		for i := 0; i < len(values); i++ {
			if s.equalsFunction(value, values[i]) {
				return values[i]
			}
		}
		s.data[key] = append(s.data[key], value)
		return value
	}
	v := make([]interface{}, 1, 10)
	v[0] = value
	s.data[key] = v
	return value
}
func (s *Set) contains(value interface{}) bool {
	key := s.hashcodeFunction(value)
	values := s.data[key]
	if s.data[key] != nil {
		for i := 0; i < len(values); i++ {
			if s.equalsFunction(value, values[i]) {
				return true
			}
		}
	}
	return false
}
func (s *Set) values() []interface{} {
	var l []interface{}
	for _, v := range s.data {
		l = append(l, v...)
	}
	return l
}
func (s *Set) String() string {
	r := ""
	for _, av := range s.data {
		for _, v := range av {
			r += fmt.Sprint(v)
		}
	}
	return r
}
type BitSet struct {
	data map[int]bool
}
func NewBitSet() *BitSet {
	b := new(BitSet)
	b.data = make(map[int]bool)
	return b
}
func (b *BitSet) add(value int) {
	b.data[value] = true
}
func (b *BitSet) clear(index int) {
	delete(b.data, index)
}
func (b *BitSet) or(set *BitSet) {
	for k := range set.data {
		b.add(k)
	}
}
func (b *BitSet) remove(value int) {
	delete(b.data, value)
}
func (b *BitSet) contains(value int) bool {
	return b.data[value]
}
func (b *BitSet) values() []int {
	ks := make([]int, len(b.data))
	i := 0
	for k := range b.data {
		ks[i] = k
		i++
	}
	sort.Ints(ks)
	return ks
}
func (b *BitSet) minValue() int {
	min := 2147483647
	for k := range b.data {
		if k < min {
			min = k
		}
	}
	return min
}
func (b *BitSet) equals(other interface{}) bool {
	otherBitSet, ok := other.(*BitSet)
	if !ok {
		return false
	}
	if len(b.data) != len(otherBitSet.data) {
		return false
	}
	for k, v := range b.data {
		if otherBitSet.data[k] != v {
			return false
		}
	}
	return true
}
func (b *BitSet) length() int {
	return len(b.data)
}
func (b *BitSet) String() string {
	vals := b.values()
	valsS := make([]string, len(vals))
	for i, val := range vals {
		valsS[i] = strconv.Itoa(val)
	}
	return "{" + strings.Join(valsS, ", ") + "}"
}
type AltDict struct {
	data map[string]interface{}
}
func NewAltDict() *AltDict {
	d := new(AltDict)
	d.data = make(map[string]interface{})
	return d
}
func (a *AltDict) Get(key string) interface{} {
	key = "k-" + key
	return a.data[key]
}
func (a *AltDict) put(key string, value interface{}) {
	key = "k-" + key
	a.data[key] = value
}
func (a *AltDict) values() []interface{} {
	vs := make([]interface{}, len(a.data))
	i := 0
	for _, v := range a.data {
		vs[i] = v
		i++
	}
	return vs
}
type DoubleDict struct {
	data map[int]map[int]interface{}
}
func NewDoubleDict() *DoubleDict {
	dd := new(DoubleDict)
	dd.data = make(map[int]map[int]interface{})
	return dd
}
func (d *DoubleDict) Get(a, b int) interface{} {
	data := d.data[a]
	if data == nil {
		return nil
	}
	return data[b]
}
func (d *DoubleDict) set(a, b int, o interface{}) {
	data := d.data[a]
	if data == nil {
		data = make(map[int]interface{})
		d.data[a] = data
	}
	data[b] = o
}
func EscapeWhitespace(s string, escapeSpaces bool) string {
	s = strings.Replace(s, "\t", "\\t", -1)
	s = strings.Replace(s, "\n", "\\n", -1)
	s = strings.Replace(s, "\r", "\\r", -1)
	if escapeSpaces {
		s = strings.Replace(s, " ", "\u00B7", -1)
	}
	return s
}
func TerminalNodeToStringArray(sa []TerminalNode) []string {
	st := make([]string, len(sa))
	for i, s := range sa {
		st[i] = fmt.Sprintf("%v", s)
	}
	return st
}
func PrintArrayJavaStyle(sa []string) string {
	var buffer bytes.Buffer
	buffer.WriteString("[")
	for i, s := range sa {
		buffer.WriteString(s)
		if i != len(sa)-1 {
			buffer.WriteString(", ")
		}
	}
	buffer.WriteString("]")
	return buffer.String()
}
const uintSize = 32 << (^uint(0) >> 32 & 1)  