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
OPERATIONAL

My C++ implementation of a mix of Java's ArrayList and Javascript's arrays !

EDITS:
16 : added a "how to use" to newFromArrayPointer
17 : small bug fixes, unit tested everything (except indexOf and lastIndexOf that fails for seemingly no reason)
18 : added filter and forEach (functionnal), indexOf lastIndexOf forEach (and probably filter) are broken for now
19 : added filterOut (functionnal), above are still broken
20 : corrected some return types, above are still broken
21 : corrected all bad return types, fixed assignment operator, made resizable non-const (should not be modified for consistency's sake), fixed indexOf, fixed lastIndexOf, fixed forEach, fixed filter, fixed filterOut, added and fixed selfFilter, added and fixed selfFilterOut. Passed all 37 unit test cases, is considered operational from now on, all edits will be for adding methods
22 : removed swap (useless now, was a stupid hotfix)
23 : corrected typos and remove
24: corrected some return types, added sort (std::sort specialization)
25: corrected typos and comments, added qsort (std::qsort specialization) and Small Utilities and Aliases
26: added explicit call to destructor at the beginning of each constructor to avoid memory leaks
27: optimized code a bit
28: doxygen ready + small bug fixes

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.