Topic 01-introduction.md
Introduction
Purpose
It is often said of Lua that it does not include batteries. That is because the goal of Lua is to produce a lean expressive language that will be used on all sorts of machines, (some of which don’t even have hierarchical filesystems). The Lua language is the equivalent of an operating system kernel; the creators of Lua do not see it as their responsibility to create a full software ecosystem around the language. That is the role of the community.
A principle of software design is to recognize common patterns and reuse them. If you find yourself writing things like io.write(string.format('the answer is %d ',42))
more than a number of times then it becomes useful just to define a function printf
. This is good, not just because repeated code is harder to maintain, but because such code is easier to read, once people understand your libraries.
Penlight captures many such code patterns, so that the intent of your code becomes clearer. For instance, a Lua idiom to copy a table is {unpack(t)}
, but this will only work for ‘small’ tables (for a given value of ‘small’) so it is not very robust. Also, the intent is not clear. So tablex.deepcopy is provided, which will also copy nested tables and and associated metatables, so it can be used to clone complex objects.
The default error handling policy follows that of the Lua standard libraries: if a argument is the wrong type, then an error will be thrown, but otherwise we return nil,message
if there is a problem. There are some exceptions; functions like input.fields default to shutting down the program immediately with a useful message. This is more appropriate behaviour for a script than providing a stack trace. (However, this default can be changed.) The lexer functions always throw errors, to simplify coding, and so should be wrapped in pcall .
By default, the error stacktrace starts with your code, since you are not usually interested in the internal details of the library. ??
If you are used to Python conventions, please note that all indices consistently start at 1.
The Lua function table.foreach has been deprecated in favour of the for in
statement, but such an operation becomes particularly useful with the higher-order function support in Penlight. Note that tablex.foreach reverses the order, so that the function is passed the value and then the key. Although perverse, this matches the intended use better.
The only important external dependence of Penlight is LuaFileSystem (lfs
), and if you want dir.copyfile to work cleanly on Windows, you will need either alien or be using LuaJIT as well. (The fallback is to call the equivalent shell commands.)
Some of the examples in this guide were created using ilua, which doesn’t require ‘=’ to print out expressions, and will attempt to print out table results as nicely as possible. This is also available under Lua for Windows, as a library, so the command lua -lilua -s
will work (the s option switches off ‘strict’ variable checking, which is annoying and conflicts with the use of _DEBUG
in some of these libraries.
To Inject or not to Inject?
It was realized a long time ago that large programs needed a way to keep names distinct by putting them into tables (Lua), namespaces (C++) or modules (Python). It is obviously impossible to run a company where everyone is called ‘Bruce’, except in Monty Python skits. These ‘namespace clashes’ are more of a problem in a simple language like Lua than in C++, because C++ does more complicated lookup over ‘injected namespaces’. However, in a small group of friends, ‘Bruce’ is usually unique, so in particular situations it’s useful to drop the formality and not use last names. It depends entirely on what kind of program you are writing, whether it is a ten line script or a ten thousand line program.
So the Penlight library provides the formal way and the informal way, without imposing any preference. You can do it formally like:
local utils = require 'pl.utils' utils.printf("%s\n","hello, world!")
or informally like:
require 'pl' utils.printf("%s\n","That feels better")
require 'pl'
makes all the separate Penlight modules available, without needing to require them each individually.. Generally, the formal way is better when writing modules, since then there are no global side-effects and the dependencies of your module are made explicit.
With Penlight after 0.9, please note that require 'pl.utils'
no longer implies that a global table pl.utils exists, since these new modules are no longer created with module()
.
Penlight will not bring in functions into the global table, or clobber standard tables like ‘io’. require(‘pl’) will bring tables like ‘utils’,‘tablex’,etc into the global table if they are used. This ‘load-on-demand’ strategy ensures that the whole kitchen sink is not loaded up front, so this method is as efficient as explicitly loading required modules.
You have an option to bring the pl.stringx methods into the standard string table. All strings have a metatable that allows for automatic lookup in string , so we can say s:upper()
. Importing stringx allows for its functions to also be called as methods: s:strip()
,etc:
require 'pl' stringx.import()
or, more explicitly:
require('pl.stringx').import()
A more delicate operation is importing tables into the local environment. This is convenient when the context makes the meaning of a name very clear:
> require 'pl' > utils.import(math) > = sin(1.2) 0.93203908596723
utils.import can also be passed a module name as a string, which is first required and then imported. If used in a module, import
will bring the symbols into the module context.
Keeping the global scope simple is very necessary with dynamic languages. Using global variables in a big program is always asking for trouble, especially since you do not have the spell-checking provided by a compiler. The pl.strict module enforces a simple rule: globals must be ‘declared’. This means that they must be assigned before use; assigning to nil
is sufficient.
> require 'pl.strict' > print(x) stdin:1: variable 'x' is not declared > x = nil > print(x) nil
The strict module provided by Penlight is compatible with the ‘load-on-demand’ scheme used by require 'pl
.
strict also disallows assignment to global variables, except in the main program. Generally, modules have no business messing with global scope; if you must do it, then use a call to rawset . Similarly, if you have to check for the existance of a global, use rawget .
If you wish to enforce strictness globally, then just add require 'pl.strict'
at the end of pl/init.lua
.
What are function arguments in Penlight?
Many functions in Penlight themselves take function arguments, like map
which applies a function to a list, element by element. You can use existing functions, like math.max , anonymous functions (like function(x,y) return x > y end
), or operations by name (e.g ‘*’ or ‘..’). The module pl.operator exports all the standard Lua operations, like the Python module of the same name. Penlight allows these to be referred to by name, so operator.gt can be more concisely expressed as ‘>’.
Note that the map
functions pass any extra arguments to the function, so we can have ls:filter('>',0)
, which is a shortcut for ls:filter(function(x) return x > 0 end)
.
Finally, pl.func supports placeholder expressions in the Boost lambda style, so that an anonymous function to multiply the two arguments can be expressed as _1*_2
.
To use them directly, note that all function arguments in Penlight go through utils.function_arg . pl.func registers itself with this function, so that you can directly use placeholder expressions with standard methods:
> _1 = func._1 > = List{10,20,30}:map(_1+1) {11,21,31}
Another option for short anonymous functions is provided by utils.string_lambda ; since 0.9 you have to explicitly ask for this feature:
> L = require 'pl.utils'.string_lambda > = List{10,20,30}:map (L'|x| x + 1') {11,21,31}
Pros and Cons of Loopless Programming
The standard loops-and-ifs ‘imperative’ style of programming is dominant, and often seems to be the ‘natural’ way of telling a machine what to do. It is in fact very much how the machine does things, but we need to take a step back and find ways of expressing solutions in a higher-level way. For instance, applying a function to all elements of a list is a common operation:
local res = {} for i = 1,#ls do res[i] = fun(ls[i]) end
This can be efficiently and succintly expressed as ls:map(fun)
. Not only is there less typing but the intention of the code is clearer. If readers of your code spend too much time trying to guess your intention by analyzing your loops, then you have failed to express yourself clearly. Similarly, ls:filter('>',0)
will give you all the values in a list greater than zero. (Of course, if you don’t feel like using List , or have non-list-like tables, then pl.tablex offers the same facilities. In fact, the List methods are implemented using tablex' functions.)
A common observation is that loopless programming is less efficient, particularly in the way it uses memory. ls1:map2('*',ls2):reduce '+'
will give you the dot product of two lists, but an unnecessary temporary list is created. But efficiency is relative to the actual situation, it may turn out to be fast enough, or may not appear in any crucial inner loops, etc.
Writing loops is ‘error-prone and tedious’, as Stroustrup says. But any half-decent editor can be taught to do much of that typing for you. The question should actually be: is it tedious to read loops? As with natural language, programmers tend to read chunks at a time.  One argument for loopless programming is the loops that you do write stand out more, and signal ‘something different happening here’. It should not be an all-or-nothing thing, since most programs require a mixture of idioms that suit the problem. Some languages (like APL) do nearly everything with map and reduce operations on arrays, and so solutions can sometimes seem forced. Wisdom is knowing when a particular idiom makes a particular problem easy to solve and the solution easy to explain afterwards.
Generally useful functions.
The function printf
discussed earlier is included in pl.utils because it makes properly formatted output easier. (There is an equivalent fprintf
which also takes a file object parameter, just like the C function.)
Utility functions like is_callable
and is_type
help with identifying what kind of animal you are dealing with. Obviously, a function is callable, but an object can be callable as well if it has overriden the __call
metamethod. The Lua type function handles the basic types, but can’t distinguish between different kinds of objects, which are all tables. So is_type
handles both cases, like is_type(s,"string")
and is_type(ls,List)
.
A common pattern when working with Lua varargs is capturing all the arguments in a table:
function t(...) local args = {...} ... end
But this will bite you someday when nil
is one of the arguments, since this will put a ‘hole’ in your table. In particular, #ls
will only give you the size upto the nil
value. Hence the need for table.pack – this is a new Lua 5.2 function which Penlight defines also for Lua 5.1.
function t(...) local args,n = table.pack(...) for i = 1,n do ... end end
The ‘memoize’ pattern occurs when you have a function which is expensive to call, but will always return the same value subsequently. utils.memoize is given a function, and returns another function. This calls the function the first time, saves the value for that argument, and thereafter for that argument returns the saved value. This is a more flexible alternative to building a table of values upfront, since in general you won’t know what values are needed.
sum = utils.memoize(function(n) local sum = 0 for i = 1,n do sum = sum + i end return sum end) ... s = sum(1e8) --takes time! ... s = sum(1e8) --returned saved value!
Penlight is fully compatible with Lua 5.1, 5.2 and LuaJIT 2. To ensure this, utils also defines the global Lua 5.2 load function when needed.
- the input (either a string or a function)
- the source name used in debug information
- the mode is a string that can have either or both of ‘b’ or ’t', depending on whether the source is a binary chunk or text code (default is ‘bt’)
- the environment for the compiled chunk
Using load should reduce the need to call the deprecated function setfenv , and make your Lua 5.1 code 5.2-friendly.
Application Support
app.parse_args is a simple command-line argument parser. If called without any arguments, it tries to use the global arg
array. It returns the flags (options begining with ‘–’) as a table of name/value pairs, and the arguments as an array. It knows about long GNU-style flag names, e.g. --value
, and groups of short flags are understood, so that -ab
is short for -a -b
. The flags result would then look like {value=true,a=true,b=true}
.
Flags may take values. The command-line --value=open -n10
would result in {value='open',n='10'}
; generally you can use ‘=’ or ‘:’ to separate the flag from its value, except in the special case where a short flag is followed by an integer. Or you may specify upfront that some flags have associated values, and then the values will follow the flag.
> require 'pl' > flags,args = utils.parse_args({'-o','fred','-n10','fred.txt'},{o=true}) > pretty.dump(flags) {o='fred',n='10'}
parse_args
is not intelligent or psychic; it will not convert any flag values or arguments for you, or raise errors. For that, have a look at Lapp.
An application which consists of several files usually cannot use require to load files in the same directory as the main script. app.require_here()
ensures that the Lua module path is modified so that files found locally are found first. In the examples
directory, test-symbols.lua uses this function to ensure that it can find symbols.lua even if it is not run from this directory.
app.appfile will create a filename that your application can use to store its private data, based on the script name. For example, app.appfile "test.txt"
from a script called testapp.lua produces the following file on my Windows machine:
C:\Documents and Settings\SJDonova\.testapp\test.txt
and the equivalent on my Linux machine:
/home/sdonovan/.testapp/test.txt
If .testapp
does not exist, it will be created.
Penlight makes it convenient to save application data in Lua format. You can use pretty.dump(t,file)
to write a Lua table in a human-readable form to a file, and pretty.read(file.read(file))
to generate the table again, using the pretty module.
Simplifying Object-Oriented Programming in Lua
Lua is similar to JavaScript in that the concept of class is not directly supported by the language. In fact, Lua has a very general mechanism for extending the behaviour of tables which makes it straightforward to implement classes. A table’s behaviour is controlled by its metatable. If that metatable has a __index
function or table, this will handle looking up anything which is not found in the original table. A class is just a table with an __index
key pointing to itself. Creating an object involves making a table and setting its metatable to the class; then when handling obj.fun
, Lua first looks up fun
in the table obj
, and if not found it looks it up in the class. obj:fun(a)
is just short for obj.fun(obj,a)
. So with the metatable mechanism and this bit of syntactic sugar, it is straightforward to implement classic object orientation.
-- animal.lua class = require 'pl.class' class.Animal() function Animal:_init(name) self.name = name end function Animal:__tostring() return self.name..': '..self:speak() end class.Dog(Animal) function Dog:speak() return 'bark' end class.Cat(Animal) function Cat:_init(name,breed) self:super(name) -- must init base! self.breed = breed end function Cat:speak() return 'meow' end class.Lion(Cat) function Lion:speak() return 'roar' end fido = Dog('Fido') felix = Cat('Felix','Tabby') leo = Lion('Leo','African') $ lua -i animal.lua > = fido,felix,leo Fido: bark Felix: meow Leo: roar > = leo:is_a(Animal) true > = leo:is_a(Dog) false > = leo:is_a(Cat) true
All Animal does is define __tostring
, which Lua will use whenever a string representation is needed of the object. In turn, this relies on speak
, which is not defined. So it’s what C++ people would call an abstract base class; the specific derived classes like Dog define speak
. (Please note that if derived classes have their own constructors, they must explicitly call the base constructor for their base class; this is conveniently available as the super
method.)
All such objects will have a is_a
method, which looks up the inheritance chain to find a match. Another form is class_of
, which can be safely called on all objects, so instead of leo:is_a(Animal)
one can say Animal:class_of(leo)
.
There are two ways to define a class, either class.Name()
or Name = class()
; both work identically, except that the first form will always put the class in the current environment (whether global or module); the second form provides more flexibility about where to store the class. The first form does name the class by setting the _name
field, which can be useful in identifying the objects of this type later. This session illustrates the usefulness of having named classes, if no __tostring
method is explicitly defined.
> class.Fred() > a = Fred() > = a Fred: 00459330 > Alice = class() > b = Alice() > = b table: 00459AE8 > Alice._name = 'Alice' > = b Alice: 00459AE8
So Alice = class(); Alice._name = 'Alice'
is exactly the same as class.Alice()
.
This useful notation is borrowed from Hugo Etchegoyen’s classlib which further extends this concept to allow for multiple inheritance.
Penlight provides a number of useful classes; there is List , which is a Lua clone of the standard Python list object, and Set which represents sets. There are three kinds of map defined: Map , MultiMap (where a key may have multiple values) and OrderedMap (where the order of insertion is remembered.). There is nothing special about these classes and you may inherit from them.
 We wish to control access to a field, but don’t wish to force the user of the class to say obj:get_field()
etc. This excerpt from tests/test-class.lua
shows how it is done:
local MyProps = class(class.properties) local setted_a, got_b function MyProps:_init () self._a = 1 self._b = 2 end function MyProps:set_a (v) setted_a = true self._a = v end function MyProps:get_b () got_b = true return self._b end local mp = MyProps() mp.a = 10 asserteq(mp.a,10) asserteq(mp.b,2) asserteq(setted_a and got_b, true)
The convention is that the internal field name is prefixed with an underscore; when reading mp.a
, first a check for an explicit getter get_a
and then only look for _a
. Simularly, writing mp.a
causes the setter set_a
to be used.
This is cool behaviour, but like much Lua metaprogramming, it is not free. Method lookup on such objects goes through __index
as before, but now __index
is a function which has to explicitly look up methods in the class, before doing any property indexing, which is not going to be as fast as field lookup. If however, your accessors actually do non-trivial things, then the extra overhead could be worth it.
This is not really intended for access control because external code can write to mp._a
directly. It is possible to have this kind of control in Lua, but it again comes with run-time costs, and in this case a simple audit of code will reveal any naughty use of ‘protected’ fields.


{% extends "layout.html" %} {% block body %} Sorry, but the page your are looking for obviously does not exist. If you typed the URL manually, check again for errors. Go back to main page {% endblock %}


Making a New Scene
To make a new scene, click the page icon in the top left of the Scene Editor (as shown in Figure 1.1.1).You will have to save a new scene before playing it, unless you are testing it from within the Scene Builder. If you click the Play Scene button or the Project->Run Game menu item the current scene will run in a test window without having to explicitly save the scene.


Folders
<Go Back>
backup-copy
css
experimental
File
File
File
File
index.html
README.md
screencap...50.png
Folders: 4
Files: 3
Size of all files: 134761 KB


6.11 psb_sprn — Reinit sparse matrix structure for psblas routines.
call psb_sprn(a, decsc_a, info, clear)
-
Type:
- Synchronous.
-
On Entry
-
-
a
- the matrix to be reinitialized.
Scope:local
Type:required
Intent: inout.
Specified as: a structured data of type psb_Tspmat_type.
-
desc_a
- the communication descriptor.
Scope:local.
Type:required.
Intent: in.
Specified as: a structured data of type psb_desc_type.
-
clear
- Choose whether to zero out matrix coefficients
Scope:local.
Type:optional.
Intent: in.
Default: true.
-
On Return
-
-
info
- Error code.
Scope: local
Type: required
Intent: out.
An integer value; 0 means no error has been detected.
Notes
- On exit from this routine the sparse matrix is in the update state.


The Java EE 7 Tutorial
48.2 Securing Web Applications
Web applications are created by application developers who give, sell, or otherwise transfer the application to an application deployer for installation into a runtime environment. Application developers communicate how to set up security for the deployed application by using annotations or deployment descriptors. This information is passed on to the deployer, who uses it to define method permissions for security roles, set up user authentication, and set up the appropriate transport mechanism. If the application developer doesn't define security requirements, the deployer will have to determine the security requirements independently.
Some elements necessary for security in a web application cannot be specified as annotations for all types of web applications. This chapter explains how to secure web applications using annotations wherever possible. It explains how to use deployment descriptors where annotations cannot be used.
48.2.1 Specifying Security Constraints
A security constraint is used to define the access privileges to a collection of resources using their URL mapping.
If your web application uses a servlet, you can express the security constraint information by using annotations. Specifically, you use the @HttpConstraint
and, optionally, the @HttpMethodConstraint
annotations within the @ServletSecurity
annotation to specify a security constraint.
If your web application does not use a servlet, however, you must specify a security-constraint
element in the deployment descriptor file. The authentication mechanism cannot be expressed using annotations, so if you use any authentication method other than BASIC
(the default), a deployment descriptor is required.
The following subelements can be part of a security-constraint
.
-
Web resource collection (
web-resource-collection
): A list of URL patterns (the part of a URL after the host name and port you want to constrain) and HTTP operations (the methods within the files that match the URL pattern you want to constrain) that describe a set of resources to be protected. Web resource collections are discussed in Specifying a Web Resource Collection. -
Authorization constraint (
auth-constraint
): Specifies whether authentication is to be used and names the roles authorized to perform the constrained requests. For more information about authorization constraints, see Specifying an Authorization Constraint. -
User data constraint (
user-data-constraint
): Specifies how data is protected when transported between a client and a server. User data constraints are discussed in Specifying a Secure Connection.
<IP_ADDRESS> Specifying a Web Resource Collection
A web resource collection consists of the following subelements.
-
web-resource-name
is the name you use for this resource. Its use is optional. -
url-pattern
is used to list the request URI to be protected. Many applications have both unprotected and protected resources. To provide unrestricted access to a resource, do not configure a security constraint for that particular request URI.The request URI is the part of a URL after the host name and port. For example, let's say that you have an e-commerce site with a catalog that you would want anyone to be able to access and browse, and a shopping cart area for customers only. You could set up the paths for your web application so that the pattern
/cart/*
is protected but nothing else is protected. Assuming that the application is installed at context path/myapp
, the following are true.-
http://localhost:8080/myapp/index.xhtml
is not protected. -
http://localhost:8080/myapp/cart/index.xhtml
is protected.
A user will be prompted to log in the first time he or she accesses a resource in the
cart/
subdirectory. -
-
http-method
orhttp-method-omission
is used to specify which methods should be protected or which methods should be omitted from protection. An HTTP method is protected by aweb-resource-collection
under any of the following circumstances:-
If no HTTP methods are named in the collection (which means that all are protected)
-
If the collection specifically names the HTTP method in an
http-method
subelement -
If the collection contains one or more
http-method-omission
elements, none of which names the HTTP method
-
<IP_ADDRESS> Specifying an Authorization Constraint
An authorization constraint (auth-constraint
) contains the role-name
element. You can use as many role-name
elements as needed here.
An authorization constraint establishes a requirement for authentication and names the roles authorized to access the URL patterns and HTTP methods declared by this security constraint. If there is no authorization constraint, the container must accept the request without requiring user authentication. If there is an authorization constraint but no roles are specified within it, the container will not allow access to constrained requests under any circumstances. Each role name specified here must either correspond to the role name of one of the security-role
elements defined for this web application or be the specially reserved role name *
, which indicates all roles in the web application. Role names are case sensitive. The roles defined for the application must be mapped to users and groups defined on the server, except when default principal-to-role mapping is used.
For more information about security roles, see Declaring Security Roles. For information on mapping security roles, see Mapping Roles to Users and Groups.
For a servlet, the @HttpConstraint
and @HttpMethodConstraint
annotations accept a rolesAllowed
element that specifies the authorized roles.
<IP_ADDRESS> Specifying a Secure Connection
A user data constraint (user-data-constraint
in the deployment descriptor) contains the transport-guarantee
subelement. A user data constraint can be used to require that a protected transport-layer connection, such as HTTPS, be used for all constrained URL patterns and HTTP methods specified in the security constraint. The choices for transport guarantee are CONFIDENTIAL
, INTEGRAL
, or NONE
. If you specify CONFIDENTIAL
or INTEGRAL
as a security constraint, it generally means that the use of SSL is required and applies to all requests that match the URL patterns in the web resource collection, not just to the login dialog box.
The strength of the required protection is defined by the value of the transport guarantee, as follows.
-
Specify
CONFIDENTIAL
when the application requires that data be transmitted so as to prevent other entities from observing the contents of the transmission. -
Specify
INTEGRAL
when the application requires that the data be sent between client and server in such a way that it cannot be changed in transit. -
Specify
NONE
to indicate that the container must accept the constrained requests on any connection, including an unprotected one.
|
Note: In practice, Java EE servers treat the |
The user data constraint is handy to use in conjunction with basic and form-based user authentication. When the login authentication method is set to BASIC
or FORM
, passwords are not protected, meaning that passwords sent between a client and a server on an unprotected session can be viewed and intercepted by third parties. Using a user data constraint with the user authentication mechanism can alleviate this concern. Configuring a user authentication mechanism is described in Specifying an Authentication Mechanism in the Deployment Descriptor.
To guarantee that data is transported over a secure connection, ensure that SSL support is configured for your server. SSL support is already configured for GlassFish Server.
|
Note: After you switch to SSL for a session, you should never accept any non-SSL requests for the rest of that session. For example, a shopping site might not use SSL until the checkout page, and then it might switch to using SSL to accept your card number. After switching to SSL, you should stop listening to non-SSL requests for this session. The reason for this practice is that the session ID itself was not encrypted on the earlier communications. This is not so bad when you're only doing your shopping, but after the credit card information is stored in the session, you don't want anyone to use that information to fake the purchase transaction against your credit card. This practice could be easily implemented by using a filter. |
<IP_ADDRESS> Specifying Security Constraints for Resources
You can create security constraints for resources within your application. For example, you could allow users with the role of PARTNER
full access to all resources at the URL pattern /acme/wholesale/*
and allow users with the role of CLIENT
full access to all resources at the URL pattern /acme/retail/*
. This is the recommended way to protect resources if you do not want to protect some HTTP methods while leaving other HTTP methods unprotected. An example of a deployment descriptor that would demonstrate this functionality is the following:
<!-- SECURITY CONSTRAINT #1 --> <security-constraint> <web-resource-collection> <web-resource-name>wholesale</web-resource-name> <url-pattern>/acme/wholesale/*</url-pattern> </web-resource-collection> <auth-constraint> <role-name>PARTNER</role-name> </auth-constraint> <user-data-constraint> <transport-guarantee>CONFIDENTIAL</transport-guarantee> </user-data-constraint> </security-constraint> <!-- SECURITY CONSTRAINT #2 --> <security-constraint> <web-resource-collection> <web-resource-name>retail</web-resource-name> <url-pattern>/acme/retail/*</url-pattern> </web-resource-collection> <auth-constraint> <role-name>CLIENT</role-name> </auth-constraint> <user-data-constraint> <transport-guarantee>CONFIDENTIAL</transport-guarantee> </user-data-constraint> </security-constraint>
48.2.2 Specifying Authentication Mechanisms
A user authentication mechanism specifies
-
The way a user gains access to web content
-
With basic authentication, the realm in which the user will be authenticated
-
With form-based authentication, additional attributes
When an authentication mechanism is specified, the user must be authenticated before access is granted to any resource that is constrained by a security constraint. There can be multiple security constraints applying to multiple resources, but the same authentication method will apply to all constrained resources in an application.
Before you can authenticate a user, you must have a database of user names, passwords, and roles configured on your web or application server. For information on setting up the user database, see Managing Users and Groups in GlassFish Server.
The Java EE platform supports the following authentication mechanisms:
-
Basic authentication
-
Form-based authentication
-
Digest authentication
-
Client authentication
-
Mutual authentication
Basic, form-based, and digest authentication are discussed in this section. Client and mutual authentication are discussed in Chapter 50, "Java EE Security: Advanced Topics".
HTTP basic authentication and form-based authentication are not very secure authentication mechanisms. Basic authentication sends user names and passwords over the Internet as Base64-encoded text. Form-based authentication sends this data as plain text. In both cases, the target server is not authenticated. Therefore, these forms of authentication leave user data exposed and vulnerable. If someone can intercept the transmission, the user name and password information can easily be decoded.
However, when a secure transport mechanism, such as SSL, or security at the network level, such as the Internet Protocol Security (IPsec) protocol or virtual private network (VPN) strategies, is used in conjunction with basic or form-based authentication, some of these concerns can be alleviated. To specify a secure transport mechanism, use the elements described in Specifying a Secure Connection.
<IP_ADDRESS> HTTP Basic Authentication
Specifying HTTP basic authentication requires that the server request a user name and password from the web client and verify that the user name and password are valid by comparing them against a database of authorized users in the specified or default realm.
Basic authentication is the default when you do not specify an authentication mechanism.
When basic authentication is used, the following actions occur.
-
A client requests access to a protected resource.
-
The web server returns a dialog box that requests the user name and password.
-
The client submits the user name and password to the server.
-
The server authenticates the user in the specified realm and, if successful, returns the requested resource.
Figure 48-1 shows what happens when you specify HTTP basic authentication.
<IP_ADDRESS> Form-Based Authentication
Form-based authentication allows the developer to control the look and feel of the login authentication screens by customizing the login screen and error pages that an HTTP browser presents to the end user. When form-based authentication is declared, the following actions occur.
-
A client requests access to a protected resource.
-
If the client is unauthenticated, the server redirects the client to a login page.
-
The client submits the login form to the server.
-
The server attempts to authenticate the user.
-
If authentication succeeds, the authenticated user's principal is checked to ensure that it is in a role that is authorized to access the resource. If the user is authorized, the server redirects the client to the resource by using the stored URL path.
-
If authentication fails, the client is forwarded or redirected to an error page.
-
Figure 48-2 shows what happens when you specify form-based authentication.
The section The hello1-formauth Example: Form-Based Authentication with a JavaServer Faces Application is an example application that uses form-based authentication.
When you create a form-based login, be sure to maintain sessions using cookies or SSL session information.
For authentication to proceed appropriately, the action of the login form must always be j_security_check
. This restriction is made so that the login form will work no matter which resource it is for and to avoid requiring the server to specify the action field of the outbound form. The following code snippet shows how the form should be coded into the HTML page:
<form method="POST" action="j_security_check"> <input type="text" name="j_username"> <input type="password" name="j_password"> </form>
<IP_ADDRESS> Digest Authentication
Like basic authentication, digest authentication authenticates a user based on a user name and a password. However, unlike basic authentication, digest authentication does not send user passwords over the network. Instead, the client sends a one-way cryptographic hash of the password and additional data. Although passwords are not sent on the wire, digest authentication requires that clear-text password equivalents be available to the authenticating container so that it can validate received authenticators by calculating the expected digest.
48.2.3 Specifying an Authentication Mechanism in the Deployment Descriptor
To specify an authentication mechanism, use the login-config
element. It can contain the following subelements.
-
The
auth-method
subelement configures the authentication mechanism for the web application. The element content must be eitherNONE
,BASIC
,DIGEST
,FORM
, orCLIENT-CERT
. -
The
realm-name
subelement indicates the realm name to use when the basic authentication scheme is chosen for the web application. -
The
form-login-config
subelement specifies the login and error pages that should be used when form-based login is specified.
|
Note: Another way to specify form-based authentication is to use the |
When you try to access a web resource that is constrained by a security-constraint
element, the web container activates the authentication mechanism that has been configured for that resource. The authentication mechanism specifies how the user will be prompted to log in. If the login-config
element is present and the auth-method
element contains a value other than NONE
, the user must be authenticated to access the resource. If you do not specify an authentication mechanism, authentication of the user is not required.
The following example shows how to declare form-based authentication in your deployment descriptor:
<login-config> <auth-method>FORM</auth-method> <realm-name>file</realm-name> <form-login-config> <form-login-page>/login.xhtml</form-login-page> <form-error-page>/error.xhtml</form-error-page> </form-login-config> </login-config>
The login and error page locations are specified relative to the location of the deployment descriptor. Examples of login and error pages are shown in Creating the Login Form and the Error Page.
The following example shows how to declare digest authentication in your deployment descriptor:
<login-config> <auth-method>DIGEST</auth-method> </login-config>
48.2.4 Declaring Security Roles
You can declare security role names used in web applications by using the security-role
element of the deployment descriptor. Use this element to list all the security roles that you have referenced in your application.
The following snippet of a deployment descriptor declares the roles that will be used in an application using the security-role
element and specifies which of these roles is authorized to access protected resources using the auth-constraint
element:
<security-constraint> <web-resource-collection> <web-resource-name>Protected Area</web-resource-name> <url-pattern>/security/protected/*</url-pattern> <http-method>PUT</http-method> <http-method>DELETE</http-method> <http-method>GET</http-method> <http-method>POST</http-method> </web-resource-collection> <auth-constraint> <role-name>manager</role-name> </auth-constraint> </security-constraint> <!-- Security roles used by this web application --> <security-role> <role-name>manager</role-name> </security-role> <security-role> <role-name>employee</role-name> </security-role>
In this example, the security-role
element lists all the security roles used in the application: manager
and employee
. This enables the deployer to map all the roles defined in the application to users and groups defined in GlassFish Server.
The auth-constraint
element specifies the role, manager
, that can access the HTTP methods PUT, DELETE, GET, and POST located in the directory specified by the url-pattern
element (/security/protected/*
).
The @ServletSecurity
annotation cannot be used in this situation because its constraints apply to all URL patterns specified by the @WebServlet
annotation.


Film List
film_id
title
description
release_year
language_id
rental_duration
rental_rate
length
replacement_cost
rating
last_update
special_features
fulltext


Keystone¶
Inter-Sphinx testing¶
Security compliance¶
The keystone charm’s password-security-compliance
configuration option sets
the [security_compliance]
section of Keystone’s configuration file. The
value of this option is a YAML dictionary that includes support for the
following keys (value formats and units are also included).
change_password_upon_first_use: <boolean>
disable_user_account_days_inactive: <int> (days)
lockout_duration: <int> (seconds)
lockout_failure_attempts: <int>
minimum_password_age: <int> (days)
password_expires_days: <int> (days)
password_regex: <string>
password_regex_description: <string>
unique_last_password_count: <int>
Important
The upstream document Security compliance and PCI-DSS should be consulted before setting any of these options.
The configuration is typically contained within a file, say config.yaml
.
For example:
password-security-compliance:
change_password_upon_first_use: True
lockout_duration: 1800
lockout_failure_attempts: 3
...
It is applied in the usual way:
juju config keystone --file config.yaml
The charm will protect service accounts (accounts requested by other units that are in the service domain) against being forced to change their password. Operators should also ensure that any other accounts are protected as per the above referenced note.
Operators should also ensure that any non-service accounts are protected as per the upstream document.
The charm will enter a blocked state if the value of charm option
password-security-compliance
is not in valid YAML format and/or the
individual service options do not conform to the proper value formats.
Token support¶
Over time OpenStack has come to support two Keystone token formats: UUID and Fernet.
Fernet tokens were added to address the issue of size observed with PKI and PKIZ tokens in addition to continuing the Keystone behaviour of persisting tokens to a common database cluster (like UUID tokens). For more information see this Fernet FAQ.
Important
Starting with OpenStack Rocky, only the Fernet format for authentication tokens is supported. This is documented as a known upgrade issue.
Fernet keys¶
Theory of operation¶
Keystone generates Fernet keys, which in turn are used to generate/encrypt and decode/decrypt Fernet tokens.
There are three key types, and each is associated with a naming scheme that is applied to the directories in which they are found. Directory names are based on integers:
- primary key
integer: the highest one
generates tokens
number of keys: one
- staged key
integer: ‘0’
will become the next primary key
can decode tokens
number of keys: one
- secondary key
integer: any other number
was previously a primary key
can decode tokens
number of keys: one or more
Each key type must be present at all times. This means Keystone uses a minimum of three keys.
Key rotation¶
Key rotation refers to the process by which two keys assume a different type, one key gets created, and typically one key gets removed:
staged evolves to primary
primary evolves to secondary
the staged is created
a secondary is removed
A key will get removed if the total number of keys surpasses the specified maximum allowed (more on this later).
This process takes place on the master keystone unit and takes into account three aspects:
rotation frequency
token expiration
maximum number of active keys
These are related according to this formula:
In the keystone charm, token expiration and the maximum number of active keys
are specified, respectively, with the token-expiration
and the
fernet-max-active-keys
configuration options.
For example, given that an administrator desires a token expiration of 1 hour (3600 seconds) and a rotation frequency of 15 minutes (900 seconds), the maximum number of active keys must be six:
The above two options can then be set accordingly:
token-expiration: 3600
fernet-max-active-keys: 6
Rotation frequency¶
From the point of view of rotation frequency:
Since the denominator must lead to a positive real number for rotation
frequency the value of fernet-max-active-keys
must be at least three, and
this constraint is enforced by the charm.
To increase rotation frequency either decrease fernet-max-active-keys
or
increase token-expiration
. To decrease rotation frequency, do the opposite.
The most notable effect of increasing rotation frequency is the reduction in key lifetime (secondary keys get removed more often).
Default values¶
These are the default values for these keystone charm options and the resulting default rotation frequency:
token-expiration
: 3600 sec (1 hour)fernet-max-active-keys
: 3rotation frequency
: 3600 sec (1 hour)
Token validation breakage¶
Token validation breakage is a situation in which a decoding key is no longer available to validate an unexpired token. This can be caused by a rotation frequency that has been set too high (a very short key lifetime) or by keys failing to synchronise (from the master keystone unit to the other units) prior to the succeeding rotation. Incremental changes to rotation frequency is therefore advised.


- get(long) - Method in class com.tomzhu.external.BPlusTree
-
try to get the associated value for the key and return a negative integer
if no such key exists
- get(long) - Method in class com.tomzhu.external.HashTable
-
try to get the associated value for the key.
- get(K) - Method in class com.tomzhu.hash.CuckooHashTable
-
try to get the associated value for the key.
- get(K) - Method in class com.tomzhu.hash.ExtensibleHashTable
-
try to get the associated value for key and return null if no such key found
- get(K) - Method in class com.tomzhu.hash.HashTableByLinearProbing
-
try to get the associated value for key.
- get(K) - Method in class com.tomzhu.hash.HashTableByQuadraticProbing
-
try to get and return the associated value for key, return null if no such key.
- get(K) - Method in class com.tomzhu.hash.HashTableBySeparateChain
-
try to get the associated value for the specific key.
- get(K) - Method in class com.tomzhu.hash.HopscotchHashTable
-
try to get the associated value for key.
- get(K) - Method in class com.tomzhu.hash.PerfectHashingTable
-
try to get the associated value for the key.
- get(int) - Method in class com.tomzhu.list.ArrayList
-
try to get the element at location
i and throws
MyNosuchElementException
when
the location is not feasible such as negative or exceeds the current size of the list.
- get(int) - Method in class com.tomzhu.list.LinkedList
-
return the element at location i , throw MyNosuchElementException when
the location i is not reliable.
- get(K) - Method in class com.tomzhu.tree.HashMap
-
try to get the value of key on this hashMap.
- get(K) - Method in class com.tomzhu.tree.KeydRedBlackTree
-
- get(E) - Method in class com.tomzhu.tree.TreeMap
-
try to get the associated value of key.
- getChild(BasicTreeNode<E>, int) - Method in class com.tomzhu.tree.BasicTree
-
return the child node at specific location i for the node.
- getChild(int) - Method in class com.tomzhu.tree.BasicTreeNode
-
get the i-th child of the current node.
- getChildrenSize(BasicTreeNode<E>) - Method in class com.tomzhu.tree.BasicTree
-
- getChildrenSize() - Method in class com.tomzhu.tree.TreeNode
-
- getChilds(BasicTreeNode<E>, boolean) - Method in class com.tomzhu.tree.BasicTree
-
return children as an array, leftToRight imply the order.
- getChilds(boolean) - Method in class com.tomzhu.tree.BasicTreeNode
-
- getChilds(boolean) - Method in class com.tomzhu.tree.BinaryTreeNode
-
- getChilds(boolean) - Method in class com.tomzhu.tree.TreeNode
-
- getElement() - Method in class com.tomzhu.tree.AVLTreeNode
-
- getFirstChild(BasicTreeNode<E>) - Method in class com.tomzhu.tree.BasicTree
-
- getFirstChild() - Method in class com.tomzhu.tree.BasicTreeNode
-
- getHead() - Method in class com.tomzhu.list.Queue
-
- getHead() - Method in class com.tomzhu.list.Stack
-
return the tail element in this stack and don't remove it.
- getHeight() - Method in class com.tomzhu.tree.AVLTreeNode
-
- getLastChild(BasicTreeNode<E>) - Method in class com.tomzhu.tree.BasicTree
-
- getLastChild() - Method in class com.tomzhu.tree.BasicTreeNode
-
- getlChildl() - Method in class com.tomzhu.tree.AVLTreeNode
-
- getLeftChild(BinaryTreeNode<E>) - Method in class com.tomzhu.tree.BinaryTree
-
- getLeftChild() - Method in class com.tomzhu.tree.BinaryTreeNode
-
- getLeftSibling(BasicTreeNode<E>) - Method in class com.tomzhu.tree.BasicTree
-
- getLeftSibling() - Method in class com.tomzhu.tree.BasicTreeNode
-
- getLoadFactor() - Method in class com.tomzhu.tree.HashMap
-
- getMax() - Method in class com.tomzhu.heap.BasicArrayHeap
-
- getMax() - Method in class com.tomzhu.heap.BasicDoubleEndedHeap
-
- getMax() - Method in class com.tomzhu.heap.BinomialQueue
-
- getMax() - Method in class com.tomzhu.heap.LeftistHeap
-
- getMax() - Method in class com.tomzhu.heap.SkewHeap
-
- getMax() - Method in class com.tomzhu.tree.AVLTree
-
- getMax() - Method in class com.tomzhu.tree.BinarySearchTree
-
- getMax() - Method in class com.tomzhu.tree.BTree
-
return the maximum element in this tree.
- getMax() - Method in class com.tomzhu.tree.RedBlackTree
-
- getMax() - Method in class com.tomzhu.tree.SplayTree
-
- getMin() - Method in class com.tomzhu.heap.BasicArrayHeap
-
- getMin() - Method in class com.tomzhu.heap.BasicDoubleEndedHeap
-
- getMin() - Method in class com.tomzhu.heap.BinomialQueue
-
- getMin() - Method in class com.tomzhu.heap.LeftistHeap
-
- getMin() - Method in class com.tomzhu.heap.SkewHeap
-
- getMin() - Method in class com.tomzhu.tree.AVLTree
-
- getMin() - Method in class com.tomzhu.tree.BinarySearchTree
-
- getMin() - Method in class com.tomzhu.tree.BTree
-
return the minimum element in this tree, return null if the tree is empty.
- getMin() - Method in class com.tomzhu.tree.RedBlackTree
-
- getMin() - Method in class com.tomzhu.tree.SplayTree
-
- getParent() - Method in class com.tomzhu.tree.AVLTreeNode
-
- getParent(BasicTreeNode<E>) - Method in class com.tomzhu.tree.BasicTree
-
- getParent() - Method in class com.tomzhu.tree.BasicTreeNode
-
- getParent() - Method in class com.tomzhu.tree.BinaryTreeNode
-
- getPriorityMax() - Method in class com.tomzhu.tree.Treap
-
- getPriorityMin() - Method in class com.tomzhu.tree.Treap
-
- getrChild() - Method in class com.tomzhu.tree.AVLTreeNode
-
- getRightChild(BinaryTreeNode<E>) - Method in class com.tomzhu.tree.BinaryTree
-
- getRightChild() - Method in class com.tomzhu.tree.BinaryTreeNode
-
- getRightSibling(BasicTreeNode<E>) - Method in class com.tomzhu.tree.BasicTree
-
- getRightSibling() - Method in class com.tomzhu.tree.BasicTreeNode
-
- getRoot() - Method in class com.tomzhu.tree.AVLTree
-
- getRoot() - Method in class com.tomzhu.tree.BasicTree
-
- getRoot() - Method in class com.tomzhu.tree.BinarySearchTree
-
- getRoot() - Method in class com.tomzhu.tree.BinaryTree
-
- getRoot() - Method in class com.tomzhu.tree.SplayTree
-
- getRootNode() - Method in class com.tomzhu.tree.AVLTree
-
- getRootNode() - Method in class com.tomzhu.tree.SplayTree
-
- getSize() - Method in class com.tomzhu.heap.BasicArrayHeap
-
- getSize() - Method in class com.tomzhu.heap.BasicDoubleEndedHeap
-
- getSize() - Method in class com.tomzhu.list.ArrayList
-
- getSize() - Method in class com.tomzhu.list.LinkedList
-
return the current size of the list.
- getSize() - Method in class com.tomzhu.list.Queue
-
- getSize() - Method in class com.tomzhu.list.Stack
-
- getSize() - Method in class com.tomzhu.tree.HashMap
-
- getValue() - Method in class com.tomzhu.tree.TreeNode
-


{% extends "edd_base.html" %} {% load static %} {% block js_css %} {{ block.super }} {% endblock js_css %} {% block head_title %} {{ block.super }} — Experiment Description File {% endblock head_title %} {% block body_title %} {{ block.super }} — Experiment Description File {% endblock body_title %} {% block content %}
An experiment description file is a simple Excel file that allows you to quickly enter the experimental conditions for your Study. EDD needs to know what the experimental conditions are for measurements you are importing, preferably before you import the data into EDD, and sometimes before even measuring it in the lab. An experiment description file is normally the most efficient way to input that information.
Before getting into the details of all the options available in the file, consider downloading the sample file. If the sample file makes sense to you out-of-the-box, run with it! If this is your first time using EDD, and you are not familiar with the concepts, the first thing to do is to learn about Lines.
A "Line" in EDD is a distinct set of experimental conditions, e.g. a single preparation of culture. A Line generally corresponds to the contents of a shake flask or well plate, though it could also be, e.g. a tube containing extract from an arabidopsis seed or an enzyme cocktail. We avoided using terms like "sample" to prevent confusion with sampling for measurement.
Each Line has a unique name within the EDD Study, an optional description, and some associated metadata that capture the experimental conditions, e.g. growth temperature, strain, media, etc. Through an intermediary called an "Assay" that you may read about later, a Line captures the association of a set of experimental conditions with the resulting measurements. Many casual EDD users wo not need to understand the details of what is an Assay.
You will often want the Line names you enter in EDD to be more descriptive than the shorthand labels on tiny tubes in the lab. You will likely want to name your Lines in EDD for experimental conditions that make them unique so that you and other researchers can easily distinguish between them in the user interface or in outputs exported from EDD. For example, "WT-LB" (short for "wild type in LB media") is more descriptive than the "A1" label on a plate well.
Your organization will likely encourage you to use a standard Line naming convention to help other researchers easily understand your data. See examples below for some typical Line names and characteristics.
An experiment description file is an efficient way for you to add Lines to your Study with a minimum of data entry. In the simplest case, each row of the file represents experimental conditions for a single Line in your Study. For example, consider the following single-row experiment description file:
| Line Name | Line Description | Media | Part ID |
|---|---|---|---|
| WT-Control | Wildtype s. cervisae | LB | JBx_042441 |
Dropping this file into EDD creates a single Line, visible in the Study's "Lines" section in nearly identical form to the input file:
| Name | Strain | Labeling | Media |
|---|---|---|---|
| WT-Control | BY4742 | -- | LB |
The contents of EDD's table are nearly identical to the input file, with some simple exceptions. Most notably, "Part ID" is provided as input to help EDD locate the relevant strain in ICE, but it is not particularly recognizable to experimentalists. Instead of the part ID provided as input to creating the Line, EDD displays the associated strain name instead, which should be more useful, while also linking the name to the related ICE entry.
You can create multiple Lines, each with replicates, with only a slightly more complicated file:
| Line Name | Line Description | Media | Part ID | Replicate Count |
|---|---|---|---|---|
| WT-Control | Wildtype s. cervisae | LB | JBx_042441 | 3 |
| 413 | gre3∆; pMOXYL3 pRS413 | LB | JBx_039498 | 3 |
Each row of the Experiment Description file in Figure 4 is a set of values that define distinct experimental conditions, along with replicates of each. Lines created by this Experiment Description file would appear in EDD as shown in Figure 5. Note that using the replicates column caused the suffix "R-#" to be appended to the Line name from the original file to make the resulting Line names unique within the Study.
| Name | Strain | Labeling | Media |
|---|---|---|---|
| WT-Control-R1 | BY4742 | -- | LB |
| WT-Control-R2 | BY4742 | -- | LB |
| WT-Control-R3 | BY4742 | -- | LB |
| 413-R1 | JBEI-9005 | -- | LB |
| 413-R2 | JBEI-9005 | -- | LB |
| 413-R3 | JBEI-9005 | -- | LB |
Column headers in the Experiment Description file describe characteristics you will assign to the Lines, and maybe Assays, in your Study. You can create an Experiment Description file with minimal input, but truly capturing the conditions of your experiment for posterity often takes a reasonable amount of additional effort. The list of conditions supported by EDD is available below, and we suggest that you scan the list and include all the relevant data in your Experiment Description file.
Some fixed Line and Assay characteristics are baked into the EDD code and into its Experiment Description file format, while others are defined by metadata types that system administrators enter into EDD's database.
Chances are good that many experimenters can just run with a subset of the columns from the sample file, but see below if you need to add other columns to fully describe the experimental conditions in your Study. The goal is to enter enough data into EDD to allow another researcher to reproduce your Study with little or no additional context. You should also prioritize entering unambiguous / machine-readable metadata in columns rather than describing your experiment in text in the "Description" column.
These fundamental Line characteristics are hard-coded into EDD, and will always be available in Experiment Description files.
| Line Characteristic | Required Column Header | Description | Interpretation in Experiment Description file | Required? |
|---|---|---|---|---|
| Name | Line Name | A short description that uniquely identifies this set of experimental conditions within your Study. Experimenters often include, e.g. the strain number, plate number, etc. | Exact value is used to name the Line, or the prefix for Line names if multiple replicates are used or if combinatorial Line creation features are in use (see below). This value will also be the prefix for Assays created by the file. Values that duplicate existing Lines in the Study or other rows in the file will cause the entire file upload to fail. | YES |
| Description | Line Description |
A short human-readable description for the Line. Ideally all experimental conditions will be captured as machine-readable metadata, but anything not currently captured as metadata should be inserted here. Column header value matches the one generated by ICE's bulk download and used by EDD's bulk Line creation script. |
The exact text of the description. | No, but strongly encouraged |
| Part ID(s) | Part ID | The unique ICE part number identifiers for strains in this culture. Note that non-strain ICE entries are not presently allowed in EDD. See below for advanced use, and note that this header matches the format of ICE's bulk export and EDD's bulk Line creation script. | Used to link EDD Lines to the referenced ICE strains. See below for directions on including multiple stains in the same Line. | No, but strongly encouraged where applicable |
| Replicates | Replicate Count | The number of experimental replicates for this set of conditions | Used to create replicates of this Line without having to duplicate data entry for it. If more than one replicate is created for a Line, the Line name will have the suffix "-R#" appended, where # is the replicate number. | No, but strongly encouraged, especially to save data entry work for EDD Line creation |
In addition to the Line characteristics built into EDD, you may also use Experiment Description files to provide any Line or Assay metadata defined in EDD's database using the Administration tools (with a few exceptions in the initial version--see below). The difference between user-specified Line characteristics and built-in characteristics should be transparent to most users. In fact, all of the previous examples have used "Media", which is not, strictly speaking, one of the built-in Line characteristics described in the table above.
To enter user-defined metadata in your Experiment Description file, just paste the exact text of the metadata name as a column header. Again the "Media" column in examples above satisfies this criterion.
Unsupported columns: the following Line characteristics are not supported as column headers in the initial version of the Experiment Description file: control, Line experimenter, Line contact. You can add these data after creating Lines using EDD's bulk Line editing feature.
You may define columns in any order, as long as the single required column, "Line Name", is present. You also do not have to worry about capitalization or accidental use of leading or trailing whitespace in the column headers. With the exception of Line names, you can leave any non-header cell blank to omit that metadata for Lines or Assays created by the corresponding table row. Note that column order in your file can affect naming in the resulting Lines or Assays, but only if you use advanced combinatorial features (see below). At the time of writing, there's no error checking on non-time inputs, so enter your data carefully!
If your experiment involves use of a large strain library, or many combinations of experimental conditions, you may want to consider options for reducing the amount of data entry required to create Lines in your EDD Study. See subsections below for several options.
One option is to use ICE's bulk export feature to create a CSV file as a starting point for your EDD Experiment Description file. EDD's Experiment Description file purposefully uses the same "Part ID" column header as ICE's export, so all you have to do is remove the other unnecessary columns from the ICE export, then add other columns to fully describe your experiment.
If you need to create a large number of Lines to represent your experiment, Experiment Description files have advanced options that allow you to significantly cut down on the amount of repetitive data entry required. See Combinatorial Line Creation and Combinatorial Assay Creation below.
An option available to you as a suppliment to Experiment Description files is bulk Line editing. After creating Lines in your Study, you can select multiple Lines to edit shared characteristics to be applied to all of them simultaneously. From the Experiment Description section of a Study that has existing Lines, check the boxes to the left of the Lines you want to edit, then hit the edit button to bulk edit them.
For Studies with very large numbers of Lines, your browser may time out during upload of an Experiment Description file while Lines or Assays are being created, giving the appearance that your file upload attempt failed. If this is the case, try refreshing your Study after a few minutes to see whether the attempt succeeded. This timeout should not occur often, and future improvements may help to avoid it. You can also use the bulk Line creation script to avoid this problem (see below).
To reduce the need for repetitive data entry in your Experiment Description file, you can append "s" or "(s)" to the end of most column headers, then add comma-separated values in that column to have EDD generate Lines combinatorially. Note that when your file contains combinatorial input, EDD will insert the values from combinatorial columns into the resulting Line names so they are unique (see examples below).
Figure 6 shows an example file that creates Lines combinatorially using different media.
| Line Name | Line Description | Media(s) | Part ID | Replicate Count |
|---|---|---|---|---|
| WT-Control | Wildtype s. cervisae | LB, EZ, Minimal | JBx_042441 | 3 |
The first difference to notice about this file is that "(s)" has been appended to the Line metadata column "Media" to inform EDD that values in that column are combinatorial. As a result of the altered column label, comma-separated values each result in the creation of a new Line, resulting in many fewer rows in the file than Lines it will create in the Study.
Rather than requiring values from the four non-media columns to be entered repetitively for each row, inserting media values combinatorially in this example allows each unique value for the other columns to be entered into the file once. Figure 7 shows the resulting Lines table in EDD. Note that both entries for the "Media(s)" column and replicate numbers have been automatically inserted into the Line names to keep them unique.
| Name | Strain | Labeling | Media |
|---|---|---|---|
| WT-Control-LB-R1 | BY4742 | -- | LB |
| WT-Control-LB-R2 | BY4742 | -- | LB |
| WT-Control-LB-R3 | BY4742 | -- | LB |
| WT-Control-EZ-R1 | BY4742 | -- | EZ |
| WT-Control-EZ-R2 | BY4742 | -- | EZ |
| WT-Control-EZ-R3 | BY4742 | -- | EZ |
| WT-Control-Minimal-R1 | BY4742 | -- | Minimal |
| WT-Control-Minimal-R2 | BY4742 | -- | Minimal |
| WT-Control-Minimal-R3 | BY4742 | -- | Minimal |
Figures 6 and 7 show a simplistic combinatorial Line creation, but this feature becomes significantly more powerful when you start to use multiple combinatorial columns together in the same file.
The relative order of combinatorial metadata columns in your file (those that you appended "(s)" to) will dictate the ordering of those metadata values within combinatorially-created Line names. Other columns that impact the Line name are the base Line name you've provided in the 'Line name' column, and the 'Replicate Count' column, if you used it. The 'Line name' and combinatorial values will be included in Line names the order the related columns appear in your file. Replicate number will always come last in Line names. For example consider the following Experiment Description file, which has columns defined in a different order than the previous ones:
| Line Description | Media(s) | Replicate Count | Line Name |
|---|---|---|---|
| Wildtype s. cervisae | LB, EZ, Minimal | 3 | WT-Control |
Since the "Line Description" column does not include values for combinatorial Line creation (has no appended "s" or "(s)"), does not affect Line names. Name-relevant columns are, in order: 'Line Name', 'Media(s)'. The order of elements in the resulting Line names will be:
The Lines table displayed in EDD as a result will be:
| Name | Labeling | Media |
|---|---|---|
| LB-WT-Control-R1 | -- | LB |
| LB-WT-Control-R2 | -- | LB |
| LB-WT-Control-R3 | -- | LB |
| EZ-WT-Control-R1 | -- | EZ |
| EZ-WT-Control-R2 | -- | EZ |
| EZ-WT-Control-R3 | -- | EZ |
| Minimal-WT-Control-R1 | -- | Minimal |
| Minimal-WT-Control-R2 | -- | Minimal |
| Minimal-WT-Control-R3 | -- | Minimal |
Note that combinatorial Line creation adds another consideration to the process of creating your Lines, but unless you are using the combinatorial creation feature, you can define columns in your file in any order without affecting the resulting Line names.
Not all columns are supported for combinatorial Line creation. Columns defined as Line metadata (see the "Line Metadata Types" table below) are supported for combinatorial Line creation, except for those that are not supported for basic input: control, Line experimenter, Line contact. For primary Line characteristics defined in the table above, only the 'Part ID(s)' column may have a comma-delimited list of values entered for combinatorial Line creation, though a single entry in the "Replicates" columns will also result in combinatorial creation of Lines.
EDD also supports combinatorially creating Lines that contain multiple strains. To specify multiple strains to be used together as a group, separate part numbers with a semicolon and enclose the group with parenthesis. For example, an Experiment Description file with the following Part ID(s) column would create two Lines, each one with two strains in co-culture: (JBx_123; JBx_456), (JBx_789, JBx_012).
In addition to creating Lines as in examples above, you can also use Experiment Description files to create Assays associated with the Lines in your Study. Recall that an Assay is the application of a specific experimental protocol to a Line (see Figure 1 above). Most users will not need to create Assays using Experiment Description files, since EDD's data import process creates Assays during the import process. The purpose of creating Assays using Experiment Description files is to use EDD to help in configuring instrumentation or to simplify the workflow for later data imports. For supported workflows, EDD has a capability to export a worklist file useful for configuring the instruments, and for simplifying the import process for resulting measurement data. When using supported instrumentation, it can be significantly less work overall to describe your experiment in EDD first before running parts of the experiment.
An "Assay" is the application of a specific protocol (e.g. proteomics) to a Line. In the simple case, you can often think of an Assay as the result of loading your sample into an instrument. Any of the following lab examples would result in creation of an Assay in EDD:
Many Assays will only be performed once during the course of an experiment, and relate to a single instant in time. While some Assays are associated with a fixed point in time, while others will cover a span of time. For example, automated platforms such as the BioHector [sic] may perform Assays on a sample that span a long time period. As such, an Assay can contain one or many measurements.
To create an Assay using your Experiment Description file, you will need to assign at least one metadata value to the Assay. To provide Assay metadata in your Experiment Description file, add one or more column headers that start with a protocol name and end with the name of the Assay metadata you want to insert. For example, a common use case will be to set times for proteomics experiments. See Column Options above for a list of protocols in this EDD instance. The following example file creates a single Line and one associated Assay:
| Line Name | Line Description | Media | Part ID | Targeted Proteomics Time |
|---|---|---|---|---|
| WT-Control | Wildtype s. cervisae | LB | JBx_042441 | 6h |
The "Targeted Proteomics Time" column is responsible for creating an Assay. Breaking this header down into its parts:
| "Targeted Proteomics": | the protocol |
| " " | a space separator |
| "Time" | the name of the Assay metadata |
Dropping this file into EDD creates a single Line, visible in the Study's "Lines" section in nearly identical form to the input file:
| Name | Strain | Labeling | Media |
|---|---|---|---|
| WT-Control | BY4742 | -- | LB |
It also makes the Study's "Data" section visible, which indicates that an Assay has been created. The single Assay that's created, "181-aceF", has the same name as the associated Line. Note that the time entered via the Experiment Description file is not visible, but is stored in EDD. The Data table's "Measuring Times" column only displays times for measurements, but remains blank since there's no associated data (only time meta-data).
To clarify units for time, Assay times must be entered with a trailing "h". For example "12h" indicates that an Assay was performed at 12 hours. Precision of your data entry for time dictates the number of digits of time inserted into the related Assay names. Assay names will be created using number of maximum number of digits after the decimal point of any time value in your file.
You can also use experiment description files to combinatorially create Assays associated with the Lines in your Study. See the Combinatorial Line Creation section above for a detailed summary of how combinatorial creation works. It is essentially the same for Lines and Assays: you append an "(s)" to the column header, then enter comma-delimited values that each get applied to a single Line or Assay. A notable exception is that Assay-related columns in Experiment Description files will start with a protocol name and end with Assay metadata. Using the example file from Figure 10 above, you could add "(s)" to the last column, then enter values for combinatorial Assay creation.
Assays created via Experiment Description files are named identically to the Lines they relate to. This allows Assay names to remain unique within each protocol, though Assays may have identical names across different protocols.
{% endblock content %}


In this example, we are going to recover the following QR code.
Of course, we cannot scan it normally, because it lost too much modules including Finder and Alignment pattern.
The first step is to reconstruct it with Painter manually (we cannot import it as image since its Finder and Alignment pattern are missing).
(Reconstructed QR code using Painter)
The next step is to set the Format Info Pattern. Because the known modules of format info pattern only located in top right corner, the easiest way to reconstruct it is to try the pattern one by one and check whether it's match or not.
(The most suitable pattern is ECC level M and Mask pattern 1)
Now we have reconstructed QR code in our Editor and the missing Finder along with Alignment pattern are recovered.
Still, we can't decode it using normal Decoder because it's too much damaged for Error level M to be corrected. So, we should recover more modules of this QR code.
The next step, analyze the QR code using Extract QR Information. Using that tool, give us the following result.
We got the decoded message, but it rather unreadable and seems broken. We can ignore that for a moment.
Pay attention to the Number of missing bytes. It said that our QR code have 39 bytes of its data missing. Meanwhile, to correcting Erasure with Reed-Solomon, the maximum number of missing bytes in ECC level M version 3 should be about 26.
Therefore, we should recover some modules until the missing bytes are dropped about 26 bytes or less. The next step, we will try recover padding bits using Padding Bits Recovery.
Luckily, our padding bits in this QR code was quite big and we successfully recovered almost half of the damaged parts.
This is our recovered QR code so far (still not decodable yet).
Checking again with Extract QR Information, we dropped number of missing bytes to 25 bytes (35.71%). Also, the final part of messsage become more readable than before (EVERYTHING from EVERYTHIMY).
QR code version 3 with ECC level M have 26 of the ECC symbol, and since our number of missing bytes is 25, we can apply Erasure correction to the current QR code (remember from previous section that we can correct Errors half of the ECC symbol and Erasures as many as the ECC symbol).
Using Reed-Solomon Decoder, we successfully recover the message.
And finally, we got the final message : "YOU CAN DO ANYTHING BUT NOT EVERYTHING".
*This example concept inspired from MMA CTF 2015 challenge and the solving concept from https://github.com/pwning/public-writeup/blob/master/mma2015/misc400-qr/writeup.md


Real-life problems naturally involve high-dimensional feature vectors. In most cases, the features contain redundant information, which means that they are not independent from each other. The large set of features can be summarized into a smaller set, with no or less redundancy. This is the goal of dimensionality reduction (DR) methods, which play an important role in the fields of data analysis, data mining, and machine learning.
The following example shows a scatter plot that represent a set of 189 mandarins, some of which present decay symptoms caused by Penicillium digitatum fungus. For each mandarin, 1569 features were measured using a spectroscopy system. These features were processed using Principal Component Analysis (PCA), a popular method of dimensionality reduction.
The graph enables to compare the PCA features with any pair of the original features. It can be observed that PCA features provide a representation that facilitates tasks such as the automatic detection of decayed fruit.


{% extends "registration/base.html" %} {% load i18n %} {% block content %}
{% trans "Your password was changed." %}


Astrologer Creta:
Please be still, I am feeling something....
...
I see a shadow...
A long, dark shadow that hugs the ground...
Now the shadow stands on it's two legs...
The arms and head are not human, and there is a tail!
Hard to explain in words... This is my feeling...
Ask her to draw


Home
About Us
Contact
My Account
New Event
Event:
You have already created this event!
Start Date:
End Date:
Description:


--- layout: post status: publish published: true title: New MC++ Winforms Article author: display_name: Tomas Restrepo login: tomasr email<EMAIL_ADDRESS>url: http://winterdom.com/ author_login: tomasr author_email<EMAIL_ADDRESS>author_url: http://winterdom.com/ wordpress_id: 894 wordpress_url: http://winterdom.com/2003/04/newmcwinformsarticle date: '2003-04-21 20:24:48 +0000' date_gmt: '2003-04-21 20:24:48 +0000' categories: - ".NET" tags: [] comments: [] ---
My friend Sam just got his first article published on MSDN online together with Chris (whom I've already congratulated via email!).
This one covers WinForms programming with Managed C++ on Everett. Be sure to check it out!


15 March 2005
As of 14 March 2005, the team has reported a total of 130 suspect cases, including 57 deaths in Zobia, Bas-Uélé district, Oriental province. These figures are based on the current situation and a retrospective analysis of cases since 15 December 2004. No cases of bubonic plague have been detected.
Laboratory analysis of specimens and contact tracing is continuing. To date, a total of 363 contacts have been followed up. Suspect cases are being treated in isolation treatment centres.


Implements likelihood based methods for mediation analysis.
| Version: | 0.5 |
| Imports: | stats, mvtnorm, plotly |
| Suggests: | mediation |
| Published: | 2018-08-31 |
| Author: | Dr. Kai Wang |
| Maintainer: | Kai Wang <kai-wang at uiowa.edu> |
| License: | GPL-2 | GPL-3 [expanded from: GPL (≥ 2)] |
| NeedsCompilation: | no |
| CRAN checks: | iMediate results |
| Reference manual: | iMediate.pdf |
| Package source: | iMediate_0.5.tar.gz |
| Windows binaries: | r-devel: iMediate_0.5.zip, r-release: iMediate_0.5.zip, r-oldrel: iMediate_0.5.zip |
| OS X binaries: | r-release: iMediate_0.5.tgz, r-oldrel: iMediate_0.5.tgz |
| Old sources: | iMediate archive |
Please use the canonical form https://CRAN.R-project.org/package=iMediate to link to this page.


monsters
we all have negative thoughts sometimes.
what if we could see them for what they really are?
get started


Burger King Sued for Meat-Contaminated Impossible Whoppers
Plant-based with a hint of meat byproduct.
by Emily EngleA vegan customer recently accused Burger King of cooking its meatless Impossible Burgers on the same grill as its meat burgers, thus contaminating them. Phillip Williams claims an Impossible Whopper he ordered at an Atlanta drive-through was “coated in meat by-products” and is seeking damages for all US purchasers of the Impossible Whopper.
The lawsuit states Burger King should “plainly disclose” that the two styles of burgers are cooked together. However, Burger King’s website notes that “for guests looking for a meat-free option, a non-broiler method of preparation is available upon request.” Similarly, Impossible Foods‘ head of sales Dana Worth recently stated that “for people who are strictly vegan, there is a microwave prep procedure that they’re welcome to ask for in any store,” in regards to Impossible product consumption.
Burger King began selling its Impossible Whopper back in August, so this offering is still relatively new for the fast-food chain.
Elsewhere in food, Chik-fil-A will no longer donate to two Anti-LGBTQ organizations.


M
R
H
Joes Burger Shack
The Family burger joint!
Get Directions
IMAGES TO BE PLACED HERE. NOT YET COMPLETED.


Example Class 3 Report (Project 3A)
Full Algorithmic Implementation
Insertion sort in its entirety is adding a number in an already sorted array. This is achieved by arranging two 2 key values first and then repeating the process for the rest of the array. The insertion sort algorithm we used works by comparing each key (of index i) in the input array against the key that comes before it (index i-1).
If the key at index i is smaller than the one at index i-1, these 2 keys would swap positions, such the key previously at index i is now at index i-1, and vice versa. They would continue to swap positions, until there are no more keys in front of it (i.e. the ith key is the first key of the array) or the key before it is smaller, as the array has already been sorted. Thus an array in ascending order is obtained.
Merge sort works by using the divide-and-conquer strategy. if the input array has a size of 1 or less, it is considered trivially sorted; otherwise, the input array will be split evenly into two subarrays and have merge sort performed on them, after which the two sorted subarrays are joined using the merge function to obtain an array of the original size, sorted in order.
Also, if one of the subarrays still has keys when the other subarray is exhausted, the remaining keys would be merged directly into the auxiliary array without comparison; and if there are 2 keys that are equal in value on separate subarrays, they would be merged together, which means one less key comparison. This case does not occur in our program as the input arrays used hold unique integers.
Generating Input Data: The input data used are arrays of unique integers, from 1 to n, where n is the size of the arrays. The array sizes used range from 1000 to 50 000, with step size of 1000. For each array size, ascending, descending and randomly ordered arrays are generated: arrays of ascending and descending order are generated using simple for-loops where each key’s value correspond to its index in the array; and arrays of random order are generated using the Fisher-Yates shuffle algorithm, where for an input array, a random number k between 0 and the number of keys yet to be shifted is generated, and shifted to the end of an output array.
Measuring Time Complexity: For each array type and size, we did 60 insertion and merge sorts, and counted the number of key comparisons as well as the the CPU time. The dataset is then trimmed to obtain the interquartile mean. These statistical results obtained are the empirical results.
Theoretical Analysis of the Time Complexity of Insertion Sort with Empirical Results:
1. Best Case [ n-1 = O(n) ]
The best case for insertion sort occurs when the array is already sorted in the desired order. In this case, each key in the array, except for the first key, only needs to be compared to the key right before it. So for an array of length n, only n-1 number of key comparisons need to be made, resulting in a time complexity of O(n).
2. Worst Case [ n*(n-1) /2 = O(n2) ]
The worst case for insertion sort occurs when the array is already sorted, but in the reverse order. In this case, each key in the array, except for the 1st key, needs to be compared to all the keys that come before it.
For a key at index i, there are i-1 keys before it, so it has to go through i-1 number of key comparisons. If there are n number of keys in the array (i.e. array of size n), there will be (n-1) + (n-2) + … + 2 + 1 = (n*(n-1) /2) number of key comparisons when sorting through this array, resulting in a time complexity of O(n2).
3. Average Case [ (n-1)*(n+2) /4 = O(n2) ]
The average case for insertion sort occurs when the keys in the array are in a completely random order. For each key in a randomly-ordered array, there is an equal probability of a key at a particular index being compared to each key that comes before it, because there is an equal probability of that particular key being smaller or larger than the key that is in front (ie ½) . Mathematically, this means that for each key at index i in the array, there is a 1/i chance of it being compared to each key at index 0 through i-1, with 1 comparison at each index.
So, on average, a key at index i goes through (1/i)(1+2+...+i) = (1/i)( i*(i+1)/2 ) = (i+1)/2 number of key comparisons.
For an array of length n, each key in the array, except for the first key, goes through the above
process. Therefore, there are
[( (n-1) + 1 ) /2] + [( (n-2) + 1 ) /2] + … + [( 2+1) /2] + [(1+1) /2]
= (½)* [( (n-1) + 1 ) + ( (n-2) + 1 ) + … + ( 2+1) + (1+1)]
= (½)* [ n + (n-1) + … + 3 + 2 ]
= (½)* [ (n-1)*(n+2) /2 ]
= (n-1)*(n+2) /4
number of key comparisons in an array of length n, resulting in a time complexity of
O(n2).
Insertion Sort on Ascending-Ordered Array
Insertion Sort on Randomly-Ordered Array
Insertion Sort on Descending-Ordered Array
Theoretical Analysis of the Time Complexity of Merge Sort
Merge sort functions by splitting the original array (of length n) into 2 subarrays of equal length (n/2), and recursively splits the subarrays till each subarray contains only 1 key. When a subarray has a length of 1, it is considered trivially sorted so there is no need for any key comparison. This is the base case (W(1) = 0) for the recurrence equation which solves the time complexity of merge sort..
The comparisons of keys in the subarrays are done in the merging of a pair of subarrays that were split from an original array. This forms the recurrence equation: W(n) = 2*W(n/2) + (number of key comparisons in the merging of subarrays) for number of key comparisons for a merge sort on an array of length n.
For an array of length n where n = 2k (k ≥ 0), there will be k number of splits. This is because each split results in a subarray of length of n/2 = 2k-1 and every subarray is split recursively till each of them has a length of 1 = 20. k number of splits would result in k number of pairs of subarrays, which in turn results in k number of merges. Therefore, the number of merges in a merge sort on an array of length n is k = log2 n.
The number of key comparisons in a merge of 2 subarrays varies, case-dependent.
1. Best Case [ (n/2)*log2 n = O( n*(lg n) ) ]
The best case for merge sort occurs when every key in one subarray are smaller than or equal to every key in the other subarray. Each key of the first subarray will be compared against the first (smallest) key of the second subarray. After comparing and finding that the last (biggest) key of the first subarray is smaller than the first (smallest) key of the second subarray, the rest of the keys in the second subarray are assumed to be bigger than all the keys in the first subarray, and are merged without a need for comparison.
As such, the number of key comparisons in this case is the length of the first subarray. If the original array is of length n and the recursive splitting is such that 2 subarrays resulting from the split are of approximately equal length, then the length of the first subarray is n/2. This means n/2 number of key comparisons for each merge, so there are n/2 number of key comparisons.
The best case can also occur when each key at index i in the first subarray is equal to each key at index i in the second subarray, in which case both keys are merged simultaneously. When the keys from both subarrays are all merged pair-wise, simultaneously, the number of key comparisons is equal to the number of keys in either subarray (i.e. length of subarray) which is also n/2.
Therefore, the number of key comparisons is given by the recurrence equation:
W(n) = 2*W(n/2) + n/2, or
W(2k) = 2* W(2k-1) + 2k-1
= 2*( 2*W(2k-2) + 2k-2 ) + 2k-1
...
= 2k * W(1) + k * ( 2k-1 )
= 0 + (log2 n) * n / 2
After simplification, this gives us a time complexity of O( n * lg n ).
2. Worst Case [ n*log2 n - n + 1 = O( n*(lg n) ) ]
The worst case occurs when the largest and second largest keys among both subarrays are in separate subarrays or, if there are two keys with the largest value, each of these keys are in separate subarrays.
This arrangement is such that all keys up to the largest keys in each subarray of length n/2 have to be compared to another key. The largest keys in both subarrays would be compared against each other before being merged simultaneously. As such, the number of comparisons in one merge is n/2 + n/2 - 1 = n-1. Note that the number of key comparisons is one less than the total length of the subarrays as the last keys of both subarrays are merged together.
Therefore, the number of key comparisons is given by the recurrence equation:
W(n) = 2* W(n/2) + (n-1), or
W(2k) = 2* W(2k-1) + (2k - 1)
= 2* [ 2* W(2k-2) + (2k-1 - 1) ] + (2k - 1)
= 22 * W(2k-2) + (2k - 2) + (2k - 1)
= 23 * W(2k-3) + (2k - 22) + (2k - 21) + (2k - 20)
…
= 2k * W(2k-k) + k * 2k - ( 2k-1 + … + 22 + 21 + 20 )
= 2k * W(1) + (log2 n) * n - ( 2k -1 )
= 0 + (log2 n) * n - n + 1
After simplification, this gives us a time complexity of O( n * lg n )
3. Average Case [ c1*n*log2 n + c2*n + c3 = O(n*(lg n) ]
The average case for merge sort occurs when keys of the input array are randomly-ordered, such that each key is equally likely to be in any position in the array. In the average case, the probability of a key in the first subarray having to be compared to a key in the second subarray in each merge has to be taken into account when calculating the average total number of key comparisons in merge sort.
Based on the best case and worst case of merge sort, we know that the number of key comparisons in a merge must be between n/2 and n-1, inclusive. That is, the possible numbers of key comparisons forms the sequence {n/2, n/2 + 1, …, n-2, n-1}.
Merging takes n-1 number of key comparisons (also the worst case) when one subarray has the largest key, while the other has the second largest key. This results in 2 combinations of (n-2)! permutations of subarrays (i.e. 2*(n-2)! permutations).
Merging takes n-2 number of key comparisons when one subarray has the largest 2 keys, while the other has the third largest key. This results in 2 combinations of (n-3)! permutations of subarrays (i.e. 2*(n-3)! permutations).
Merging takes n-3 number of key comparisons when one subarray has the largest 3 keys, while the other has the fourth largest key. This results in 2 combinations of (n-4)! permutations of subarrays (i.e. 2*(n-4)! permutations).
...
Merging takes n-(n/2 - 1) number of key comparisons when one subarray has the largest n/2 - 1 keys, while the other has the (n/2)th largest key (ie one subarray has all but the smallest larger keys, while the other subarray has all but the largest smaller keys). This results in 2 combinations of (n - (n/2 - 1+1))! = (n/2)! permutations of subarrays (i.e. 2*(n/2)! permutations).
In general, merging takes n-j number of key comparisons when one subarray has the largest j keys, while the other has the (j+1)th largest key. This results in 2 combinations of (n−j+1)! permutations of subarrays (i.e. 2*(n−j+1)! permutations).
The general term for number of combinations for a particular number of key comparisons does not apply to n/2 number of key comparisons (also the best case). n/2 number of key comparisons has only 2 combinations: the first subarray contains all the smaller keys, while the second subarray contains all the larger keys, and vice versa.
As such, the probability for merging requiring a particular number of key comparisons is given by:
P(n-j)
= (number of permutations of subarrays that can result in that number of key comparisons) /
(total number of possible permutations of subarrays)
= 2*(n−j+1)! / ( 2*(n-2)! + 2*(n-3)! + … + 2*(n/2)! + 2)
After obtaining the above probability, the average number of key comparisons in one merge is given by: sum
of ( (n-j) * P(n-j) ). The number of key comparisons required in for merge sort on average can
thus be obtained by solving the recurrence equation:
W(1) = 0
W(n) = 2*W(n/2) + (average number of key comparisons in one merge of subarrays of size
n/2)
The result should be in the order of c1*n *(log2 n) - c2*n + c3 = O( n * lg n ) which closely corresponds to the the average number of key comparisons shown on page 43 of (Vitter and Flajolet, 1990).
Alternatively, the order of time complexity for the average case of merge sort is the upper-bounded by the worst case ( O( (n*log2 n) - n + 1 ) ) and lower-bounded by the best case ( Ω( (n/2)*log2 n ) ), so it is in the tight bound of θ(n * lg n).
Merge Sort on Ascending-Ordered Array
Merge Sort on Randomly-Ordered Array
Merge Sort on Descending-Ordered Array
Comparison of empirical results with theoretical analysis of time complexity
With the exception of average case time complexity of merge sort, the empirical results of all cases of both sorting algorithms corresponds to the time complexity obtained via theoretical analysis, such that a simple substitution of array size into the time complexity equations results in the actual number of key comparisons.
References
Vitter, J. and Flajolet, P. (1990). Average-Case Analysis of Algorithms and Data Structures. [online] Algo.inria.fr. Available at: http://algo.inria.fr/flajolet/Publications/ViFl90.pdf [Accessed 6 Oct. 2018]
Authors
SE1 (Group 2)
- LYZ
- Ngo Jun Hao Jason
- TSF
- TYHK
- YHL


package auth
Type Members
-
class
CustomSecuredErrorHandler
extends SecuredErrorHandler with I18nSupport
Custom secured error handler.
-
class
CustomUnsecuredErrorHandler
extends UnsecuredErrorHandler
Custom unsecured error handler.
-
trait
DefaultEnv
extends Env
The default env.
-
case class
WithProvider
[A <: Authenticator](provider: String) extends Authorization[User, A] with Product with Serializable
Grants only access if a user has authenticated with the given provider.
Grants only access if a user has authenticated with the given provider.
- A
The type of the authenticator.
- provider
The provider ID the user must authenticated with.


Hello World!
I'm baby vegan 90's jianbing viral, keffiyeh kinfolk scenester chicharrones bicycle rights. Coloring book
master
cleanse chartreuse tilde glossier, unicorn humblebrag prism dreamcatcher fashion axe meh mlkshk raclette put
a
bird on it. Af poutine snackwave 8-bit VHS gastropub tbh artisan lo-fi blog forage. PBR&B artisan next level
four loko, franzen sartorial pabst vape palo santo. Tofu art party microdosing ennui. Tousled four loko
intelligentsia flexitarian kitsch.
Shaman umami green juice mustache craft beer next level shoreditch vape unicorn wolf. Four loko tofu ramps
single-origin coffee pabst keffiyeh, before they sold out cardigan farm-to-table vinyl mumblecore
flexitarian.
Keytar sustainable cardigan polaroid poutine. 90's post-ironic flexitarian freegan, woke prism gastropub
cloud
bread health goth gochujang meh hella sustainable street art lyft.
Waistcoat yuccie la croix PBR&B stumptown. XOXO put a bird on it umami swag shaman. Banjo hella drinking
vinegar
put a bird on it prism, cred pinterest lumbersexual tacos salvia taxidermy seitan aesthetic crucifix
iceland.
Edison bulb pinterest raw denim thundercats yuccie mumblecore man bun 90's. Microdosing cliche yr pabst
glossier
fanny pack. Bitters pour-over mumblecore fam enamel pin, kitsch roof party.
Cornhole tbh fashion axe godard crucifix chambray everyday carry, kitsch umami flannel fanny pack.  You probably haven't heard of them ramps seitan ugh bespoke tumblr. Scenester squid YOLO,
asymmetrical
butcher locavore blog vice tote bag brunch ethical DIY chicharrones brooklyn selfies. Photo booth synth poke
pickled artisan, messenger bag quinoa put a bird on it beard subway tile chillwave deep v vice truffaut meh.


Installation
The core-periphery implementations are available in Python on Github.
pip install git+https://github.com/ryanjgallagher/core_periphery_sbm
Running Core-Periphery Models
The models can be run in Python with any NetworkX graph. To infer a hub-and-spoke structure:
import networkx as nx
from core_periphery_sbm import core_periphery as cp
# Load Les Mis graph from NetworkX
G = nx.les_miserables_graph()
# Initialize hub-and-spoke model and infer structure
hubspoke = cp.HubSpokeCorePeriphery(n_gibbs=100, n_mcmc=10*len(G))
hubspoke.infer(G)
Similarly, we can infer a layered structure with n_layers
:
layered = cp.LayeredCorePeriphery(n_layers=3, n_gibbs=100, n_mcmc=10*len(G))
layered.infer(G)
The models are inferred through an MCMC-within-Gibbs sampling procedure. There are n_gibbs
samples that are taken, and during each Gibbs sample, an MCMC chain of n_mcmc
steps is run on the labels of the network.
From the Gibbs samples, we can infer the core-periphery assignment of each node. Lower indices indicate more core positions. For example, in the hub-and-spoke model, 0 indicates the core and 1 indicates the periphery. In the layered model, 0 is the innermost layer.
# Get core and periphery assignments from hub-and-spoke model
node2label_hs = hubspoke.get_labels(last_n_samples=50)
# Get layer assignments from the layered model
node2label_l = layered.get_labels(last_n_samples=50)
Core-Periphery Model Selection
Given core-periphery labels inferred from the hub-and-spoke and layered models, we want to determine which partition best describes the core-periphery structure of a network. We can do this by comparing the description length of the models. The smaller the description length, the better the model fit. We can approximate the description length for each core-periphery model using n_samples
:
from core_periphery_sbm import model_fit as mf
# Get description length of hub-and-spoke model
inf_labels_hs = hubspoke.get_labels(last_n_samples=50, prob=False, return_dict=False)
mdl_hubspoke = mf.mdl_hubspoke(G, inf_labels_hs, n_samples=100000)
# Get the description length of layered model
inf_labels_l = layered.get_labels(last_n_samples=50, prob=False, return_dict=False)
mdl_layered = mf.mdl_layered(G, inf_labels_l, n_layers=3, n_samples=100000)