C++ ArrayList / JS Arrays (in one header file only)

/**Requirements: *typeT must be either a class (ex: 'class Car' leads to 'ArrayList<Car>'), an enumerated type (ex: 'struct Car' leads to 'ArrayList<Car>') or a standard type(ex: 'int' leads to 'ArrayList<int>') *typeT must have the operator == overloaded/defined *typeT must overload the assignment operator (and copy constructor is always good too) * *typeT may overload the comparison operator< (for sorting methods only) */ #ifndef ARRAYLIST_HPP_INCLUDED #define ARRAYLIST_HPP_INCLUDED #include <stdlib.h> #include <iostream> #include <string> #include <regex> #include <functional> #include <algorithm> #include <initializer_list> template <class typeT> class ArrayList{ using type = typeT; private: type* arr; int max_index; bool resizable; public: int length; /***@@CONSTRUCTORS@@***/ /**Constructor *@param arr_size being the size of the ArrayList *@param can_resize being the DEFINITIVE resizable state */ ArrayList(int arr_size = 16, bool can_resize = true):resizable(can_resize){ this->~ArrayList(); arr_size = (arr_size < 1) ? 1 : arr_size; this->max_index = arr_size;//define the unreachable index this->arr = (type*)malloc(arr_size * sizeof(type)); this->length = 0; /*this->resizable = can_resize;*/ } /**Copy constructor that copies an ArrayList (removes empty slots) *@param a being the ArrayList to copy */ ArrayList(const ArrayList<type>& a):resizable(a.resizable){ //this->~ArrayList(); type* tmp = this->arr; this->arr = (type*)malloc(a.length * sizeof(type)); free((void*)tmp); for(int i = 0 ; i < a.length ; i+=1){ this->arr[i] = a.arr[i]; } this->length = a.length; this->max_index = a.length; } /**Assignment operator overload (equivalent to the copy constructor) *@param a being the ArrayList to make a copy of *@return a reference to the current ArrayList (to chain =) */ ArrayList<type>& operator=(const ArrayList<type>& a){ //this->~ArrayList(); type* tmp = this->arr; this->arr = (type*)malloc(a.max_index * sizeof(type)); free((void*)tmp); for(int i = 0 ; i < a.length ; i+=1){ this->arr[i] = a.arr[i]; } this->length = a.length; this->max_index = a.max_index; this->resizable = a.resizable; return (*this); } /**Constructor via {} initilazier list *@param init_list being the initializer list passed * *@warning as a choice for the implementation, ArrayList created using this constructor are resizable */ ArrayList(const std::initializer_list<type>& init_list){ this->~ArrayList(); (*this) = ArrayList<type>(); for(type t : init_list) this->push(t); } /***@@DESTRUCTORS@@***/ ~ArrayList(){ free((void*)this->arr); } /***@@SUBSCRIPT@@***/ /**Subscript operator overload returning (a reference to) the element at the given index *@return The first element if the index is incorrect(if 0 sized then error), the requested element if correct */ type& operator[](int index){ int i = (isValidIndex(index)) ? index : 0; return this->arr[i]; } /***@@FUNCTOR@@***/ /**Functor to set the value at a given index *@param index being the index to set the value *@param elem being the new value *@return TRUE if it set the value, FALSE otherwise */ bool operator()(int index, const type& elem){ if(isValidIndex(index)){ this->arr[index] = elem; return true; } return false; } /***@@ACCESS@@***/ /**get resizable state (can never be modified) *@return resizable */ bool isResizable(){ return this->resizable; } /***@@HELPERS@@***/ /**Method determining whether an index is valid for this instance or not *@param i being the index that we want to test its validity *@return TRUE if valid, FALSE otherwise */ bool isValidIndex(int i){ return (i>=0 && i<length); } /**Method determining whether the ArrayList is empty or not *@return TRUE if empty, FALSE otherwise */ bool isEmpty(){ return this->length==0; } /**Method determining whether the ArrayList is full of not *@return TRUE if full, FALSE otherwise */ bool isFull(){ return this->length == this->max_index; } /***@@METHODS@@***/ /**Create a clone of the current ArrayList *@return a clone of the current ArrayList */ ArrayList<type> clone(){ return ArrayList(*this); } /**Add an element to the end of the ArrayList *@param elem being the element to add *@return TRUE if added, FALSE otherwise */ bool push(const type& elem){ if(isFull() && resizable){ type* new_arr = (type*)malloc((this->max_index+1) * sizeof(type));//create new arr that is 1unit bigger for(int i = 0 ; i < this->length ; i+=1){ new_arr[i] = this->arr[i];//copy old's value into new } new_arr[this->length] = elem;//add the passed element type* tmp = this->arr;//cache address for free this->arr = new_arr;//replace old with new free((void*)tmp);//free old this->max_index+=1;//incr this->length+=1; return true; } if(!isFull()){ this->arr[length] = elem;//add at this new index this->length += 1;//incr length return true; } return false; } /**Remove elements from the array starting at a given position *@param pos being the initial position *@param amount being the amount of elements to remove *@return TRUE if they have been removed, FALSE otherwise * *@DEPRECATED *@NOTWORKING */ bool old_splice(int pos, int amount = 1){ //Need Debug int right_index = -1; if(amount>0 && amount<=this->length && this->isValidIndex(pos)){ right_index = (pos+amount <= this->length) ? pos+amount : length;//calculate the right limit of the interval int delta = right_index - pos; for(int i = pos ; i < right_index ; i+=1){/*##mod condition (<= to <)##*/ if(i+delta < length) this->arr[i] = this->arr[i+delta];//moves to the left } type* new_arr = (type*)malloc(this->max_index * sizeof(type));//new alloc /*length -= (amount >= length) ? length-pos : amount;*///decrease length length-=delta; for(int i = 0 ; i < length ; i+=1){ new_arr[i] = this->arr[i];//copy into newly allocated arr } type* tmp = this->arr;//get address to free afterward this->arr = new_arr;//replace with new array free((void*)tmp);//free old one return true; } return false; } /**Remove elements from the array starting at a given position *@param pos being the initial position *@param amount being the amount of elements to remove (default: 1) *@return TRUE if they have been removed, FALSE otherwise */ bool splice(int pos, int amount=1){ if(amount > 0){ amount = (pos+amount>length) ? length-pos/*-1*/ : amount; type* new_arr = (type*)malloc(this->max_index * sizeof(type)); for(int i = 0 ; i < length ; i+=1){ if(i < pos){ new_arr[i] = this->arr[i]; }else{ if(length > 1 && i+1<length) new_arr[i] = this->arr[i+1]; } } length -= amount; type* tmp = this->arr; this->arr = new_arr; free((void*)tmp); return true; } return false; } /**Method that deallocate memory used by the inner array (does not delete the object) (dunno why you'd do that but you can) */ void exterminate(){ free((void*)(this->arr)); } /**Method that creates a copy of the ArrayList as an array (pointer) *@return a pointer to the copy of the array */ type* asPointer(){ type* ret = (type*)malloc(length * sizeof(type));//allocate memory to the return pointer for(int i = 0 ; i < this->length ; i+=1){ ret[i] = this->arr[i]; } return ret; } /**Method that creates a copy of the ArrayList as an array (pointer) *@return a pointer to the copy of the array */ type* asArray(){ return this->asPointer(); } /**Class method that creates an ArrayList from an array(pointer) *@param given_array being the array(pointer) *@param GA_length being the length of the given array (do not respect this at your own risks) *@param can_resize being the final value for the resizable state of the ArrayList (default: true) *@return an ArrayList containing the elements that were contained in the array (same order) if everything went well, a non viable ArrayList otherwise *@HowToUse ArrayList<someType> arr = ArrayList<someType>::newFromArrayPointer(pointer_of_someType, some_length, wanna_resize_or_not) */ static ArrayList<type> newFromArrayPointer(type* given_array, int GA_length, bool can_resize = true){ ArrayList<type> ret(GA_length, can_resize);//create a cache object for(int i = 0 ; i < GA_length ; i+=1){ bool pushed; try{ pushed = ret.push(given_array[i]);//try to push everything in the empty cache object if(!pushed) throw 911; }catch(int x){ std::cout << "Error, call " << x << "!\n" << "There has been an error creating an ArrayList from the array at the address< " << given_array <<" >therefore creation has been aborted and the returned ArrayList is not complete"; } if(!pushed) break;//legit break } return ArrayList(ret);//return a usable object } /**Method inserting an element into the array at a given index *@param index being the index we want to put the value at *@param elem being the value *@return TRUE if inserted, FALSE otherwise */ bool insertAt(int index, const type& elem){ if(!(index>=0 && index<=this->length)) return false; if(isFull() && resizable){ type* new_arr = (type*)malloc((length + 1) * sizeof(type));//allocate 1unit more memory for(int i = 0 ; i < length ; i+=1){ new_arr[i] = this->arr[i];//copy values } type* tmp = this->arr;//cache old to use free later on this->arr = new_arr; free((void*)tmp); return this->insertAt(index, elem); } if(!isFull()){ for(int i = 0 ; i < length ; i+=1){//loop through the array if(i == index){//find the index /*starts at length since we didn't increment the length prior to this point*/ for(int j = length ; j >= i+1 ; j-=1){//ladder climbing value sorting this->arr[j] = this->arr[j-1]; } this->arr[i] = elem;//set value this->length+=1;//incr length return true; } } if(index == this->length) return this->push(elem); } return false; } /**Method that clears the ArrayList (using splice) */ void clear(){ this->splice(0, this->length); //(*this) = ArrayList<type>(max_index, resizable); } /**Method that resets the ArrayList via assignment */ void reset(){ (*this) = ArrayList<type>(max_index, resizable); } /**Method that removes the last element from the ArrayList *@return TRUE if removed, FALSE otherwaise */ bool pop(){ if(!isEmpty()) return this->splice(length-1); return false; } /**Method that removes the first element from the ArrayList *@return TRUE if removed, FALSE otherwise */ bool shift(){ if(!isEmpty()) return this->splice(0); return false; } /**Method that inserts an element at the front of the ArrayList *@param elem being the element to insert *@return TRUE if inserted, FALSE otherwise */ bool unshift(const type& elem){ if(isEmpty()) return push(elem); if((isFull() && resizable) || !isFull()) return insertAt(0, elem); return false; } /**Method that returns the first index of a given element *@param elem being the element we are looking for *@return -1 if not in the ArrayList, its first index otherwise */ int indexOf(const type& elem){ for(int i = 0 ; i < length ; i+=1){ if(this->arr[i] == elem) return i; } return -1; } /**Method that determines whether the ArrayList contains the given element or not *@param elem being the element *@return TRUE if in the ArrayList, FALSE otherwise */ bool contains(const type& elem){ return this->indexOf(elem) != -1; } /**Method that returns the last index of the elem *@param elem being the element to find the index of *@return -1 if not in the ArrayList, its last index otherwise */ int lastIndexOf(const type& elem){ int ret = -1; for(int i = 0 ; i < length ; i+=1){ if(this->arr[i] == elem){ ret = i; } } return ret; } /**Method that removes the first occurrence of an element from the ArrayList *@param elem being the element to remove *@return TRUE if removed, FALSE otherwise */ bool remove(const type& elem){ int index = indexOf(elem); if(index != -1) return this->splice(index); return false; } /**Method that removes an element from its index in the ArrayList (you could still use splice instead) *@param index being the index of the element to remove *@param choiceSafety being a safety mechanism (due to method overloading) to ensure that you remove from index and not from an element (if you don't wanna use the safety system, go for splice instead) *@return TRUE if removed, FALSE otherwise */ bool remove(int index, bool choiceSafety){ if(this->isValidIndex(index)) return this->splice(index); return ; } /***@@OPERATORS@@***/ /**Stream Operator IN that allows to push and chain operations (no boolean safety) *@param elem being the element to insert at the end of the ArrayList *@return a reference to the current object, which allows to chain operations */ ArrayList<type>& operator<<(const type& elem){ this->push(elem); return (*this); } /**Stream Operator OUT that allows to pop and chain operations (no boolean safety) *@param amount being the amount of element to pop from the ArrayList (cf. pop) */ ArrayList<type>& operator>>(int amount){ if(!isEmpty() && amount>0){ int nb = (amount > length) ? length : amount; for(int i = 0 ; i < nb ; i+=1){ pop(); } } return (*this); } /**< that allows to compare lengths *@param a being the other ArrayList *@return TRUE if <, FALSE otherwise */ bool operator<(const ArrayList<type>& a)const{ return this->length < a.length; } /**> that allows to compare lengths *@param a being the other ArrayList *@return TRUE if >, FALSE otherwise */ bool operator>(const ArrayList<type>& a)const{ return this->length > a.length; } /**<= that allows to compare lengths *@param a being the other ArrayList *@return TRUE if <=, FALSE otherwise */ bool operator<=(const ArrayList<type>& a)const{ return (*this)<a || this->length==a.length; } /**>= that allows to compare lengths *@param a being the other ArrayList *@return TRUE if >=, FALSE otherwise */ bool operator>=(const ArrayList<type>& a)const{ return (*this)>a || this->length==a.length; } /**== that allows to tell if an ArrayList is equivalent to an other ArrayList *@param a being the other ArrayList *@return TRUE if they have the same elements in the same order, FALSE otherwise */ bool operator==(ArrayList<type>& a){ if(a.length != this->length) return false; for(int i = 0 ; i < a.length ; i+=1){ if(a[i] != this->arr[i]) return false; } return true; } /**!= that allows to tell if an ArrayList is not equivalent to an other ArrayList *@param a being the other ArrayList *@return TRUE if not equivalent, FALSE otherwise */ bool operator!=(ArrayList<type>& a){ return !( this->operator==(a) ); } /***@@DEBUG@@***/ /**Debug helper that displays in a "fancy" way the content of the ArrayList */ void disp(){ for(int i = 0 ; i < this->length ; i+=1) std::cout << "Item #" << i << " : " << (*this)[i] <<'\n'; } /**Debug helper that displays in a "fancy" way the content of the ArrayList *@param tab being a string made of tabulations only (if not, replace by empty string via regex) */ void disp(std::string tab){ try{ std::regex re("^(\\t*)$"); std::smatch match; if( !(std::regex_search(tab, match, re) && match.size() > 1) ){ tab = std::string(""); } }catch(const std::regex_error& e){ std::cout<<"Regex Error on member function 'disp(std::string)'"<<'\n'; } for(int i = 0 ; i < this->length ; i+=1) std::cout << tab << "Item #" << i << " : " << (*this)[i] << '\n'; } /***@@ADVANCEDCOMPATIBILITY@@***/ /**Advanced for-loop compatibility - begin *@return a pointer to the first slot */ type* begin(){ return &(arr[0]); } /**Advanced for-loop compatibility - end *@return a pointer to the slot after the last slot (the unreachable/should not be reached index) */ type* end(){ return &(arr[length]); } /***@@@FUNCTIONALaddons@@***/ /**Execute a function on each element of the ArrayList *@param lambda being a function pointer/Functor/lambda function (must take an argument of type 'type&' (reference to element) and have a return type of 'void') */ void forEach(const std::function<void(type&)>& lambda){ for(type& elem : (*this)) lambda(elem); } /**Execute a function on each element of the ArrayList *@param lambda being a function pointer/Functor/lambda function (must take an argument of type 'int' (index of element) and an argument of type 'type&' (reference to element) and have a return type of 'void') */ void forEach(const std::function<void(int, type&)>& lambda){ for(int i = 0 ; i < length ; i+=1) lambda(i, this->operator[](i)); } /**Filtering (keep) *@param predicate being a function pointer/Functor/lambda function (must take an argument of type 'const type&' and have a return type of 'bool') *@param can_resize being here to set if the returned ArrayList can be resize or not (default: TRUE) */ ArrayList<type> filter(const std::function<bool(const type&)>& predicate, bool can_resize = true){ ArrayList<type> ret; for(const type& elem : (*this)){ if(predicate(elem)) ret.push(elem); } type* tmp_ptr = ret.asPointer(); ret = ArrayList<type>::newFromArrayPointer(tmp_ptr, ret.length, can_resize); free((void*)tmp_ptr); return ret; } /**Filtering (remove) *@param predicate being a function pointer/Functor/lambda function (must take an argument of type 'const type&' and have a return type of 'bool') *@param can_resize being here to set if the returned ArrayList can be resize or not (default: TRUE) */ ArrayList<type> filterOut(const std::function<bool(const type&)>& predicate, bool can_resize = true){ ArrayList<type> ret; for(const type& elem : (*this)){ if(!predicate(elem)) ret.push(elem); } type* tmp_ptr = ret.asPointer(); ret = ArrayList<type>::newFromArrayPointer(tmp_ptr, ret.length, can_resize); free((void*)tmp_ptr); return ret; } /**Self filtering (keep) *@param predicate being a function pointer/Functor/lambda function (must take an argument of type 'const type&' and have a return type of 'bool') */ ArrayList<type>& selfFilter(const std::function<bool(const type&)>& predicate){ this->operator=( this->filter(predicate, resizable) ); return (*this); } /**Self filtering (remove) *@param predicate being a function pointer/Functor/lambda function (must take an argument of type 'const type&' and have a return type of 'bool') */ ArrayList<type>& selfFilterOut(const std::function<bool(const type&)>& predicate){ this->operator=( this->filterOut(predicate, resizable) ); return (*this); } /***@@SmallUtilitiesOrAliases@@***/ /**Sets the value at the specified index *@param index being the index of the element we want to set the value of *@param value being the actual value *@return TRUE if set, FALSE otherwise */ bool set(int index, const type& value){ return (*this)(index, value); } /**Gets the value at the specified index *@param index being the index of the element we want to get *@return the element if a correct index, the first element otherwise */ type get(int index){ return (*this)[index]; } /**Adds an element at the end of the array (Java-style) *@param elem being the element to add to the array *@return TRUE if added, FALSE otherwise */ bool add(const type& elem){ return this->push(elem); } /**Insert an element at a given index (Java-style) *@param index being the index you want to insert the element at *@param elem being the element to insert *@return TRUE if inserted, FALSE otherwise */ bool add(int index, const type& elem){ return this->insertAt(index, elem); } /**Swap elements *@param a being the index of the first element *@param b being the index of the second element */ void swap(int a, int b){ if(!isValidIndex(a) || !isValidIndex(b)) return; std::swap(this->arr[a], this->arr[b]); } /***@@SORTING@@***/ /**std sort specialization *@param beginning being the index from where to start sorting (inclusive) *@param ending being the index from where to stop sorting (inclusive) *@param sortPredicate being a pointer to a function/Functor/Lambda function that compare two elements of type 'typeT' * *@principle sortPredicate(a, b)==true implies that indexOf(a) < indexOf(b) *@requirements if no predicate is given, then it uses the < operator to sort *(therefore overload < if you want to sort without predicate) */ void sort(){this->sort(0, length-1);} void sort(int beginning, int ending){ if(isValidIndex(beginning) && beginning<ending && isValidIndex(ending)) std::sort(this->begin()+beginning, this->begin()+ending+1); } void sort(const std::function<bool(const type&, const type&)>& sortPredicate){ this->sort(0, length-1, sortPredicate); } void sort(int beginning, int ending, const std::function<bool(const type&, const type&)>& sortPredicate){ if(isValidIndex(beginning) && beginning<ending && isValidIndex(ending)) std::sort(this->begin()+beginning, this->begin()+ending+1, sortPredicate); } /**std qsort specialization *@param sortFunc being a pointer to a function/Functor/Lambda function that compare two elements of type 'typeT' * *@principle sortFunc(a, b)<0 implies that indexOf(a) < indexOf(b) (you might need to implement >0 and ==0 too) *@requirements if no predicate is given, then it uses the < operator to sort *(therefore overload < if you want to sort without comparison function) *@requirements Comparator must be a type which use of operator() is as follows *(const void*, const void*)->int (usual comparison functions) */ void qsort(){ std::qsort((void*)this->arr, length, sizeof(type), [](const void* x, const void* y)->int{ type a = *static_cast<const type*>(x); type b = *static_cast<const type*>(y); if(a == b) return 0; if(a < b) return -1; return 1; }); } template <class Comparator> void qsort(const Comparator& sortFunc){ std::qsort((void*)this->arr, length, sizeof(type), sortFunc); } }; /**@@@ADDFUNCTIONALITIES@@@**/ #endif // ARRAYLIST_HPP_INCLUDED