Skip List based implementation of the set interface. More...

#include <sets.h>

Inheritance diagram for original::JSet< TYPE, Compare, ALLOC >:

Collaboration diagram for original::JSet< TYPE, Compare, ALLOC >:

Classes
class	Iterator
	Forward iterator for JSet. More...

Public Member Functions
	JSet (Compare comp=Compare{}, ALLOC alloc=ALLOC{})
	Constructs empty JSet.

	JSet (const JSet &other)
	Copy constructor.

JSet &	operator= (const JSet &other)
	Copy assignment operator.

	JSet (JSet &&other) noexcept
	Move constructor.

JSet &	operator= (JSet &&other) noexcept
	Move assignment operator.

u_integer	size () const override
	Gets number of elements.

bool	contains (const TYPE &e) const override
	Checks if element exists.

bool	add (const TYPE &e) override
	Adds new element.

bool	remove (const TYPE &e) override
	Removes element.

Iterator *	begins () const override
	Gets begin iterator.

Iterator *	ends () const override
	Gets end iterator.

std::string	className () const override
	Gets class name.

std::string	toString (bool enter) const override
	Converts to string representation.

	~JSet () override
	Destructor.

Public Member Functions inherited from original::iterable< const TYPE >
auto	forEach (Callback operation) -> void

auto	forEach (const Callback &operation) const -> void

iterAdaptor	begin ()
	Returns an iterator adapter pointing to the beginning of the container.

iterAdaptor	begin () const
	Returns a const iterator adapter pointing to the beginning of the container.

iterAdaptor	end ()
	Returns an iterator adapter pointing to the end sentinel of the container.

iterAdaptor	end () const
	Returns a const iterator adapter pointing to the end sentinel of the container.

iterAdaptor	first ()
	Returns an iterator adapter pointing to the first element.

iterAdaptor	first () const
	Returns a const iterator adapter pointing to the first element.

iterAdaptor	last ()
	Returns an iterator adapter pointing to the last element.

iterAdaptor	last () const
	Returns a const iterator adapter pointing to the last element.

void	forEach (Callback operation=Callback{})
	Applies a given operation to each element in the iterable container.

void	forEach (const Callback &operation=Callback{}) const
	Applies a given operation to each element in the iterable container (const version).

auto	forEach (Callback operation) -> void

auto	forEach (const Callback &operation) const -> void

Public Member Functions inherited from original::printable
	operator std::string () const
	Explicit conversion to std::string.

	operator const char * () const
	Explicit conversion to C-style string.

const char *	toCString (bool enter) const
	Direct C-string access with formatting control.

template<typename TYPE>
auto	formatString (const TYPE &t) -> std::string

template<typename TYPE>
auto	formatCString (const TYPE &t) -> const char *

template<typename TYPE>
auto	formatEnum (const TYPE &t) -> std::string

template<typename TYPE>
auto	formatString (TYPE *const &ptr) -> std::string

Friends
class	Iterator

Additional Inherited Members
Static Public Member Functions inherited from original::printable
template<typename TYPE>
static std::string	formatString (const TYPE &t)
	Universal value-to-string conversion.

template<typename TYPE>
static std::string	formatString (TYPE *const &ptr)
	Pointer-specific formatting.

template<typename TYPE>
static const char *	formatCString (const TYPE &t)
	C-string cache for temporary usage.

template<typename TYPE>
static std::string	formatEnum (const TYPE &t)
	Enum formatting utility.

template<>
auto	formatString (const char &t) -> std::string

template<>
auto	formatString (const bool &t) -> std::string

template<>
auto	formatString (const char *const &ptr) -> std::string

Detailed Description

template<typename TYPE, typename Compare = increaseComparator<TYPE>, typename ALLOC = allocator<couple<const TYPE, const bool>>>
class original::JSet< TYPE, Compare, ALLOC >

Skip List based implementation of the set interface.

Template Parameters

TYPE	Element type (must be comparable)
Compare	Comparison function type (default: increaseComparator<TYPE>)
ALLOC	Allocator type (default: allocator<couple<const TYPE, const bool>>)

This class provides a concrete implementation of the set interface using a probabilistic skip list. It combines the functionality of:

set (interface)
skipList (storage with bool values)
iterable (iteration support)

Performance Characteristics:

Insertion: Average O(log n), Worst O(n)
Lookup: Average O(log n), Worst O(n)
Deletion: Average O(log n), Worst O(n)

The implementation guarantees:

Elements sorted according to comparator
Unique elements (no duplicates)
Type safety
Exception safety (basic guarantee)
Iterator validity unless modified

Constructor & Destructor Documentation

◆ JSet() [1/3]

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC >::JSet	(	Compare	comp = Compare{},
		ALLOC	alloc = ALLOC{} )

explicit

Constructs empty JSet.

Parameters

comp	Comparison function to use
alloc	Allocator to use

◆ JSet() [2/3]

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC >::JSet ( const JSet< TYPE, Compare, ALLOC > & other )

Copy constructor.

Parameters

other JSet to copy

Performs deep copy of all elements and skip list structure

Note: Allocator is copied if propagate_on_container_copy_assignment is true

◆ JSet() [3/3]

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC >::JSet ( JSet< TYPE, Compare, ALLOC > && other )

noexcept

Move constructor.

Parameters

other JSet to move from

Transfers ownership of resources from other

Note: Leaves other in valid but unspecified state

◆ ~JSet()

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC >::~JSet ( )

overridedefault

Destructor.

Cleans up all skip list nodes and allocated memory

Note: O(n) time complexity

Member Function Documentation

◆ add()

template<typename TYPE, typename Compare, typename ALLOC>

bool original::JSet< TYPE, Compare, ALLOC >::add ( const TYPE & e )

override

Adds new element.

Parameters

e	Element to add

Returns: true if added, false if element existed

◆ begins()

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC >::Iterator * original::JSet< TYPE, Compare, ALLOC >::begins ( ) const

overridevirtual

Gets begin iterator.

Returns: New iterator at first element (minimum element)

Note: O(log n) time complexity to find first element

Implements original::iterable< const TYPE >.

◆ className()

template<typename TYPE, typename Compare, typename ALLOC>

std::string original::JSet< TYPE, Compare, ALLOC >::className ( ) const

nodiscardoverridevirtual

Gets class name.

Returns: "JSet"

Reimplemented from original::printable.

◆ contains()

template<typename TYPE, typename Compare, typename ALLOC>

bool original::JSet< TYPE, Compare, ALLOC >::contains ( const TYPE & e ) const

override

Checks if element exists.

Parameters

e	Element to check

Returns: true if element exists

◆ ends()

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC >::Iterator * original::JSet< TYPE, Compare, ALLOC >::ends ( ) const

overridevirtual

Gets end iterator.

Returns: New iterator at last element (maximum element)

Note: O(log n) time complexity to find last element

Implements original::iterable< const TYPE >.

◆ operator=() [1/2]

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC > & original::JSet< TYPE, Compare, ALLOC >::operator= ( const JSet< TYPE, Compare, ALLOC > & other )

Copy assignment operator.

Parameters

other JSet to copy

Returns: Reference to this JSet

Performs deep copy of all elements and skip list structure

Note: Allocator is copied if propagate_on_container_copy_assignment is true

◆ operator=() [2/2]

template<typename TYPE, typename Compare, typename ALLOC>

original::JSet< TYPE, Compare, ALLOC > & original::JSet< TYPE, Compare, ALLOC >::operator= ( JSet< TYPE, Compare, ALLOC > && other )

noexcept

Move assignment operator.

Parameters

other JSet to move from

Returns: Reference to this JSet

Transfers ownership of resources from other

Note: Leaves other in valid but unspecified state; Allocator is moved if propagate_on_container_move_assignment is true

◆ remove()

template<typename TYPE, typename Compare, typename ALLOC>

bool original::JSet< TYPE, Compare, ALLOC >::remove ( const TYPE & e )

override

Removes element.

Parameters

e	Element to remove

Returns: true if removed, false if element didn't exist

Note: Average O(log n), worst case O(n) time complexity

◆ size()

template<typename TYPE, typename Compare, typename ALLOC>

original::u_integer original::JSet< TYPE, Compare, ALLOC >::size ( ) const

nodiscardoverride

Gets number of elements.

Returns: Current size

◆ toString()

template<typename TYPE, typename Compare, typename ALLOC>

std::string original::JSet< TYPE, Compare, ALLOC >::toString ( bool enter ) const

nodiscardoverridevirtual

Converts to string representation.

Parameters

enter Add newline if true

Returns: String representation of elements

Note: O(n) time complexity

Reimplemented from original::printable.

The documentation for this class was generated from the following file:

src/core/sets.h

Classes

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ JSet() [1/3]

◆ JSet() [2/3]

◆ JSet() [3/3]

◆ ~JSet()

Member Function Documentation

◆ add()

◆ begins()

◆ className()

◆ contains()

◆ ends()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove()

◆ size()

◆ toString()