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      * @param {object} addObject
 87      */
 88     insertSortedObject:function (addObject) {
 89         if(!addObject)
 90             throw "cc.ArrayForObjectSorting.insertSortedObject(): addObject should be non-null.";
 91         var idx = this.indexOfSortedObject(addObject);
 92         this.insertObject(addObject, idx);
 93     },
 94 
 95     /*!
 96      * Removes an object in array.
 97      *
 98      * Removes an object with given key and value. If no object is found in array
 99      * with the key and value, no action is taken.
100      *
101      * @param value to remove
102      */
103     removeSortedObject:function (delObject) {
104         if (this.count() == 0) {
105             return;
106         }
107 
108         var idx = this.indexOfSortedObject(delObject);
109         if (idx < this.count() && idx != cc.INVALID_INDEX) {
110             var foundObj = this.objectAtIndex(idx);
111             if (foundObj.getObjectID() == delObject.getObjectID()) {
112                 this.removeObjectAtIndex(idx);
113             }
114         }
115     },
116 
117     /*!
118      * Sets a new value of the key for the given object.
119      *
120      * In case where sorting value must be changed, this message must be sent to
121      * keep consistency of being sorted. If it is changed externally, it must be
122      * sorted completely again.
123      *
124      * @param value to set
125      * @param object the object which has the value
126      */
127     setObjectID_ofSortedObject:function (tag, setObject) {
128         var idx = this.indexOfSortedObject(setObject);
129         if (idx < this.count() && idx != cc.INVALID_INDEX) {
130             var foundObj = this.objectAtIndex(idx);
131             if (foundObj.getObjectID() == setObject.getObjectID()) {
132                 this.removeObjectAtIndex(idx);
133                 foundObj.setObjectID(tag);
134                 this.insertSortedObject(foundObj);
135             }
136         }
137     },
138 
139     objectWithObjectID:function (tag) {
140         if (this.count() == 0) {
141             return null;
142         }
143         var foundObj = new cc.SortedObject();
144         foundObj.setObjectID(tag);
145 
146         var idx = this.indexOfSortedObject(foundObj);
147         if (idx < this.count() && idx != cc.INVALID_INDEX) {
148             foundObj = this.objectAtIndex(idx);
149             if (foundObj.getObjectID() != tag)
150                 foundObj = null;
151         }
152         return foundObj;
153     },
154 
155     /*!
156      * Returns an object with given key and value.
157      *
158      * Returns an object with given key and value. If no object is found,
159      * it returns nil.
160      *
161      * @param value to locate object
162      * @return object found or nil.
163      */
164     getObjectWithObjectID:function (tag) {
165         return null;
166     },
167 
168     /*!
169      * Returns an index of the object with given key and value.
170      *
171      * Returns the index of an object with given key and value.
172      * If no object is found, it returns an index at which the given object value
173      * would have been located. If object must be located at the end of array,
174      * it returns the length of the array, which is out of bound.
175      *
176      * @param value to locate object
177      * @return index of an object found
178      */
179     indexOfSortedObject:function (idxObj) {
180         var idx = 0;
181         if (idxObj) {
182             //       CCObject* pObj = (CCObject*)bsearch((CCObject*)&object, data.arr, data.num, sizeof(CCObject*), _compareObject);
183             // FIXME: need to use binary search to improve performance
184             var uPrevObjectID = 0;
185             var uOfSortObjectID = idxObj.getObjectID();
186 
187             var locObjectArr = this._saveObjectArr;
188             for (var i = 0; i < locObjectArr.length; i++) {
189                 var pSortableObj = locObjectArr[i];
190                 var curObjectID = pSortableObj.getObjectID();
191                 if ((uOfSortObjectID == curObjectID) ||
192                     (uOfSortObjectID >= uPrevObjectID && uOfSortObjectID < curObjectID)) {
193                     break;
194                 }
195                 uPrevObjectID = curObjectID;
196                 idx++;
197             }
198         } else {
199             idx = cc.INVALID_INDEX;
200         }
201         return idx;
202     },
203 
204     //implement array method
205     count:function () {
206         return this._saveObjectArr.length;
207     },
208 
209     lastObject:function () {
210         var locObjectArr = this._saveObjectArr;
211         if (locObjectArr.length == 0)
212             return null;
213         return locObjectArr[locObjectArr.length - 1];
214     },
215 
216     objectAtIndex:function (idx) {
217         return this._saveObjectArr[idx];
218     },
219 
220     addObject:function (addObj) {
221         this._saveObjectArr.push(addObj);
222         this._saveObjectArr.sort(_compareObject);
223     },
224 
225     removeObjectAtIndex:function (idx) {
226         this._saveObjectArr.splice(idx, 1);
227         this._saveObjectArr.sort(_compareObject);
228     },
229 
230     insertObject:function (addObj, idx) {
231         this._saveObjectArr.splice(idx, 0, addObj);
232         this._saveObjectArr.sort(_compareObject);
233     }
234 });
235