/****************************************************************************
 *
 *   Copyright (c) 2015 Mark Charlebois. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 * 3. Neither the name PX4 nor the names of its contributors may be
 *    used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 ****************************************************************************/

#pragma once

class ORBSet
{
public:
	struct Node {
		Node *next{nullptr};
		const char *node_name{nullptr};
	};

	ORBSet() = default;

	~ORBSet()
	{
		while (_top != nullptr) {
			unlinkNext(_top);

			if (_top->next == nullptr) {
				free((void *)_top->node_name);
				_top->node_name = nullptr;

				delete _top;
				_top = nullptr;
			}
		}
	}

	void insert(const char *node_name)
	{
		Node **p;

		// Don't allow duplicates to be inserted
		if (find(node_name)) {
			return;
		}

		if (_top == nullptr) {
			p = &_top;

		} else {
			p = &_end->next;
		}

		*p = new Node();

		if (_end) {
			_end = _end->next;

		} else {
			_end = _top;
		}

		_end->next = nullptr;
		_end->node_name = strdup(node_name);
	}

	bool find(const char *node_name)
	{
		Node *p = _top;

		while (p) {
			if (strcmp(p->node_name, node_name) == 0) {
				return true;
			}

			p = p->next;
		}

		return false;
	}

	bool erase(const char *node_name)
	{
		Node *p = _top;

		if (_top && (strcmp(_top->node_name, node_name) == 0)) {
			p = _top->next;

			if (_top->node_name) {
				free((void *)_top->node_name);
				_top->node_name = nullptr;
			}

			delete _top;
			_top = p;

			if (_top == nullptr) {
				_end = nullptr;
			}

			return true;
		}

		while (p->next) {
			if (strcmp(p->next->node_name, node_name) == 0) {
				unlinkNext(p);
				return true;
			}
		}

		return false;
	}

private:

	void unlinkNext(Node *a)
	{
		Node *b = a->next;

		if (b != nullptr) {
			if (_end == b) {
				_end = a;
			}

			a->next = b->next;

			if (b->node_name) {
				free((void *)b->node_name);
				b->node_name = nullptr;
			}

			delete b;
			b = nullptr;
		}
	}

	Node *_top{nullptr};
	Node *_end{nullptr};
};