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