Как реализовать BitSet с Go?

Question

Я не нашел пакет BitSet в Go, поэтому я попытался реализовать его.Я хотел бы использовать массив uint64 для хранения битов.

Мне нужно количество бит для выделения массива uint64.С Java я могу определить конструктор, который принимает целое число.Хотя Go не предоставляет конструктор, как я могу правильно инициализировать объект BitSet, когда пользователь вызывает new ()?

Answer 1

Объявите bitSet как частную структуру:

type bitSet struct {
  len int
  array []uint64
}

Выставить интерфейс BitSet:

type BitSet interface {
  Has(pos int) bool
  Add(pos int) bool
  Len() int
}

Также выставляем функцию NewBitSet:

func NewBitSet(len int) BitSet {
  return &bitSet{len, make(uint64, (len+7) / 8) }
}

Это способ Go для инкапсуляции: разделяйте интерфейс, а не реализацию.

Answer 2

Если вы используете срез [] uint64 для хранения ваших данных, то нулевой срез может функционировать как пустой BitSet. Фактически добавление к нулевому срезу выделяет для вас новый массив, хотя спецификация языка не гарантирует этого. При такой настройке новый (BitSet) будет сразу же использоваться. Пример:

bitset.go:

package bitset

const size = 64

type bits uint64

// BitSet is a set of bits that can be set, cleared and queried.
type BitSet []bits

// Set ensures that the given bit is set in the BitSet.
func (s *BitSet) Set(i uint) {
    if len(*s) < int(i/size+1) {
        r := make([]bits, i/size+1)
        copy(r, *s)
        *s = r
    }
    (*s)[i/size] |= 1 << (i % size)
}

// Clear ensures that the given bit is cleared (not set) in the BitSet.
func (s *BitSet) Clear(i uint) {
    if len(*s) >= int(i/size+1) {
        (*s)[i/size] &^= 1 << (i % size)
    }
}

// IsSet returns true if the given bit is set, false if it is cleared.
func (s *BitSet) IsSet(i uint) bool {
    return (*s)[i/size]&(1<<(i%size)) != 0
}

bitset_test.go:

package bitset

import "fmt"

func ExampleBitSet() {
    s := new(BitSet)
    s.Set(13)
    s.Set(45)
    s.Clear(13)
    fmt.Printf("s.IsSet(13) = %t; s.IsSet(45) = %t; s.IsSet(30) = %t\n",
               s.IsSet(13), s.IsSet(45), s.IsSet(30))
    // Output: s.IsSet(13) = false; s.IsSet(45) = true; s.IsSet(30) = false
}

Answer 3

Стандарт Го big.Int может использоваться как набор битов:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    var bits big.Int
    for i := 1000; i < 2000; i++ {
        bits.SetBit(&bits, i, 1)
    }
    for i := 0; i < 10000; i++ {
        if bits.Bit(i) != 0 {
            fmt.Println(i)
        }
    }
}

https://play.golang.org/p/xbIK-boouqC

Answer 4

Короткий ответ: вы не можете правильно инициализировать объект BitSet, когда клиент вызывает new ().

Лучшее, что вы можете сделать, это сделать так, чтобы нулевое значение вашего BitSet было действительным. Это то, что делают типы типа list.List, sync.Mutex и big.Int. Таким образом, вы узнаете, что клиент не может получить недопустимое значение.

Следующая лучшая вещь, которую вы можете сделать, это создать функцию, похожую на конструктор (в данном случае названную NewBitSet), и ожидать, что клиенты будут ее вызывать.