//num is odd or even
func isEven(n int) bool {
  return n&1 == 0
}

//test nth bit is set
func isSet(x int, n uint) bool {
  return (x & (1 << n)) > 0
}

func setBit(x int, n uint) int {
  return x | (1 << n)
}

func unSetBit(x int, n uint) int {
  // negate = all 0 except 1 position
  return x & ^(1 << n)
}

func toggleBit(x int, n uint) int {
  // ^ = xor = both same = 0 else 1
  // only of or is true
  //xor twice returns original value
  return x ^ (1 << n)
}

//turn off rightmost 1-bit
func turnOffRightMost(x int) int {
  return x & (x - 1)
}

//turns off all other bits except rightmost "on" bit
func isolateRightmostBit(x int) int {
  return x & (-x)
}

//produces all 1's if x = 0
func rightPropogateRightmostBit(x int) int {
  return x | (x - 1)
}

//flip all bits in integer
func flipBits(x int) uint {
  return ^uint(x)
}

func CountingSort(vals []int, maxVal int) {
  histogram := make(map[int]int, maxVal+1)
  for _, val := range vals {
      histogram[val]++
  }

  pos := 0
  for i := 0; i < maxVal; i++ {
      if _, ok := histogram[i]; ok {
          for j := 0; j < histogram[i]; j++ {
              vals[pos] = i
              pos++
          }
      }
  }
}

func RadixSort(vals []int) {
  m := vals[0]
  const base = 10

  for _, val := range vals {
      if val > m {
          m = val
      }
  }

  exp := 1
  for m/exp > 0 {
      bucket := make([][]int, base)
      //count keys
      for i := 0; i < len(vals); i++ {
          key := (vals[i] / exp) % base
          bucket[key] = append(bucket[key], vals[i])
      }
      idx := 0
      for i := 0; i < len(bucket); i++ {
          for j := 0; j < len(bucket[i]); j++ {
              vals[idx] = bucket[i][j]
              idx++
          }
      }
      exp *= 10
  }
}

func InsertSort(vals []int) {
  for i, _ := range vals {
      j := i
      for j > 0 && vals[j-1] > vals[j] {
          vals[j], vals[j-1] = vals[j-1], vals[j]
          j--
      }
  }
}

func merge(vals []int, helper []int, low int, middle int, high int) {
  //copy both halves into helper slice
  for i := low; i <= high; i++ {
      helper[i] = vals[i]
  }

  helperLeft := low
  helperRight := middle + 1
  current := low

  //iterate through helper array. Compare left and right
  // half, copying the smaller of the 2 into original
  for helperLeft <= middle && helperRight <= high {
      if helper[helperLeft] <= helper[helperRight] {
          vals[current] = helper[helperLeft]
          helperLeft++
      } else {
          vals[current] = helper[helperRight]
          helperRight++
      }
      current++
  }

  // Copy the rest of the left side of the array into the
  // target array.
  remaining := middle - helperLeft
  for i := 0; i <= remaining; i++ {
      vals[current+i] = helper[helperLeft+i]
  }

}

func mergesort(vals []int, helper []int, low int, high int) {
  if low < high {
      middle := (low + high) / 2
      mergesort(vals, helper, low, middle)
      mergesort(vals, helper, middle+1, high)
      merge(vals, helper, low, middle, high)
  }
}

func MergeSort(vals []int) {
  helper := make([]int, len(vals))
  mergesort(vals, helper, 0, len(vals)-1)
}

func partition(vals []int, left int, right int) int {
  middle := (left + right) / 2
  pivotVal := vals[middle]

  //swap middle/right
  vals[middle], vals[right] = vals[right], vals[middle]

  lessPointer := left
  for greaterPointer := left; greaterPointer < right; greaterPointer++ {
      if vals[greaterPointer] <= pivotVal {
          vals[greaterPointer], vals[lessPointer] = vals[lessPointer], vals[greaterPointer]
          lessPointer++
      }
  }

  vals[lessPointer], vals[right] = vals[right], vals[lessPointer]

  return lessPointer
}

func quickSort(vals []int, min int, max int) {
  if min < max {
      p := partition(vals, min, max)
      quickSort(vals, min, p-1)
      quickSort(vals, p+1, max)
  }
}

func QuickSort(vals []int) {
  quickSort(vals, 0, len(vals)-1)
}

type Heap struct {
  data []int
  //maxSize      int
  //itemsInArray int
}

func NewHeap(size int) *Heap {
  h := new(Heap)
  h.data = make([]int, 0, size)
  return h
}

//moves element up to its proper position
//respecting binary tree property
func (h *Heap) up(idx int) {
  for {
      parent := (idx - 1) / 2
      if idx == parent || h.data[idx] < h.data[parent] {
          //at end of array or idx is in proper position
          break
      }
      //Swap with parent
      h.data[parent], h.data[idx] = h.data[idx], h.data[parent]
      idx = parent
  }
}

func (h *Heap) down(idx int) {
  end := len(h.data)
  for {
      //start with left child
      child := 2*idx + 1

      if child > end {
          break
      }

      if child+1 < end && h.data[child] < h.data[child+1] {
          //use right child
          child++
      }

      if h.data[child] < h.data[idx] {
          //proper position
          break
      }

      //swap parent with child
      h.data[child], h.data[idx] = h.data[idx], h.data[child]
      //move to grandchildren
      idx = child
  }
}

func (h *Heap) Pop() int {
  result := h.data[0]
  h.data[0] = h.data[len(h.data)-1]
  h.down(0)
  h.data = h.data[:len(h.data)-2]

  //shrink when excess capacity hits 3/4
  if len(h.data) <= cap(h.data)/4 {
      h.resize(len(h.data) / 4)
  }
  return result
}

func (h *Heap) resize(size int) {
  len := len(h.data)
  temp := make([]int, len, size)
  for idx, val := range temp {
      temp[idx] = val
  }
  h.data = temp
}

func (h *Heap) Push(v int) {
  h.data = append(h.data, v)
  h.up(len(h.data) - 1)
  //grow when cap hit
  if len(h.data) == cap(h.data) {
      h.resize(len(h.data) * 2)
  }
}

type Node struct {
  Data int
  Next *Node
}

func (n *Node) Append(newNode *Node) {
  temp := n
  for temp.Next != nil {
      temp = temp.Next
  }

  n.Next = newNode
}

func reverseLinkedList(node *Node) {
  var prev *Node
  current := node

  for current != nil {
      next := current.Next
      current.Next = prev
      prev = current
      current = next
  }
  node = prev
}

   //simple stack structure
  type stack []int

  func (s stack) Empty() bool { return len(s) == 0 }
  func (s stack) Peek() int   { return s[len(s)-1] }
  func (s *stack) Put(i int)  { (*s) = append((*s), i) }
  func (s *stack) Pop() int {
      d := (*s)[len(*s)-1]
      (*s) = (*s)[:len(*s)-1]
      return d
  }

   //Binary search
  func Search(vals []int, target int) int {
      return binarySearch(vals, target, 0, len(vals)-1)
  }

  func binarySearch(vals []int, target int, start int, end int) int {
      if start > end {
          //not found
          return -1
      }

      middle := int(math.Floor((float64(start) + float64(end)) / 2.0))
      value := vals[middle]

      if value > target {
          return binarySearch(vals, target, start, middle-1)
      }

      if value < target {
          return binarySearch(vals, target, middle+1, end)
      }

      return middle //found
  }

   
  //reverse polish notation calculator
  //takes a string like "699+/"
  //prints result e.g. 9
  func ReversePolishCalculator(expression string) {
  var s stack
  for _, c := range expression {
      switch c {
      case '+':
          a := s.Pop()
          b := s.Pop()
          s.Put(a + b)
          break
      case '-':
          a := s.Pop()
          b := s.Pop()
          s.Put(a - b)
          break
      case '/':
          a := s.Pop()
          b := s.Pop()
          s.Put(a / b)
          break
      case '*':
          a := s.Pop()
          b := s.Pop()
          s.Put(a * b)
          break
      default:
          s.Put(int(c) - 48)
      }
  }

  //result
  fmt.Printf("%v=%v", expression, s.Pop())

  }