1 /****************************************************************************
  2  Copyright (c) 2008-2010 Ricardo Quesada
  3  Copyright (c) 2011-2012 cocos2d-x.org
  4  Copyright (c) 2013-2014 Chukong Technologies Inc.
  5  Copyright (c) 2010 Sangwoo Im
  6 
  7  http://www.cocos2d-x.org
  8 
  9  Permission is hereby granted, free of charge, to any person obtaining a copy
 10  of this software and associated documentation files (the "Software"), to deal
 11  in the Software without restriction, including without limitation the rights
 12  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 13  copies of the Software, and to permit persons to whom the Software is
 14  furnished to do so, subject to the following conditions:
 15 
 16  The above copyright notice and this permission notice shall be included in
 17  all copies or substantial portions of the Software.
 18 
 19  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 20  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 21  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 22  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 23  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 24  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 25  THE SOFTWARE.
 26  ****************************************************************************/
 27 
 28 /**
 29  * The sortable object interface
 30  * @class
 31  * @extends cc.Class
 32  */
 33 cc.SortableObject = cc.Class.extend(/** @lends cc.SortableObject */{
 34     setObjectID:function (objectId) {
 35     },
 36     getObjectID:function () {
 37         return 0;
 38     }
 39 });
 40 
 41 /**
 42  * The SortedObject class
 43  * @class
 44  * @extends cc.SortableObject
 45  */
 46 cc.SortedObject = cc.SortableObject.extend(/** @lends cc.SortedObject */{
 47     _objectID:0,
 48 
 49     ctor:function () {
 50         this._objectID = 0;
 51     },
 52 
 53     setObjectID:function (objectID) {
 54         this._objectID = objectID;
 55     },
 56 
 57     getObjectID:function () {
 58         return this._objectID;
 59     }
 60 });
 61 
 62 var _compareObject = function (val1, val2) {
 63     return (val1.getObjectID() - val2.getObjectID());
 64 };
 65 
 66 /**
 67  * Array for object sorting utils
 68  * @class
 69  * @extend cc.Class
 70  */
 71 cc.ArrayForObjectSorting = cc.Class.extend(/** @lends cc.ArrayForObjectSorting# */{
 72     _saveObjectArr:null,
 73 
 74     ctor:function () {
 75         this._saveObjectArr = [];
 76     },
 77     /**
 78      * Inserts a given object into array.
 79      *
 80      * Inserts a given object into array with key and value that are used in
 81      * sorting. "value" must respond to message, compare:, which returns
 82      * (NSComparisonResult). If it does not respond to the message, it is appended.
 83      * If the compare message does not result NSComparisonResult, sorting behavior
 84      * is not defined. It ignores duplicate entries and inserts next to it.
 85      *
 86      * @function
 87      * @param {Object} addObject    Object to insert
 88      */
 89     insertSortedObject:function (addObject) {
 90         if(!addObject)
 91             throw "cc.ArrayForObjectSorting.insertSortedObject(): addObject should be non-null.";
 92         var idx = this.indexOfSortedObject(addObject);
 93         this.insertObject(addObject, idx);
 94     },
 95 
 96     /*!
 97      * Removes an object in array.
 98      *
 99      * Removes an object with given key and value. If no object is found in array
100      * with the key and value, no action is taken.
101      *
102      * @function
103      * @param {Object} delObject    Object to remove
104      */
105     removeSortedObject:function (delObject) {
106         if (this.count() === 0) {
107             return;
108         }
109 
110         var idx = this.indexOfSortedObject(delObject);
111         if (idx < this.count() && idx !== cc.INVALID_INDEX) {
112             var foundObj = this.objectAtIndex(idx);
113             if (foundObj.getObjectID() === delObject.getObjectID()) {
114                 this.removeObjectAtIndex(idx);
115             }
116         }
117     },
118 
119     /*!
120      * Sets a new value of the key for the given object.
121      *
122      * In case where sorting value must be changed, this message must be sent to
123      * keep consistency of being sorted. If it is changed externally, it must be
124      * sorted completely again.
125      *
126      * @function
127      * @param {Number} tag          Tag to set
128      * @param {Object} setObject    The object which would be set
129      */
130     setObjectID_ofSortedObject:function (tag, setObject) {
131         var idx = this.indexOfSortedObject(setObject);
132         if (idx < this.count() && idx !== cc.INVALID_INDEX) {
133             var foundObj = this.objectAtIndex(idx);
134             if (foundObj.getObjectID() === setObject.getObjectID()) {
135                 this.removeObjectAtIndex(idx);
136                 foundObj.setObjectID(tag);
137                 this.insertSortedObject(foundObj);
138             }
139         }
140     },
141 
142     objectWithObjectID:function (tag) {
143         if (this.count() === 0) {
144             return null;
145         }
146         var foundObj = new cc.SortedObject();
147         foundObj.setObjectID(tag);
148 
149         var idx = this.indexOfSortedObject(foundObj);
150         if (idx < this.count() && idx !== cc.INVALID_INDEX) {
151             foundObj = this.objectAtIndex(idx);
152             if (foundObj.getObjectID() !== tag)
153                 foundObj = null;
154         }
155         return foundObj;
156     },
157 
158     /*!
159      * Returns an object with given key and value.
160      *
161      * Returns an object with given key and value. If no object is found,
162      * it returns nil.
163      *
164      * @function
165      * @param {Number} tag  Tag to locate object
166      * @return {Object|null}
167      */
168     getObjectWithObjectID:function (tag) {
169         return null;
170     },
171 
172     /*!
173      * Returns an index of the object with given key and value.
174      *
175      * Returns the index of an object with given key and value.
176      * If no object is found, it returns an index at which the given object value
177      * would have been located. If object must be located at the end of array,
178      * it returns the length of the array, which is out of bound.
179      *
180      * @function
181      * @param {Number} idxObj   Id to locate object
182      * @return {Number} index of an object found
183      */
184     indexOfSortedObject:function (idxObj) {
185         var idx = 0;
186         if (idxObj) {
187             //       CCObject* pObj = (CCObject*)bsearch((CCObject*)&object, data.arr, data.num, sizeof(CCObject*), _compareObject);
188             // FIXME: need to use binary search to improve performance
189             var uPrevObjectID = 0;
190             var uOfSortObjectID = idxObj.getObjectID();
191 
192             var locObjectArr = this._saveObjectArr;
193             for (var i = 0; i < locObjectArr.length; i++) {
194                 var pSortableObj = locObjectArr[i];
195                 var curObjectID = pSortableObj.getObjectID();
196                 if ((uOfSortObjectID === curObjectID) ||
197                     (uOfSortObjectID >= uPrevObjectID && uOfSortObjectID < curObjectID)) {
198                     break;
199                 }
200                 uPrevObjectID = curObjectID;
201                 idx++;
202             }
203         } else {
204             idx = cc.INVALID_INDEX;
205         }
206         return idx;
207     },
208 
209     //implement array method
210     count:function () {
211         return this._saveObjectArr.length;
212     },
213 
214     lastObject:function () {
215         var locObjectArr = this._saveObjectArr;
216         if (locObjectArr.length === 0)
217             return null;
218         return locObjectArr[locObjectArr.length - 1];
219     },
220 
221     objectAtIndex:function (idx) {
222         return this._saveObjectArr[idx];
223     },
224 
225     addObject:function (addObj) {
226         this._saveObjectArr.push(addObj);
227         this._saveObjectArr.sort(_compareObject);
228     },
229 
230     removeObjectAtIndex:function (idx) {
231         this._saveObjectArr.splice(idx, 1);
232         this._saveObjectArr.sort(_compareObject);
233     },
234 
235     insertObject:function (addObj, idx) {
236         this._saveObjectArr.splice(idx, 0, addObj);
237         this._saveObjectArr.sort(_compareObject);
238     }
239 });
240