/*ident	"@(#)Bits:Bits.c	3.1" */
/******************************************************************************
*
* C++ Standard Components, Release 3.0.
*
* Copyright (c) 1991, 1992 AT&T and Unix System Laboratories, Inc.
* Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
*
* THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and Unix System
* Laboratories, Inc.  The copyright notice above does not evidence
* any actual or intended publication of such source code.
*
******************************************************************************/

#include "Bits.h"

// The numbering scheme in this library is consistently
// ``little-end''  -- bit 0 is the low-order bit of the word
// stored in the lowest location of a class.

Bits::Bits(register Bits_chunk val, register unsigned ct)
{
	if (ct < Bits_len_ATTLC) {
		register Bits_chunk mask = ~Bits_chunk(0) << ct;
		while (val & mask) {
			ct++;
			mask <<= 1;
		}
	}
	if (size(ct))
		*(Bits_chunk *)b = val;
}

Bits::operator Bits_chunk() const
{
	register const Bits_chunk* p = b;
	register const Bits_chunk* lim = limit();

	while (p < lim) {
		if (*p++)
			return p[-1];
	}

	return 0;
}

int
Bits::compare(const Bits& x) const
{
	int w = bound(size());
	int xw = bound(x.size());
	int len, r;
	register const Bits_chunk* p;
	register const Bits_chunk* q;
	register const Bits_chunk* lim;

	// two null strings are equal
	if (w == 0 && xw == 0)
		return 0;

	// a null string is the smallest string
	if (w == 0)
		return -1;
	if (xw == 0)
		return 1;

	// if the lengths differ, check the high-order
	// part of the longer string; leave shorter length
	// in len if we get out of this
	if (w != xw) {
		if (w > xw) {
			len = xw;
			p = &b[len];
			q = &b[w];
			r = 1;
		} else {
			len = w;
			p = &x.b[len];
			q = &x.b[xw];
			r = -1;
		}

		do {
			if (*p++)
				return r;
		} while (p < q);
	} else
		len = w;

	// now compare low-order parts, going from high-order
	// end to low-order end (the direction is important!)
	p = (const Bits_chunk *)b + len;
	q = (const Bits_chunk *)x.b + len;
	lim = b;
	while (p > lim) {
		if (*--p != *--q)
			return *p < *q? -1: 1;
	}

	// the bits are equal -- length determines the result
	return int(size()) - int(x.size());
}

Bits&
Bits::complement()
{
	register Bits_chunk* p = b;
	register const Bits_chunk* lim = limit();

	while (p < lim) {
		*p = ~*p;
		p++;
	}

	normalize();

	return *this;
}

Bits&
Bits::concat(const Bits& x)
{
	operator<<= (x.size());
	operator|= (x);
	return *this;
}

unsigned
Bits::count() const
{
	register const Bits_chunk* p = b;
	register const Bits_chunk* lim = limit();
	register unsigned r = 0;

	while (p < lim) {
		register unsigned long x = *p++;
		register int i = Bits_len_ATTLC;

		while (--i >= 0) {
			if (x & 1)
				r++;
			x >>= 1;
		}
	}

	return r;
}

// Are two bit strings identical?
int
Bits::equal(const Bits& x) const
{
	// two strings of different sizes are not equal
	if (size() != x.size())
		return 0;

	// two null strings are equal
	if (size() == 0)
		return 1;

	// else go the long route
	return compare(x) == 0;
}

Bits&
Bits::operator&= (const Bits& x)
{
	if (size() < x.size())
		size(x.size());

	register Bits_chunk* p = b;
	register const Bits_chunk* q = x.b;
	register const Bits_chunk* lim = x.limit();

	while (q < lim)
		*p++ &= *q++;

	lim = limit();
	while (p < lim)
		*p++ = 0;

	return *this;
}

Bits&
Bits::operator^= (const Bits& x)
{
	if (size() < x.size())
		size(x.size());

	register Bits_chunk* p = b;
	register const Bits_chunk* q = x.b;
	register const Bits_chunk* lim = x.limit();

	while (q < lim)
		*p++ ^= *q++;

	return *this;
}

// The following routines can surely be made more efficient.
// I have not done so for two reasons:
//
//	1. The function call and memory allocation overhead
//	   will probably dominate for all but the largest of
//	   bit strings.
//
//	2. This code is tricky.  Further optimization would
//	   erode my confidence in getting it right.

Bits&
Bits::operator<<= (int k)
{
	// Quick test for shift by 0 or negative
	if (k <= 0) {
		if (k < 0)
			operator>>= (-k);
		return *this;
	}

	// Enlarge the structure to contain the result; return on error
	if (size(size() + k) == 0)
		return *this;

	register Bits_chunk* lim = b;

	// If needed, shift left by chunks
	int chunkoffset = k >> Bits_shift_ATTLC;
	if (chunkoffset) {
		register Bits_chunk* dest = limit();
		register Bits_chunk* src = dest - chunkoffset;

		while (src > lim) *--dest = *--src;

		while (dest > lim) *--dest = 0;
	}

	// If needed, shift left by bits
	register int bitoffset = k & Bits_mask_ATTLC;
	if (bitoffset) {
		register Bits_chunk* p = limit();
		register int compoffset = Bits_len_ATTLC - bitoffset;

		while (--p > lim)
			*p = (*p << bitoffset) | (*(p-1) >> compoffset);

		// Shift low-order chunk
		*lim <<= bitoffset;
	}

	normalize();

	return *this;
}


Bits&
Bits::operator|= (const Bits& x)
{
	if (size() < x.size())
		size(x.size());

	register Bits_chunk* p = b;
	register const Bits_chunk* q = x.b;
	register const Bits_chunk* lim = x.limit();

	while (q < lim)
		*p++ |= *q++;

	return *this;
}

Bits&
Bits::operator>>= (int k)
{
	// Quick test for shift by 0 or negative
	if (k <= 0) {
		if (k < 0)
			operator<<= (-k);
		return *this;
	}

	// Check for shifting all significance out
	int newsize = size() - k;
	if (newsize <= 0) {
		size(0);
		return *this;
	}

	// If needed, shift right by chunks, leaving high-order
	// garbage words that will be sized out later
	int chunkoffset = k >> Bits_shift_ATTLC;
	if (chunkoffset) {
		register Bits_chunk* dest = b;
		register Bits_chunk* src = dest + chunkoffset;
		register const Bits_chunk* lim = limit();

		do *dest++ = *src++;
		while (src < lim);
	}

	// If needed, shift right by bits
	register int bitoffset = k & Bits_mask_ATTLC;
	if (bitoffset) {
		register Bits_chunk* p = b;
		register Bits_chunk* lim = p + chunk(newsize-1);
		register int compoffset = Bits_len_ATTLC - bitoffset;

		while (p < lim) {
			*p = (*p >> bitoffset) | (*(p+1) << compoffset);
			p++;
		}

		// Shift high-order chunk right
		*lim >>= bitoffset;
		if (lim+1 < limit())
			*lim |= *(lim+1) << compoffset;
	}

	// Finally, make the size right, discarding junk bits
	size(newsize);

	return *this;
}

// How many significant bits?
unsigned
Bits::signif() const
{
	if (size() == 0)
		return 0;

	register const Bits_chunk* p = limit();
	register const Bits_chunk* lim = b;

	while (--p >= lim) {
		if (*p) {
			register Bits_chunk x = *p;
			register int k = Bits_len_ATTLC;

			while (--k >= 0) {
				if (x & (Bits_chunk(1) << k))
					return k + 1 + Bits_len_ATTLC * (p - lim);
			}
		}
	}

	return 0;
}

unsigned
Bits::size(unsigned x)
{
	int newsize = bound(x);
	if (b.size() != newsize)
		b.size(newsize);
	n = b.size()? x: 0;

	normalize();

	return n;
}

Bits
concat(const Bits& x, const Bits& y)
{
	Bits r = x;
	r.concat(y);
	return r;
}

Bits
operator& (const Bits& x, const Bits& y)
{
	Bits r = x;
	r &= y;
	return r;
}

Bits
operator^ (const Bits& x, const Bits& y)
{
	Bits r = x;
	r ^= y;
	return r;
}

Bits
operator<< (const Bits& x, int n)
{
	Bits r = x;
	r <<= n;
	return r;
}

Bits
operator~ (const Bits& x)
{
	Bits r = x;
	r.complement();
	return r;
}

Bits
operator| (const Bits& x, const Bits& y)
{
	Bits r = x;
	r |= y;
	return r;
}

Bits
operator>> (const Bits& x, int n)
{
	Bits r = x;
	r >>= n;
	return r;
}

#include <iostream.h>

ostream& operator<<(ostream& os,const Bits& b){
    for(int i = b.size();i;i--){
	os << b[i-1]; 
    }
    return os;
}