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 */ #ifndef ARRAYLIST_HPP_INCLUDED #define ARRAYLIST_HPP_INCLUDED #include <stdlib.h> #include <iostream> #include <string> #include <regex> #include <functional> template <class typeT> class ArrayList{ using type = typeT; private: type* arr; int max_index; const bool resizable; public: int length; /***@@CONSTRUCTORS@@***/ /**Constructor *@param arr_size being the size of the ArrayList *@param can_resize beng the DEFINITIVE resizable state */ ArrayList(int arr_size = 16, bool can_resize = true):resizable(can_resize){ 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 returns a copy of the ArrayList removing empty slots *@param a being the ArrayList to copy */ ArrayList(const ArrayList<type>& a):resizable(a.resizable){ 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; /*this->resizable = a.isResizable();*/ } /***@@DESTRUCTORS@@***/ ~ArrayList(){ free((void*)this->arr); } /***@@SUBSCRIPT@@***/ /**Subscript operator overload returning the element at the given index *@return The first element if the index is incorrect(if 0 sized then error), the wanted element if correct */ type operator[](int index){ int i = (this->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, type elem){ if(this->isValidIndex(index)){ this->arr[index] = elem; return true; } return false; } /***@@ACCESS@@***/ /**get resizable *@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 ArrayList *@return a clone of the 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(type elem){ if(isFull() && resizable){ type* new_arr = (type*)malloc((this->length+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 *@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) 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) */ 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 (OPTIONAL: default is 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 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 *@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, 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 (makes it empty) *@DEPRECATED *@NOTWORKING */ void reset(){ type* tmp = this->arr;//cache this->arr = (type*)malloc(max_index * sizeof(type));//allocate new memory this->length=0;//nullify length free((void*)tmp);//deallocate } /**Method that clears the ArrayList (makes it empty) *@DEPRECATED *@NOTWORKING */ void clean(){ this->reset(); } /**Method that clears the ArrayList (using splice) */ void clear(){ this->splice(0, this->length); } /**Method that removes the last element from the ArrayList *@return TRUE if removed, FALSE otherwaise */ bool pop(){ if(!this->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(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(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(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(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(type elem){ int index = indexOf(elem); if(index != -1) return this->splice(elem); 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 *@return a reference to the current object, which allows to chain operations */ ArrayList<type>& operator<<(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) ); } /**Assignment operator overload (equivalent to the copy constructor) *@param a being the ArrayList to make a copy of *@return a copy of the ArrayList */ ArrayList<type> operator=(const ArrayList<type>& a){ return ArrayList<type>(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&' and have a return type of 'void') */ void forEach(std::function<void(type&)> lambda){ for(auto elem : (*this)) lambda(elem); } /**Filtering *@param predicate being a function pointer/Functor/lambda function (must take an argument of type '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(std::function<bool(type)> predicate, bool can_resize = true){ ArrayList<type> ret; for(auto 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; } }; /**@@@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.