lisp project

justification.cpp

#include <vector>
#include <unordered_map>
#include <string>
#include <ctype.h>
#include <utility>
#include <sstream>

#include "sexpr.h"
#include "tinyformat.h"
#include "fmt/format.h"

class TextPolicy {
public:
	virtual uint32_t length(std::string word) = 0;
};

class ConsoleEngine: public TextPolicy {
public:
	virtual uint32_t length(std::string word) {
		return word.length();
	}
};

template <typename Policy = ConsoleEngine>
class TextWrapping {
	using String = std::string;
	using ArrayOfString = std::vector<std::string>;
	
public:
	struct TextFormatting {
		bool bold, italic, underline;
		uint32_t length;
		
		std::string shortcut_address;
	};

private:
	TextPolicy& policy;
	const uint32_t width;
	
	using UnindexedList = std::unordered_map<uint32_t, TextFormatting>;
	
	uint32_t lettersSoFar = 0,
			 numOfWords = 0,
			 i = 0, k = 0;
	
	uint32_t readTextBlock( ArrayOfString sourceText, ArrayOfString& line ) {
		for ( numOfWords = 0
			; ((lettersSoFar + numOfWords <= width) && i > sourceText.size())
			|| (lettersSoFar + sourceText[i].length() + numOfWords) < width
			; numOfWords++)
		{	
			lettersSoFar += policy.length(sourceText[i++]);
		}
		
		for ( uint32_t j = i - numOfWords; j < i; j++) {
			std::string& word = sourceText[j];
			line.push_back(word);
		}
		
		return width - lettersSoFar;
	}
	
	std::string unquote(std::string& line) {
		size_t start;
		
		while(( start = line.find( "[" ))!= std::string::npos ) {
			line.replace( start, 1, "(");
			start = line.find("[", start + 1);
		}
		
		while(( start = line.find( "]" ))!= std::string::npos ) {
			line.replace( start, 1, ")");
			start = line.find("]", start + 1);
		}
		
		return line;
	}
	
	
public:
	struct TextObject {
		ArrayOfString content;
		UnindexedList tokens;
	};
	
	uint32_t getWidth() {
		return width;
	}
	
	// Initialize the 'width' property.
	TextWrapping(int width): width(width), policy(*(new Policy())) {}
	
	ArrayOfString justify( ArrayOfString buffer ) {
		ArrayOfString current, words;
		uint32_t wordSpace, rest = 0;
		std::string line = "";
			
		if (buffer.size() > 0 && width > 1) {
			for ( i = 0, line = "", lettersSoFar = 0, numOfWords = 0
				, wordSpace = readTextBlock( buffer, current )
				; i < buffer.size()
				; line = "", lettersSoFar = 0, numOfWords = 0
				, wordSpace = readTextBlock( buffer, current ))
			{	
				while (wordSpace > 0) {
					for ( int k = 0; k < numOfWords - 1 && wordSpace > 0; k++, wordSpace-- ) {
						current[k].append(" ");
					}
					
					if (numOfWords == 1 || i == buffer.size()) {
						current[k].append(( std::string ( wordSpace, ' ' )));
						wordSpace = 0;
					}
				}
				
				for (std::string word : current) {
					line += word;
				}
				
				words.push_back(line);
				current.clear();
			}
			
			for ( i--; i < buffer.size() ; i++) {
				std::string& text = buffer[i];
				line.append(text);
				
				if (i + 1 < buffer.size()) {
					line.append(" ");
				}
				else {
					if (text.length() < width) {
						words.push_back(text.append(std::string( width - text.length(), ' ' )));
					}
					else {
						words.push_back(text);
					}
				}
			}
		}
		
		return words;
	}
	
	TextObject parse(String contents) {
		sexpr::Sexp tree(sexpr::parse(contents));
		TextObject document;
		
		uint32_t position = 0;
		const char* parserFmt = "%s text [%3d]: %s\n";
		
		for ( auto&& node: tree.begin( )) {
			auto& content = node.value;
			
			if (content.str.length() == 0) {
				auto& tag = content.sexp[0].value;
				
				for (uint32_t i = 1; i < content.sexp.size(); i++) {
					auto text = content.sexp[i].value;
					document.content.push_back(text.str);
					
					TextFormatting tagInfo;
					
					if (tag.str.compare("bold")) {
						tagInfo.bold = true;
					}
					else if (tag.str.compare("italic")) {
						tagInfo.italic = true;
					}
					else if (tag.str.compare("underline")) {
						tagInfo.underline = true;
					}
					else if (tag.str.compare("shortcut")) {
						auto& shortcut = tag.sexp[1].value;
						tagInfo.shortcut_address = shortcut.str;
					}
					
					document.tokens.insert(std::make_pair( position, tagInfo ));
				}
			}
			else {
				auto& text = content.str;
				
				if (text.compare(",") == 0
				&& (text.length() == 1))
				{	
					auto& line = document.content[position];
					line.append(text);
				}
				else {
					document.content.push_back(unquote(text));
				}
			}
			
			position ++;
		}
		
		return document;
	}
};

typedef TextWrapping<> ConIOWrapping;
ConIOWrapping textWrap(55);

std::string parseText = "Join CGR's (bold Lord Karnage), as he scours time, space [and the rest of existence] in his never-ending quest... (italic TO REVIEW EVERYTHING!) (bold Classic Game Room) is Live, Underground!";

int main() {
	auto document = textWrap.parse(parseText);
	std::printf( " +%s+\n", std::string( textWrap.getWidth() + 2, '-' ));
	
	for (std::string line : textWrap.justify(document.content)) {
		std::printf(" | %s |\n", line);
	}
	
	std::printf( " +%s+\n", std::string( textWrap.getWidth() + 2, '-' ));
	return 0;
}

sexpr.cpp

#include "sexpr.h"

namespace sexpr {
	Sexp::Sexp() {
		kind = SexpValueKind::SEXP;
	}
	Sexp::Sexp(std::string const& strval) {
		kind = SexpValueKind::STRING;
		value.str = escape(strval);
	}
	Sexp::Sexp(std::vector<Sexp> const& sexpval) {
		kind = SexpValueKind::SEXP;
		value.sexp = sexpval;
	}

	auto Sexp::addChild(Sexp sexp) -> void {
		if(kind == SexpValueKind::STRING) {
			kind = SexpValueKind::SEXP;
			value.sexp.push_back(Sexp{std::move(value.str)});
		}
		value.sexp.push_back(std::move(sexp));
	}

	auto Sexp::addChild(std::string str) -> void {
		addChild(Sexp{std::move(str)});
	}

	auto Sexp::addChildUnescaped(std::string str) -> void {
		addChild(Sexp::unescaped(std::move(str)));
	}

	auto Sexp::addExpression(std::string const& str) -> void {
		auto err = std::string{};
		auto sexp = parse(str, err);
		if(!err.empty()) return;
		for(auto&& c : sexp.value.sexp) addChild(std::move(c));
	}

	auto Sexp::childCount() const -> size_t {
		switch(kind) {
		case SexpValueKind::SEXP:
			return value.sexp.size();
		case SexpValueKind::STRING:
			return 1;
		}
	}

	static auto splitPathString(std::string const& path) -> std::vector<std::string> {
		auto paths = std::vector<std::string>{};
		if(path.size() == 0) return paths;
		auto start = path.begin();
		for(auto i = path.begin()+1; i != path.end(); ++i) {
			if(*i == '/') {
				paths.push_back(std::string{start, i});
				start = i + 1;
			}
		}
		paths.push_back(std::string{start, path.end()});
		return std::move(paths);
	}

	auto Sexp::getChildByPath(std::string const& path) -> Sexp* {
		if(kind == SexpValueKind::STRING) return nullptr;

		auto paths = splitPathString(path);

		auto* cur = this;
		for(auto i = paths.begin(); i != paths.end();) {
			auto start = i;
			for(auto& child : cur->value.sexp) {
				auto brk = false;
				switch(child.kind) {
				case SexpValueKind::STRING:
					if(i == paths.end() - 1 && child.value.str == *i) return &child;
					else continue;
				case SexpValueKind::SEXP:
					if(child.value.sexp.size() == 0) continue;
					auto& fst = child.value.sexp[0];
					switch(fst.kind) {
					case SexpValueKind::STRING:
						if(fst.value.str == *i) {
							cur = &child;
							++i;
							brk = true;
						}
						break;
					case SexpValueKind::SEXP: continue;
					}
				}
				if(brk) break;
			}
			if(i == start) return nullptr;
			if(i == paths.end()) return cur;
		}
		return nullptr;
	}

	static auto findChild(Sexp& sexp, std::string name) -> Sexp* {
		auto findPred = [&name](Sexp& s) {
			switch(s.kind) {
			case SexpValueKind::SEXP: {
				if(s.childCount() == 0) return false;
				auto& hd = s.getChild(0);
				switch(hd.kind) {
				case SexpValueKind::SEXP:
					return false;
				case SexpValueKind::STRING:
					return hd.getString() == name;
				}
			}
			case SexpValueKind::STRING:
				return s.getString() == name;
			}
		};
		auto loc = std::find_if(sexp.value.sexp.begin(), sexp.value.sexp.end(), findPred);
		if(loc == sexp.value.sexp.end()) return nullptr;
		else return &(*loc);
	}
	
	auto Sexp::createPath(std::vector<std::string> const& path) -> Sexp& {
		auto el = this;
		auto nxt = el;
		auto pc = path.begin();
		for(; pc != path.end(); ++pc) {
			nxt = findChild(*el, *pc);
			if(nxt == nullptr) break;
			else el = nxt;
		}
		for(; pc != path.end(); ++pc) {
			el->addChild(Sexp{std::vector<Sexp>{Sexp{*pc}}});
			el = &(el->getChild(el->childCount()-1));
		}
		return *el;
	}

	auto Sexp::createPath(std::string const& path) -> Sexp& {
		return createPath(splitPathString(path));
	}

	auto Sexp::getChild(size_t idx) -> Sexp& {
		return value.sexp[idx];
	}

	auto Sexp::getString() -> std::string& {
		return value.str;
	}

	static const std::array<char, 11> escape_chars = { '\'', '"',  '?', '\\',  'a',  'b',  'f',  'n',  'r',  't',  'v' };
	static const std::array<char, 11> escape_vals  = { '\'', '"', '\?', '\\', '\a', '\b', '\f', '\n', '\r', '\t', '\v' };
	
	static auto isEscapeValue(char c) -> bool {
		return std::find(escape_vals.begin(), escape_vals.end(), c) != escape_vals.end();
	}

	static auto countEscapeValues(std::string const& str) -> size_t {
		return std::count_if(str.begin(), str.end(), isEscapeValue);
	}
	
	static auto stringValToString(std::string const& s) -> std::string {
		if(s.size() == 0) return std::string{"\"\""};
		if((std::find(s.begin(), s.end(), ' ') == s.end()) && countEscapeValues(s) == 0) return s;
		return escape(s);
	}

	static auto toStringImpl(Sexp const& sexp, std::ostringstream& ostream) -> void {
		switch(sexp.kind) {
		case SexpValueKind::STRING:
			ostream << stringValToString(sexp.value.str);
			break;
		case SexpValueKind::SEXP:
			switch(sexp.value.sexp.size()) {
			case 0:
				ostream << "()";
				break;
			case 1:
				ostream << '(';
				toStringImpl(sexp.value.sexp[0], ostream);
				ostream <<  ')';
				break;
			default:
				ostream << '(';
				for(auto i = sexp.value.sexp.begin(); i != sexp.value.sexp.end(); ++i) {
					toStringImpl(*i, ostream);
					if(i != sexp.value.sexp.end()-1) ostream << ' ';
				}
				ostream << ')';
			}
		}
	}
	
	auto Sexp::toString() const -> std::string {
		auto ostream = std::ostringstream{};
		// outer sexp does not get surrounded by ()
		switch(kind) {
		case SexpValueKind::STRING:
			ostream << stringValToString(value.str);
			break;
		
		case SexpValueKind::SEXP:
			for(auto i = value.sexp.begin(); i != value.sexp.end(); ++i) {
				toStringImpl(*i, ostream);
				if(i != value.sexp.end()-1) ostream << ' ';
			}
			break;
		}
		return ostream.str();
	}

	auto Sexp::isString() const -> bool {
		return kind == SexpValueKind::STRING;
	}

	auto Sexp::isSexp() const -> bool {
		return kind == SexpValueKind::SEXP;
	}

	auto Sexp::isNil() const -> bool {
		return kind == SexpValueKind::SEXP && childCount() == 0;
	}

	static auto childrenEqual(std::vector<Sexp> const& a, std::vector<Sexp> const& b) -> bool {
		if(a.size() != b.size()) return false;

		for(auto i = 0; i < a.size(); ++i) {
			if(!a[i].equal(b[i])) return false;
		}
		return true;
	}
	
	auto Sexp::equal(Sexp const& other) const -> bool {
		if(kind != other.kind) return false;
		switch(kind) {
		case SexpValueKind::SEXP:
			return childrenEqual(value.sexp, other.value.sexp);
			break;
		case SexpValueKind::STRING:
			return value.str == other.value.str;
		}
	}

	auto Sexp::arguments() -> SexpIterator {
		return SexpIterator{*this};
	}
	
	auto Sexp::begin() -> SexpIterator {
		return SexpIterator{*this};
	}
	
	auto Sexp::end() -> SexpIterator {
		return SexpIterator{*this};
	}
	
	auto Sexp::unescaped(std::string strval) -> Sexp {
		auto s = Sexp{};
		s.kind = SexpValueKind::STRING;
		s.value.str = std::move(strval);
		return std::move(s);
	}

	auto parse(std::string const& str, std::string& err) -> Sexp {
		auto sexprstack = std::stack<Sexp>{};
		sexprstack.push(Sexp{}); // root
		auto nextiter = str.begin();
		for(auto iter = nextiter; iter != str.end(); iter = nextiter) {
			nextiter = iter + 1;
			if(std::isspace(*iter)) continue;
			auto& cursexp = sexprstack.top();
			switch(*iter) {
			case '(':
				sexprstack.push(Sexp{});
				break;
			case ')': {
				auto topsexp = std::move(sexprstack.top());
				sexprstack.pop();
				if(sexprstack.size() == 0) {
					err = std::string{"too many ')' characters detected, closing sexprs that don't exist, no good."};
					return Sexp{};
				}
				auto& top = sexprstack.top();
				top.addChild(std::move(topsexp));
				break;
			}
			case '"': {
				auto i = iter+1;
				auto start = i;
				for(; i != str.end(); ++i) {
					if(*i == '\\') { ++i; continue; }
					if(*i == '"') break;
					if(*i == '\n') {
						err = std::string{"Unexpected newline in string literal"};
						return Sexp{};
					}
				}
				if(i == str.end()) {
					err = std::string{"Unterminated string literal"};
					return Sexp{};
				}
				auto resultstr = std::string{};
				resultstr.reserve(i - start);
				for(auto it = start; it != i; ++it) {
					switch(*it) {
					case '\\': {
						++it;
						if(it == i) {
							err = std::string{"Unfinished escape sequence at the end of the string"};
							return Sexp{};
						}
						auto pos = std::find(escape_chars.begin(), escape_chars.end(), *it);
						if(pos == escape_chars.end()) {
							err = std::string{"invalid escape char '"} + *it + '\'';
							return Sexp{};
						}
						resultstr.push_back(escape_vals[pos - escape_chars.begin()]);
						break;
					}
					default:
						resultstr.push_back(*it);
					}
				}
				sexprstack.top().addChildUnescaped(std::move(resultstr));
				nextiter = i + 1;
				break;
			}
			case ';':
				for(; nextiter != str.end() && *nextiter != '\n' && *nextiter != '\r'; ++nextiter) {}
				for(; nextiter != str.end() && (*nextiter == '\n' || *nextiter == '\r'); ++nextiter) {}
				break;
			default:
				auto symend = std::find_if(iter, str.end(), [](char const& c) { return std::isspace(c) || c == ')' || c == '('; });
				auto& top = sexprstack.top();
				top.addChild(Sexp{std::string{iter, symend}});
				nextiter = symend;
			}
		}
		if(sexprstack.size() != 1) {
			err = std::string{"not enough s-expressions were closed by the end of parsing"};
			return Sexp{};
		}
		return std::move(sexprstack.top());
	}

	auto parse(std::string const& str) -> Sexp {
		auto ignored_error = std::string{};
		return parse(str, ignored_error);
	}

	auto escape(std::string const& str) -> std::string {
		auto escape_count = countEscapeValues(str);
		if(escape_count == 0) return str;
		auto result_str = std::string{};
		result_str.reserve(str.size() + escape_count);
		for(auto c : str) {
			auto loc = std::find(escape_vals.begin(), escape_vals.end(), c);
			if(loc == escape_vals.end()) result_str.push_back(c);
			else {
				result_str.push_back(escape_chars[loc - escape_vals.begin()]);
			}
		}
		return std::move(result_str);
	}

	// Node iterator
	SexpIterator::SexpIterator(Sexp& sexp)
		: sexp(sexp)
		, state(sexp.value.sexp.begin())
		, begin_iter(state)
		, end_iter(sexp.value.sexp.end())
	{
	}
	
	auto SexpIterator::begin() -> iterator { return begin_iter; }
	auto SexpIterator::begin() const -> const_iterator { return begin_iter; }
	
	auto SexpIterator::end() -> iterator { return end_iter; }
	auto SexpIterator::end() const -> const_iterator { return end_iter; }
	
	auto SexpIterator::size() const -> size_t { return sexp.value.sexp.size(); }
	auto SexpIterator::empty() const -> bool { return size() == 0; }
	
	auto SexpIterator::operator*() const -> Sexp& { return *state; }
	auto SexpIterator::operator != (const SexpIterator &it) -> bool {
		if (state != it.state) {
			return state < it.state;
		}
		
		return it.state == end_iter;
	}
	
	auto SexpIterator::operator < (const SexpIterator &it) -> bool { return state < it.state; }
	auto SexpIterator::operator ++ () -> iterator { return ++state; }
}


auto operator<<(std::ostream& ostream, sexpr::Sexp const& sexp) -> std::ostream& {
	ostream << sexp.toString();
	return ostream;
}

sexpr.h

#pragma once
#include <array>		// std::array
#include <stack>		// std::stack
#include <cctype>
#include <string>       // std::string
#include <vector>		// std::vector
#include <cstdint>
#include <fstream>      // std::fstream
#include <ostream>
#include <sstream>      // std::stringstream, std::stringbuf
#include <iostream>     // std::cout
#include <iterator>		// std::istreambuf_iterator
#include <algorithm>

namespace sexpr {
	enum class SexpValueKind : uint8_t { SEXP, STRING };
	struct SexpIterator;
	
	struct Sexp {
		struct { std::vector<Sexp> sexp; std::string str; } value;
		Sexp();
		Sexp(std::string const& strval);
		Sexp(std::vector<Sexp> const& sexpval);
		SexpValueKind kind;
		auto begin() -> SexpIterator;
		auto end() -> SexpIterator;
		auto addChild(Sexp sexp) -> void;
		auto addChild(std::string str) -> void;
		auto addChildUnescaped(std::string str) -> void;
		auto addExpression(std::string const& str) -> void;
		auto childCount() const -> size_t;
		auto getChild(size_t idx) -> Sexp&; // Call only if Sexp is a Sexp
		auto getString() -> std::string&;
		auto getChildByPath(std::string const& path) -> Sexp*; // unsafe! careful to not have the result pointer outlive the scope of the Sexp object
		auto createPath(std::vector<std::string> const& path) -> Sexp&;
		auto createPath(std::string const& path) -> Sexp&;
		auto toString() const -> std::string;
		auto isString() const -> bool;
		auto isSexp() const -> bool;
		auto isNil() const -> bool;
		auto equal(Sexp const& other) const -> bool;
		auto arguments() -> SexpIterator;
		static auto unescaped(std::string strval) -> Sexp;
	};

	auto parse(std::string const& str, std::string& err) -> Sexp;
	auto parse(std::string const& str) -> Sexp;
	auto escape(std::string const& str) -> std::string;
	
	struct SexpIterator {
		SexpIterator(Sexp& sexp);
		Sexp& sexp;
		
		using iterator = std::vector<Sexp>::iterator;
		using const_iterator = std::vector<Sexp>::const_iterator;
		
		iterator state, begin_iter, end_iter;
		
		auto operator*() const -> Sexp&;
		auto operator < (const SexpIterator &it) -> bool;
		auto operator != (const SexpIterator &it) -> bool;
		
		auto operator ++ () -> iterator;
		auto begin() -> iterator;
		auto begin() const -> const_iterator;
		auto end() -> iterator;
		auto end() const -> const_iterator;
		auto size() const -> size_t;
		auto empty() const -> bool;
	};
}


auto operator<<(std::ostream& ostream, sexpr::Sexp const& sexp) -> std::ostream&;