#! /usr/bin/env python3

"""
bitset.py

Written by Geremy Condra

Licensed under GPLv3

Released 3 May 2009

This module provides a simple bitset implementation
for Python.
"""

from collections import Sequence
import math

class Bitset(Sequence):
	"""A very simple bitset implementation for Python.

	Note that, like with normal numbers, the leftmost
	index is the MSB, and like normal sequences, that
	is 0.

	Usage:
		>>> b = Bitset(5)
		>>> b
		Bitset(101)
		>>> b[:]
		[True, False, True]
		>>> b[0] = False
		>>> b
		Bitset(001)
		>>> b << 1
		Bitset(010)
		>>> b >> 1
		Bitset(000)
		>>> b & 1
		Bitset(001)
		>>> b | 2
		Bitset(011)
		>>> b ^ 6
		Bitset(111)
		>>> ~b
		Bitset(110)
	"""

	value = 0
	length = 0

	@classmethod
	def from_sequence(cls, seq):
		"""Iterates over the sequence to produce a new Bitset.

		As in integers, the 0 position represents the LSB.
		"""
		n = 0
		for index, value in enumerate(reversed(seq)):
			n += 2**index * bool(int(value))
		b = Bitset(n)
		return b

	def __init__(self, value=0, length=0):
		"""Creates a Bitset with the given integer value."""
		self.value = value
		try: self.length = length or math.floor(math.log(value, 2)) + 1
		except Exception: self.length = 0

	def __and__(self, other):
		b = Bitset(self.value & int(other))
		b.length = max((self.length, b.length))
		return b

	def __or__(self, other):
		b = Bitset(self.value | int(other))
		b.length = max((self.length, b.length))
		return b

	def __invert__(self):
		b = Bitset(~self.value)
		b.length = max((self.length, b.length))
		return b

	def __xor__(self, value):
		b = Bitset(self.value ^ int(value))
		b.length = max((self.length, b.length))
		return b

	def __lshift__(self, value):
		b = Bitset(self.value << int(value))
		b.length = max((self.length, b.length))
		return b

	def __rshift__(self, value):
		b = Bitset(self.value >> int(value))
		b.length = max((self.length, b.length))
		return b

	def __eq__(self, other):
		try:
			return self.value == other.value
		except Exception:
			return self.value == other

	def __int__(self):
		return self.value

	def __str__(self):
		s = ""
		for i in self[:]:
			s += "1" if i else "0"
		return s

	def __repr__(self):
		return "Bitset(%s)" % str(self)

	def __getitem__(self, s):
		"""Gets the specified position.

		Like normal integers, 0 represents the MSB.
		"""
		try:
			start, stop, step = s.indices(len(self))
			results = []
			for position in range(start, stop, step):
				pos = len(self) - position - 1
				results.append(bool(self.value & (1 << pos)))
			return results
		except:
			pos = len(self) - s - 1
			return bool(self.value & (1 << pos))
 
	def __setitem__(self, s, value):
		"""Sets the specified position/s to value.

		Like normal integers, 0 represents the MSB.
		"""
		try:
			start, stop, step = s.indices(len(self))
			for position in range(start, stop, step):
				pos = len(self) - position - 1
				if value: self.value |= (1 << pos)
				else: self.value &= ~(1 << pos)
			maximum_position = max((start + 1, stop, len(self)))
			self.length = maximum_position
		except:
			pos = len(self) - s - 1
			if value: self.value |= (1 << pos)
			else: self.value &= ~(1 << pos)
			if len(self) < pos: self.length = pos
		return self

	def __iter__(self):
		"""Iterates over the values in the bitset."""
		for i in self[:]:
			yield i

	def __len__(self):
		"""Returns the length of the bitset."""
		return self.length