Optimized OpenSCAD Vector w/ Eigen types

VectorObject.cc

/*
 *  OpenSCAD (www.openscad.org)
 *  Copyright (C) 2009-2011 Clifford Wolf <clifford@clifford.at> and
 *                          Marius Kintel <marius@kintel.net>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  As a special exception, you have permission to link this program
 *  with the CGAL library and distribute executables, as long as you
 *  follow the requirements of the GNU GPL in regard to all of the
 *  software in the executable aside from CGAL.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

#include <cassert>
#include <cmath>
#include <numeric>
#include <sstream>
// #include <boost/variant/apply_visitor.hpp>
// #include <boost/variant/static_visitor.hpp>
/*Unicode support for string lengths and array accesses*/
#include <glib.h>

#include "Value.h"
#include "VectorObject.h"
#include "Expression.h"
#include "EvaluationSession.h"
#include "printutils.h"
#include "boost-utils.h"

// VectorObject

std::shared_ptr<VectorObject> VectorObject::emplace_back(Value &&value)
{
	// assert(!dynamic_cast<GenericVectorObject*>(this));
	if (value.type() == Value::Type::NUMBER) {
		return push_back(value.toDouble());
	}
	if (value.type() == Value::Type::EMBEDDED_VECTOR) {
		return emplace_back(std::move(val.toEmbeddedVectorNonConst()));
	}

	// This is anything but a GenericVectorObject, convert to one.
	auto vv = to_generic();
	vv.emplace_back(value);
	return vv;
}

std::shared_ptr<VectorObject> VectorObject::emplace_back(EmbeddedVectorType &&mbed)
{
	return to_generic()->emplace_back(std::move(mbed));
}

bool VectorObject::operator<(const VectorObject &v) const override
{
	auto first1 = this->begin(), last1 = this->end(), first2 = v.begin(), last2 = v.end();
	size_t i = 0;
	for (; (first1 != last1) && (first2 != last2); ++first1, ++first2, ++i) {
		Value temp = *first1 < *first2;
		if (temp.isUndefined()) {
			temp.toUndef().append(STR("in vector comparison at index " << i));
			return temp;
		}
		if (temp.toBool()) return true;
		if ((*first2 < *first1).toBool()) return false;
	}
	return (first1 == last1) && (first2 != last2);
}

std::shared_ptr<VectorObject> VectorObject::make_double_vector(size_t capacity) override
{
	if (capacity <= 2) return std::make_shared<VectorNdObject<2>>();
	if (capacity == 3) return std::make_shared<VectorNdObject<3>>();
	if (capacity == 4) return std::make_shared<VectorNdObject<4>>();
	return std::make_shared<VectorXdObject>(capacity);
}
std::shared_ptr<VectorObject> VectorObject::make_generic_vector(size_t capacity) override
{
	return std::make_shared<GenericVectorObject>(capacity);
}

// GenericVectorObject

GenericVectorObject::~GenericVectorObject()
{
	VectorObject *orig = this;
	if (orig->evaluation_session) {
		orig->evaluation_session->accounting().removeVectorElement(orig->vec.size());
	}
	std::shared_ptr<VectorObject> curr;
	std::vector<std::shared_ptr<VectorObject>> purge;
	while (true) {
		if (v && v->embed_excess) {
			for (Value &val : v->vec) {
				auto type = val.type();
				if (type == Value::Type::EMBEDDED_VECTOR) {
					auto &temp = boost::get<EmbeddedVectorType>(val.value).ptr;
					if (temp.use_count() <= 1) purge.emplace_back(std::move(temp));
				}
				else if (type == Value::Type::VECTOR) {
					auto &temp = boost::get<VectorType>(val.value).ptr;
					if (temp.use_count() <= 1) purge.emplace_back(std::move(temp));
				}
			}
		}
		if (purge.empty()) break;
		curr =
				std::move(purge.back()); // this should cause destruction of the *previous value* for curr
		v = curr.get();
		purge.pop_back();
	}
	// delete orig;
}
std::shared_ptr<VectorObject> GenericVectorObject::emplace_back(EmbeddedVectorType &&mbed) override
{
	if (mbed.size() > 1) {
		// embed_excess represents how many to add to vec.size() to get the total elements after
		// flattening, the embedded vector itself already counts towards an element in the parent's
		// size, so subtract 1 from its size.
		embed_excess += mbed.size() - 1;
		vec.emplace_back(std::move(mbed));
		if (evaluation_session) {
			evaluation_session->accounting().addVectorElement(1);
		}
	}
	else if (mbed.size() == 1) {
		// If embedded vector contains only one value, then insert a copy of that element
		// Due to the above mentioned "-1" count, putting it in directaly as an EmbeddedVector
		// would not change embed_excess, which is needed to check if flatten is required.
		for (auto &val : mbed) {
			emplace_back(val.clone);
		}
	}
	// else mbed.size() == 0, do nothing
	return shared_from_this();
}

VectorObject.h

#pragma once

#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>
#include <limits>
#include <iostream>
#include <memory>

// // Workaround for https://bugreports.qt-project.org/browse/QTBUG-22829
// #ifndef Q_MOC_RUN
// #include <boost/variant.hpp>
// #include <boost/lexical_cast.hpp>
// #include <glib.h>
// #endif

#include "linalg.h"
#include "memory.h"

class GenericVectorObject;

// Base class for a vector backing store, which has many specialized subclasses
// that are optimized for geometry processing.
//
// For an empty default value, just create an EmptyVectorObject.
// Reserving capacity is very important as it's used (along with the actual
// values being added) to decide which backing store to create.
//
// Mutation methods (including reserve) can return the same instance if it
// supports the operation, or a different instance (with values
// transparently copied over) if it needs a different implementation /
// backing store.
//
// This is loosely inspired by V8's array storage.
//
// EmptyVectorObject -> emplace_back(double) = Vector2dObject (size == 1)
// EmptyVectorObject -> reserve(3) -> emplace_back(double) = Vector3dObject (size == 1)
// EmptyVectorObject -> reserve(4) -> emplace_back(double) = Vector4dObject (size == 1)
// EmptyVectorObject -> reserve(N > 4) -> emplace_back(double) = VectorXdObject (size == 1)

// Vector2dObject (size = 2) -> emplace_back(double) = Vector3dObject (size == 3)
// Vector3dObject (size = 3) -> emplace_back(double) = Vector4dObject (size == 4)
// Vector4dObject (size = 4) -> emplace_back(double) = VectorXdObject (size == 5)
// Vector*dObject -> emplace_back(Value != double) = GenericVectorObject
//
// EmptyVectorObject -> reserve(3) -> emplace_back(Vector3dObject) = Matrix3dObject (size == 1)
// EmptyVectorObject -> reserve(4) -> emplace_back(Vector4dObject) = Matrix4dObject (size == 1)
//
// EmptyVectorObject -> emplace_back(Value != NUMBER) = GenericVectorObject (size == 1)
//

class VectorObject : public std::enable_shared_from_this<VectorObject>
{
protected:
	class EvaluationSession *evaluation_session =
			nullptr; // Used for heap size bookkeeping. May be null for vectors of known small maximum
							 // size.

public:
	// TODO: pass EvaluationSession *evaluation_session in ctor

	~VectorObject() {}

	struct const_iterator {
	private:
		std::vector<std::pair<std::shared_ptr<VectorObject>, size_t>> stack;
		Value tmp_value;

	public:
		const_iterator(const std::shared_ptr<VectorObject> &vo, size_t index)
		{
			stack.emplace_back(vo, index);
			check_and_push();
		}

		const_iterator &operator++()
		{
			while (!stack.empty() && ++get_index() >= get_vo()->size()) {
				stack.pop_back();
			}
			check_and_push();
			return *this;
		}

		const Value &operator*() const
		{
			auto vo = get_vo();
			auto i = get_index();
			if (auto dvo = dynamic_pointer_cast<DoubleVectorObject>(vo)) {
				tmp_value = dvo->doubleValueAt(i);
				return tmp_value;
			}
			else if (auto gvo = dynamic_pointer_cast<GenericVectorObject>(vo)) {
				return gvo->genericValueAt(i);
			}
			throw 0;
		}
		const Value *operator->() const { return &(*this); }

		bool operator==(const const_iterator &other) const
		{
			return vec == other.vec && index == other.index;
		}

	private:
		inline const std::shared_ptr<VectorObject> &get_vo() { return stack.back().first; }
		inline size_t &get_index() { return stack.back().second; }
		void check_and_push()
		{
			std::shared_ptr<VectorObject> vo;
			size_t index;
			while ((vo = get_vo()) && (index = get_index()) < vo->size()) {
				if (auto gvo = dynamic_pointer_cast<GenericVectorObject>(vo)) {
					auto &value = gvo->genericValueAt(index);
					if (value.type() != Type::EMBEDDED_VECTOR) {
						break;
					}
					stack.emplace_back(value.toEmbeddedVector().ptr, 0);
				}
				else {
					break;
				}
			}
		}
	};

	const_iterator begin() const { return const_iterator(shared_from_this(), 0); }
	const_iterator end() const { return const_iterator(shared_from_this(), size()); }
	virtual std::shared_ptr<VectorObject> flatten()
	{
		if (!needs_flattening()) {
			return shared_from_this();
		}
		if (flattens_to_doubles()) {
			auto vec = make_double_vector(size());
			for (auto &val : *this) {
				vec.push_back(val.toDouble());
			}
			return vec;
		}
		else {
			auto vec = make_generic_vector(size());
			for (auto &val : *this) {
				vec.emplace_back(val);
			}
			return vec;
		}
	}
	virtual std::shared_ptr<GenericVectorObject> to_generic()
	{
		auto vec = make_generic_vector(size());
		for (auto &value : *this) {
			vec->emplace_back(value);
		}
		return vec;
	}
	virtual std::shared_ptr<VectorObject> reserve(size_t s) = 0;
	virtual std::shared_ptr<VectorObject> push_back(double value) = 0;
	virtual std::shared_ptr<VectorObject> emplace_back(Value &&value);
	virtual size_t size() const = 0;

	virtual bool operator==(const VectorObject &v) const = 0;
	virtual bool operator<(const VectorObject &v) const = 0;

	virtual std::shared_ptr<VectorObject> operator+(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a + b; }, v);
	}
	virtual std::shared_ptr<VectorObject> operator+(double v) const
	{
		return applyOp([](auto &a, auto &b) { return a + b; }, v);
	}

	virtual std::shared_ptr<VectorObject> operator-(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a - b; }, v);
	}
	virtual std::shared_ptr<VectorObject> operator-(double v) const
	{
		return applyOp([](auto &a, auto &b) { return a - b; }, v);
	}

	virtual std::shared_ptr<VectorObject> operator*(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a * b; }, v);
	}
	virtual std::shared_ptr<VectorObject> operator*(double v) const
	{
		return applyOp([](auto &a, auto &b) { return a * b; }, v);
	}

	virtual std::shared_ptr<VectorObject> operator/(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a / b; }, v);
	}
	virtual std::shared_ptr<VectorObject> operator/(double v) const
	{
		return applyOp([](auto &a, auto &b) { return a / b; }, v);
	}

	virtual bool needs_flattening() const = 0;

protected:
	template <class Op>
	std::shared_ptr<VectorObject> applyOp(const Op &op, const VectorObject &v) const
	{
		auto out = make_generic_vector(op1.size());
		// TODO(ochafik): zip_iterators

		// FIXME: should we really truncate to shortest vector here?
		//   Maybe better to either "add zeroes" and return longest
		//   and/or issue an warning/error about length mismatch.
		for (auto it1 = op1.begin(), end1 = op1.end(), it2 = op2.begin(), end2 = op2.end();
				 it1 != end1 && it2 != end2; ++it1, ++it2) {
			out->emplace_back(op(*it1, *it2));
		}
		return out;
	}
	template <class Op>
	virtual std::shared_ptr<VectorObject> applyOp(const Op &op, double v) const
	{
		auto out = make_generic_vector(op1.size());
		for (auto &value : *this) {
			out->emplace_back(op(value, v));
		}
		return out;
	}
	virtual bool flattens_to_doubles() const = 0;

	// Specialized handler for EmbeddedVectorTypes
	virtual std::shared_ptr<VectorObject> emplace_back(EmbeddedVectorType &&mbed);

	virtual std::shared_ptr<VectorObject> make_double_vector(size_t capacity);
	virtual std::shared_ptr<VectorObject> make_generic_vector(size_t capacity);
};
// Keeps track of how much we want to reserve, and lazily creates
// the right kind of vector upon actual emplace_back / push_back.
class EmptyVectorObject : public VectorObject
{
	size_t reserved;

public:
	EmptyVectorObject() : reserved(0) {}

	bool needs_flattening() const override { return false; }
	bool flattens_to_doubles() const override { return true; }
	std::shared_ptr<VectorObject> flatten() override { return shared_from_this(); }

	std::shared_ptr<VectorObject> reserve(size_t s) override
	{
		reserved = max(reserved, s);
		return shared_from_this();
	}
	std::shared_ptr<GenericVectorObject> to_generic() override
	{
		return make_generic_vector(reserved);
	}
	std::shared_ptr<VectorObject> push_back(double value) override
	{
		return make_double_vector(reserved)->push_back(value);
	}
	std::shared_ptr<VectorObject> emplace_back(Value &&value) override
	{
		if (val.type() == Value::Type::NUMBER) {
			return push_back(val.toDouble());
			// } else if (val.type() == Value::Type::VECTOR &&
			// dynamic_pointer_cast<Vector3dObject>(val.toVector().ptr)) {
			//   return std::make_shared<Matrix3dObject>()->push_back(val);
			// } else if (val.type() == Value::Type::VECTOR &&
			// dynamic_pointer_cast<Vector4dObject>(val.toVector().ptr)) {
			//   return std::make_shared<Matrix4dObject>()->push_back(val);
		}
		else {
			return to_generic()->emplace_back(value);
		}
	}

	bool operator<(const VectorObject &v) const override
	{
		return !dynamic_cast<EmptyVectorObject *>(&v);
	}

	size_t size() const override { return 0; }
};

class GenericVectorObject : public VectorObject
{
	size_t embed_excess;
	bool embeds_flatten_to_double;

public:
	std::vector<Value> vec;

	GenericVectorObject(std::vector<Value> &&v) : vec(std::move(v)) {}
	GenericVectorObject(size_t capacity) { vec.reserve(capacity); }
	GenericVectorObject() {}
	virtual ~GenericVectorObject();

	std::shared_ptr<VectorObject> reserve(size_t s) override
	{
		vec.reserve(s);
		return shared_from_this();
	}
	std::shared_ptr<GenericVectorObject> to_generic() override { return shared_from_this(); }
	std::shared_ptr<VectorObject> push_back(double x) override
	{
		vec.emplace_back(Value(x));
		return shared_from_this();
	}

	std::shared_ptr<VectorObject> emplace_back(Value &&value) override
	{
		vec.emplace_back(value);
		return shared_from_this();
	}

	bool operator<(const VectorObject &v) const override;

	size_t size() const override { return vec.size() + embed_excess; }
	const Value &genericValueAt(size_t i) const override { return vec[i]; }

protected:
	// Specialized handler for EmbeddedVectorTypes
	std::shared_ptr<VectorObject> emplace_back(EmbeddedVectorType &&mbed) override;

	bool needs_flattening() const override { return embed_excess > 0; }
	bool flattens_to_doubles() const override
	{
		return embeds_flatten_to_double && std::every(vec.begin(), vec.end(), [](auto &v) {
						 return v.type() == Value::Type::NUMBER;
					 });
	}
};

class DoubleVectorObject : public VectorObject
{
public:
	bool needs_flattening() const override { return false; }
	bool flattens_to_doubles() const override { return true; }
	virtual double doubleValueAt(size_t i) const = 0;

	bool operator<(const VectorObject &v) const override
	{
		// TODO: can we use Eigen for this?
		if (auto dvo = dynamic_cast<DoubleVectorObject *>(&v)) {
			if (size() == v.size()) {
				for (size_t i = 0, n = size(); i < n; i++) {
					auto a = doubleValueAt(i);
					auto b = dvo->doubleValueAt(i);
					if (a < b) return true;
					if (a != b) return false;
				}
				return false;
			}
		}
		return VectorObject::operator<(v);
	}
};

// Matrix <double , 4 , 1 > Vector4d ;
template <size_t N>
class VectorNdObject : public DoubleVectorObject
{
	size_t size;

public:
	typedef Eigen::Matrix<double, N, 1> VectorNd;
	VectorNd vector;

	VectorNdObject(VectorNd &&v, size_t s = N) : vector(std::move(v)), size(s) { assert(s <= N); }
	VectorNdObject() : size(0) {}

	std::shared_ptr<VectorObject> reserve(size_t s) override
	{
		if (s <= N) {
			return shared_from_this();
		}
		return appendTo(make_double_vector(s));
	}
	std::shared_ptr<GenericVectorObject> to_generic() override
	{
		return appendTo(make_generic_vector(/* capacity= */ N));
	}
	std::shared_ptr<VectorObject> push_back(double value) override
	{
		if (size == N) {
			return appendTo(make_double_vector(size + 1));
		}
		vector[size++] = value;
		return shared_from_this();
	}

	virtual std::shared_ptr<VectorObject> operator+(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a + b; }, v);
	}

	virtual std::shared_ptr<VectorObject> operator-(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a - b; }, v);
	}

	virtual std::shared_ptr<VectorObject> operator*(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a * b; }, v);
	}

	virtual std::shared_ptr<VectorObject> operator/(const VectorObject &v) const
	{
		return applyOp([](auto &a, auto &b) { return a / b; }, v);
	}

	std::shared_ptr<VectorObject> operator+(double v) const override
	{
		return VectorNdObject<N>(std::move(vector + v), size);
	}
	std::shared_ptr<VectorObject> operator-(double v) const override
	{
		return VectorNdObject<N>(std::move(vector - v), size);
	}
	std::shared_ptr<VectorObject> operator*(double v) const override
	{
		return VectorNdObject<N>(std::move(vector * v), size);
	}
	std::shared_ptr<VectorObject> operator/(double v) const override
	{
		return VectorNdObject<N>(std::move(vector / v), size);
	}

	size_t size() const override { return size; }

	double doubleValueAt(size_t i) const override
	{
		if (i > N) throw 0;
		return vector[i];
	}

private:
	template <class Op>
	std::shared_ptr<VectorObject> applyOp(const Op &op, const VectorObject &v) const
	{
		if (auto vd = dynamic_cast<VectorNdObject<N>>(&v)) {
			return VectorNdObject<N>(std::move(op(vector, vd->vector), min(size, vd->size)));
		}
		return VectorObject::applyOp(op, v);
	}

	const std::shared_ptr<VectorObject> &appendTo(const std::shared_ptr<VectorObject> &out)
	{
		for (size_t i = 0; i < N; i++) {
			out->push_back(vector[i]);
		}
		return out;
	}
};

class VectorXdObject : public DoubleVectorObject
{
	size_t size;

public:
	Eigen::VectorXd vector;

	VectorXdObject(Eigen::VectorXd &&v, size_t s) : vector(std::move(v)), size(s) {}
	VectorXdObject(size_t capacity) : size(0) { vector.resize(capacity); }

	std::shared_ptr<VectorObject> reserve(size_t s) override
	{
		if (size) {
			vector.conservativeResize(capacity);
		}
		else {
			vector.resize(capacity);
		}
		return shared_from_this();
	}
	std::shared_ptr<GenericVectorObject> to_generic() override
	{
		auto v = make_generic_vector(size());
		for (auto &x : vector) {
			v->emplace_back(Value(x));
		}
		return v;
	}
	std::shared_ptr<VectorObject> push_back(double value) override
	{
		if (size == vector.size() - 1) {
			reserve((size * 15) / 10 + 16);
		}
		vector[size++] = value;
		return shared_from_this();
	}

	size_t size() const override { return size; }
	double doubleValueAt(size_t i) const override
	{
		if (i > size) throw 0;
		return Value(vector[i]);
	}
};
// class Vector4dObject : public VectorObject {
//  public:
//   Eigen::Vector4d vector;
// };
// class Matrix3dObject : public VectorObject {
//  public:
//   Eigen::Matrix3d matrix;
// };
// class Matrix4dObject : public VectorObject {
//  public:
//   Eigen::Matrix4d matrix;
// };