RopeList

RopeList.cpp

#include "RopeList.h"

#include <assert.h>
#include <stdio.h>
#include <algorithm>


RopeList::RopeList()
	:
	fRoot(NULL)
{
}


RopeList::~RopeList()
{
	MakeEmpty();
}


void
RopeList::PrintToStream()
{
	PrintToStreamInt(fRoot);
}


// #pragma mark - Adding and removing items


bool
RopeList::AddItem(Item* item, int32 index)
{
	if (item == NULL || item->list != NULL)
		return false;

	if (index < 0 || index > CountItems())
		return false;

	if (fRoot == NULL) {
		item->list = this;
		fRoot = item;
		return true;
	}

	fRoot = InsertInt(fRoot, item, index);
	item->list = this;
	fRoot->parent = NULL;

	return true;
}


bool
RopeList::AddItem(Item* item)
{
	return AddItem(item, CountItems());
}


bool
RopeList::MoveFrom(RopeList& srcList, int32 dstIndex, int32 srcIndex, int32 count)
{
	// TODO: implement
	return false;
}


bool
RopeList::RemoveItem(Item* item)
{
	return RemoveItem(IndexOf(item));
}


RopeList::Item*
RopeList::RemoveItem(int32 index)
{
	if (index < 0 || index >= CountItems())
		return NULL;

	if (fRoot->isLeaf) {
		Item* item = static_cast<Item*>(fRoot);
		item->list = NULL;
		fRoot = NULL;
		return item;
	}

	LeafNode* item = NULL;
	fRoot = RemoveInt(static_cast<IntNode*>(fRoot), item, index);
	fRoot->parent = NULL;

	item->list = NULL;
	item->parent = NULL;

	return static_cast<Item*>(item);
}


bool
RopeList::RemoveItems(int32 index, int32 count)
{
	// TODO: implement
	return false;
}


bool
RopeList::ReplaceItem(int32 index, Item* item)
{
	// TODO: implement
	return false;
}


void
RopeList::MakeEmpty()
{
	// TODO: implement
}


// #pragma mark - Reorder items


void
RopeList::SortItems(int (*compareFunc)(const Item*, const Item*))
{
	// TODO: implement
}


bool
RopeList::SwapItems(int32 indexA, int32 indexB)
{
	// TODO: implement
	return false;
}


bool
RopeList::MoveItem(int32 from, int32 to)
{
	// TODO: implement
	return false;
}


// #pragma mark - Retrieve items


RopeList::Item*
RopeList::ItemAt(int32 index) const
{
	if (index < 0 || index >= CountItems())
		return NULL;

	Node* node = fRoot;
	while (!node->isLeaf) {
		IntNode* intNode = static_cast<IntNode*>(node);
		int32 leftNodeLen = intNode->left->Length();
		if (index < leftNodeLen) {
			node = intNode->left;
		} else {
			index -= leftNodeLen;
			node = intNode->right;
		}
	}

	return static_cast<Item*>(node);
}


RopeList::Item*
RopeList::FirstItem() const
{
	return ItemAt(0);
}


RopeList::Item*
RopeList::LastItem() const
{
	return ItemAt(CountItems() - 1);
}


// #pragma mark - Query


bool
RopeList::HasItem(const Item* item) const
{
	return item != NULL && item->list == this;
}


int32
RopeList::IndexOf(const Item* item) const
{
	if (item == NULL || item->list != this)
		return -1;

	int32 index = 0;
	const Node* node = item;
	while (node->parent != NULL) {
		if (node->parent->right == node)
			index += node->parent->left->Length();

		node = node->parent;
	}

	return index;
}


int32
RopeList::CountItems() const
{
	return fRoot == NULL ? 0 : fRoot->Length();
}


bool
RopeList::IsEmpty() const
{
	return fRoot == NULL;
}
void
RopeList::DoForEach(bool (*func)(Item* item))
{
	// TODO: implement
}


void
RopeList::DoForEach(bool (*func)(Item* item, void* arg), void* arg)
{
	// TODO: implement
}



// #pragma mark -


int32
RopeList::Node::Height()
{
	return isLeaf ? 0 : static_cast<IntNode*>(this)->height;
}


int32
RopeList::Node::Length()
{
	return isLeaf ? 1 : static_cast<IntNode*>(this)->length;
}


RopeList::IntNode::IntNode(Node* left, Node* right)
	:
	Node(false),
	left(left),
	right(right)
{
	Update();
}


void
RopeList::IntNode::Update()
{
	height = std::max(left->Height(), right->Height()) + 1;
	length = left->Length() + right->Length();
	left->parent = this;
	right->parent = this;
}


int32
RopeList::IntNode::BalanceFactor()
{
	return right->Height() - left->Height();
}


// #pragma mark -


RopeList::IntNode*
RopeList::InsertInt(Node* node, LeafNode* item, int32 index)
{
	if (node->isLeaf) {
		if (index == 0)
			return new IntNode(item, node);
		else
			return new IntNode(node, item);
	}
	IntNode* intNode = static_cast<IntNode*>(node);
	int32 leftNodeLen = intNode->left->Length();
	if (index < leftNodeLen)
		intNode->left = InsertInt(intNode->left, item, index);
	else
		intNode->right = InsertInt(intNode->right, item, index - leftNodeLen);

	return Balance(intNode);
}


RopeList::Node*
RopeList::RemoveInt(IntNode* node, LeafNode*& item, int32 index)
{
	int32 leftNodeLen = node->left->Length();
	if (index < leftNodeLen) {
		if (node->left->isLeaf) {
			item = static_cast<LeafNode*>(node->left);
			Node* rem = node->right;
			delete node;
			return rem;
		}
		node->left = RemoveInt(static_cast<IntNode*>(node->left), item, index);
	} else {
		if (node->right->isLeaf) {
			item = static_cast<LeafNode*>(node->right);
			Node* rem = node->left;
			delete node;
			return rem;
		}
		node->right = RemoveInt(static_cast<IntNode*>(node->right), item, index - leftNodeLen);
	}
	return Balance(node);
}


RopeList::IntNode*
RopeList::RotateLeft(IntNode* q)
{
	IntNode* p = static_cast<IntNode*>(q->right);
	assert(!p->isLeaf);
	q->right = p->left;
	p->left = q;
	q->Update();
	p->Update();
	return p;
}


RopeList::IntNode*
RopeList::RotateRight(IntNode* p)
{
	IntNode* q = static_cast<IntNode*>(p->left);
	assert(!q->isLeaf);
	p->left = q->right;
	q->right = p;
	p->Update();
	q->Update();
	return q;
}


RopeList::IntNode*
RopeList::Balance(IntNode* p)
{
	p->Update();
	switch (p->BalanceFactor()) {
		case 2: {
			IntNode* rightIntNode = static_cast<IntNode*>(p->right);
			assert(!rightIntNode->isLeaf);
			if (rightIntNode->BalanceFactor() < 0)
				p->right = RotateRight(rightIntNode);

			return RotateLeft(p);
		}
		case -2: {
			IntNode* leftIntNode = static_cast<IntNode*>(p->left);
			assert(!leftIntNode->isLeaf);
			if (leftIntNode->BalanceFactor() > 0)
				p->left = RotateLeft(leftIntNode);

			return RotateRight(p);
		}
		default: {
			return p;
		}
	}
}


void
RopeList::Indent(int32 indent)
{
	for (int32 i = 0; i < indent; i++)
		printf("  ");
}


void
RopeList::PrintToStreamInt(Node* node, int32 indent, int32 index)
{
	if (node == NULL)
		return;

	if (node->isLeaf) {
		Indent(indent);
		printf("%" B_PRId32": LeafNode()\n", index);
		return;
	}

	IntNode* intNode = static_cast<IntNode*>(node);
	Indent(indent);
	printf("IntNode(%" B_PRId32 ", bf: %" B_PRId32 ")\n", intNode->Length(), intNode->BalanceFactor());
	PrintToStreamInt(intNode->left, indent + 1, index);
	PrintToStreamInt(intNode->right, indent + 1, index + intNode->left->Length());
}

RopeList.h

#pragma once

#include <SupportDefs.h>


class RopeList {
public:
	struct Item;

	RopeList();
	~RopeList();

	void PrintToStream();

	// Adding and removing items
	bool AddItem(Item* item, int32 index);
	bool AddItem(Item* item);
	bool MoveFrom(RopeList& srcList, int32 dstIndex, int32 srcIndex, int32 count);

	bool RemoveItem(Item* item);
	Item* RemoveItem(int32 index);
	bool RemoveItems(int32 index, int32 count);
	bool ReplaceItem(int32 index, Item* item);

	void MakeEmpty();

	// Reorder items
	void SortItems(int (*compareFunc)(const Item*, const Item*));
	bool SwapItems(int32 indexA, int32 indexB);
	bool MoveItem(int32 from, int32 to);

	// Retrieve items
	Item* ItemAt(int32 index) const;
	Item* FirstItem() const;
	Item* LastItem() const;

	// Query
	bool HasItem(const Item* item) const;
	int32 IndexOf(const Item* item) const;
	int32 CountItems() const;
	bool IsEmpty() const;

	// Iteration
	void DoForEach(bool (*func)(Item* item));
	void DoForEach(bool (*func)(Item* item, void* arg), void* arg);

private:
	struct IntNode;

	struct Node {
		IntNode* parent;
		bool isLeaf;

		Node(bool isLeaf) : isLeaf(isLeaf) {}

		inline int32 Height();
		inline int32 Length();
	};

	struct IntNode: public Node {
		Node* left;
		Node* right;
		int32 height;
		int32 length;

		inline IntNode(Node* left, Node* right);
		inline void Update();
		inline int32 BalanceFactor();
	};

	struct LeafNode: public Node {
		RopeList* list;

		LeafNode() : Node(true), list(NULL) {}
	};

public:
	struct Item: private LeafNode {
	private:
		friend class RopeList;
	};

private:
	IntNode* InsertInt(Node* node, LeafNode* item, int32 index);
	Node* RemoveInt(IntNode* node, LeafNode*& item, int32 index);

	IntNode* RotateLeft(IntNode* node);
	IntNode* RotateRight(IntNode* node);
	IntNode* Balance(IntNode* node);

	void Indent(int32 indent);
	void PrintToStreamInt(Node* node, int32 indent = 0, int32 index = 0);

private:
	Node* fRoot;
};