path: root / Year 1 / Object-oriented Programming / Solutions Sem. 05 / ex2-interval.cpp

// 
// ++============++
// || Оценка: Да ||
// ++============++
//
// +-----------+
// | !Бележки! |
// +-----------+
//
// > Ангел Димитриев - Fri, 25 Mar 2022, 19:45
// Супер решение.
// 
// Единственотата по-сериозна забележка, която имам е че изчисляваш counts при извикването на set.-a.
// 
// Не винаги е добре това, защото може временно да ти потрябва огромен интервал, а ти ще му сметнеш всичките характеристики, дори и да не са поискани. По-правилно би било да ги смяташ в palindromesCount/primesCount/nonRepeatingDigitsCount и да имаш променлива isModified, за да знаеш дали трябва да ги смяташ
//

#include <iostream> // cin, cout
#include <math.h>   // sqrt

/* Generic functions */

bool isPowerOf2(int x)
{
	return x > 0 &&            // No (normal) power of 2 creates negatives or 0
		   (x & (x - 1)) == 0; // Thanks https://stackoverflow.com/a/600306/12036073, original implementation was a lot less efficient
}

bool isPrime(int num) // Forked from my own implementation - https://gitlab.com/Syndamia/algorithms/-/blob/master/C/IsPrime.c
{
	if (num < 0) num *= -1; // This is required, since we calculate sqrt(num)

	if (num == 2 || num == 3 || num == 5 || num == 7 || num == 11 || num == 13)
		return true;

	// A lot of numbers are divisible by these ones, so we're going to do a bit of simple optimization
	if (num == 0 || num == 1 || num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num % 7 == 0 || num % 11 == 0 || num % 13 == 0)
		return false;

	// All primes follow the formula 6n +- 1 (where n >= 1). Since we've already checked up to 13, we're going to
	// start with 18 - 1 = 17. Also using root of number to eliminate a lot of checks.
	// Primary source: https://en.wikipedia.org/wiki/Primality_test#Simple_methods
	for (int i = 18, root = sqrt(num); i - 1 <= root; i += 6)
	{
		if (num % (num - 1) == 0 || num % (num + 1) == 0)
			return false;
	}
	return true;
}

bool isPalindrome(int num)
{
	if (num < 0)
		return false;

	int buff = 0, tNum = num;
	while (tNum != 0)
	{
		buff = buff * 10 + (tNum % 10);
		tNum /= 10;
	}
	return buff == num;
}

bool hasRepeatingDigits(int num)
{
	if (num < 0) num *= -1; // if num is negative, num % 10 will also be negative, which mustn't happen

	bool digitOccur[] = { false, false, false, false, false, false, false, false, false, false };
	while (num != 0)
	{
		if (digitOccur[num % 10])
			return true;
		digitOccur[num % 10] = true;
		num /= 10;
	}
	return false;
}

bool hasNotRepeatingDigits(int num)
{
	return !hasRepeatingDigits(num);
}

/* Class Interval */

class Interval
{
	int a;
	int b;

	// "Caches" for the heavy operations
	int primeNumbersCount;
	int palindromeNumbersCount;
	int nonRepeatingDigitsNumbersCount;
	bool edgesPowersOf2;

	int counter(bool (comparator)(int)) const
	{
		int count = 0;
		for (int i = a; i <= b; i++)
		{
			if (comparator(i))
				count++;
		}
		return count;
	}

	void calculateCounts()
	{
		this->primeNumbersCount = counter(isPrime);
		this->palindromeNumbersCount = counter(isPalindrome);
		this->nonRepeatingDigitsNumbersCount = counter(hasNotRepeatingDigits);
	}

public:
	Interval();
	Interval(int a, int b);

	int get_a() const;
	void set_a(int a);

	int get_b() const;
	void set_b(int b);

	int getLen() const;
	bool hasInInterval(int x) const;

	// The operations for each one are "heavy" so we calculated them on interval
	// edges set and return the "cached" value
	int primesCount() const;
	int palindromesCount() const;
	int nonRepeatingDigitsCount() const;
	bool edgesArePowersOf2() const;

	Interval intersect(const Interval& inter) const;
	bool isSupInterval(const Interval& inter) const;
};

Interval::Interval() : Interval(0, 0)
{}
Interval::Interval(int a, int b)
{
	if (a > b) a = b = 0;

	this->edgesPowersOf2 = isPowerOf2(a) && isPowerOf2(b);
	this->a = a; // We can't use setter here, since it will try to calculate the counts, and we don't want to do that yet.
	this->set_b(b);
}

int Interval::get_a() const
{
	return this->a;
}
void Interval::set_a(int a)
{
	this->a = a;
	if (a > b) this->b = a; // Note: behaviour not defined in task

	this->calculateCounts();
	this->edgesPowersOf2 &= isPowerOf2(a);
}

int Interval::get_b() const
{
	return this->b;
}
void Interval::set_b(int b)
{
	this->b = b;
	if (b < a) this->a = b; // Note: behaviour not defined in task

	this->calculateCounts();
	this->edgesPowersOf2 &= isPowerOf2(b);
}

int Interval::getLen() const
{
	return this->get_a() - this->get_b();
}
bool Interval::hasInInterval(int x) const
{
	return this->get_a() <= x && x <= this->get_b();
}

int Interval::primesCount() const
{
	return this->primeNumbersCount;
}
int Interval::palindromesCount() const
{
	return this->palindromeNumbersCount;
}
int Interval::nonRepeatingDigitsCount() const
{
	return this->nonRepeatingDigitsNumbersCount;
}
bool Interval::edgesArePowersOf2() const
{
	return this->edgesPowersOf2;
}

Interval Interval::intersect(const Interval& inter) const
{
	// [ ] { }  or  { } [ ]  where [] is this, {} is inter
	if (this->b < inter.get_a() || this->a > inter.get_b())
		return Interval();

	// [ { ] }   where [] is this, {} is inter
	if (this->a <= inter.get_a())
		return Interval(inter.a, this->b);
	// { [ } ]   where [] is this, {} is inter
	else
		return Interval(this->a, inter.b);
}
bool Interval::isSupInterval(const Interval& inter) const
{
	return this->a >= inter.a && inter.b <= this->b;
}

/* Main */

void printInter(const Interval& inter)
{
	std::cout << "[" << inter.get_a() << "," << inter.get_b() << "]" << std::endl;
}

int main()
{
	/* Стойчо ни беше направил документ за unit тестове, но имайки предвид, че формално ги няма в задачата, не съм правил */

	Interval t1(3, 10), t2(4, 14), t3;
	printInter(t1);
	printInter(t2);
	printInter(t3);

	Interval intT1T2 = t1.intersect(t2);
	printInter(intT1T2); // [4,10]
	
	std::cout << t2.isSupInterval(intT1T2) << std::endl; // true
	std::cout << intT1T2.primesCount() << std::endl; // 2 (5 and 7)
	std::cout << t2.hasInInterval(14) << " " << t2.hasInInterval(15) << std::endl; // "1 0"
	
	Interval t4(0, 100), t5(-100, 0);
	std::cout << "Pal: " << t4.palindromesCount() << " " << t5.palindromesCount() << std::endl; // "19 1" (negatives arent palindromes)
	std::cout << "Primes: " << t4.primesCount() << " " << t5.primesCount() << std::endl; // "25 25"
	std::cout << "Non repeat: " << t4.nonRepeatingDigitsCount() << " " << t5.nonRepeatingDigitsCount() << std::endl; // "91 91"
	
	std::cout << t5.hasInInterval(-99) << t5.hasInInterval(0) << t5.hasInInterval(1) << std::endl; // "110"

	Interval t6(256, 1024), t7(-1024, -256);
	std::cout << "Two Power Ends: " << t4.edgesArePowersOf2() << " " << t5.edgesArePowersOf2() << " " << t6.edgesArePowersOf2() << " " << t7.edgesArePowersOf2() << std::endl; // "0 0 1 0"
}