Best Python code snippet using green
short.js
Source:short.js  
1/* */ 2'use strict';3var curve = require('./index');4var elliptic = require('../../elliptic');5var BN = require('bn.js');6var inherits = require('inherits');7var Base = curve.base;8var assert = elliptic.utils.assert;9function ShortCurve(conf) {10  Base.call(this, 'short', conf);11  this.a = new BN(conf.a, 16).toRed(this.red);12  this.b = new BN(conf.b, 16).toRed(this.red);13  this.tinv = this.two.redInvm();14  this.zeroA = this.a.fromRed().cmpn(0) === 0;15  this.threeA = this.a.fromRed().sub(this.p).cmpn(-3) === 0;16  this.endo = this._getEndomorphism(conf);17  this._endoWnafT1 = new Array(4);18  this._endoWnafT2 = new Array(4);19}20inherits(ShortCurve, Base);21module.exports = ShortCurve;22ShortCurve.prototype._getEndomorphism = function _getEndomorphism(conf) {23  if (!this.zeroA || !this.g || !this.n || this.p.modn(3) !== 1)24    return;25  var beta;26  var lambda;27  if (conf.beta) {28    beta = new BN(conf.beta, 16).toRed(this.red);29  } else {30    var betas = this._getEndoRoots(this.p);31    beta = betas[0].cmp(betas[1]) < 0 ? betas[0] : betas[1];32    beta = beta.toRed(this.red);33  }34  if (conf.lambda) {35    lambda = new BN(conf.lambda, 16);36  } else {37    var lambdas = this._getEndoRoots(this.n);38    if (this.g.mul(lambdas[0]).x.cmp(this.g.x.redMul(beta)) === 0) {39      lambda = lambdas[0];40    } else {41      lambda = lambdas[1];42      assert(this.g.mul(lambda).x.cmp(this.g.x.redMul(beta)) === 0);43    }44  }45  var basis;46  if (conf.basis) {47    basis = conf.basis.map(function(vec) {48      return {49        a: new BN(vec.a, 16),50        b: new BN(vec.b, 16)51      };52    });53  } else {54    basis = this._getEndoBasis(lambda);55  }56  return {57    beta: beta,58    lambda: lambda,59    basis: basis60  };61};62ShortCurve.prototype._getEndoRoots = function _getEndoRoots(num) {63  var red = num === this.p ? this.red : BN.mont(num);64  var tinv = new BN(2).toRed(red).redInvm();65  var ntinv = tinv.redNeg();66  var s = new BN(3).toRed(red).redNeg().redSqrt().redMul(tinv);67  var l1 = ntinv.redAdd(s).fromRed();68  var l2 = ntinv.redSub(s).fromRed();69  return [l1, l2];70};71ShortCurve.prototype._getEndoBasis = function _getEndoBasis(lambda) {72  var aprxSqrt = this.n.ushrn(Math.floor(this.n.bitLength() / 2));73  var u = lambda;74  var v = this.n.clone();75  var x1 = new BN(1);76  var y1 = new BN(0);77  var x2 = new BN(0);78  var y2 = new BN(1);79  var a0;80  var b0;81  var a1;82  var b1;83  var a2;84  var b2;85  var prevR;86  var i = 0;87  var r;88  var x;89  while (u.cmpn(0) !== 0) {90    var q = v.div(u);91    r = v.sub(q.mul(u));92    x = x2.sub(q.mul(x1));93    var y = y2.sub(q.mul(y1));94    if (!a1 && r.cmp(aprxSqrt) < 0) {95      a0 = prevR.neg();96      b0 = x1;97      a1 = r.neg();98      b1 = x;99    } else if (a1 && ++i === 2) {100      break;101    }102    prevR = r;103    v = u;104    u = r;105    x2 = x1;106    x1 = x;107    y2 = y1;108    y1 = y;109  }110  a2 = r.neg();111  b2 = x;112  var len1 = a1.sqr().add(b1.sqr());113  var len2 = a2.sqr().add(b2.sqr());114  if (len2.cmp(len1) >= 0) {115    a2 = a0;116    b2 = b0;117  }118  if (a1.negative) {119    a1 = a1.neg();120    b1 = b1.neg();121  }122  if (a2.negative) {123    a2 = a2.neg();124    b2 = b2.neg();125  }126  return [{127    a: a1,128    b: b1129  }, {130    a: a2,131    b: b2132  }];133};134ShortCurve.prototype._endoSplit = function _endoSplit(k) {135  var basis = this.endo.basis;136  var v1 = basis[0];137  var v2 = basis[1];138  var c1 = v2.b.mul(k).divRound(this.n);139  var c2 = v1.b.neg().mul(k).divRound(this.n);140  var p1 = c1.mul(v1.a);141  var p2 = c2.mul(v2.a);142  var q1 = c1.mul(v1.b);143  var q2 = c2.mul(v2.b);144  var k1 = k.sub(p1).sub(p2);145  var k2 = q1.add(q2).neg();146  return {147    k1: k1,148    k2: k2149  };150};151ShortCurve.prototype.pointFromX = function pointFromX(x, odd) {152  x = new BN(x, 16);153  if (!x.red)154    x = x.toRed(this.red);155  var y2 = x.redSqr().redMul(x).redIAdd(x.redMul(this.a)).redIAdd(this.b);156  var y = y2.redSqrt();157  if (y.redSqr().redSub(y2).cmp(this.zero) !== 0)158    throw new Error('invalid point');159  var isOdd = y.fromRed().isOdd();160  if (odd && !isOdd || !odd && isOdd)161    y = y.redNeg();162  return this.point(x, y);163};164ShortCurve.prototype.validate = function validate(point) {165  if (point.inf)166    return true;167  var x = point.x;168  var y = point.y;169  var ax = this.a.redMul(x);170  var rhs = x.redSqr().redMul(x).redIAdd(ax).redIAdd(this.b);171  return y.redSqr().redISub(rhs).cmpn(0) === 0;172};173ShortCurve.prototype._endoWnafMulAdd = function _endoWnafMulAdd(points, coeffs) {174  var npoints = this._endoWnafT1;175  var ncoeffs = this._endoWnafT2;176  for (var i = 0; i < points.length; i++) {177    var split = this._endoSplit(coeffs[i]);178    var p = points[i];179    var beta = p._getBeta();180    if (split.k1.negative) {181      split.k1.ineg();182      p = p.neg(true);183    }184    if (split.k2.negative) {185      split.k2.ineg();186      beta = beta.neg(true);187    }188    npoints[i * 2] = p;189    npoints[i * 2 + 1] = beta;190    ncoeffs[i * 2] = split.k1;191    ncoeffs[i * 2 + 1] = split.k2;192  }193  var res = this._wnafMulAdd(1, npoints, ncoeffs, i * 2);194  for (var j = 0; j < i * 2; j++) {195    npoints[j] = null;196    ncoeffs[j] = null;197  }198  return res;199};200function Point(curve, x, y, isRed) {201  Base.BasePoint.call(this, curve, 'affine');202  if (x === null && y === null) {203    this.x = null;204    this.y = null;205    this.inf = true;206  } else {207    this.x = new BN(x, 16);208    this.y = new BN(y, 16);209    if (isRed) {210      this.x.forceRed(this.curve.red);211      this.y.forceRed(this.curve.red);212    }213    if (!this.x.red)214      this.x = this.x.toRed(this.curve.red);215    if (!this.y.red)216      this.y = this.y.toRed(this.curve.red);217    this.inf = false;218  }219}220inherits(Point, Base.BasePoint);221ShortCurve.prototype.point = function point(x, y, isRed) {222  return new Point(this, x, y, isRed);223};224ShortCurve.prototype.pointFromJSON = function pointFromJSON(obj, red) {225  return Point.fromJSON(this, obj, red);226};227Point.prototype._getBeta = function _getBeta() {228  if (!this.curve.endo)229    return;230  var pre = this.precomputed;231  if (pre && pre.beta)232    return pre.beta;233  var beta = this.curve.point(this.x.redMul(this.curve.endo.beta), this.y);234  if (pre) {235    var curve = this.curve;236    var endoMul = function(p) {237      return curve.point(p.x.redMul(curve.endo.beta), p.y);238    };239    pre.beta = beta;240    beta.precomputed = {241      beta: null,242      naf: pre.naf && {243        wnd: pre.naf.wnd,244        points: pre.naf.points.map(endoMul)245      },246      doubles: pre.doubles && {247        step: pre.doubles.step,248        points: pre.doubles.points.map(endoMul)249      }250    };251  }252  return beta;253};254Point.prototype.toJSON = function toJSON() {255  if (!this.precomputed)256    return [this.x, this.y];257  return [this.x, this.y, this.precomputed && {258    doubles: this.precomputed.doubles && {259      step: this.precomputed.doubles.step,260      points: this.precomputed.doubles.points.slice(1)261    },262    naf: this.precomputed.naf && {263      wnd: this.precomputed.naf.wnd,264      points: this.precomputed.naf.points.slice(1)265    }266  }];267};268Point.fromJSON = function fromJSON(curve, obj, red) {269  if (typeof obj === 'string')270    obj = JSON.parse(obj);271  var res = curve.point(obj[0], obj[1], red);272  if (!obj[2])273    return res;274  function obj2point(obj) {275    return curve.point(obj[0], obj[1], red);276  }277  var pre = obj[2];278  res.precomputed = {279    beta: null,280    doubles: pre.doubles && {281      step: pre.doubles.step,282      points: [res].concat(pre.doubles.points.map(obj2point))283    },284    naf: pre.naf && {285      wnd: pre.naf.wnd,286      points: [res].concat(pre.naf.points.map(obj2point))287    }288  };289  return res;290};291Point.prototype.inspect = function inspect() {292  if (this.isInfinity())293    return '<EC Point Infinity>';294  return '<EC Point x: ' + this.x.fromRed().toString(16, 2) + ' y: ' + this.y.fromRed().toString(16, 2) + '>';295};296Point.prototype.isInfinity = function isInfinity() {297  return this.inf;298};299Point.prototype.add = function add(p) {300  if (this.inf)301    return p;302  if (p.inf)303    return this;304  if (this.eq(p))305    return this.dbl();306  if (this.neg().eq(p))307    return this.curve.point(null, null);308  if (this.x.cmp(p.x) === 0)309    return this.curve.point(null, null);310  var c = this.y.redSub(p.y);311  if (c.cmpn(0) !== 0)312    c = c.redMul(this.x.redSub(p.x).redInvm());313  var nx = c.redSqr().redISub(this.x).redISub(p.x);314  var ny = c.redMul(this.x.redSub(nx)).redISub(this.y);315  return this.curve.point(nx, ny);316};317Point.prototype.dbl = function dbl() {318  if (this.inf)319    return this;320  var ys1 = this.y.redAdd(this.y);321  if (ys1.cmpn(0) === 0)322    return this.curve.point(null, null);323  var a = this.curve.a;324  var x2 = this.x.redSqr();325  var dyinv = ys1.redInvm();326  var c = x2.redAdd(x2).redIAdd(x2).redIAdd(a).redMul(dyinv);327  var nx = c.redSqr().redISub(this.x.redAdd(this.x));328  var ny = c.redMul(this.x.redSub(nx)).redISub(this.y);329  return this.curve.point(nx, ny);330};331Point.prototype.getX = function getX() {332  return this.x.fromRed();333};334Point.prototype.getY = function getY() {335  return this.y.fromRed();336};337Point.prototype.mul = function mul(k) {338  k = new BN(k, 16);339  if (this._hasDoubles(k))340    return this.curve._fixedNafMul(this, k);341  else if (this.curve.endo)342    return this.curve._endoWnafMulAdd([this], [k]);343  else344    return this.curve._wnafMul(this, k);345};346Point.prototype.mulAdd = function mulAdd(k1, p2, k2) {347  var points = [this, p2];348  var coeffs = [k1, k2];349  if (this.curve.endo)350    return this.curve._endoWnafMulAdd(points, coeffs);351  else352    return this.curve._wnafMulAdd(1, points, coeffs, 2);353};354Point.prototype.eq = function eq(p) {355  return this === p || this.inf === p.inf && (this.inf || this.x.cmp(p.x) === 0 && this.y.cmp(p.y) === 0);356};357Point.prototype.neg = function neg(_precompute) {358  if (this.inf)359    return this;360  var res = this.curve.point(this.x, this.y.redNeg());361  if (_precompute && this.precomputed) {362    var pre = this.precomputed;363    var negate = function(p) {364      return p.neg();365    };366    res.precomputed = {367      naf: pre.naf && {368        wnd: pre.naf.wnd,369        points: pre.naf.points.map(negate)370      },371      doubles: pre.doubles && {372        step: pre.doubles.step,373        points: pre.doubles.points.map(negate)374      }375    };376  }377  return res;378};379Point.prototype.toJ = function toJ() {380  if (this.inf)381    return this.curve.jpoint(null, null, null);382  var res = this.curve.jpoint(this.x, this.y, this.curve.one);383  return res;384};385function JPoint(curve, x, y, z) {386  Base.BasePoint.call(this, curve, 'jacobian');387  if (x === null && y === null && z === null) {388    this.x = this.curve.one;389    this.y = this.curve.one;390    this.z = new BN(0);391  } else {392    this.x = new BN(x, 16);393    this.y = new BN(y, 16);394    this.z = new BN(z, 16);395  }396  if (!this.x.red)397    this.x = this.x.toRed(this.curve.red);398  if (!this.y.red)399    this.y = this.y.toRed(this.curve.red);400  if (!this.z.red)401    this.z = this.z.toRed(this.curve.red);402  this.zOne = this.z === this.curve.one;403}404inherits(JPoint, Base.BasePoint);405ShortCurve.prototype.jpoint = function jpoint(x, y, z) {406  return new JPoint(this, x, y, z);407};408JPoint.prototype.toP = function toP() {409  if (this.isInfinity())410    return this.curve.point(null, null);411  var zinv = this.z.redInvm();412  var zinv2 = zinv.redSqr();413  var ax = this.x.redMul(zinv2);414  var ay = this.y.redMul(zinv2).redMul(zinv);415  return this.curve.point(ax, ay);416};417JPoint.prototype.neg = function neg() {418  return this.curve.jpoint(this.x, this.y.redNeg(), this.z);419};420JPoint.prototype.add = function add(p) {421  if (this.isInfinity())422    return p;423  if (p.isInfinity())424    return this;425  var pz2 = p.z.redSqr();426  var z2 = this.z.redSqr();427  var u1 = this.x.redMul(pz2);428  var u2 = p.x.redMul(z2);429  var s1 = this.y.redMul(pz2.redMul(p.z));430  var s2 = p.y.redMul(z2.redMul(this.z));431  var h = u1.redSub(u2);432  var r = s1.redSub(s2);433  if (h.cmpn(0) === 0) {434    if (r.cmpn(0) !== 0)435      return this.curve.jpoint(null, null, null);436    else437      return this.dbl();438  }439  var h2 = h.redSqr();440  var h3 = h2.redMul(h);441  var v = u1.redMul(h2);442  var nx = r.redSqr().redIAdd(h3).redISub(v).redISub(v);443  var ny = r.redMul(v.redISub(nx)).redISub(s1.redMul(h3));444  var nz = this.z.redMul(p.z).redMul(h);445  return this.curve.jpoint(nx, ny, nz);446};447JPoint.prototype.mixedAdd = function mixedAdd(p) {448  if (this.isInfinity())449    return p.toJ();450  if (p.isInfinity())451    return this;452  var z2 = this.z.redSqr();453  var u1 = this.x;454  var u2 = p.x.redMul(z2);455  var s1 = this.y;456  var s2 = p.y.redMul(z2).redMul(this.z);457  var h = u1.redSub(u2);458  var r = s1.redSub(s2);459  if (h.cmpn(0) === 0) {460    if (r.cmpn(0) !== 0)461      return this.curve.jpoint(null, null, null);462    else463      return this.dbl();464  }465  var h2 = h.redSqr();466  var h3 = h2.redMul(h);467  var v = u1.redMul(h2);468  var nx = r.redSqr().redIAdd(h3).redISub(v).redISub(v);469  var ny = r.redMul(v.redISub(nx)).redISub(s1.redMul(h3));470  var nz = this.z.redMul(h);471  return this.curve.jpoint(nx, ny, nz);472};473JPoint.prototype.dblp = function dblp(pow) {474  if (pow === 0)475    return this;476  if (this.isInfinity())477    return this;478  if (!pow)479    return this.dbl();480  if (this.curve.zeroA || this.curve.threeA) {481    var r = this;482    for (var i = 0; i < pow; i++)483      r = r.dbl();484    return r;485  }486  var a = this.curve.a;487  var tinv = this.curve.tinv;488  var jx = this.x;489  var jy = this.y;490  var jz = this.z;491  var jz4 = jz.redSqr().redSqr();492  var jyd = jy.redAdd(jy);493  for (var i = 0; i < pow; i++) {494    var jx2 = jx.redSqr();495    var jyd2 = jyd.redSqr();496    var jyd4 = jyd2.redSqr();497    var c = jx2.redAdd(jx2).redIAdd(jx2).redIAdd(a.redMul(jz4));498    var t1 = jx.redMul(jyd2);499    var nx = c.redSqr().redISub(t1.redAdd(t1));500    var t2 = t1.redISub(nx);501    var dny = c.redMul(t2);502    dny = dny.redIAdd(dny).redISub(jyd4);503    var nz = jyd.redMul(jz);504    if (i + 1 < pow)505      jz4 = jz4.redMul(jyd4);506    jx = nx;507    jz = nz;508    jyd = dny;509  }510  return this.curve.jpoint(jx, jyd.redMul(tinv), jz);511};512JPoint.prototype.dbl = function dbl() {513  if (this.isInfinity())514    return this;515  if (this.curve.zeroA)516    return this._zeroDbl();517  else if (this.curve.threeA)518    return this._threeDbl();519  else520    return this._dbl();521};522JPoint.prototype._zeroDbl = function _zeroDbl() {523  var nx;524  var ny;525  var nz;526  if (this.zOne) {527    var xx = this.x.redSqr();528    var yy = this.y.redSqr();529    var yyyy = yy.redSqr();530    var s = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy);531    s = s.redIAdd(s);532    var m = xx.redAdd(xx).redIAdd(xx);533    var t = m.redSqr().redISub(s).redISub(s);534    var yyyy8 = yyyy.redIAdd(yyyy);535    yyyy8 = yyyy8.redIAdd(yyyy8);536    yyyy8 = yyyy8.redIAdd(yyyy8);537    nx = t;538    ny = m.redMul(s.redISub(t)).redISub(yyyy8);539    nz = this.y.redAdd(this.y);540  } else {541    var a = this.x.redSqr();542    var b = this.y.redSqr();543    var c = b.redSqr();544    var d = this.x.redAdd(b).redSqr().redISub(a).redISub(c);545    d = d.redIAdd(d);546    var e = a.redAdd(a).redIAdd(a);547    var f = e.redSqr();548    var c8 = c.redIAdd(c);549    c8 = c8.redIAdd(c8);550    c8 = c8.redIAdd(c8);551    nx = f.redISub(d).redISub(d);552    ny = e.redMul(d.redISub(nx)).redISub(c8);553    nz = this.y.redMul(this.z);554    nz = nz.redIAdd(nz);555  }556  return this.curve.jpoint(nx, ny, nz);557};558JPoint.prototype._threeDbl = function _threeDbl() {559  var nx;560  var ny;561  var nz;562  if (this.zOne) {563    var xx = this.x.redSqr();564    var yy = this.y.redSqr();565    var yyyy = yy.redSqr();566    var s = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy);567    s = s.redIAdd(s);568    var m = xx.redAdd(xx).redIAdd(xx).redIAdd(this.curve.a);569    var t = m.redSqr().redISub(s).redISub(s);570    nx = t;571    var yyyy8 = yyyy.redIAdd(yyyy);572    yyyy8 = yyyy8.redIAdd(yyyy8);573    yyyy8 = yyyy8.redIAdd(yyyy8);574    ny = m.redMul(s.redISub(t)).redISub(yyyy8);575    nz = this.y.redAdd(this.y);576  } else {577    var delta = this.z.redSqr();578    var gamma = this.y.redSqr();579    var beta = this.x.redMul(gamma);580    var alpha = this.x.redSub(delta).redMul(this.x.redAdd(delta));581    alpha = alpha.redAdd(alpha).redIAdd(alpha);582    var beta4 = beta.redIAdd(beta);583    beta4 = beta4.redIAdd(beta4);584    var beta8 = beta4.redAdd(beta4);585    nx = alpha.redSqr().redISub(beta8);586    nz = this.y.redAdd(this.z).redSqr().redISub(gamma).redISub(delta);587    var ggamma8 = gamma.redSqr();588    ggamma8 = ggamma8.redIAdd(ggamma8);589    ggamma8 = ggamma8.redIAdd(ggamma8);590    ggamma8 = ggamma8.redIAdd(ggamma8);591    ny = alpha.redMul(beta4.redISub(nx)).redISub(ggamma8);592  }593  return this.curve.jpoint(nx, ny, nz);594};595JPoint.prototype._dbl = function _dbl() {596  var a = this.curve.a;597  var jx = this.x;598  var jy = this.y;599  var jz = this.z;600  var jz4 = jz.redSqr().redSqr();601  var jx2 = jx.redSqr();602  var jy2 = jy.redSqr();603  var c = jx2.redAdd(jx2).redIAdd(jx2).redIAdd(a.redMul(jz4));604  var jxd4 = jx.redAdd(jx);605  jxd4 = jxd4.redIAdd(jxd4);606  var t1 = jxd4.redMul(jy2);607  var nx = c.redSqr().redISub(t1.redAdd(t1));608  var t2 = t1.redISub(nx);609  var jyd8 = jy2.redSqr();610  jyd8 = jyd8.redIAdd(jyd8);611  jyd8 = jyd8.redIAdd(jyd8);612  jyd8 = jyd8.redIAdd(jyd8);613  var ny = c.redMul(t2).redISub(jyd8);614  var nz = jy.redAdd(jy).redMul(jz);615  return this.curve.jpoint(nx, ny, nz);616};617JPoint.prototype.trpl = function trpl() {618  if (!this.curve.zeroA)619    return this.dbl().add(this);620  var xx = this.x.redSqr();621  var yy = this.y.redSqr();622  var zz = this.z.redSqr();623  var yyyy = yy.redSqr();624  var m = xx.redAdd(xx).redIAdd(xx);625  var mm = m.redSqr();626  var e = this.x.redAdd(yy).redSqr().redISub(xx).redISub(yyyy);627  e = e.redIAdd(e);628  e = e.redAdd(e).redIAdd(e);629  e = e.redISub(mm);630  var ee = e.redSqr();631  var t = yyyy.redIAdd(yyyy);632  t = t.redIAdd(t);633  t = t.redIAdd(t);634  t = t.redIAdd(t);635  var u = m.redIAdd(e).redSqr().redISub(mm).redISub(ee).redISub(t);636  var yyu4 = yy.redMul(u);637  yyu4 = yyu4.redIAdd(yyu4);638  yyu4 = yyu4.redIAdd(yyu4);639  var nx = this.x.redMul(ee).redISub(yyu4);640  nx = nx.redIAdd(nx);641  nx = nx.redIAdd(nx);642  var ny = this.y.redMul(u.redMul(t.redISub(u)).redISub(e.redMul(ee)));643  ny = ny.redIAdd(ny);644  ny = ny.redIAdd(ny);645  ny = ny.redIAdd(ny);646  var nz = this.z.redAdd(e).redSqr().redISub(zz).redISub(ee);647  return this.curve.jpoint(nx, ny, nz);648};649JPoint.prototype.mul = function mul(k, kbase) {650  k = new BN(k, kbase);651  return this.curve._wnafMul(this, k);652};653JPoint.prototype.eq = function eq(p) {654  if (p.type === 'affine')655    return this.eq(p.toJ());656  if (this === p)657    return true;658  var z2 = this.z.redSqr();659  var pz2 = p.z.redSqr();660  if (this.x.redMul(pz2).redISub(p.x.redMul(z2)).cmpn(0) !== 0)661    return false;662  var z3 = z2.redMul(this.z);663  var pz3 = pz2.redMul(p.z);664  return this.y.redMul(pz3).redISub(p.y.redMul(z3)).cmpn(0) === 0;665};666JPoint.prototype.inspect = function inspect() {667  if (this.isInfinity())668    return '<EC JPoint Infinity>';669  return '<EC JPoint x: ' + this.x.toString(16, 2) + ' y: ' + this.y.toString(16, 2) + ' z: ' + this.z.toString(16, 2) + '>';670};671JPoint.prototype.isInfinity = function isInfinity() {672  return this.z.cmpn(0) === 0;...rbtree.py
Source:rbtree.py  
1class Node:2    def __init__(self, key):3        self.key = key4        self.red = True5        self.right = None6        self.left = None7        self.parent = None8class RBtree(Node):9    def __init__(self):10        self.root = None11    def insert(self, key):12        node = Node(key)13        node.red = True14        if self.root == None:15            node.red = False16            self.root = node17            node.left = Node(None)18            node.left.red = False19            node.right = Node(None)20            node.right.red = False21            return22        currentNode = self.root23        while currentNode.key != None:24            potentialParent = currentNode25            if node.key < currentNode.key:26                currentNode = currentNode.left27            else:28                currentNode = currentNode.right29        node.parent = potentialParent30        if node.key < node.parent.key:31            currentNode.left = node32            node.parent.left = node33            34        else:35            currentNode.right = node36            node.parent.right = node37        node.left = Node(None)38        node.left.red = False39        node.right = Node(None)40        node.right.red = False41        self._fixTree(node)42    def MinNode(self,key=None):43        if self.root is not None:44            current = self.root45            while (current.left.key is not None):46                current = current.left47            return current48        else:49            print("tree is empty")50    def MaxNode(self):51        if self.root is not None:52            current = self.root53            while (current.right.key is not None):54                current = current.right55            return current56        else:57            print("tree is empty")58    def search(self, key):59        if self.root is not None:60            currentNode = self.root61            while currentNode.key != None and key != currentNode.key:62                if key < currentNode.key:63                    currentNode = currentNode.left64                else:65                    currentNode = currentNode.right66            return currentNode67        else:68            print("tree is empty")69    def FindNext(self, x):70        current = self.search(x)71        if current:72            current = current.right73            if current.key is not None:74                while (current.left.key is not None):75                    current = current.left76                return current77        else:78            print('x is not exist in tree')79    def FindPrev(self, x):80        current = self.search(x)81        if current:82            current=current.left83            if current.key is not None:84                while (current.right.key is not None):85                    current = current.right86                return current87        else:88            print('x is not exist in tree')89    def deleteNode(self, key):90        currentNode = self.search(key)91        if currentNode is not self.root:92            if currentNode.key is not None:93                if currentNode == currentNode.parent.left:94                    self._delete_left_node(currentNode)95    96                else:97                    self._delete_right_node(currentNode)98            else:99                 print("Node is not exists")100        else:101            self._delete_root_node(currentNode)102            103#________________auxiliary_methods______________104            105    def _fixTree(self, node):106        while node.parent is not None and node.parent.red == True:107            if node.parent == node.parent.parent.left:108                uncle = node.parent.parent.right109                if uncle.red:110                    node.parent.red = False111                    uncle.red = False112                    node.parent.parent.red = True113                    node = node.parent.parent114                else:115                    if node == node.parent.right:116                        node = node.parent117                        self._left_rotate(node)118                    node.parent.red = False119                    node.parent.parent.red = True120                    self._right_rotate(node.parent.parent)121            else:122                uncle = node.parent.parent.left123                if uncle.red:124                    node.parent.red = False125                    uncle.red = False126                    node.parent.parent.red = True127                    node = node.parent.parent128                else:129                    if node == node.parent.left:130                        node = node.parent131                        self._right_rotate(node)132                    node.parent.red = False133                    node.parent.parent.red = True134                    self._left_rotate(node.parent.parent)135        self.root.red = False        136            137    def _left_rotate(self, node):138        sibling = node.right139        node.right = sibling.left140        if sibling.left != None:141            sibling.left.parent = node142        sibling.parent = node.parent143        if node.parent == None:144            self.root = sibling145        else:146            if node == node.parent.left:147                node.parent.left = sibling148            else:149                node.parent.right = sibling150        sibling.left = node151        node.parent = sibling152    def _right_rotate(self, node):153        sibling = node.left154        node.left = sibling.right155        if sibling.right != None:156            sibling.right.parent = node157        sibling.parent = node.parent158        if node.parent == None:159            self.root = sibling160        else:161            if node == node.parent.right:162                node.parent.right = sibling163            else:164                node.parent.left = sibling165        sibling.right = node166        node.parent = sibling167            168    169    170    def _delete_left_node(self,currentNode):171        if currentNode.left.key is None and currentNode.right.key is None:172            self._delete_left_node_noChildren(currentNode)173        elif currentNode.left.key is  None and  currentNode.right.key is not None:174            self._delete_left_node_onlyRightChildren(currentNode)175        elif currentNode.left.key is not None and  currentNode.right.key is None:176            self._delete_left_node_onlyLeftChildren(currentNode)177        else:178            self._delete_left_node_bothChildren(currentNode)179    180    181                182    def _delete_right_node(self,currentNode):183        if currentNode.left.key is None and currentNode.right.key is None:184             self._delete_right_node_noChildren(currentNode)               185                    186        elif currentNode.left.key is  None and currentNode.right.key is not None:187            self._delete_right_node_onlyRightChildren(currentNode)188        elif currentNode.left.key is not None and currentNode.right.key is  None:189            self._delete_right_node_onlyLeftChildren(currentNode)190        else:191            self._delete_right_node_bothChildren(currentNode)192    193    194    def _delete_root_node(self, currentNode):195        if currentNode.left.key is None and currentNode.right.key is None:196            self.root = None197        elif currentNode.left.key is None and currentNode.right.key is not None:198            self.root=currentNode.right199            currentNode.right.parent = None200        elif currentNode.left.key is not None and currentNode.right.key is None:201            self.root = currentNode.left202            currentNode.left.parent = None203        else:204            next = self.FindNext(currentNode.key)205            next.parent = None206            self.root = next207            currentNode.left.parent = self.root208            self.root.left = currentNode.left209        self.root.red = False210        211    def _delete_left_node_noChildren(self, currentNode):212        currentNode.parent.left = currentNode.left213        currentNode.left.parent = currentNode.parent214        if currentNode.red is False:215            brother = currentNode.parent.right216            if brother.red == False:217                if brother.left.red and brother.right.red:218                    brother.right.red = False219                    self._left_rotate(brother.parent)220                elif brother.left.red and brother.right.red==False:221                    brother.left.red = False222                    brother.red = True223                    self._right_rotate(brother)224                    self._left_rotate(brother.parent.parent)225                elif brother.right.red and brother.left.red == False:226                    brother.right.red = False227                    self._left_rotate(brother.parent)      228            else:229                if brother.left.key is not None and brother.right.key is not None:230                    brother.red = False231                    brother.left.red = True232                    self._left_rotate(brother.parent)233                    234    def _delete_left_node_onlyRightChildren(self, currentNode):235        currentNode.parent.left = currentNode.right236        currentNode.right.parent = currentNode.parent237        if currentNode.red is False:238            if currentNode.right.red:239                currentNode.right.red = False240        else:241            brother = currentNode.parent.right242            if brother.red == False:243                if brother.left.red and brother.right.red:244                    brother.right.red = False245                    self._left_rotate(brother.parent)246                elif brother.left.red and brother.right.red==False:247                    brother.left.red = False248                    brother.red = True249                    self._right_rotate(brother)250                    self._left_rotate(brother.parent.parent)251                elif brother.right.red and brother.left.red == False:252                    brother.right.red = False253                    self._left_rotate(brother.parent)        254            else:255                if brother.left.key is not None and brother.right.key is not None:256                    brother.red = False257                    brother.left.red = True258                    self._left_rotate(brother.parent)259                    260    def _delete_left_node_onlyLeftChildren(self, currentNode):261        currentNode.parent.left = currentNode.left262        currentNode.left.parent = currentNode.parent263        if currentNode.red is False:264            if currentNode.left.red:265                currentNode.left.red = False266    267    def _delete_left_node_bothChildren(self, currentNode):268        next = self.FindNext(currentNode.key)269        currentNode.parent.left = next270        next.parent = currentNode.parent271        currentNode.left.parent = next272        next.left = currentNode.left273        if next.red is False:274            if next.right.red:275                 next.right.red = False276                 next.red = True277        else:278            next.red = False279    def _delete_right_node_noChildren(self, currentNode):280        currentNode.parent.right = currentNode.right281        currentNode.right.parent = currentNode.parent282        if currentNode.red is False:283            brother = currentNode.parent.left284            print(brother.key)285            if brother.red == False:286                if brother.left.red and brother.right.red:287                    brother.right.red = False288                    self._right_rotate(brother.parent)289                elif brother.right.red and brother.left.red == False:290                    brother.right.red = False291                    brother.red = True292                    self._left_rotate(brother)293                    self._right_rotate(brother.parent.parent)294                elif brother.left.red and brother.right.red == False:295                    brother.left.red = False296                    self._right_rotate(brother.parent)297                    298            else:299                    if brother.left.key is not None and brother.right.key is not None:300                        brother.red = False301                        brother.right.red = True302                        self._right_rotate(brother.parent)303        304    def _delete_right_node_onlyRightChildren(self, currentNode):305        currentNode.parent.right = currentNode.right306        currentNode.right.parent = currentNode.parent307        if currentNode.red is False:308            if currentNode.right.red:309                currentNode.right.red = False310                311    def _delete_right_node_onlyLeftChildren(self, currentNode):312         currentNode.parent.right = currentNode.left313         currentNode.left.parent = currentNode.parent314         if currentNode.red is False:315             if currentNode.left.red:316                 currentNode.left.red = False317        318    def _delete_right_node_bothChildren(self, currentNode):319        next = self.FindNext(currentNode.key)320        currentNode.parent.right = next321        next.parent = currentNode.parent322        currentNode.left.parent= next323        next.left = currentNode.left324        print(next.key)325    326        if next.red is False:327            if next.right.red:   328                next.right.red = False329                next.red = True330        else:...edwards.js
Source:edwards.js  
1/* */ 2'use strict';3var curve = require('./index');4var elliptic = require('../../elliptic');5var BN = require('bn.js');6var inherits = require('inherits');7var Base = curve.base;8var assert = elliptic.utils.assert;9function EdwardsCurve(conf) {10  this.twisted = (conf.a | 0) !== 1;11  this.mOneA = this.twisted && (conf.a | 0) === -1;12  this.extended = this.mOneA;13  Base.call(this, 'edwards', conf);14  this.a = new BN(conf.a, 16).umod(this.red.m);15  this.a = this.a.toRed(this.red);16  this.c = new BN(conf.c, 16).toRed(this.red);17  this.c2 = this.c.redSqr();18  this.d = new BN(conf.d, 16).toRed(this.red);19  this.dd = this.d.redAdd(this.d);20  assert(!this.twisted || this.c.fromRed().cmpn(1) === 0);21  this.oneC = (conf.c | 0) === 1;22}23inherits(EdwardsCurve, Base);24module.exports = EdwardsCurve;25EdwardsCurve.prototype._mulA = function _mulA(num) {26  if (this.mOneA)27    return num.redNeg();28  else29    return this.a.redMul(num);30};31EdwardsCurve.prototype._mulC = function _mulC(num) {32  if (this.oneC)33    return num;34  else35    return this.c.redMul(num);36};37EdwardsCurve.prototype.jpoint = function jpoint(x, y, z, t) {38  return this.point(x, y, z, t);39};40EdwardsCurve.prototype.pointFromX = function pointFromX(x, odd) {41  x = new BN(x, 16);42  if (!x.red)43    x = x.toRed(this.red);44  var x2 = x.redSqr();45  var rhs = this.c2.redSub(this.a.redMul(x2));46  var lhs = this.one.redSub(this.c2.redMul(this.d).redMul(x2));47  var y2 = rhs.redMul(lhs.redInvm());48  var y = y2.redSqrt();49  if (y.redSqr().redSub(y2).cmp(this.zero) !== 0)50    throw new Error('invalid point');51  var isOdd = y.fromRed().isOdd();52  if (odd && !isOdd || !odd && isOdd)53    y = y.redNeg();54  return this.point(x, y);55};56EdwardsCurve.prototype.pointFromY = function pointFromY(y, odd) {57  y = new BN(y, 16);58  if (!y.red)59    y = y.toRed(this.red);60  var y2 = y.redSqr();61  var lhs = y2.redSub(this.one);62  var rhs = y2.redMul(this.d).redAdd(this.one);63  var x2 = lhs.redMul(rhs.redInvm());64  if (x2.cmp(this.zero) === 0) {65    if (odd)66      throw new Error('invalid point');67    else68      return this.point(this.zero, y);69  }70  var x = x2.redSqrt();71  if (x.redSqr().redSub(x2).cmp(this.zero) !== 0)72    throw new Error('invalid point');73  if (x.isOdd() !== odd)74    x = x.redNeg();75  return this.point(x, y);76};77EdwardsCurve.prototype.validate = function validate(point) {78  if (point.isInfinity())79    return true;80  point.normalize();81  var x2 = point.x.redSqr();82  var y2 = point.y.redSqr();83  var lhs = x2.redMul(this.a).redAdd(y2);84  var rhs = this.c2.redMul(this.one.redAdd(this.d.redMul(x2).redMul(y2)));85  return lhs.cmp(rhs) === 0;86};87function Point(curve, x, y, z, t) {88  Base.BasePoint.call(this, curve, 'projective');89  if (x === null && y === null && z === null) {90    this.x = this.curve.zero;91    this.y = this.curve.one;92    this.z = this.curve.one;93    this.t = this.curve.zero;94    this.zOne = true;95  } else {96    this.x = new BN(x, 16);97    this.y = new BN(y, 16);98    this.z = z ? new BN(z, 16) : this.curve.one;99    this.t = t && new BN(t, 16);100    if (!this.x.red)101      this.x = this.x.toRed(this.curve.red);102    if (!this.y.red)103      this.y = this.y.toRed(this.curve.red);104    if (!this.z.red)105      this.z = this.z.toRed(this.curve.red);106    if (this.t && !this.t.red)107      this.t = this.t.toRed(this.curve.red);108    this.zOne = this.z === this.curve.one;109    if (this.curve.extended && !this.t) {110      this.t = this.x.redMul(this.y);111      if (!this.zOne)112        this.t = this.t.redMul(this.z.redInvm());113    }114  }115}116inherits(Point, Base.BasePoint);117EdwardsCurve.prototype.pointFromJSON = function pointFromJSON(obj) {118  return Point.fromJSON(this, obj);119};120EdwardsCurve.prototype.point = function point(x, y, z, t) {121  return new Point(this, x, y, z, t);122};123Point.fromJSON = function fromJSON(curve, obj) {124  return new Point(curve, obj[0], obj[1], obj[2]);125};126Point.prototype.inspect = function inspect() {127  if (this.isInfinity())128    return '<EC Point Infinity>';129  return '<EC Point x: ' + this.x.fromRed().toString(16, 2) + ' y: ' + this.y.fromRed().toString(16, 2) + ' z: ' + this.z.fromRed().toString(16, 2) + '>';130};131Point.prototype.isInfinity = function isInfinity() {132  return this.x.cmpn(0) === 0 && this.y.cmp(this.z) === 0;133};134Point.prototype._extDbl = function _extDbl() {135  var a = this.x.redSqr();136  var b = this.y.redSqr();137  var c = this.z.redSqr();138  c = c.redIAdd(c);139  var d = this.curve._mulA(a);140  var e = this.x.redAdd(this.y).redSqr().redISub(a).redISub(b);141  var g = d.redAdd(b);142  var f = g.redSub(c);143  var h = d.redSub(b);144  var nx = e.redMul(f);145  var ny = g.redMul(h);146  var nt = e.redMul(h);147  var nz = f.redMul(g);148  return this.curve.point(nx, ny, nz, nt);149};150Point.prototype._projDbl = function _projDbl() {151  var b = this.x.redAdd(this.y).redSqr();152  var c = this.x.redSqr();153  var d = this.y.redSqr();154  var nx;155  var ny;156  var nz;157  if (this.curve.twisted) {158    var e = this.curve._mulA(c);159    var f = e.redAdd(d);160    if (this.zOne) {161      nx = b.redSub(c).redSub(d).redMul(f.redSub(this.curve.two));162      ny = f.redMul(e.redSub(d));163      nz = f.redSqr().redSub(f).redSub(f);164    } else {165      var h = this.z.redSqr();166      var j = f.redSub(h).redISub(h);167      nx = b.redSub(c).redISub(d).redMul(j);168      ny = f.redMul(e.redSub(d));169      nz = f.redMul(j);170    }171  } else {172    var e = c.redAdd(d);173    var h = this.curve._mulC(this.c.redMul(this.z)).redSqr();174    var j = e.redSub(h).redSub(h);175    nx = this.curve._mulC(b.redISub(e)).redMul(j);176    ny = this.curve._mulC(e).redMul(c.redISub(d));177    nz = e.redMul(j);178  }179  return this.curve.point(nx, ny, nz);180};181Point.prototype.dbl = function dbl() {182  if (this.isInfinity())183    return this;184  if (this.curve.extended)185    return this._extDbl();186  else187    return this._projDbl();188};189Point.prototype._extAdd = function _extAdd(p) {190  var a = this.y.redSub(this.x).redMul(p.y.redSub(p.x));191  var b = this.y.redAdd(this.x).redMul(p.y.redAdd(p.x));192  var c = this.t.redMul(this.curve.dd).redMul(p.t);193  var d = this.z.redMul(p.z.redAdd(p.z));194  var e = b.redSub(a);195  var f = d.redSub(c);196  var g = d.redAdd(c);197  var h = b.redAdd(a);198  var nx = e.redMul(f);199  var ny = g.redMul(h);200  var nt = e.redMul(h);201  var nz = f.redMul(g);202  return this.curve.point(nx, ny, nz, nt);203};204Point.prototype._projAdd = function _projAdd(p) {205  var a = this.z.redMul(p.z);206  var b = a.redSqr();207  var c = this.x.redMul(p.x);208  var d = this.y.redMul(p.y);209  var e = this.curve.d.redMul(c).redMul(d);210  var f = b.redSub(e);211  var g = b.redAdd(e);212  var tmp = this.x.redAdd(this.y).redMul(p.x.redAdd(p.y)).redISub(c).redISub(d);213  var nx = a.redMul(f).redMul(tmp);214  var ny;215  var nz;216  if (this.curve.twisted) {217    ny = a.redMul(g).redMul(d.redSub(this.curve._mulA(c)));218    nz = f.redMul(g);219  } else {220    ny = a.redMul(g).redMul(d.redSub(c));221    nz = this.curve._mulC(f).redMul(g);222  }223  return this.curve.point(nx, ny, nz);224};225Point.prototype.add = function add(p) {226  if (this.isInfinity())227    return p;228  if (p.isInfinity())229    return this;230  if (this.curve.extended)231    return this._extAdd(p);232  else233    return this._projAdd(p);234};235Point.prototype.mul = function mul(k) {236  if (this._hasDoubles(k))237    return this.curve._fixedNafMul(this, k);238  else239    return this.curve._wnafMul(this, k);240};241Point.prototype.mulAdd = function mulAdd(k1, p, k2) {242  return this.curve._wnafMulAdd(1, [this, p], [k1, k2], 2);243};244Point.prototype.normalize = function normalize() {245  if (this.zOne)246    return this;247  var zi = this.z.redInvm();248  this.x = this.x.redMul(zi);249  this.y = this.y.redMul(zi);250  if (this.t)251    this.t = this.t.redMul(zi);252  this.z = this.curve.one;253  this.zOne = true;254  return this;255};256Point.prototype.neg = function neg() {257  return this.curve.point(this.x.redNeg(), this.y, this.z, this.t && this.t.redNeg());258};259Point.prototype.getX = function getX() {260  this.normalize();261  return this.x.fromRed();262};263Point.prototype.getY = function getY() {264  this.normalize();265  return this.y.fromRed();266};267Point.prototype.eq = function eq(other) {268  return this === other || this.getX().cmp(other.getX()) === 0 && this.getY().cmp(other.getY()) === 0;269};270Point.prototype.toP = Point.prototype.normalize;...blur.py
Source:blur.py  
1"""2File: blur.py3Name:4-------------------------------5This file shows the original image first,6smiley-face.png, and then compare to its7blurred image. The blur algorithm uses the8average RGB values of a pixel's nearest neighbors.9"""10from simpleimage import SimpleImage11BLUR_INDEX = 512def main():13    """14    TODO: put in a picture and show the blurred version of it15    """16    old_img = SimpleImage("images/smiley-face.png")17    old_img.show()18    blurred_img = blur(old_img)19    for i in range(BLUR_INDEX):20        blurred_img = blur(blurred_img)21    blurred_img.show()22def blur(img):23    """24    :param img: An image to be blurred25    :return: a blurred image26    """27    new_img = SimpleImage.blank(img.width, img.height)28    for x in range(img.width):29        for y in range(img.height):30            pixel = new_img.get_pixel(x, y)31            sum_red = 032            sum_blue = 033            sum_green = 034            if x == 0:35                if y == 0:36                    for i in range(0, 2):37                        for j in range(0, 2):38                            neighbor = img.get_pixel(x + i, y + j)39                            sum_red += neighbor.red40                            sum_blue += neighbor.blue41                            sum_green += neighbor.green42                    pixel.red = sum_red / 443                    pixel.blue = sum_blue / 444                    pixel.green = sum_green / 445                elif y == img.height-1:46                    for i in range(0, 2):47                        for j in range(-1, 1):48                            neighbor = img.get_pixel(x + i, y + j)49                            sum_red += neighbor.red50                            sum_blue += neighbor.blue51                            sum_green += neighbor.green52                    pixel.red = sum_red / 453                    pixel.blue = sum_blue / 454                    pixel.green = sum_green / 455                else:56                    for i in range(0, 2):57                        for j in range(-1, 2):58                            neighbor = img.get_pixel(x + i, y + j)59                            sum_red += neighbor.red60                            sum_blue += neighbor.blue61                            sum_green += neighbor.green62                    pixel.red = sum_red / 663                    pixel.blue = sum_blue / 664                    pixel.green = sum_green / 665            elif y == 0:66                if x == img.width-1:67                    for i in range(-1, 1):68                        for j in range(0, 2):69                            neighbor = img.get_pixel(x + i, y + j)70                            sum_red += neighbor.red71                            sum_blue += neighbor.blue72                            sum_green += neighbor.green73                    pixel.red = sum_red / 474                    pixel.blue = sum_blue / 475                    pixel.green = sum_green / 476                else:77                    for i in range(-1, 2):78                        for j in range(0, 2):79                            neighbor = img.get_pixel(x + i, y + j)80                            sum_red += neighbor.red81                            sum_blue += neighbor.blue82                            sum_green += neighbor.green83                    pixel.red = sum_red / 684                    pixel.blue = sum_blue / 685                    pixel.green = sum_green / 686            elif x == img.width-1:87                if y == img.height-1:88                    for i in range(-1, 1):89                        for j in range(-1, 1):90                            neighbor = img.get_pixel(x + i, y + j)91                            sum_red += neighbor.red92                            sum_blue += neighbor.blue93                            sum_green += neighbor.green94                    pixel.red = sum_red / 495                    pixel.blue = sum_blue / 496                    pixel.green = sum_green / 497                else:98                    for i in range(-1, 1):99                        for j in range(-1, 2):100                            neighbor = img.get_pixel(x + i, y + j)101                            sum_red += neighbor.red102                            sum_blue += neighbor.blue103                            sum_green += neighbor.green104                    pixel.red = sum_red / 6105                    pixel.blue = sum_blue / 6106                    pixel.green = sum_green / 6107            elif y == img.height-1:108                for i in range(-1, 2):109                    for j in range(-1, 1):110                        neighbor = img.get_pixel(x + i, y + j)111                        sum_red += neighbor.red112                        sum_blue += neighbor.blue113                        sum_green += neighbor.green114                pixel.red = sum_red / 6115                pixel.blue = sum_blue / 6116                pixel.green = sum_green / 6117            else:118                for i in range(-1, 2):119                    for j in range(-1, 2):120                        neighbor = img.get_pixel(x+i, y+j)121                        sum_red += neighbor.red122                        sum_blue += neighbor.blue123                        sum_green += neighbor.green124                pixel.red = sum_red/9125                pixel.blue = sum_blue/9126                pixel.green = sum_green/9127    return new_img128# ---- DO NOT EDIT CODE BELOW THIS LINE ---- #129if __name__ == '__main__':...Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.
You could also refer to video tutorials over LambdaTest YouTube channel to get step by step demonstration from industry experts.
Get 100 minutes of automation test minutes FREE!!
