Class in Sqimitive Ordered

obj.mixIn(Sqimitive.Ordered)    // add to an instance (must be empty!)
Class.mixIn(Sqimitive.Ordered)  // or add to a class

// Or add to a class when declaring it:
var Class = Sqimitive.Base.extend({
  mixIns: [Sqimitive.Ordered],
  // ...
})

Properties

_ordered

Modifiers: protected

Holds positional information about objects contained within this instance.

Value Types

Types	Notes
array of object	Keys: Members Name Types Notes child object A Sqimitive in _children key string child’s key in _children pos any The value from nestEx’s options.pos

_ordered is a properly sorted array of _children, in order determined by _sorter(). It’s kept in sync with _children automatically.

The format of _ordered objects conveniently matches the format of object accepted by nestEx():

// Assuming both collections are Ordered and _owning, this removes
// the first child from col1 and inserts it in col2, preserving
// the same position and key:
col2.nestEx(col1.at(0))

You’re advised against accessing _ordered at all. Instead, use at().

Defined in: main.js, line 7410 • Show code

_ordered: [],

Methods

indexFor ( array, value, func, cx, oldIndex )

Modifiers: static

Part of: tag_Utilities

Determines insertion position for a new member value in a sorted array using binary search.

indexFor() is an adaptation of Underscore’s un:sortedIndex(). It supports two sort callback styles: relative ((a, b), as for Array’s sort()) and weight-based ((a), as for no:sortBy()).

First time func is called it’s given only 1 argument (value) and expected to return value’s weight (which is stored for later calls), then it’s called repeatedly to compare value against other members (returning < 0 if b must go before a, > 0 if after, == 0 if their sort order is the same and either can go in front of another).

In Ordered, indexFor() is used to maintain the order of children (in _ordered) using _sorter() for func. Usually there’s no need to call indexFor() directly.

cx is func’s context (required).

oldIndex is value’s current position in array. This allows checking if re-positioning is needed once value weight has possibly changed without pulling it out, as long as other members remain sorted. func with 3 arguments is never called for oldIndex.

Example

Relative func ignores the first call, otherwise is the same as with standard sort():

Sqimitive.Ordered.indexFor(a, v, function (a, b) {
  return a > b ? +1 : (a < b ? -1 : 0)
  // This would fail without a check because b may be null:
  return b && (a.prop - b.prop)
})

Weight-based func uses all 3 arguments:

Sqimitive.Ordered.indexFor(a, v, function (a, b, posB) {
  var posA = a.someWeightProp    // assuming it's a number
  return arguments.length == 1 ? posA : (posA - posB)
})

Example

indexFor() is generic and doesn’t have to be used for sorting. For example, given a slow pathfind() function, a long path (where members are {x, y} objects in order: first – the closest possible step, last – the goal) and the task of determining the farthest reachable path item:

// path = [ {x: 0, y: 0}, {x: 1, y: 0}, {x: 1, y: 1}, ... ]

for (var i = 0; i < path.length; i++) {
  if (!pathfind(path[i].x, path[i].y, maxCost)) { break }
}
  // path[i - 1] = last reachable item

The above code works but does up to path.length calls to pathfind() whereas this approach with indexFor() will do less calls on average:

var i = indexFor(_.range(path.length), null, function (a) {
  if (arguments.length > 1) {
    return pathfind(path[a].x, path[a].y, maxCost) ? -1 : +1
  }
})

Example

If oldIndex is given then result of oldIndex or oldIndex + 1 indicates that value is already in the correct position. Result of oldIndex + 2 and greater indicates that it should be moved after its current position, which usually means value is splice()’d from oldIndex and then splice()’d to result - 1.

indexFor([1, 3, 5], 2, (a, b) => a - b)            //=> 1
indexFor([1, 3, 5], 3, (a, b) => a - b, null, 1)   //=> 1 or 2
indexFor([1, 7, 5], 7, (a, b) => a - b, null, 1)   //=> 3

Defined in: main.js, lines 7925-7938 (14 lines) • Show code

indexFor: function (array, value, func, cx, oldIndex) {
  var pos = array.length && func.call(cx, value)
  var high = array.length - (array.length - 1 == oldIndex)
  for (var low = 0, rel = 1; low < high && rel; ) {
    var mid = low + high >>> 1
    rel = func.call(cx, array[mid + (mid == oldIndex)], value, pos)
    //! +ig
    // Exiting immediately if rel == 0 (found a member with the same sort
    // order) - low remains next to current index so order of ? : is
    // important and : must correspond to "<= 0".
    rel > 0 ? high = mid : low = mid + 1
  }
  return low
},

_repos ( child, index )

Modifiers: protected

Called when a child’s position has changed or was assumed for the first time.

Arguments

Name	Types	Notes
sqim	object	The child that has changed position.
index	int	sqim’s current (new) index in this; can be given to at()

Typically, you’d listen to/override this method to keep positions of children on screen (in their parent’s Base.el) in sync with their “logical” order (in this).

Example

Adapted code snippet from the sample To-Do application:

_repos: function (child, index) {
  index >= this.length - 1
    ? child.el.appendTo(this.el)
    : child.el.insertBefore(this.el.children()[index])
},

_repos() is called for newly nest’ed _children and those that have changed pos. It’s not called for removed children. The default implementation in Ordered does nothing.

_repos() is called before nestEx returns. An example when this matters:

// models holds data, views - its representations. Both are Ordered.
models.on({
  '+nestEx': function (res) {         // (1)
    views.nest(res.key, new View(...))
  },
  _repos: function (child, index) {   // (2)
    var key = child._parentKey
    views.nest(key, views.nested(key), {pos: index})
  },
})

models.nest(new Model(...))
// 1. models.nestEx inherited from Base runs
// 2. models.nestEx (_nested) inherited from Ordered runs
// 3. ...which fires models._repos
// 4. (2) runs first - views.nested() returns null leading to error
// 5. (1) would run once all _repos listeners including (2) were called

This can be properly rewritten as follows:

models.on({
  '+nestEx': function (res) {
    views.nest(res.key, new View(...), {pos: res.index})
  },
  _repos: function (child, index) {
    var view = views.nested(child._parentKey)
    view && views.nest(child._parentKey, view, {pos: index})
  },
})

resort() calls _repos() for all children (even if some didn’t change positions – this is hard to determine). Here, note Array’s forEach() implications: going in ascending order from child #0 to last, and if _repos() mutates children then _repos() is not called for some of them (so don’t mutate).

from plainstub

• This method returns nothing.
• It should not be called directly.

Defined in: main.js, line 7666

_sorter ( a, b, posB )

Modifiers: protected

The comparison function for determining desired child order.

Result Types

Types	Notes
< 0 if a must go before b
> 0 if it must go after
0 if they can go in any order; it’s generally recommended to avoid 0 to ensure that re-sorting the same array doesn’t result in a different order of members

You want to override _sorter() if you are not happy with the default implementation. If you do, see indexFor() for the invocation format. Default implementation compares using pos (if given to nestEx()) or key (if nesting using _defaultKey() then keys are _cid-s).

Example

Adapted code snippet from the sample To-Do application that is using the value of the order option of a given child if no explicit pos was provided for it when nesting:

'=_sorter': function (sup, a, b, posB) {
  var posA = a.pos == null ? a.child.get('order') : a.pos
  return arguments.length == 2 ? posA
    : (posA > posB ? +1 : (posA < posB ? -1
        // If properties match - sort stably by unique and constant _cid-s.
        : (a.child._cid - b.child._cid)))
},

a and b are objects in the _ordered format. b is null on the first iteration (see indexFor()). This object’s state is inconsistent when _sorter() is called so avoid accessing data outside of the given arguments:

• During nestEx() one of a/b may be missing from _ordered but present in _children.
• During resort() order of _ordered members is unspecified.

Note: if consumers of this object are using pos, make sure either they supply correct types or you normalize them in _sorter: number 10 is > 2 but string '10' is < '2'. Children keys are always cast to strings, such as here: nestEx({key: 10}).

Defined in: main.js, lines 7612-7617 (6 lines) • Show code

_sorter: function (a, b, posB) {
  a = a.pos == null ? a.key : a.pos
  return arguments.length == 1 ? a
    // Not simply a - posB to work with non-numeric key/pos.
    : (a > posB ? +1 : (a < posB ? -1 : 0))
},

at ( index )

Part of: tag_Utilities

Returns detailed info about a child by its index in this collection.

Result Types

Types	Notes
undefined
object entry in the format of _ordered

With at() you can obtain a child’s key or pos. Use it from util functions like each() which provide you with an index in _ordered (or in the result of slice()).

Warning: at() returns the object from _ordered verbatim – do not change it, or shallow-copy before you do.

Unlike slice(), at() does not accept negative index.

Example

sqim.at(0)        //=> {child: Sqimitive, key: 'foo', pos: 3}
sqim.at(999)      //=> undefined (if length <= 999)
sqim.at(-1)       //=> always undefined

this.groupBy(function (sqim, i) { return this.at(i).pos })
  //=> {pos1value: [child, ...], value2: [child, ...]}

// If clone is a non-_owning Ordered collection, populate it from orig:
orig.each(function (child, i) {
  clone.nestEx(orig.at(i))
})

// Using nest() is possible but will discard pos and keys of children:
orig.each(function (child) {
  clone.nest(child)
})

poskeyOne common pitfall when updating pos is passing a different key to nest() or nestEx(). In particular, omitting key of nest() means “take _defaultKey() value”, not “take current child’s _parentKey”.

var Collection = Sqimitive.Base.extend({
  _owning: false,
})
col = new Collection
col.nest('x', sqim1, {pos: 1})
col.nest('y', sqim2, {pos: 2})
col.nest(/*_defaultKey => sqim1._cid, */ sqim1, {pos: 3})
  // col now has 3 members: {1: sqim1, 2: sqim2, 3: sqim1}
col.nest('x', sqim1, {pos: 4})
  // changed pos of the first member: {2: sqim2, 3: sqim1, 4: sqim1}

Defined in: main.js, lines 7786-7788 (3 lines) • Show code

at: function (index) {
  return this._ordered[index]
},

nestEx ( options )

Ordered extends the inherited nestEx (typically Base.nestEx()) and handles new options keys:

Arguments

Name	Types	Notes
pos	any, optional	The caller may explicitly specify new child’s position relative to other children; pos may be used by _sorter() (in the default implementation it is).
repos	bool, optional	If set, acts as if pos was changed and re-calculates the child’s index.
index	number	Set on return to the actual position of the new child in _ordered; index can be given to at()
oldIndex	number	Only set on return if options.changed is unset.

If re-nesting the same child on the same key, Base.nestEx() does nothing but Ordered’s nestEx compares old and new options.pos. If they are not isEqual() or if repos is set, it updates the child’s position in _ordered and calls _repos() if it’s different. This doesn’t affect options.changed, it remains false even on _repos() but you can detect this situation by comparing index with oldIndex:

col.nestEx({child: sqim, pos: -123})   // new child, explicit pos
  //=> {..., changed: true, previous: null, index: 0}
col.nestEx({child: sqim, pos: 9000})   // existing child, changed pos
  //=> {..., changed: false, previous: sqim, index: 3, oldIndex: 0}

Example

repos is typically used when _sorter’s order depends on something other than key and pos – changes to these can be only done via nestEx() and are therefore handled automatically. Adapted code snippet from the sample To-Do application:

App.Tasks = App.Base.extend({
  _childEvents: ['change'],
  events: {
    '.change': function (sqim, option) {
      option == 'caption' && this.nest(sqim, {repos: true})
    },
    // Overridden _sorter:
    '=_sorter': function (sup, a, b, posB) {
      var posA = a.pos == null ? a.child.get('caption') : a.pos
      // ...
    },
  },
})

Compare with “external” approach based on pos alone:

App.Tasks = App.Base.extend({
  _childEvents: ['change'],
  events: {
    '.change': function (sqim, option, now) {
      option == 'caption' && this.nest(sqim, {pos: now})
    },
    // Default _sorter is good.
  },
})

Note: you must provide the child’s current key (or have (default) _defaultKey() do that as in these examples) to only update the order without re-nesting the child. See poskey for details.

Defined in: main.js, line 7413

pop ( )

Part of: tag_Utilities

Removes the last child and returns it.

from posh

Result Types

Types	Notes
object former child
undefined if empty

shift() and pop() allow treating an Ordered sqimitive as a queue (FIFO/LIFO). Use nest() with a counter to push/unshift.

Example

sqim.counter = 0
sqim.nest(new C1, {pos:  sqim.counter++})   // push
sqim.nest(new C2, {pos: -sqim.counter++})   // unshift
sqim.last()                                 //=> C1
sqim.first()                                //=> C2
sqim.pop()                                  //=> C1
sqim.shift()                                //=> C2
sqim.pop()                                  //=> undefined
sqim.shift()                                //=> undefined

Defined in: main.js, lines 7824-7827 (4 lines) • Show code

pop: function () {
  var entry = _.last(this._ordered)
  return entry && this.unlist(entry.key)
},

resort ( )

Re-sorts the entire collection from scratch.

Result Types

Types	Notes
this

Call resort() if an option that affects the sort order (_sorter) was changed or if sorting was temporary disabled.

Calls _repos() on every member after sorting _ordered.

Example

Sqimitive.Base.extend({
  mixIns: [Sqimitive.Ordered],
  _opt: {invert: false},

  events: {
    '=_sorter': function (sup) {
      var res = sup(this, arguments)
      // Invert sort order based on the option's value:
      return this.get('invert') ? -res : res
    },

    change_invert: 'resort-',
  },
})

Example

Temporary disabling automatic sorting is useful during mass-assignment (assignChildren()):

var hook = this.on('=_indexFor', Sqimitive.Core.stub)
try {
  this.assignChildren(data)
} finally {
  this.off(hook)
  this.resort()
}

Defined in: main.js, lines 7656-7664 (9 lines) • Show code

resort: function () {
  this._ordered.sort(function (a, b) {
    // function _sorter(a, b, posB) - obtain that posB (simulating first
    // iteration of indexFor()).
    return this._sorter(a, b, this._sorter(b))
  }.bind(this))
  this.forEach(this._repos, this)
  return this
},

reverse ( )

Part of: tag_Utilities

Returns _children in reverse order.

This differs from standard Array’s reverse() that works in-place.

Defined in: main.js, lines 7836-7840 (5 lines) • Show code

reverse: function () {
  var res = []
  for (var i = this.length; i--; ) { res.push(this._ordered[i].child) }
  return res
},

shift ( )

Part of: tag_Utilities

Removes the first child and returns it.

Result Types

Types	Notes
poshobject former child
undefined if empty

shift() and pop() allow treating an Ordered sqimitive as a queue (FIFO/LIFO). Use nest() with a counter to push/unshift.

Example

sqim.counter = 0
sqim.nest(new C1, {pos:  sqim.counter++})   // push
sqim.nest(new C2, {pos: -sqim.counter++})   // unshift
sqim.last()                                 //=> C1
sqim.first()                                //=> C2
sqim.pop()                                  //=> C1
sqim.shift()                                //=> C2
sqim.pop()                                  //=> undefined
sqim.shift()                                //=> undefined

Defined in: main.js, lines 7812-7815 (4 lines) • Show code

shift: function () {
  var entry = this._ordered[0]
  return entry && this.unlist(entry.key)
},