javascript - How to sort an array with sometimes incomparable values? -


i trying sort values incomparable each other. data sorting resembles tree 

1. if depends on b, should sorted after b 2. if b depends on a, b should sorted after 3. if neither or b depend on each other incomparable , no comparison can drawn

i using sort function in javascript custom compare function. suspect not appropriate require topological sorting

example code tests:

// k depends on nothing - every other element depends on k, k should come first var k = {   uuid: 'k',   dependson: [] };  // z depends on k , k must come before z var z = {   uuid: 'z',   dependson: ['k'] }  // y should go before x x depends on y // y depends on k k should go before y var y = {   uuid: 'y',   dependson: ['k'] }  // x has both y , k dependencies var x = {   uuid: 'x',   dependson: ['y', 'k'] }  function compare(a, b) {   // if have same uuid; same   if (a.uuid === b.uuid) {     return 0   }    // if depends on b, should after b   (var = 0, len = a.dependson.length; < len; i++) {     var dependson = a.dependson[i];      if (dependson === b.uuid) {       return 1     }   }    // if b depends on a, b should after   (var = 0, len = b.dependson.length; < len; i++) {     var dependson = b.dependson[i];      if (dependson === a.uuid) {       return -1     }   }    // edge case,    // if neither or b depends on each other, don't have relative ranking   return null }  // every possible permutation - should sort same orders // expected order k, z, y, x or k, y, z, x or k, y, x, z // because: // k -> z  z depends on k // k -> y  y depends on k // no relative ranking between z , y don't depend on each other // x depends on both y , k x come after them var perms = [   [x, y, z, k],   [x, y, k, z],   [x, z, y, k],   [x, z, k, y],   [x, k, y, z],   [x, k, z, y],   [y, x, z, k],   [y, x, k, z],   [y, z, x, k],   [y, z, k, x],   [y, k, x, z],   [y, k, z, x],   [z, x, y, k],   [z, x, k, y],   [z, y, x, k],   [z, y, k, x],   [z, k, x, y],   [z, k, y, x],   [k, x, y, z],   [k, x, z, y],   [k, y, x, z],   [k, y, z, x],   [k, z, x, y],   [k, z, y, x], ]  var _ = require('underscore') perms.foreach(function(perm) {   var s = perm.sort(compare)   var p = _.pluck(s, 'uuid')   console.log(p, _.isequal(p, ['k', 'z', 'y', 'x']) || _.isequal(p, ['k', 'y', 'z', 'x']) || _.isequal(p, ['k', 'y', 'x', 'z'])) })

example output (with annotation): 

[ 'k', 'y', 'x', 'z' ] true [ 'k', 'y', 'x', 'z' ] true [ 'k', 'x', 'z', 'y' ] false \\ x depends on k , y should after y [ 'k', 'x', 'z', 'y' ] false [ 'k', 'y', 'x', 'z' ] true [ 'k', 'x', 'z', 'y' ] false \\ x depends on k , y should after y [ 'k', 'y', 'x', 'z' ] true [ 'k', 'y', 'x', 'z' ] true [ 'k', 'y', 'z', 'x' ] true [ 'k', 'y', 'z', 'x' ] true [ 'k', 'y', 'x', 'z' ] true [ 'k', 'y', 'z', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'y', 'x', 'z' ] true [ 'k', 'x', 'z', 'y' ] false \\ x depends on k , y should after y [ 'k', 'y', 'x', 'z' ] true [ 'k', 'y', 'z', 'x' ] true [ 'k', 'z', 'y', 'x' ] true [ 'k', 'z', 'y', 'x' ] true

i found seemingly not actively maintained library did job:

toposort

// k depends on nothing - every other element depends on k, k should come first var k = {   uuid: 'k',   dependson: [] };  // z depends on k , k must come before z var z = {   uuid: 'z',   dependson: ['k'] }  // y should go before x x depends on y // y depends on k k should go before y var y = {   uuid: 'y',   dependson: ['k'] }  // x has both y , k dependencies var x = {   uuid: 'x',   dependson: ['y', 'k'] };  function edges(array) {   var edges = []   (var k in array) {     var node = array[k]      node.dependson.foreach(function(dependency) {       edges.push([dependency].concat(node.uuid))     })   }    return edges }  // every possible permutation - should sort same orders // expected order k, z, y, x or k, y, z, x or k, y, x, z // because: // k -> z  z depends on k // k -> y  y depends on k // no relative ranking between z , y don't depend on each other // x depends on both y , k x come after them var perms = [   [x, y, z, k],   [x, y, k, z],   [x, z, y, k],   [x, z, k, y],   [x, k, y, z],   [x, k, z, y],   [y, x, z, k],   [y, x, k, z],   [y, z, x, k],   [y, z, k, x],   [y, k, x, z],   [y, k, z, x],   [z, x, y, k],   [z, x, k, y],   [z, y, x, k],   [z, y, k, x],   [z, k, x, y],   [z, k, y, x],   [k, x, y, z],   [k, x, z, y],   [k, y, x, z],   [k, y, z, x],   [k, z, x, y],   [k, z, y, x], ]  var _ = require('underscore') var toposort = require('toposort') perms.foreach(function(perm) {   var p = toposort(edges(perm));   console.log(p, _.isequal(p, ['k', 'z', 'y', 'x']) || _.isequal(p, ['k', 'y', 'z', 'x']) || _.isequal(p, ['k', 'y', 'x', 'z'])) })

Comments

Post a Comment

Popular posts from this blog

android - Get AccessToken using signpost OAuth without opening a browser (Two legged Oauth) -

i using signpost oauth access data magento server. have read various tutorials on same , reach point open browser user can enter credentials. however, per requirement have automate part. hence, user should not browser page. have set-up done on server side ( magento ), hit url , returned call page. same through program in android. i have tried below, consumer = new commonshttpoauthconsumer(key, secret); provider = new commonshttpoauthprovider(oauth_init_url,access_token_url, authorize_url); try { provider.retrieverequesttoken(consumer, oauth.out_of_band); log.d("tokens" , consumer.gettoken() + " -- " + consumer.gettokensecret()); } and request tokens. dont know how bypass next step. tried directly accessing accesstoken (stupid of me) provider.retrieveaccesstoken(consumer, "mycallback://callback"); no luck, ends in oauth.signpost.exception.oauthnotauthorizedexception: authorization failed (server replied 401). ...
Read more

org.mockito.exceptions.misusing.InvalidUseOfMatchersException: mockito -

getting error org.mockito.exceptions.misusing.invaliduseofmatchersexception: invalid use of argument matchers! 1 matchers expected, 2 recorded. exception may occur if matchers combined raw values: //incorrect: somemethod(anyobject(), "raw string"); when using matchers, arguments have provided matchers. example: //correct: somemethod(anyobject(), eq("string matcher")); at when( getprogramservice .callservice(any(getprogramtype.class))) .thenreturn(jaxbresponse); please explain error , possible resolution the code posted looks fine; don't see problem it. code before or above causing exception. key here: invalid use of argument matchers! 1 matchers expected, 2 recorded. any , used above, doesn't return "special kind of null" or "special kind of getprogramtype"; don't exist. instead, returns null , side effect puts matcher on stack. whe...
Read more

google shop client API returns 400 bad request error while adding an item -

i'm working on solution add items in google shopping market java application. following tutorial real mess because of missing classes of laste release, after setting 1.5-beta maven managed make base example typecheck correctly classes. still can make simple task of adding 1 item. instead of posting whole code i'm posting part creates product feed. private product createproduct(string id) { product product = new product(); product.title = "red wool sweater"; product.content = new content( "text", "comfortable , soft, sweater keep warm on " + "cold winter nights. red , blue stripes."); product.appcontrol = new appcontrol(); product.appcontrol.addrequireddestination("productads"); product.externalid = id; product.lang = "it"; product.country = "it"; product.condition = "nuovo"; product.price = new price("eu...
Read more