text:
layout: default
title: Reporting issues
nav_order: 2
---

# Reporting Issues

**Run `brew update` twice and `brew doctor` *before* creating an issue!**

This document will help you check for common issues and make sure your issue has not already been reported.

## Check for common issues

Follow these steps to fix common problems:

* Run `brew update` twice.

* Run `brew doctor` and fix all the warnings (**outdated Xcode/CLT and unbrewed dylibs are very likely to cause problems**).

* Check that **Command Line Tools for Xcode (CLT)** and **Xcode** are up to date.

* If commands fail with permissions errors, check the permissions of `/usr/local`'s subdirectories. If you're unsure what to do, you can run:

  ```shell
  $ cd /usr/local
  $ sudo chown -R $(whoami) bin etc include lib sbin share var opt Cellar Caskroom Frameworks
  ```

* Read through the [[Troubleshooting]].

## Check to see if the issue has been reported

* Search the [issue tracker](https://github.com/OSGeo/homebrew-osgeo4mac/issues) to see if someone else has already reported the same issue.
* Make sure you issue is specific to this tap and it's not part of other formula or dependency part of [core](https://github.com/Homebrew/homebrew-core/issues), [cask](https://github.com/Homebrew/homebrew-cask/issues) or other tap.

## Create an issue

If your problem hasn't been solved or reported, then create an issue:

1. Upload debugging information to a [Gist](https://gist.github.com):
  * If you had a formula-related problem: run `brew gist-logs <formula>` (where `<formula>` is the name of the formula).
  * If you encountered a non-formula problem: upload the output of `brew config` and `brew doctor` to a new [Gist](https://gist.github.com).

2. [Create a new issue](https://github.com/Homebrew/homebrew-core/issues/new/choose).
  * Give your issue a descriptive title which includes the formula name (if applicable) and the version of macOS you are using. For example, if a formula fails to build, title your issue "\<formula> failed to build on \<10.x>", where "\<formula>" is the name of the formula that failed to build, and "\<10.x>" is the version of macOS you are using.
  * Include the URL output by `brew gist-logs <formula>` (if applicable). Please check [how to get the building logs](#how-to-get-the-building-logs) for more info.
  * Include links to any additional Gists you may have created (such as for the output of `brew config`,  `brew doctor` or the output of your terminal).
  * Please make, one problem one error. Don't mix up things because it isn't going to have any sense.
  * Don't dumb in the description of the issue a incredible amount of code, use a [Gist](https://gist.github.com) instead.
  **What is an incredible amount of code?** Well, you'll know it when you'll see it. Scrolling down endlessly to be able some meaningful text doesn't usually have any sense.
  * Try to be as descriptive as possible, without being redundant, in other words **be concise**. This is not a chat or a forum, but informal style is encourage. Please follow the [Code of Conduct.](https://github.com/OSGeo/homebrew-osgeo4mac/blob/master/CODE_OF_CONDUCT.md#specific-guidelines).

## How to get the building logs?

One of the things you can provide us with is the building logs. You have to take into account that when doing parallel-job (multi-core) compilations, any final error is generally not the actual error that caused the build to fail. When posting log output from a multi-core build, that last error notice is _usually_ preceded by completely unrelated output from other parallel jobs that are finishing up first, with the actual in-line error much further up in the log. This is the case for the ubiquitous Make tool, though sequential log output may be created by other compilation tools, e.g. Ninja.

In other, and more simple, words, if you just post the output of your terminal chances are that the actual and real problem isn't showing there, so you have to search for the building logs.

Homebrew comes already with a tool that allow you to fetch and upload those logs in just one command `brew gist-logs`. You just have to run `brew gist-logs qgis` and the tool will upload those logs to the github gist platform. If you add the flag `-n` it will even open an issue in our repo with the gist linked. You can check other options running in your terminal `brew gist-logs -h`.

Unfortunately, the `brew gist-logs` command can truncate large log files before uploading, indicated by a `[...snip...]` in the uploaded log. In which case, the actual in-line error _may_ have been removed. In that case you have to do the job manually yourself. You have to search in `~/Library/Logs/Homebrew/<formula>/<log>` or `~/Library/Logs/Homebrew/<formula>/0#.make` (for Make builds) and search in those logs for **`error:`** or maybe **`fatal error:`** (note case and colon).

When reporting issues, post the actual error and the matching compilation command(s) preceding it (again, may be further up in the log), or update the github gist page of the `brew gist-logs` output with the full log file that was truncated (gists are micro code repos, so you can update individual files).

redpajama_set_name: RedPajamaGithub


The billing for the time on location starts upon landing at airport of destination and ends upon departure on of said airport. The time allocated for the support on location is paid 25% upon ordering, 25% upon receiving the ticket(s) and 50% upon arrival at clients city of destination. All transfer per Banking Wire or via Transferwise.
Our hour rates are US$ 95,00 for support on location. We reserve the right to charge any additional hours if work hours exceed the planned and agreed support time at our normal hour rate. This time will need to be agreed and paid before work continues on location beyond the initial scope of work.
Asia (including China, Malaysia, Korea, India, and Russia): $150/day paid upfront for the duration of the work.
We charge daily expenses from the day we leave our CSC (Competence Center) until the day we return to our CSC.
Since our team consists of international located developers, we might need visas to several destinations. If we are traveling to a country where we need to obtain a visa, then it is the client's responsibility to pay for the visa and related costs.
The client is responsible for providing a good accommodation for our team. Our definition of good accommodation is at least a 4 star hotel, with decent amenities. Costs must be paid directly by our client (we do not pay for our stay). Note that we can only stay in hotels that have a wireless Internet connection. If any charges occur for internet access or related costs they will be paid for by the client.
The client has to provide us with round-trip plane tickets Economy Plus or Business class (on intercontinental flights) with an airline of our choice to reach our work location, additionally, the client has to transport us from the airport to the hotel and back.
The client has to provide us with local transportation from our hotel to the work premises and back or cater for 1st class train tickets.


Mark Davidson, Laura Croft, Steve O'Hara and Dave Wark discuss what they've been watching, review The Social Network, as well as continuing in their quest to find the Best Worst Movie of All Time with Plan 9 From Outer Space. They also attempt to speak 'Sorkinese' (the language of all of Aaron Sorkin's characters). Turns out if they could speak in Sorkinese, they'd speak in Sorkinese.
EDIT: I promised I'd post links to Empire's articles about Alien 3.


text:
if [[ "$PACKER_BUILDER_TYPE" == virtualbox* ]]; then
  ## https://access.redhat.com/site/solutions/58625 (subscription required)
  # add 'single-request-reopen' so it is included when /etc/resolv.conf is generated
  echo 'RES_OPTIONS="single-request-reopen"' >> /etc/sysconfig/network
  /sbin/service network restart
  echo 'Slow DNS fix applied (single-request-reopen)'
else
  echo 'Slow DNS fix not required for this platform, skipping'
fi


check out the available workshops HERE!
the FULL program for the painting lessons and workshops 2019 WILL BE HERE SOOn.
Want me to keep you posted about the new workshops and lessons....?
send me an email or sign up here!
FOR MY WORKSHOPS AND PAINTING CLASSES. AND TELL ME PLEASE IN YOUR eMAIL WHAT YOU ARE INTERESTED IN TO LEARN FROM ME....? ARE YOU also INTERESTED IN EN PLEIN AIR WORKSHOPS PLEASE LET ME KNOW AND I PUT YOU ON MY LIST.


text:
\section{Introduction}
\label{sec:introduction}
\hfill

Binary search trees (BSTs) are ubiquitous in computer science. Their
relevance is well established, both in theory and in
practise. Figure~\ref{fig:intro} illustrates this data structure. The
numbers in the nodes represent the keys. If read left to right, the
keys form an ordered sequence, shown bellow the tree. This
property can be used to efficiently determine if a given number exists
in the tree. If we want to check if the tree contains the number
$0.55$ we can start by comparing this value with the one at the
root, $0.56$. Since the number we are searching for is larger than
$0.56$, the search continues in the left sub-tree, i.e., it
proceeds to the node containing $0.40$, thus discarding all the
sub-tree to the right. It is the process of eliminating a large
portion of its search space that makes BSTs efficient.
\begin{figure}[h]
  \centering
  \input{Intro.gte}
  \caption{Binary search tree containing keys from $[0,1]$.}
  \label{fig:intro}
\end{figure}

As the search goes through the tree it will eventually reach the
node containing $0.52$, at which point it becomes apparent that
 $0.55$ is not present in the structure. In fact this search
 concludes that no number in the open interval $]0.52, 0.56[$
exists in the tree. This is the only valid conclusion. Even
though the search passed through nodes $0.40$ and $0.51$ it would not
be valid to conclude that no number in $]0.40,0.51[$ exists, because
$0.41$ is on the tree. Hence whenever a search fails we still obtain
information from the data structure. In particular we obtained the
numbers in the tree that are the successor ($0.56$) and the
predecessor ($0.52$) of $0.55$.

Consider how the shape of the tree affects the performance of the
queries. If we are computing a single, isolated, query, we
may want to guarantee that, at each node, the size of the left and
right sub-trees is roughly the same. Note that we never know which
sub-tree a given search will choose. If both sub-trees have the same
size at least half the search space is discarded at each
step. Alternatively we could impose that the tree does not contain
long branches, since a search might have to traverse all of it.

Either way, some policy must be used to main a tree shape that reduces
the search time. Determining ``good'' tree shapes is a complex task,
specially when we consider a sequence of queries, instead of a single
query. Moreover, must of the time, this sequence is not known a
priori.  If a sequence of a couple million queries searches for $0.21$
in half of them and only once for $0.85$, then it might be better to
keep $0.21$ at the root and leave $0.85$ on the longest existing
branch. We would expect such a shape to reduce the overall
time. Hence a balanced tree is important if we need to answer several
essentially distinct queries. On the other hand if the queries are
strongly biased towards a specific region of the keys maintaining
certain branches shorter than the rest might be necessary.

Several strategies are known to maintain efficient BST shapes, see
Knuth~\cite{Knuth:1998:ACP:280635} for an introduction to the
subject. In this paper we focus on the approach used by splay
trees~\cite{Sleator:1985:SBS:3828.3835}. Our goal is to show that this
approach is optimal, in the sense that no other strategy can be
asymptotically faster than splay trees. Notice that splay trees
dynamically alter their structure as they process queries. Hence we
assume that any other BST can do the same.  Figure~\ref{fig:introSp}
illustrates the tree that results from accessing $0.21$ on a splay
tree.
\begin{figure}[tb]
  \centering
  \input{IntroSp.gte}
  \caption{After splaying $0.21$.}
  \label{fig:introSp}
\end{figure}

Our main contribution is the following:
\begin{itemize}
\item We, almost, show that splay trees are dynamically optimal. This
  means that no other BST is asymptotically faster than splay trees,
  no matter what is the structure of the query sequence or the
  re-shaping policy it uses. This property was
  conjectured to be true, over 30 years
  ago~\cite{Sleator:1985:SBS:3828.3835}.

  Our proof depends on a regular access property, which we deem
  plausible and conjecture to be true, see
  Section~\ref{sec:analysis-overview}. At this time we do not have a
  proof of this property.
\end{itemize}
\section{The Problem}
\label{sec:problem}
\hfill

The introduction exemplified how a BST can be used to maintain a
finite set $K$ of, keys, elements of a universe set $X$. In our
example $X$ is $\mathbb{Q}$. Our goal is to maintain a data structure
such that given a fraction $x$ from $\mathbb{Q}$ we can determine if
$x$ is in $K$, or not. We refer to these operations as queries. A
query is successful it $x$ does belong to $K$ and unsuccessful
otherwise.

Several efficient data structures exist for this problem, depending on
which resources are critical and on which extra operations are
necessary. For our example we also want map behaviour. This means that
the elements of $K$ contain information. Whenever $x$ does exist in
$K$ we also want to access the associated information. The two major
classes of data structures that can be used in this scenario are trees
and hashes. The set $\mathbb{Q}$ is, in general, referred to as the key
universe and the associated information is referred  to as the value
set. In this paper we omit this latter set.

Contrary to hashes, BSTs rely on the order relation among the elements
of the universe. In $\mathbb{Q}$ we have for example that $(1/4) <
(1/2)$. Hence BSTs can efficiently determine successors and
predecessors. The successor of $x$ in $K$ is $\min\{y \in C | x <
y\}$. To simplify the analysis we do not consider unsuccessful
queries, i.e., we assume that all the queries find elements in $K$. An
unsuccessful query for $x$ can be modelled by two successful ones,
one for the successor and one for the predecessor. In general BSTs
support inserting and removing elements from $K$, but we also
do not study those operations.

The re-structuring policy of splay trees consists in moving the
accessed nodes, and the nodes in the respective path, upwards towards
the root. The precise operations are shown in
Figures~\ref{F:zig},~\ref{F:zigzig}~and~\ref{F:zigzag}, where the node
containing $x$ is the one being accessed. The configuration before the
access is represented on the left and the structure after the access
on the right. Accesses when $x$ is on the right sub-tree are obtained by
symmetry.
\begin{figure}[tb]
\begin{center}
\input{zig-R.gte}
\caption{Zig operation.}
\label{F:zig}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\input{zigzig-R.gte}
\caption{Zig Zig operation.}
\label{F:zigzig}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\input{zigzag-R.gte}
\caption{Zig Zag operation.}
\label{F:zigzag}
\end{center}
\end{figure}

To compare splay trees with any other BST we assume that the other BST
works in the following way. Besides the tree itself there is a cursor
that moves between nodes. An algorithm on a BST may perform any of
the following operations:
\begin{description}
\item[Compare] the key at the cursor with the current
  search value.
\item[Move] the cursor to an adjacent node, left child, right child
  or parent.
\item[Rotate] the node upwards. The Zig operation is a rotation of
  node $x$, (Figure~\ref{F:zig}).
\end{description}
To perform a search in a BST the cursor starts at the root and
performs a sequence of the previous operations. The result of the
search is the node for which a comparison with $x$ was equal. This
node may, or may not, be the last one in the sequence. At the end of a
search the cursor must return to the root, those moves are accounted
for.

In this model we allow for constant extra information at each node,
such as colour for red-black trees or height for AVL trees. The
intention is to forbid dynamic memory blocks, which
could be used to implement hashing. Hence only a fixed constant amount
of information can be added to a node. Other BST models exist, that
 can be shown to be within a constant factor of the one we
consider~\cite{DBLP:journals/siamcomp/Wilber89}.

Among all BSTs we focus on the one that achieves
the best performance for a query sequence. This means choosing the
tree after knowing the complete query sequence, in other words,
offline. We refer to this optimal tree as $T$.

We do not count compare operations and therefore assume that they cost
0. For the optimal tree we count the number of moves and rotations,
but for the splay tree we only count the number of moves. This avoids
having to carry around a factor of 2 or 3, which would result from
counting rotations and or comparisons.

\section{Analysis Overview}
\label{sec:analysis-overview}
\hfill

In this section we overview the main techniques in the analysis and
describe our new potential function.
\begin{description}
\item[Amortized analysis.] The analysis is amortized, meaning that the
  time a splay operation takes is not accounted per si, but
  considering preceding and succeeding
  operations~\cite{doi:10.1137/0606031}. Therefore the amount of time
  an operation requires can be partially shifted to some other
  operation in the sequence. The resulting time is known as the
  amortized time. The most common way to transform the total sum into
  an equivalent telescopic sum is to associate a ``potential'' value
  to each state of the data structure $D$, the value $\Phi(D)$. The
  amortized cost of an operation is then defined as $\hat{c} = c +
  \Phi(D') - \Phi(D)$, were $c$ is the actual cost and $\Phi(D')$ the
  potential after the operation is performed. Summing the previous
  equations over all $m$ queries, and using the fact that it is a
  telescopic sum, we obtain a global relation $\sum_{1\leq i \leq m}
  c_i = \left( \sum_{1\leq i \leq m} \hat{c}_i \right) -
  \Phi(D_m)$. In this equation $\Phi(D_m)$ represents the potential
  after the sequence, which might be a negative number. The value
  $\Phi(D_0)$ represents the potential at the beginning and it was
  omitted because it is assumed to be $0$.  This is a classical tool
  in the analysis of splay trees. We present a new potential
  function. This function is chosen so that the structure of the
  optimal tree gets transferred into the splay tree.
\item[Restricted Accesses.] After bounding the amortized cost of
  accesses in $S$ we proceed to amortize the cost of rotations in
  $T$. Such rotations alter $\Phi(D)$ and therefore most be accounted
  for. To obtain a constant bound on this variation we introduce
  extra, organizing splays, in $S$. The amortized time to compute
  these extra splays will depend on the depth of the node we are
  rotating in $T$. Therefore if $T$ performs two rotations in a row we
  need to count the node depth twice. To obtain a valid bound we
  force $T$ to move its cursor back to the root after performing a
  rotation. We also further impose that $T$ may not access nodes of
  depth $3$ or more. Although these restrictions seem harsh we show
  that, with a linear slowdown factor, it is possible to force the
  optimal sequence to respect them, Lemma~\ref{lem:simulateT}.
\item[Organizing Splays.] Splay trees do not know the full sequence of
  queries in advance, fortunately the analysis does. This means that
  in the analysis it is possible to verify if the structure of the
  splay tree is adequate for the upcoming queries. We optimize the
  tree structure by adding extra organizing splays. These splays
  introduce the logic dependency on a regular access.
\end{description}
The regular access statement is the following:
\newtheorem{conjecture}[theorem]{Conjecture}
\begin{conjecture}[Regular Access]
\label{C:regular}
Let $c_1 + \ldots + c_{m}$ be the total cost of a sequence of $m$
splay operations and $c'_1 + \ldots + c'_{m+e}$ the cost of performing
the same sequence of splay operations, augmented with $e$ extra splays
anywhere. Then $c_1 + \ldots + c_{m} = O(c'_1 + \ldots + c'_{m+e})$.
\end{conjecture}

This conjecture basically states that computing more splays takes
longer. We assumed this property in our reasoning, until it became
evident that it was not trivial to establish. Our proof relies
precisely on this property because the extra splays are used to
optimize the tree for future accesses.

We will now define the potential function $\Phi$ and give an overview
of the results that we prove in Section~\ref{sec:details}. $T$ denotes
the optimal tree. To every node $v$ of $T$ we assign a weight $w_T(v)
= 1/4^{d_T(v)}$, where $d_T(v)$ is the depth of $v$, i.e., the
distance to the root. The root itself has depth $0$, its children have
depth $1$ and so on. For each node we add up all the weights of its
sub-tree, including $w_T(v)$ itself, the resulting sum is denoted
$s_T(v)$. The rank $r_T(v)$ is computed as $\log(s_T(v))$. The
potential of tree $T$ is given by the following sum:
\[
P(T) = \sum_{v \in T} r_T(v)
\]

Let us consider the trees in Figure~\ref{F:examplePhi}. We have that
$w_T(a) = w_T(c) = 1/16$, $w_T(b) = w_T(e) = 1/4$ and $w_T(d) =1$.
The resulting $r$ values are $r_T(a) = r_T(c) =\log(1/4^2) = -4$,
$r_T(e) = -2$, $r_T(b) = \log (1/4+1/8) = \log (3/8)$ and $r_T(d) =
\log (1 + 1/2 + 1/8) = \log (13/8)$. Hence the total potential of $T$ is
$P(T) = r_T(b) + r_T(d) -10$.

We use $S$ to denote the splay tree. There is a one to one relation
between the nodes of these trees, because both trees share the same
key values. For any node $v$, of $T$, its correspondent in $S$ is
$f(v)$, by correspondent we mean that $v$ and $f(v)$ store the same
key value.  This correspondence is used to transfer the weight values
from $T$ to $S$, more precisely set $w(f(v)) = w_T(v)$. We omit the
$S$ subscript to simplify notation. The values of $w$, $s$ and $r$
that do not have a subscript refer to $S$. Moreover we also omit the
function $f$ and assume instead that $v$ in $S$ means $f(v)$. Hence
the previous relation will be written as $w(v) = w_T(v)$. The values
$s(v)$ and $P(S)$ are computed as before. In general $s(v)$ and
$s_T(v)$ are not, necessarily, equal. See
Figure~\ref{F:examplePhi}. Likewise $P(T)$ and $P(S)$ are also not,
necessarily, equal. In fact we use $\Phi(D) = P(S) - P(T)$ as our
potential function.

 In our example we have that $r(a) = r_T(a)$, $r(c) =
r_T(c)$, $r(e) = r_T(e)$, $r(b)= r_T(d)$ and $r(d) = \log(1 + 1/4 +
1/16) = \log (21/16)$. Therefore
$\Phi(D) = \log(21/16) - \log(3/8) = \log(7/2)$.
\begin{figure}[htbp]
\begin{center}
\input{simpleTS-I.gte}
\caption{Optimal tree $T$ on top, splay tree $T$ in the bottom, upside down.
Example of computing $\Phi$. The $f$ function is illustrated
  by the dashed arrows.  The weight values $w$ are show in between the
  two trees. Inside the black rectangles we show the $s$ values
  associated with the nodes. }
\label{F:examplePhi}
\end{center}
\end{figure}

In the analysis we assume that $S$ and $T$ take turns. First $S$
searches for $x$ and $T$ remains idle. Then $T$ searches for the same
$x$, while $S$ remains idle. Hence whenever the structure of $S$ changes
$P(S)$ changes, but $P(T)$ remains constant. However when the
structure of $T$ changes, both $P(T)$ and $P(S)$ change.

The structure of our argument is as follows:

\begin{itemize}
\item We show that $-n < \Phi(D_m)$, Lemma~\ref{lem:bound-phi}, where
  $n$ is the number of keys.
\item We show that the amortized cost
to splay a node $v$, in $S$, is at most $O(1 + d_T(v))$,
Lemma~\ref{sec:amortized-costs-s}.
\item  We show that whenever there is a
rotation at node $v$ in $T$ we have $\Delta \Phi = O(1)$, by splaying
at most 3 nodes, whose depth in $T$ is at most $d_T(v)$,
Lemma~\ref{lem:powerDelta}.
\item  We combine these results with a restricted
optimal sequence, Lemma~\ref{lem:simulateT}, and obtain an
optimality result, Theorem~\ref{teo:optimal}.
\end{itemize}
Thus we establish that if the optimal tree, with $n$
nodes, needs $R$ rotations and $M$ moves to process a given query
sequence then splay trees require $O(n + R + M)$ time, provided they
have the regular access property.
\section{The Details}
\label{sec:details}
\hfill

\begin{figure}
  \centering
  \begin{tabular}{ll}
    $T$ & The optimal binary search tree.  \\
    $T'$ & A restricted version of $T$. \\
    $S$ & The splay tree. \\
    $n$ & Number of nodes in $T$ and $S$ \\
    $m$ & Number of queries in a sequence. \\
    $e$ & Number of added organizing splays. \\
    $R$ & Number of rotations in $T$ \\
    $M$ & Number of cursor moves in $T$ \\
    $R'$, $M'$ & Same as $R$ and $M$, but in $T'$ \\
    $v$, $u$ & Nodes \\
    $t$ & The root node \\
    $d_T(v)$ & The depth of node $v$ in $T$ \\
    $w(v)$ & Weight of node $v$ \\
    $s(v)$ & Sum of the weights, in the sub-tree bellow $v$ \\
    $r(v) = \log(s(v))$ & Rank for node $v$ \\
    $w_T(v)$, $s_T(v)$, $r_T(v)$ & Weight, sum and rank in $T$ \\
    $\Phi(D)$ & Potential value for a given state of $S$ and $T$
  \end{tabular}
  \caption{Symbol table.}
  \label{fig:notation}
\end{figure}
In this section we fill in the details that are summarized in the
previous section. This section is divided into three parts. We start
by studying the properties of our potential function $\Phi$. We then
shift the focus to $T$ and explain how to restrict the general access
sequence to ensure that it respects certain desirable conditions. The
last part presents bounds for the amortized costs of accessing elements
in $S$ and rotating nodes in $T$. We then combine these results to
obtain an optimality result.
\subsection{Properties of $\Phi$}
\label{sec:properties-phi}
\hfill

Let us start by analyzing the potential function $\Phi(D)$. We assume
that the initial configuration of $S$ and $T$ is the same. Therefore
 $P(S)=P(T)$ and  $\Phi(D_0) = 0$.

Given that we are using base $2$ logarithms it would be natural to use
base $(1/2)$ powers for the weights $w$ and $w_T$. Using $(1/4)$
instead causes the amortized access cost to be twice as big. On the
other hand we obtain some handy properties.
\begin{lemma}
\label{lem:boundSV}
Let $v$ be a node. The following bounds hold:
  \begin{align}
    0 &\leq w(v) &&\mbox{ for any $v$ in $T$ or $S$.} \label{eq:basic0} \\
    w(v) &\leq 1 &&\mbox{ for any $v$ in $T$ or $S$.} \label{eq:basic4} \\
    w(v) &\leq s(v) &&\mbox{ for any $v$ in $T$ or $S$.} \label{eq:basic1} \\
    s_T(v) &< 2 \times w_T(v)&& \mbox{ only for $v$ in  $T$.} \label{eq:basic2} \\
    s(v) &< 2 &&\mbox{ for any $v$ in $T$ or $S$ } \label{eq:basic3} \\
    s(t') &= s_T(t) &&\mbox{ for the root $t'$ of $S$ and $t$ of $T$ } \label{eq:basic5}
  \end{align}
\end{lemma}
\begin{proof}
  Inequalities~(\ref{eq:basic0}) and~(\ref{eq:basic4}), follow
  directly from our definition of weights.

Inequality~(\ref{eq:basic1}), follows from the definition of
$s$ and Inequality~(\ref{eq:basic0}).

Inequality~(\ref{eq:basic2}) use a geometric series. For the nodes $v$
in $T$ the value $s_T(v)$ is a sum of powers of $1/4$, which depends
on the topology of tree. If $T$ is a single branch then
$s_T(v) < w_T(v) (1 + (1/4) + (1/4^{2}) + \ldots + (1/4^j) + \ldots) < (4
w_T(v)/3)$. If $T$ is perfectly balanced,
this bound becomes even larger. In that case $s_T(v) < w_T(v)(1 +
2 \times (1/4) + 2^2 \times (1/4^2) + \ldots + 2^j \times (1/4^j) +
\ldots) < 2
\times w_T(v)$. In this case the bound comes from the geometric series
of $(1/2)$. Moreover the remaining cases will also be bounded by the
geometric series of $(1/2)$.

Inequality~(\ref{eq:basic3}) holds for $T$, because of
inequalities~(\ref{eq:basic4}) and~(\ref{eq:basic2}). For $S$ note
that in general $T$ cannot have more than $2^d$ nodes with depth $d$
and consequently $S$ cannot have more that $2^d$ nodes with weight
$(1/4^d)$, hence we obtain the geometric series of $(1/2)$ again.

For equality~(\ref{eq:basic5}) notice that the sums at the root
contain all the weight values. Since these values are
mapped from $T$ to $S$ they are globally the same and therefore so is
their sum.
\end{proof}

In particular from Inequality~(\ref{eq:basic3}) we deduce that $r(t)
\leq 1$, for the root $t$ of $S$.

Using potential functions that can assume negative values implies that
the value of $\Phi(D_m)$ becomes a term in the total time. Hence we
bound this value.
\begin{lemma}
\label{lem:bound-phi}
The bound $-n < \Phi(D)$ holds for any configuration of $S$ and $T$,
where $n$ is the number of keys.
\end{lemma}
\begin{proof}
The following derivation establishes the result.
\begin{eqnarray}
  P(S) - P(T) & = & \Phi(D) \\
  \sum_{v \in S} \log(w(v)) - P(T) & \leq & P(S) - P(T)\label{eq:2}\\
  \sum_{v \in S} \log(w(v)) - \sum_{v \in T} \log(2w_T(v)) & < & \sum_{v \in S}
  \log(w(v)) - P(T) \label{eq:3}\\
  -\sum_{v \in T} 1 & = & \sum_{v \in S} \log(w(v)) - \sum_{v \in T} \log(2w_T(v)) \label{eq:4} \\
  -n & = &  -\sum_{v \in T} 1
\end{eqnarray}
To obtain Inequality~(\ref{eq:2}) use Inequality~(\ref{eq:basic1}), for
all the terms of the sum in $P(S)$.
For Inequality~(\ref{eq:3}) use Inequality~(\ref{eq:basic2}) and
apply logarithms and change signals.
Equation~(\ref{eq:4}) follows from the same argument as
Equation~(\ref{eq:basic5}) and the fact that $\log(2w_T(v)) = 1 + \log(w_T(v))$.
\end{proof}

\subsection{Restricting $T$}
\label{sec:restricting-t}
\hfill

Competing directly with $T$ is fairly hard, partially because the
sequence of accesses in $T$ is completely free. For our
purposes we need that the accesses in $T$ respect the following
properties:
\begin{itemize}
\item When a node $v$ is visited by the cursor or involved in a
  rotation its depth is less than $3$, i.e., $d_T(v) < 3$.
\item After a rotation the cursor moves back to the root.
\end{itemize}
We refer to a sequence of nodes that respects these conditions
as a restricted sequence. Let us show that given any access sequence of
visited nodes in $T$ it is possible to simulate it in another
tree $T'$, so that the accesses in $T'$ are restricted. By simulation
we mean that the sequence visited by the cursor of $T$ is a
sub-sequence of the one visited by the cursor of $T'$. Naturally the
 simulation will be slower than the original sequence.
\begin{lemma}
\label{lem:simulateT}
  Any sequence of nodes visited by the cursor of $T$, consisting of
  $M$ moves and $R$ rotations, can be simulated by a restricted
  sequence of cursor moves on a tree $T'$ with $4M+3R$
  moves and $2M+R$ rotations.
\end{lemma}
\begin{proof}
\begin{figure}
  \centering
  \input{simulate-I.gte}
  \caption{Simulation of $T$ (left) by $T'$ (right). Initial
    configuration on top. The middle configuration represents the
    result of moving the cursor from node $y$ to node $x$. The bottom
    configuration shows the result of performing a rotation on $x$,
    while in the middle configuration.}
  \label{fig:simul}
\end{figure}
Figure~\ref{fig:simul} illustrates the operations that we consider in
this Lemma. Besides the same keys as $T$, the tree $T'$ contains two extra keys,
$\min$ and $\max$, that are, respectively, smaller and larger than all
the other keys in $T$. The simulation works by keeping the node at the
cursor of $T$ in the root of $T'$.

We assume that the initial state of $T$ and $T'$ is almost alike. The
same key is stored a the root. The children of $T'$ are $\min$ and
$\max$. The left sub-tree of $T$ is stored in the right child of
$\min$ and the right sub-tree of $T$ is stored in the left child of
$\max$. Shown at the top in Figure~\ref{fig:simul}.

Whenever the cursor of $T$ moves down the corresponding node is moved
up to the root of $T'$, the process is a ZigZag operation on $T'$, or
ZagZig depending on which grand-child. Note that between the rotations
of the ZigZag operation the cursor must return to the root to comply
with the second condition of restricted sequences. These
movements are underlined in the example. Hence every downward
move in $T$ originates $4$ moves and $2$ rotations in $T'$. This
process transforms the trees in the top of Figure~\ref{fig:simul}, to
the trees in the middle. In this example the sequence of operations
is: \texttt{moveTo($\min$)}, \texttt{moveTo($x$)}, \texttt{rotate()},
\underline{\texttt{moveTo($y$)}, \texttt{moveTo($x$)}}
\texttt{rotate()}.

The cursor may also move upwards on the tree, hence
reversing the previous move. In this case the sequence of operations
would be: \texttt{moveTo($y$)},\texttt{rotate()},
\texttt{moveTo($x$)}, \texttt{moveTo($\min$)}, \texttt{rotate()},
\texttt{moveTo($y$)}. This requires $4$ moves and $2$
rotations. Therefore a move in $T$
originates $4$ moves and $2$ rotations in $T'$.

In this example the initial move was to $y$, because $y$ is the child
in $T'$ that corresponds to he parent in $T$. To determine this
property we could store, in $T'$ the depth of the nodes in $T$. Only
for the nodes in the leftmost and rightmost branches of $T'$,
otherwise updated values would be hard to maintain. However it is not
necessary to do so. Recall that $T'$ is simulating $T$ and $T$ is the
optimal tree, which does not need to consult the keys to know which
move to perform, it only needs to behave as a BST. Therefore $T'$ also
does not need extra information.

Whenever a rotation is performed in $T$ the structure of $T'$ must be
adapted accordingly. Recall that a rotation on node $v$ means
that $v$ is moved upwards. In Figure~\ref{fig:simul} the
transition from the middle to the bottom shows how a
rotation alters the structure of $T'$. In this case the sequence of
moves is: \texttt{moveTo($y$)}, \texttt{moveTo($\max$)},
\texttt{rotate()}, \texttt{moveTo($x$)}. Hence a rotation originates
$3$ moves and $1$ rotation in $T'$. The general procedure is to move
to $y$ because it is the child of $T'$ that corresponds to the parent
of $x$ in $T$, and move again in the same direction, in this case to
$\max$. This node is rotated upwards and the procedure finishes by
returning to the cursor back to the root.

Note that in Figure~\ref{fig:simul} the cursor of $T$ is drawn close
to the root. In general the structure of the upward path from the
cursor of $T$ to the root gets splitted into the leftmost and
rightmost branches of $T'$, but the update procedure is essentially as
explained.
\end{proof}

In the following results we continue to use $T$, instead of $T'$,
which simplifies the analysis. The tree $T'$ is used only in
Theorem~\ref{teo:optimal}.
\subsection{Amortized Costs of $S$ and $T$}
\label{sec:amortized-costs-s}
\hfill

Let us now bound the amortized time of
splaying a node of $S$.
\begin{lemma}
\label{lem:amortizedS}
Splaying a node $v$ takes at most $4 + 6 d_{T}(v)$, amortized time,
where $d_{T}(v)$ is the depth of the corresponding node in $T$.
\end{lemma}
\begin{proof}
The following derivation establishes this bound:
\begin{eqnarray}
\hat{c}_{i} & \leq & 1 + 3[r(t) - r(v)] \label{eq:aad1}\\
            & < & 1 + 3[1 - r(v)] \label{eq:aad2}\\
            & = & 4 - 3 r(v) \label{eq:aad3}\\
            & \leq & 4 - 3 \log(w(v)) \label{eq:aad4}\\
            & = & 4 - 3 \log(1/4^{d_{T}(v)}) \label{eq:aad5}\\
            & = & 4 + 6 d_{T}(v) \label{eq:aad6}
\end{eqnarray}
Inequality~(\ref{eq:aad1}) is the classic amortized access
Lemma~\ref{lem:amortizedAccess}, see
Section~\ref{sec:related-work}. Inequality~(\ref{eq:aad2}) follows
from~(\ref{eq:basic3}) and recalling that $r(t) =
\log(s(t))$. Inequality~(\ref{eq:aad4}) results from applying
logarithms and switching signs to~(\ref{eq:basic1}). The remaining
equations use the definition of weight $w$ and simplify the result.
\end{proof}

This Lemma shows that the amortized time to splay a node is slightly
more than $6$ times the time that it is necessary to access the
corresponding node in $T$. Let us focus on the amortized cost of
accessing nodes in $T$. Whenever $T$ accesses a node there is no real
cost for $S$. However if those accesses involve rotations in $T$ then
the value of $\Phi$ changes, which will constitute an amortized cost
that $S$ most account for.
\begin{lemma}
  \label{lem:powerDelta}
  Whenever a node $v$ of $T$, with $d_T(v) < 3$, gets rotated the
  bound $\Delta \Phi \leq 11 + \log (11)$ holds, after, at most, $3$ nodes of $S$
  are splayed. Each splayed node $v^*$ has $d_T(v^*) \leq d_T(v)$.
\end{lemma}
\begin{proof}
Recall that in a rotation the node $v$ moves upwards on the tree.
We consider the cases when $d_T(v) = 1$ and $d_T(v) = 2$.
\begin{figure}[bt]
\begin{center}
\input{rotP-R.gte}
\caption{Variation of $\Phi$ with rotation on T.}
\label{F:rotP}
\end{center}
\end{figure}

The proof is illustrated in Figure~\ref{F:rotP}, which shows
the situation when $d_T(v) = 1$, but from which we can infer
properties that apply to all cases.

 The optimal tree $T$ is represented on top and the splay tree $S$ in
 the bottom, upside down. To simplify let us assume that these trees
 are only slightly different. Meaning that they share some
 structure. The nodes in sub-trees $A$, $B$ and $C$ are the same, but
 their shape is not necessarily equal. For example the
 descendants of node $u$ are not, necessarily, the same.

A fundamental observation for this proof is that almost all the nodes,
in the trees, contribute $0$ to the value $\Delta \Phi$. The only
nodes that effectively contribute to $\Delta \Phi$ belong to, at
least, one the following categories:
\begin{enumerate}
\item Nodes that contain descendants from more than one of the sets
  $A$, $B$, $C$, either in $S$ or $T$ or both. Examples of these nodes
  are the ones containing $x$ and $y$. Moreover some nodes $a \in A$,
  $b \in B$ and $c \in C$ may appear in $S$ with this property.
\item Nodes for which the set of descendants is altered by the
  rotation in $T$. Only nodes $x$ and $y$.
\end{enumerate}

Hence we are claiming that the nodes in $A$, $B$ and $C$ do not contribute to
  $\Delta \Phi$.  Consider a node $u$, contained in the sub-tree
  $A$. Let $w_T(u)$ be the weight of $u$ before the rotation and
  $w_T'(u)$ be the weight after the rotation. Likewise we consider the
  $s_T$, $s_T'$, $r_T$, $r_T'$ values and the values $s$, $s'$, $r$,
  $r'$, over $S$.

  Let us account for the contribution of $u$ to $\Delta \Phi$, i.e.,
  $r'(u)-r(u)+r_T(u)-r'_T(u)=
  \log([s'(u)/s(u)]\times[s_T(u)/s'_T(u)])$.  Notice that $w'(u)/w(u)=
  4$, because the depth of $u$ decreases in $T$. Likewise
  $s'(u)/s(u)=4$, because the same happens for all the elements in
  $A$. On the other hand $s_T(u)/s'_T(u)= 1/4$ because the order of
  the factors is reversed. Therefore the previous value is $\log (4/4) =
  0$. A similar reasoning holds for the elements in $C$. The nodes in
  $B$ do not suffer potential variations and therefore contribute $0$
  to the overall variation.

  In this scenario the only nodes that contribute to $\Delta \Phi$ are
  the ones that contain descendants from more than one of the $A$,
  $B$, $C$ sets. In our simplification only $x$ and $y$. However in
  the general case the nodes in sub-trees $A$, $B$ and $C$ have
  different relations in $S$ and in $T$. Hence we need to be more
  precise as to what these nodes should be. The nodes in $A$ are the
  descendants of $x$ that are smaller than $x$. The nodes in $B$ are
  the descendants of both $x$ and $y$. The nodes in $y$ are the
  descendants of $y$ that are larger than $y$.

  To force these sets of nodes to be consistent between $S$ and
  $T$ we splay node $x$ and node $y$ in $S$, in this order. Now $A$ and
  $C$ contain the same nodes in $S$ and $T$, but it may happen that
  some ZigZig operation pulls a node $b$ upwards from $B$, so that it
  splits $B$ and is in between the nodes $x$
  and $y$. In this case we must also count the contribution from $b$.

  Using an argument similar to the one above we can guarantee that
  $s'(b)/s(b) \leq 4$ and $s_T(b)/s'_T(b) = 1$ and therefore
  $r'(b)-r(b)+r_T(b)-r'_T(b) \leq 2+0 = 2$.

  For the node containing $x$ we also have that $s'(x)/s(x) \leq 4$,
  but $s_T(x)/s'_T(x)$ is trickier, because $s'_T(x)$ now includes the
  extra terms related to $w_T'(y)$ and $s_T'(C)$, these
  values are non-negative and therefore
  decrease the fraction $s_T(x)/s'_T(x)$. Therefore the bound of $4$
  holds true. Hence for the node
  containing $x$ we count another $4$ units, as
  $r'(x)-r(x)+r_T(x)-r'_T(x) \leq 2+2 = 4$.

  For the node containing $y$ we also have that $s'(y)/s(y)
 \leq 4$ but $s_T(y)/s'_T(y)$ is again trickier. The following
 derivation obtains a bound.
  \begin{eqnarray}
    s_T(y)/s'_T(y) & = &
    \frac{w_T(y)+s_T(C)+s_T(B)+w_T(x)+s_T(A)}{s'_T(y)} \label{eq:6} \\
& = & \frac{w_T(y)+s_T(C)+s_T(B)}{s'_T(y)} +
\frac{w_T(x)+s_T(A)}{s'_T(y)}  \label{eq:7}\\
& \leq & 4 + \frac{w_T(x)+s_T(A)}{s'_T(y)} \label{eq:8} \\
& \leq & 4 + \frac{w_T(x)+s_T(A)}{1/4} \label{eq:9} \\
& = & 4 + \frac{(1/4)+s_T(A)}{1/4} \label{eq:10} \\
& \leq & 4 + \frac{(1/4)+(1/8)}{1/4} \label{eq:11} \\
& \leq & 4 + 1.5 \label{eq:12}
  \end{eqnarray}

  Equations~(\ref{eq:6}) and~(\ref{eq:7}) are simple
  manipulations. Inequality~(\ref{eq:8}) is our general bound of $4$,
  for the fraction that does not change the
  descendants. Inequality~(\ref{eq:basic1}) yields $1/4 = w'_T(y) \leq
  s'_T(y)$, which we use to establish
  Inequality~(\ref{eq:9}). Inequality~(\ref{eq:11}) follows from
  Inequality~(\ref{eq:basic2}) that yields $s_T(A) \leq 2 \times 1/16 =
  1/8$.  Therefore the total for $y$ is $r'(y)-r(y)+r_T(y)-r'_T(y)
  \leq 2 + \log(5.5) = 1 + \log(11)$.

  Summing up, in this case we splayed two nodes and have to account
  for $b$, $x$ and $y$, therefore
  $\Delta \Phi \leq 2 + 4 + (1 + \log(11)) = 7 + \log(11)$.

  Let us consider the case $d_T(v) = 2$. This means that there is a
  node $v_r$ which is an ancestor of $y$, in $T$. Let us assume
  that $v_r$ is to the right of $C$. The case where the node is to the
  left of $A$ is easier. It may happen that
  $v_r$ is inside $C$ in $S$, in that case we splay $v_r$. This
  splay operation may in turn split $C$ by pulling up a node $c$. In
  total we splayed 3 nodes and have $5$ nodes that may contribute to
  $\Delta \Phi$, the nodes $b$ and $c$, that got pulled up, and the
  nodes $x$, $y$, $v_r$.

  For node $c$ we have a bound of $4$, using the argument above, which
  holds  because the descendants of $c$ in $T$ do not
  change. Hence $r'(c)-r(c)+r_T(c)-r'_T(c) \leq 2+2 = 4$.

  Note that $v_r = t$ is the root of both $S$ and $T$. Therefore we
  can can bound its variation by $0$, instead of our pessimistic $4$
  value. For this node we have $r'(t) = r'_T(t)$ and $r(t) = r_T(t)$,
  by Equation~(\ref{eq:basic5}). Hence in this case the total bound is
  $\Delta \Phi \leq 2 + 4 + 4 + (1 + \log(11)) + 0 = 11 + \log (11)$

  Notice that all this splaying may change the ancestor relation
  between $x$ and $y$ in $S$.  This may happen when there is no node
  $b$ and we are pulling a node $v_\ell$, to the left of $A$. This
  relation in $S$ does not change the argument above, as both $x$ and
  $y$ are being pessimistically bounded in $S$. The crucial
  consequence of the extra splays is that the nodes in $A$, $B$ and
  $C$ are properly encapsulated, and the number of nodes whose
  descendants belong to more than one of these sets is limited.
\end{proof}

We can now prove our optimality result.
\begin{theorem}
\label{teo:optimal}
Consider a sequence of $m$ queries, to a splay tree $S$ with $n+2$ keys,
for which, a similar, optimal tree $T$ uses $R$ rotations and $M$ cursor
movements. Provided that splay trees have regular access, then the
total number of operations performed by $S$ is $O(n + R + M)$.
\end{theorem}
\begin{proof}
The proof is given by the following deduction:
\begin{eqnarray}
\sum_{1 \leq i \leq m} c_i - k (n+2) & \leq & k \left( \sum_{1\leq i \leq
    m+e} \ell + c'_i \right) - k (n+2)\label{Eq:R0}  \nonumber \\
 & = & k \left( (m+e) \ell - (n+2) + \sum_{1\leq i \leq
    m+e} c'_i \right) \label{Eq:R1}\\
& \leq & k \left((m+e) \ell + \Phi(D_m) + \sum_{1\leq i \leq m+e} c'_i \right) \label{Eq:R2} \\
& = & k \left((m+e) \ell + \Phi(D_m) - \Phi(D_0) + \sum_{1\leq i \leq m+e} c'_i \right) \label{Eq:R3} \\
& = & k \left((m+e) \ell + \sum_{1\leq i \leq m+e} \hat{c}'_i
\right) \label{Eq:R4} \\
& \leq & k \left[(m+e) \ell + (11 + \log 11) R' + (1 + 3) (4 + 6 M')
\right] \label{Eq:R5} \\
& \leq & k \left[(m+3R') \ell + (11+\log 11) R' + (1 + 3) (4 + 6 M')
\right] \label{Eq:R6} \\
& = & k \left[m \ell + 16 + (11 + 3 \ell + \log 11) R' + 24 M'
\right] \label{Eq:R7} \\
& = & k \left[m \ell + 16 + (11 + 3 \ell + \log 11) (2M + R) + 24(4M+3R) \right] \label{Eq:R8} \\
& = & k \left[m \ell + 16 + (118 + 6 \ell + 2 \log 11) M + (83 + 3 \ell
  + \log 11) R  \right] \label{Eq:R9}
\end{eqnarray}
The above deduction uses the restricted sequence over $T'$, instead
of the original optimal sequence over $T$. We point out which of the
results in the previous lemmas apply to $T'$. The values $R'$ and $M'$
refer to the number of rotations and cursor movements in $T'$.

We aim to bound the value on the left.
 The first inequality is our regular access conjecture. In here we are
 using explicit constants, $k$ and $\ell$, instead of the notation
 $O$, to determine the hidden factors. Equation~(\ref{Eq:R1})
 rearranges the sums. Equation~(\ref{Eq:R2}) follows from
 Lemma~\ref{lem:bound-phi}. In Equation~(\ref{Eq:R3}) we add the value
 $\Phi(D_0)=0$, because we are assuming that the initial structure of
 $S$ and $T'$ is the same.  Equation~(\ref{Eq:R4}) follows from the
 telescopic nature of the definition of amortized costs.

Inequality~(\ref{Eq:R5}) follows from Lemmas~\ref{lem:amortizedS}
and~\ref{lem:powerDelta}. From Lemma~\ref{lem:amortizedS} we conclude that the sum of the
$\hat{c}'_i$ that corresponds to splay operations that answer queries
is at most $(4 + 6 M')$, because $T'$ must also move its cursor to
those nodes and between any such nodes the cursor returns to the
root. Therefore for $T'$ to answer a query it most perform at least
$d_T(v)$ cursor movements, where $v$ is the node containing the key
that corresponds to the query.

To bound the sum of the $\hat{c}'_i$ that corresponds to the costs to
update $S$, due to rotations in $T'$, we use
Lemma~\ref{lem:powerDelta}. Note that we can apply this Lemma because
of the first property of restricted sequences. The fixed cost yields
the term $(11 + \log 11) R'$. The amortized cost of splaying, at most,
$3$ nodes of $S$ is bounded by the term $3(4 + 6 M')$. This bound
holds because the second property of
restricted sequences implies that $T'$ must perform at least $d_T(v)$
cursor movements before rotating node $v$. This
property states that after each rotation
the cursor of $T'$ returns to the root, see
Section~\ref{sec:restricting-t}.

In Equation~(\ref{Eq:R6}) we use the fact that $e \leq 3R'$, i.e., we
use at most $3$ extra splays for each rotation in
$T'$. Equation~(\ref{Eq:R7}) results by rearranging terms. In
Equation~(\ref{Eq:R8}) we use the bounds from
Lemma~\ref{lem:simulateT}. Equation~(\ref{Eq:R9}) obtains the final
bound, by rearranging terms.
\end{proof}

Let us now survey related work, so that we can discuss our result in
context.

\section{Related Work}
\label{sec:related-work}
\hfill

This section describes splay trees and some previous
results. These trees were proposed by Sleator and
Tarjan~\cite{Sleator:1985:SBS:3828.3835} in 1985. An extensive up
to date survey on dynamic optimally was given by
Iacono~\cite{Survey}.

There are several restricted optimally results for BSTs. Assuming that
the optimal BST is static than the best performance is the
entropy $O(\sum_{i=1}^m f_i \log(m/f_i))$, where $m$ is the
total number of queries and $f_i$ is the number of queries for the
$i$-th key. Knuth presented the first algorithm to determine such an
optimal tree~\cite{Knuth:1998:ACP:280635}. This dynamic programming
algorithm requires $O(n^2)$ time to determine the optimal tree. Kurt
Mehlhorn obtained a faster, $O(n)$ time algorithm, which approximates
the optimal tree~\cite{Mehlhorn}. In the context of this paper this
result would be referred to as statically optimal, because we are
hiding factors into the $O$ notation. Splay trees also obtain this
kind of optimality and moreover do not need to know the $f_i$
values. Static optimality becomes the best upper bound when the keys
in the query sequence are independent of each other.

We are only interested in approximating dynamic optimality, i.e.,
using $O$ notation and being a factor away from the optimal value,
because it is expected that the exact problem is
NP-Complete~\cite{BST_SODA2009}. Even in this case the only BST that
achieves the dynamic optimality bound, assumes free rotations and
takes exponential time to select
operations~\cite{DBLP:journals/algorithmica/BlumCK03}.

The good performance properties of splay trees are due to the access
Lemma, which was establish in the paper on splay
trees~\cite{Sleator:1985:SBS:3828.3835}. Here we repeat the original
argument and highlight the fact that it follows from Jenssen's
Inequality~\cite{Jenssen}.
\begin{lemma}[Amortized Access]
\label{lem:amortizedAccess}
Splaying a node $v$ to the root $t$ takes at most $1+3[r(t)-r(v)]$,
amortized time.
\end{lemma}
\begin{proof}
  Recall Figures~\ref{F:zig},~\ref{F:zigzig} and~\ref{F:zigzag}.  When
  $v$ is at the root, the bound is trivial. Hence let us focus on the
  last operation that is used to access $v$, which contains $x$ in our
  figures.
\begin{description}
\item[Zig] In this case $x$ is a child of $y$, which is at the
  root. The amortized cost is computed as follows:
\begin{eqnarray}
\hat{c}_{Zig} &=& 1 + r'(x) + r'(y) - r(x) - r(y) \label{eq:z1}\\
 & \leq & 1 + r'(x) - r(x) \label{eq:z2} \\
 & \leq & 1 + 3[r'(x) - r(x)]
\end{eqnarray}
The only nodes that change rank are $x$ and $y$. The
Inequality~(\ref{eq:z1}) follows from the fact that $r'(y) \leq
r(y)$. On the other hand Inequality~(\ref{eq:z2}) is true because
$r(x) \leq r'(x)$.
\item[ZigZig] In this case $x$, $y$ and $z$ change rank
\begin{eqnarray}
\hat{c}_{ZigZig} & = & 2 + r'(x) + r'(y) + r'(z) - r(x) - r(y) - r(z) \label{eq:zz1}\\
& = & 2  + r'(y) + r'(z) - r(x) - r(y) \label{eq:zz2} \\
& \leq & 2  + r'(x) + r'(z) - 2 r(x) \label{eq:zz3} \\
& \leq & 3[r'(x)-r(x)] \label{eq:zz4}
\end{eqnarray}
Equation~(\ref{eq:zz2}) follows from the fact that $r'(x) =
r(z)$. Inequality~(\ref{eq:zz3}) is true because $r'(y) \leq r'(x)$ and
$- r(y) \leq - r(x)$. Inequality~(\ref{eq:zz4}) reduces to proving that $
(r(x) + r'(z))/2 \leq r'(x) - 1$, this relation is known as Jensen's
inequality and it holds because the $\log$ function is concave. More
explicitly the relation is the following:
\begin{equation*}
\frac{\log(s(x)) + \log(s'(z))}{2} \leq \log\left(\frac{s(x)+s'(z)}{2}\right)
\end{equation*}
\item[ZigZag] In this case $x$, $y$ and $z$ change rank.
\begin{eqnarray}
\hat{c}_{ZigZag} & = & 2 + r'(x) + r'(y) + r'(z) - r(x) - r(y) - r(z) \label{eq:za1}\\
& = & 2  + r'(y) + r'(z) - r(x) - r(y) \label{eq:za2} \\
& \leq & 2  + r'(y) + r'(z) - 2 r(x) \label{eq:za3} \\
& \leq & 2[r'(x)-r(x)] \label{eq:za4} \\
& \leq & 3[r'(x)-r(x)] \label{eq:za5}
\end{eqnarray}
Equation~(\ref{eq:za2}) follows from the fact that $r'(x) =
r(z)$. Inequality~(\ref{eq:za3}) is true because $- r(y) \leq
-r(x)$. Inequality~(\ref{eq:za4}) is also Jensen's inequality, in this
case it reduces to $(r'(y)+ r'(z))/2 \leq r'(x) - 1$. The
Inequality~(\ref{eq:za5}) is true because $r(x) \leq r'(x)$.
\end{description}
Notice that in any access to $S$ there is at most $1$ Zig operation
and several ZigZig and ZigZag. This justifies why it is important to
omit the term $1$ in the bound for the ZigZig and ZigZag
operations. The overall bound is obtained by summing the bounds of the
respective operations. This sum telescopes to the expression in the
Lemma.
\end{proof}

A recent detailed study of this Lemma is
available~\cite{DBLP:conf/esa/ChalermsookG0MS15}. An important
consequence of the splay operation is that most of the nodes in the
splayed branch are moved upwards, i.e., their depth gets reduced,
essentially in half. A
detailed study on depth reduction was given by
Subramanian~\cite{DBLP:journals/jal/Subramanian96}.

Several good performance theorem follow from this Lemma:
\begin{description}
\item[Static Optimality,] obtaining the entropy bound we mentioned in
  the beginning of the Section.
\item[Static Finger,] the performance of splay trees can
  be made to made dependent on the position of a given element of the
  key set $X$. Let $f$ be the position of a certain element $x$ in the
  ordered set $X$ and $|x_i-f|$ the distance between that element and
  the element $x_i$, the $i$-th element in the query sequence. Then
  processing a sequence of queries with a splay tree takes $O(n \log n
  + m + \sum_{i=1}^m\log(|x_i-f|+1))$. In fact splay trees have an even better
  better performance because the chosen element at position $f$ can be
  made
  dynamic~\cite{doi:10.1137/S0097539797326988,doi:10.1137/S009753979732699X},
  but this result requires a longer analysis.
\item[Working Set,] meaning that recently accessed are quicker to
  access again. Let $t(x)$ be the number of different items accessed
  before accessing $x$ since the last time $x$ was accessed, or since
  the beginning of the sequence if $x$ was never accessed before. The
  the total time to process a sequence of queries is $O(n \log n + m +
  \sum_{i=1}^m \log(t(i)+1))$. An important consequence of this bound
  is that if the keys are assigned arbitrarily (but consistently) to
  unordered data, splay trees behave as dynamically
  optimal~\cite{DBLP:journals/algorithmica/Iacono05}.
\item[Unified bound,] combining the best performance of the 3 previous
  bounds. Dedicated structures where designed to achieve an even
  better bound which uses the dynamic finger
  bound~\cite{DBLP:journals/tcs/BadoiuCDI07}, instead of the static
  version. Generalized versions of this bound, with tighter values for
  structured sequences where also
  proposed~\cite{DBLP:journals/corr/abs-1302-6914}.
\end{description}
Another important performance bound is the sequential access, or
scanning, bound, which states that accessing the $n$ keys sequentially
takes only $O(n)$ time. This was initially established by
Tarjan~\cite{TarjanSeq} with a factor of $9$, the current best factor
of 4.5~\cite{Elmasry2004459} was proven by Elmasry.

Besides dynamic optimality  Sleator and
Tarjan~\cite{Sleator:1985:SBS:3828.3835} proposed the traversal
conjecture, which remains unproven. It is similar to the sequential
access but the key order is taken to be the preorder of another
BST.

Other open conjectures on splay trees include the Deque conjecture,
which claims that splay trees can be used to implement a deque, with
$O(1)$ amortized time per
operation~\cite{dequeCom,DBLP:journals/corr/abs-0707-2160}. The split
conjecture claims that deleting all the nodes of a splay tree takes
$O(n)$ time, in whatever order~\cite{lucas1992competitiveness}.

Studying binary search trees from a geometric point of view has
yielded several important results~\cite{BST_SODA2009}. It presented an
online algorithm, which may yield dynamically optimal BSTs. This
algorithm is referred to as greedy, and it was originally proposed as
an offline
algorithm~\cite{lucas1988canonical,munro2000competitiveness}. The
first $O(\log n)$ performance bound, of this algorithm, was
established by Fox~\cite{DBLP:conf/wads/Fox11}.

The same authors proposed Tango trees which are $O(\log \log n)$
competitive to the optimal BST~\cite{Tango_SICOMP}. This was the first
structure to obtain a proven non-trivial competitive ratio. The worst
case performance of these trees was further
improved~\cite{DBLP:conf/wads/DerryberryS09} to $O(\log n)$ per
operation. The $O(\log \log n)$ ratio was also proved for the
chain-splay variation of splaying~\cite{Georgakopoulos200837}.

Another alternative to try and obtain, proven, dynamic optimality
consists in combining BSTs. In~\cite{ComboBST_ICALP2013} the authors
show that given any constant number of online BST algorithms (subject
to certain technical restrictions), there is an
online BST algorithm that performs asymptotically as well on any
sequence as the best input BST algorithm.

Iacono~\cite{Survey} recently proposed another approach, the Weighted
Majority Algorithm. This approach is proven to yield a dynamically
optimal BST, provided any such data structure exists.

A considerable amount of research as also gone into the study of lower
bounds, i.e., formulating expressions that are smaller than $R+M$,
i.e., the amount of operations required by $T$. The first lower bounds
where established by
Wilber~\cite{DBLP:journals/siamcomp/Wilber89}. These bounds where
further improved by the geometric view of BSTs~\cite{BST_SODA2009}. In
this view accesses to nodes in a tree are drawn as points in the
plane. One coordinate stores the ordered keys and the other coordinate
represents time. We can then consider rectangles using these points as
corners. Two rectangles rectangles are independent if their corners
are outside their interception or in the boundary of the
interception. An access sequence in a BST must respect any independent
set of rectangles. Hence the maximum independent set of rectangles
yields a lower bound for the number of visited nodes in a BST.

The alternation lower and the funnel bounds can also be explained with
the geometric view of BSTs. Moreover this latter bound is also related
to the number of turns that it is necessary to move a key to root,
with a procedure proposed by Allen and
Munro~\cite{DBLP:journals/jacm/AllenM78}.

\section{Conclusions and Further Work}
\label{sec:concl-furth-work}
\hfill

In this paper we studied the dynamic optimality conjecture of splay
trees, which was proposed by the authors of these
trees~\cite{Sleator:1985:SBS:3828.3835} and has stood for more than 30
years. During this time a vast amount of results and approaches have
been proposed for this problem and related conjectures. Note that a
proof of dynamic optimality would establish other conjectures.

All this research has resulted in new data structures, several of
which where proven to be $(\log \log n)$ competitive. The results we
present are a step forward. We reduced dynamic
optimality to the regular access conjecture. This conjecture seems
very plausible. On the other hand, if it is false that would also be a
remarkable property.

In the future we plan to research this conjecture. An exhaustive
literature review may provide the necessary tools to solve it. We also
plan to investigate if our potential function can be applied to the
analysis of other dynamically optimal candidates, namely the greedy
algorithm, combining BSTs or the weighted majority algorithm.

\bibliographystyle{siam}

redpajama_set_name: RedPajamaArXiv


text:
10 x WSOP Champ Guilty Of Cheating
October 27, 2017 by Sophie Lise
WSOP Champ Ivey Found Guilty Of Cheating
Shockwaves ran through the gambling world when it was announced this week that ten times World Series of Poker champ Phil Ivey, is a cheater. This follows a court case heard at the UK Supreme Court between Ivey and the Crockfords Club. This case was on appeal from 2016 after the court originally found Ivey guilty of cheating the Crockfords Club out of over £7 million pounds in 2012.
Ivey has now lost his appeal against the case and he will surely go down in infamy. The cheating allegations stem from a high stakes variant on Baccarat called Punto Banco. Crockfords accused Ivey of using a technique called "edge sorting" which is a form of advantage play.
The technique relies on a player noting small differences in the designs on the back of playing cards in order to gain a tactical advantage on the dealer. While Ivey did not manually do anything, he would ask the dealer to rotate certain cards in order to determine their value, citing that he is superstitious.
The Judgement
The owner of the Crockfords Club hired a strong legal team to prosecute Ivey and the Judge found him guilty. In his ruling the judge stated that Ivey gave himself an advantage that goes outside skill within the game environment. He said that in his opinion, that constitutes cheating.
The court added after his appeal was lost that Punto Banco is a game of pure chance. It is an essential element that makes the game. They used a comparison that if Ivey had gained access to the shoe and rearranged cards, that would also be seen as cheating and parallels can be drawn between that and "edge sorting". They also added that he made the croupier complicit n his cheating without her realising it, making it a well thought out and executed cheat.
Frustration For Ivey
COO of Genting, Paul Willcock stated the company's happiness with the verdict and he hopes it shows that Genting did not deny paying out the winnings for an arbitrary reason. They believed at the time and now that court and the Supreme Court have shown it to be the case, that they acted correctly and in good faith.
Ivey however disagrees with the verdict. He said that the court did not understand advantage play and what it means to be a professional gambler. He said that the ruling goes contrary to the facts and logic.

redpajama_set_name: RedPajamaCommonCrawl


A rapidly growing congregation located in an expanding suburban community provided St. Joseph the Worker Catholic Church the initiative to add a new worship space to their existing facility. Kodet Architectural Group designed a worship space addition with seating for over 900 and an adjacent chapel and gathering space for over flow.
The new expansion features a worship space with seating in the round, folded plate (intricately detailed) ceiling and a translucent curtail wall for views both in and out of the space. The original worship area is now used as a multi-purpose space.


Sour Grapes has come a long way since Arturo Donjuan, founding member, would wake up hours before junior high to tag around Oak Cliff. Arturo, along with brothers Carlos, Miguel and about 10 other artists, comprise the group, whose portfolio and influence are growing.
Whether you know it or not, you've probably seen some of their work -- and you're about to see a whole lot more.
See also: The Sour Grapes Graffiti Crew: Born and Raised in Oak Cliff, and Not on Bishop Ave.
Sour Grapes just finished a mural for the Belmont Hotel. The wall near I-30 and Sylvan Avenue is now adorned with 3D-looking smiling sky-scrapers and some of Sour Grapes' signature popsicle-esque characters.
Starting in mid-July they'll begin work on a $50,000 piece, commissioned by the city, to beautify the Jefferson Viaduct's Zang and Marsalis entry/exitways. They plan to finish sometime in August, which is good because they've already been commissioned by VICE to make a Brisk mural in Houston. Unlike the Belmont Hotel wall, this mural has been sketched and planned out because one of the characters will be made into a vinyl toy by LRG.
In January 2014, the crew takes its talent to Milan, where it will work on a mural for Cinelli bikes. Carlos Donjuan, an art professor at UTA, will also be doing an art show.
In addition to doing art all around the world, Arturo, who day-lights as a barber, will soon open a new old-fashioned barber shop on Mockingbird Lane. The shop will offer classic cuts and straight razor shaves.


Industrial design with a modern flair. Adjustable from 23" to 32" seat heights, this unique stool is as functional as it is fun.
Seat Height Options: Adjustable 22 3/4" up to 32 1/4"
Overall Height with 30" Seat: 40 3/4"


text:
NewsChristianity/ReligionCoronavirus-COVID-19Vaccine MandatesVaccine Passports
Saskatchewan Becomes First Canadian Province to Set Date for Ending COVID Restrictions
February 9, 2022 110 views0
(by Jack Bingham | LifeSite News) – Saskatchewan has become the first province in Canada to announce firm dates for the removal of all so-called COVID-19 measures.
On Tuesday morning, Premier of Saskatchewan Scott Moe followed through with his plans to axe all COVID-19 measures in the province, setting the date for the end of the vaccine passport for February 14, with mandatory masking gone by February 28. Moe also indicated that other governments will likely follow Saskatchewan's lead in removing all public health directives soon, including the notoriously pro-mandate federal government.
"I knew that this [vaccine passport] policy would create deep divisions in our families, in our friendship groups, in our province," Moe admitted at the start of the press conference.
"People would potentially have different access, or rights, based on what their relative vaccination status would be… so what was actually a pretty extraordinary step to take, in this province, effectively created two class of citizens."
While not saying he regrets implementing such a divisive and discriminatory policy, Moe did say that now with the "omicron variant" it has become clear that "the benefits of this policy no longer outweigh the costs."
Continuing to remind residents that he supports mass vaccination, Moe stated that if "someone makes a different choice" and chooses to remain vaccine-free, that is "their right, and this government is going to respect that right."
"So, effective at midnight, this Sunday, February 13th, all provincial proof-of-vaccination requirements will end," the premier explained, adding that the last remaining policy, mandatory masking, will be gone by the "end of the month."
Touching on other governments, Moe stated, "I have no doubt that you will see other provinces putting forward what their plan is on living with COVID and taking steps on getting life back to normal… I would put forward that the federal government should also put forward what their plan is for the federally regulated industries… And I think in fairness you will see the federal government as well, in the next while, come forward… ." Read Full Article >


I just can't help myself. I love intricate, detailed oriented cards. Over the 13 years as a Stampin' Up! Demonstrator I have shared my passion with my customers and this months technique club learnt how to make this card (inspired by Satomi Wellard). It features the Be Mine and Meant To Be stamps and framelits from the Occasion catalog.
Be sure to join my Facebook group page for more info on this card. All you have to do is go to Facebook and search - For The Love Of Stamping Group page. Then request to become a member.
Hi unable to find group page can you add me please.


My Life Without A Jetpack - Special: Taking A Break.
Comic 215 - Special: Taking A Break.
As you know, we always tell the truth here in My Life Without A Jetpack. So here's the ugly truth: I fell down some stairs and broke my right wrist. I also hurt my other hand, though not so badly, my right knee, and my head (nothing serious). Obviously, that means I can't letter comics; up to a couple of days ago I couldn't even pull up my pants… matter of fact, I'm forced to wear sweatpants only. A belt, a button, and a zipper are impossible for me to handle right now. My left hand has gotten better, luckily; I measure its progress by how much easier it gets to open the microwave door. I also have to type with just one finger of my left hand; I'm actually dictating this whole thing to the computer via voice recognition software. Pretty neat, huh? I feel like I'm on a Star Trek ship.


text:
Outcome of the European Elections in Catalonia
June 20, 2014 · by EFAy	· in Uncategorized.	·
The last European elections have been a great success for many reasons in Catalonia.
First of all, the turnout has increased 11 points, from the 36% in 2009 to 47% in 2014, a unique case in Europe. Secondly, the pro referendum parties have received more than the 60% of the votes. Finally, Esquerra Republicana has won the elections for the first time after the Spanish Civil War. To summarize, Catalonia has sent a clear message to the European Union: "We want to be the next state in the EU". Fortunately, the success hasn't been only in Catalonia. Esquerra Republicana (with the partial support of PSM-EN) has also received its better results in the Balearic Islands, at 7,25%.
What has happened? ERC has surpassed the PSOE-PSC (Catalan Socialist Party) as the main leftist force in Catalonia (and also in some villages of Majorca), and now, the two main forces on the left and right (CIU) stand for independence. The success has been so great that ERC has also won in the outskirts of Barcelona, where mostly of the Spanish immigration from the 60's live nowadays, and where PSOE-PSC used to get their best results.
These elections have been the last test before the independence referendum of next 9th of November, and the outcome has been very satisfactory. The two main Spanish parties (PP and PSOE) are very worried due to their bad performance in the elections, especially in Catalonia (where together they received 23% of the votes). On the other hand, all the pro referendum parties in Catalonia (except from CUP, which didn't stand in the elections) have improved their results.
The people of Catalonia have understood the critical situation of the country and have voted responsibly, and in doing so they have sent a clear message to the world: Let us vote, let us be the next EU state.
Max Zañartu i Plaza
EFAy Bureau Member
← L'Union Européenne vers un clash institutionnel?
Time for self-determination →


This entry was posted in BIKE, Day Ride, FOOD, OTHER, Trips and tagged belt drive, belt drive bike, bicycle, bike, bike path, camera, carbon drive, carbon drive bike, cookies, eugene, fire truck, fireworks, flower, hanafuda, homemade soda, ice cream, iPhone, KEEN, LHT, Linus, Long Haul Trucker, Mario, mixte, MKS, MKS Pedals, Nintendo, Nutcase, Nutcase Helmet, Oregon, park, Park Tool, Park Tools, photo, Playmobil, soda, Stein Tools, sunset, Surly, vegan, vegan cookies, vegetarian, watermelon. Bookmark the permalink.
Those 3 you listed are some of my favorite, especially the Playmobil in real life.


text:
El Salvador Main Page · Country Profiles Main Page
Population: 6.07 million (2011 est)
Capital city: San Salvador (1.8 million)
People: Mestizo 90%, Caucasian 9%, Indigenous 1%
Languages: The official language is Spanish.
Religion(s): Predominantly Roman Catholic (86%)
Currency: The American Dollar is the official currency in El Salvador. Although some prices are still quoted in the Salvadorean Colon, payment is expected in dollars. The exchange rate is fixed at US$1.00 = 8.75 Salvadorean Colón.
Major political parties: Farabundo Marti National Liberation Front (FMLN), Nationalist Republican Alliance (ARENA), National Conciliation Party (PCN), Christian Democratic Party (PDC). The recently formed GANA Party is an offshoot of ARENA.
Government: El Salvador has a republican system of government consisting of 3 separate and independent branches: the Executive Branch, headed by the President; the Legislative Branch; and the Judicial Branch headed by the Supreme Court.
Head of State: President Carlos Mauricio Funes Cartagena sworn in 1 June 2009.
Prime Minister/Premier: Not applicable
Foreign Minister: Hugo Martinez
Membership of international groups/organisations: El Salvador is a member of the United Nations and several of its specialised agencies; the Organisation of American States (OAS), the Central American Common Market (CACM), The Central American Parliament (PARLACEN) and the Central American Integration System (SICA) whose General Secretariat is based in El Salvador. El Salvador has also been chosen as for the Headquarters of the Puebla-Panama Plan (PPP). It actively participates in the Central American Security Commission (CASC) which seeks to promote regional arms control. El Salvador is a member of the World Trade Organisation (WTO) and is pursuing regional free trade agreements. El Salvador has joined its 6 Central American neighbours in signing the Alliance for Sustainable Development known as the Conjunta Centro-America – USA or CONCAUSA to promote sustainable economic development in the region. El Salvador was the first Central American country to ratify the Central American Free Trade Agreement (CAFTA) with the USA on 18 December 2004. Together with its neighbours, El Salvador has successfully negotiated a Political Dialogue and Co-operation Agreement with the EU, which was signed in Rome on 15 December 2004. El Salvador was one of the first members to join the International Atomic Energy Agency (IAEA) in 1957.
In El Salvador the quality of and access to healthcare are directly tied to income levels. Adequate health care is available to those able to pay the high cost. Health care for the urban and rural poor is limited.
Health services are not readily accessible to a majority of the population. In the more isolated regions of El Salvador, there are almost no physicians. Government clinics often lack adequate personnel, equipment and medicines.
Life expectancy: Male: 70.16 years, female 76.87 years (2011 est.)
Infant mortality rate: Male 22.3693 deaths/1,000 live births, female 18.15 deaths/1,000 live briths (2011 est.)
Nominal GDP: US$ 21.2 billion (2010)
Nominal GDP per head: US$ 3,618 (2010)
Annual growth: 0.7% (2010 CIA World Factbook)
Inflation: 1.2% (2010 est CIA World Factbook)
Major industries: Food processing, beverages, petroleum, chemicals fertilizer, textiles.
Export partners: US 43.5%, Guatemala 14.2%, Honduras 13.6%, Nicaragua 5.6% (2011 CIA world
factbook)
Import partners: US 32.1%, Guatemala, 11.5%, Mexico 8.2%, , China 4.8% (2011 CIA world factbook)
El Salvador's economy has undergone a transformation, moving from an agricultural economy, centred around coffee production, to a largely services-based economy focusing on commerce and financial services. In the past 10 years manufacturing has also grown, thanks mainly to the development of the industries dealing with offshore assembly for re-export. Inflation is increasing. Economic growth is forecast to decline in 2009 due to the global slowdown and to El Salvador's dependence on US exports and remittances from the US. El Salvador leads the region in remittances per capita with income equivalent to nearly all export income.
Salvadorian authorities are aware that it is not convenient for the country to have an excessive dependence on remittances and the US market. The deterioration of the fiscal situation is now the main source of macroeconomic concern. The Government is now depending on foreign assistance loans to fill its budgetary gaps.
300-600 El Salvador forms part of the Mayan Empire.
1524 Spanish adventurer Pedro de Alvarado conquers El Salvador.
1540 Indigenous resistance finally crushed and El Salvador becomes a Spanish colony.
1821 El Salvador gains independence from Spain but joins the Mexican empire.
1823 El Salvador becomes part of the United Provinces of Central America, which also encompass Costa Rica, Guatemala, Honduras and Nicaragua.
1840 El Salvador becomes fully independent following the dissolution of the United Provinces of Central America.
1859 President Gerardo Barrios introduces coffee growing.
1932 Some 30,000 are killed during the suppression of a peasant uprising led by Agustine Farabundo Marti. Right-wing National Conciliation Party (PCN) comes to power in the wake of a military coup.
1969 On 14 July war broke out on the Honduras-El Salvador border ostensibly caused by a disputed result in a soccer match between the 2 countries. After 3 days, around 2,000 deaths and a complete rupture of diplomatic relations, the Organisation of American States (OAS) negotiated a cease-fire.
Only in 1992 did both sides accept an International Court of Justice ruling demarcating the border in its current location.
1977 Guerrilla activities by the left-wing Farabundo Marti National Liberation Front (FMLN) intensify amidst reports of increased human rights violations by government troops and death squads. General Carlos Romero elected President.
1979-81 Around 30,000 people are killed by army-backed right-wing death squads.
1979 General Romero ousted in coup by reformist officers who install a military- civilian junta, but this fails to curb army backed political violence.
1980 Archbishop of San Salvador and human rights campaigner Oscar Romero assassinated; Jose Napoleon Duarte becomes the first civilian president since 1931.
1981 France and Mexico recognise the FMLN as a legitimate political force but the US continues to assist the Salvadorian Government whose army continues to back right-wing death squads.
1982 Extreme right-wing National Republican Alliance (ARENA) wins parliamentary elections, held in an atmosphere of considerable iolence. Duarte wins presidential election. Duarte begins quest for negotiated settlement with FMLN.
1989 FMLN attacks intensify; another ARENA candidate, Alfredo Cristiani, voted president in elections widely believed to have been rigged.
1992 Government and FMLN sign United Nations sponsored peace accord; FMLN recognised as political party.
1993 Government declares amnesty for those implicated by UN-sponsored commission on human rights atrocities.
1994 ARENA candidate Armando Calderon Sol elected president.
1997 FMLN makes good progress in parliamentary elections; leftist Hector Silva elected Mayor of San Salvador.
1999 ARENA candidate Francisco Flores beats former guerrilla Facundo Guardado in presidential election.
2001 January, February – massive earthquakes kill 1,200 people and leave a million homeless.
2004 21 March Presidential Elections Antonio Saca of the ARENA party wins in the first round with 57.51% of the votes (a second round not therefore being required). The main opposition FMLN party, led by Schafik Handal, trailed at 35.9%
2004 1 June inauguration of new Salvadorean President Elias Antonio Saca.
2006 (24 January), Schafik Handel, the 75-year old leader of the opposition FMLN party dies of a heart attack.
2006 (17 March), Violeta de Menjivar from the FMLN party was declared the winner of the San Salvador Mayoral election, the first woman to hold the post.
2009 (18 January), FMLN win 35 seats in the legislative elections. The governing ARENA party lose 3 seats, but Norman Quijano wins the San Salvador mayoral election, the first time in 12 years a ARENA candidate has held the post.
2009 (15 March) Maurico Funes of the left-wing FMLN party emerged victorious in the largely peaceful and free Presidential elections. Funes garnered 51.3% of the vote compared with 48.3% for the governing party's candidate, RodrigoÁvila
2009 (1 June) Maurico Funes sworn in as President. One of Funes' first acts as President was to restore diplomatic ties with Cuba, thereby officially re-establishing relations broken off since 1961.
BBC News Country Timeline: El Salvador (http://news.bbc.co.uk/1/hi/world/americas/country_profiles/1220818.stm)
Relations with neighbours
In July 1969, El Salvador and Honduras fought the 100-hour Soccer War over disputed border areas and friction resulting from the 300,000 Salvadoreans who had emigrated to Honduras in search of land and employment. The catalyst was nationalistic feelings aroused by a series of soccer matches between the 2 countries. The 2 countries formally signed a peace treaty on 30 October 1980 which put the border dispute before the International Court of Justice (ICJ). In September 1992 the Court issued a 400-page ruling awarding much of the disputed land to Honduras.
Alleged Salvadorean refusal to give effect to the ICJ's judgement on the delimitation of the boundaries between the 2 countries, is an ongoing irritant and has led to Honduras raising the issue with the UN Security Council. In December 2003 the ICJ declined El Salvador's application for a revision of its 1992 ruling. El Salvador continues to claim tiny Conejo Island, not identified in the ICJ decision, off Honduras in the Gulf of Fonseca.
Relations with the international community
See Membership of International Organisations above.
Moves towards regional economic integration in Central America are continuing. During the early part of 2004, the five Central American countries concluded negotiations with the USA on the Central American Free Trade Agreement (CAFTA). Known in Spanish as the TLC (Tratado de Libre Comercio), the agreement was signed by El Salvador, Guatemala, Honduras, Nicaragua, Costa Rica and the Dominican Republic. El Salvador was the first country to ratify the agreement (18 December 2004), followed by Honduras (3 March 2005), Guatemala (10 March 2005) and Dominican Republic and Nicaragua in the Autumn of 2005. This leaves Costa Rica as the only country still to ratify. Violent protests greeted ratification in Honduras and Guatemala. During 2004 and early 2005 several Central American countries signed bilateral border agreements to simplify customs procedures for goods (and tourists) passing from one country to another. El Salvador has also strengthened its ties with the Northern Triangle economies (Guatemala and Honduras) by eliminating trade barriers and improving custom processes. In May 2010 El Salvador and Central America signed an Association Agreement with the European Union.
Relations with the UK
In May 2011 the Foreign Secretary announced that a new British Embassy would be opening in El Salvador. The Embassy is due to open in 2012. Until then HM Ambassador to Guatemala is accredited as non-resident Ambassador to El Salvador.
Recent inward visits
-- February 2008: Minister for Environment Carlos José Guerrero Contreras visited to develop relations between UK and El Salvador in the field of climate change.
-- January 2010: Minister of Environment, Herman Rosa Chavez visited the UK and met with members of the Government, media and think tank representatives.
-- October 2011: A delegation of El Salvadoran parliamentarians visited the UK and met with NGOs and climate change representatives, sponsored by the Inter-Parliamentary Union (IPU).
-- November 2011: Foreign Minister Hugo Roger Martínez and Minister for Environment Herman Rosa Chávez visited London to take place in a SICA Forum, co-hosted by the Foreign and Commonwealth Office.
Recent outward visits
A delegation of the Inter-Parliamentary Union representing both House of Commons and House of Lords visited in June 2006. The Foreign and Commonwealth Office Director Americas visited in December 2011 and launched UK trade initiatives in El Salvador.
The smallest country in Central America, El Salvador is bordered by Honduras to the north and east and by Guatemala to the west. It has a 307km coastline on the Pacific and is the only country in the region not to have a Caribbean shore. Known as the land of volcanoes – with the attendant seismic activity – the terrain is mountainous with a narrow coastal belt and central plateau. In the west of the country, the Santa Ana volcano is active.
The main UK investors are Shell, Unilever and HSBC. In 2009 UK exports to El Salvador amounted to £13 million. This comprised mainly chemicals and related products, general machinery and transport equipment, plastics, inorganic chemicals and dairy products (Salvadorian Central Bank of Reserve).
During the same period, El Salvador exported £5 million worth of goods to the UK. These comprised articles of apparel and clothing, coffee, tea, cocoa, spices, plastics, clothing and beverages(Salvadorian Central Bank of Reserve).
UK Trade & Investment Country Profile: El Salvador (http://www.uktradeinvest.gov.uk/ukti/el_salvador)
The UK provides aid to El Salvador through the multilateral agencies, in particular the EU and the InterAmerican Development Bank (IADB).
UK emergency relief contributions totalled £1.6 million as part of the international effort following the major earthquakes in El Salvador in January and February 2001
The EU provided a package of €4m of assistance to the region, including El Salvador, following the devastating rains of 2011 caused by Tropical Depression 12-E.
In 2010 the British Embassy in Guatemala assisted the visit of the Salvadorian Minister to the UK and supported a training scheme for his team focusing on climate change. The Embassy has also supported a programmed aimed at reinstating former gang members into society, and is currently supporting a programme of community policing training.
For more information on the current projects being funded by the UK in El Salvador, visit the British Embassy Guatemala City project pages. (http://ukinguatemala.fco.gov.uk/en/about-us/working-with-guatemala/development-assistance/)
El Salvador is a democratic republic governed by a President and an 84-member unicameral Legislative Assembly. The President is elected by universal suffrage and serves for a 5-year term by absolute majority vote. A second round run-off is required in the event that no candidate receives more than 50% of the first round vote. Members of the assembly, also elected by universal suffrage, serve for 3-year terms. The country has an independent judiciary and Supreme Court.
At the close of 1989, an end to the civil war seemed remote. Yet in April 1990, representatives of both the FMLN and the government, under the chairmanship of the UN, met and talked in Geneva in the first of a series of negotiations that would lead to peace. A lengthy and problem-ridden negotiating process resulted in a UN-brokered agreement, the Chapultepec Accords, signed on 16 January 1992, followed on 1 February by a formal cease-fire. On 15 December 1992, the day the FMLN registered as a formal political party, the civil war was formally ended. National elections took place in March 1994. The 3 major contending parties were ARENA, the FMLN and the PDC. In the first round of voting in the presidential elections, these parties gained 49%, 25% and 16% of the votes cast, respectively. Following a run off contest in April, Armando Calderon Sol, the ARENA candidate was elected President with 68.2% of the votes cast and was sworn in as President on 1 June 1994. ARENA candidate Francisco Guillermo Flores Perez became president in 1999 after beating former guerrilla Facundo Guardado. The last Presidential elections took place on 21 March 2004. Antonio Saca of the ruling ARENA party won by an overwhelming majority with 57.51% of the vote. The main opposition FMLN party, trailed with 35.9%. The other 2 contending parties - PDC-PDU Coalition and PCN failed to secure the 3% required to retain their legitimacy as political parties. Elections for the Legislative Assembly took place in March 2006. The governing ARENA party won 34 of the 84 seats, whilst the leftist FMLN won 32.
On 24 January 2006, Schafik Handel, the 75-year old leader of the opposition FMLN party died of a heart attack.
Elections for the Legislative Assembly took place in January 2009. The governing ARENA party won 32of the 84 seats, whilst the leftist FMLN won 35.
The Presidential election on 15 March 2009 was won by Mauricio Funes, of the FMLN party, in a closely run contest. Funes secured just over 51% of the vote, whilst Rodrigo Avila, candidate for the governing ARENA party, gained approximately 48% of the vote.
Maurico Funes was sworn in on 1 June 2009 as the first President from the leftist FMLN party since the signing of the Peace Accords in 1992. In his inauguration address Funes promised to restore diplomatic relations with Cuba and he announced the $474 million Anticrisis Plan, a set of measures meant to stabilise the Salvadoran economy and stimulate job creation.
Last Updated: January 2012
El Salvador Main Page Country Profiles Main Page
($) United States Dollar (USD)


You might have noticed that the back corners of our Indow window inserts have a piece missing. It's not really missing, it's designed that way. The cut out piece prevents the corner from buckling and creating gaps between the tubing and window frame. It's how we get the most insulated windows.
When the window inserts are pressed into place, there is compression all along the tubing. The corner piece of the frame is compressed from two different directions at once. To absorb that compression, the cutout allows the corner piece to rotate back into the window frame. The "corner brace" as we call it, gives the corner of the tube the rigidity it needs to spring back and allows the corners to be snug and tight without buckling.
The material you see exposed—the corner brace—is a smaller foam silicone tube that sits inside the larger silicone tube edging the acrylic panel. Our window inserts didn't start out that way.
We knew some part of our solid tubing surrounding the window inserts had to be removed in order for our compression system to work. We used to hand punch ¾" round dots from sheets of open cell foam and individually glue them into the corners. Someone would be sitting there with a round punch and a hammer and just whack, whack, whack… But those pieces would become discolored and lose their springiness over time.
Now we have them molded out of silicone, saving us production time and giving us a more functional and durable solution. We simply cut out part of the really strong silicone tubing, pop the reinforcing corner brace inside, which allows a graceful collapse, but keeps it strong enough to fill in the corner without any gaps.
It's a simple and elegant solution to ensure our window inserts have the best compression and create the most insulated windows. Indow window inserts are always improving thanks to our innovative and creative team.
Hi Linda! Thanks for letting us know. We're reaching out to your dealer so they should be getting in touch with you soon. Please get in contact with us here if you don't hear anything: [email protected].


text:
Q: Unlock/Lock device using DevicePolicyManager I am trying to make an app that automatically locks the screen to force it into sleep mode and reactivated it / unlock it at a specific time
I've managed to lock the screen using the DevicePolicyManager and making my app device admin,
policies.xml
    <?xml version= "1.0" encoding= "utf-8" ?>
<device-admin xmlns:android="http://schemas.android.com/apk/res/android" >
    <uses-policies>
        <force-lock />
    </uses-policies>
</device-admin>

to lock the screen i'm using a button
     DevicePolicyManager deviceManger ;
public void lockPhone (View view) {
      deviceManger.lockNow() ;
    }

I am using an android TV box , the screen gets locked and goes into idle mode .
How can I unlock it again programmatically without pressing the power button on the remote.

redpajama_set_name: RedPajamaStackExchange


text:
Channel 5 current affairs show The Wright Stuff to be renamed Jeremy Vine when new host takes over
News diary 13-19 August: Imran Khan to be sworn in as Prime Minister of Pakistan and North and South Korean officials to meet
Beautician wins complaint against Mail on Sunday over 'cosmetic cowboy' claims
A beautician has won a complaint against the Mail on Sunday over an article investigating the rise of treatments being carried out by unqualified practitioners, calling it "the curse of the cosmetic cowboys".
The article, headlined "You've got so many lines you'll end up like Gordon Ramsay", was published in the newspaper on 31 December last year and online a day earlier.
Halifax Courier's failure to protect source led to her being sacked from shop job, IPSO finds
Report charts UK press coverage of trans issues becoming more respectful yet 'heated'
UK editors reject pleas to outlaw discrimination against ethnic and religious groups in IPSO code review
It reported on an investigation by the newspaper into cosmetic treatments carried out by "rogue beauticians" doing "dangerous and illegal procedures".
The article said the investigation followed a "shocking rise in cases of botched treatments".
Beautician Danielle Hindley was named and pictured in the article as a case study after an undercover journalist booked a "plasma skin tightening" appointment with her.
It reported Hindley had told the journalist that "nothing could go wrong, saying it was 'one of the easiest treatments I have ever learnt to do'", and pictured a former client of hers who approached the newspaper with "swollen eyes" and burn marks.
Hindley complained to the Independent Press Standards Organisation, denying she was a "rogue beautician" or "cosmetic cowboy".
She said including her details in the context of the article was damaging to her professional reputation and significantly misleading.
Hindley said she was acting within the law and denied any wrongdoing in relation to the reporter or her former client, who had been told the risks of the treatment, IPSO said.
The Mail on Sunday did not accept a breach of the code, telling IPSO there was no suggestion that all the allegations made about beauticians in the main article related to Hindley.
However it offered to publish a clarification to say Hindley is a trained beautician who was legally qualified to carry out the plasma treatment.
IPSO found that the newspaper had not offered sufficient basis for its claim that Hindley had acted improperly or recklessly and upheld a breach of Clause 1 (accuracy).
The Mail on Sunday has now published a fuller correction, which also appears at the top of the amended article online, where all references to Hindley have been removed.
The correction, which noted IPSO had upheld a complaint against the title, said: "In a previous version of this article we suggested that Danielle Hindley, who administers plasma skin tightening treatment, was a 'rogue beautician' and a 'cosmetic cowboy'.
"We have been asked to confirm, that Ms Hindley is a trained beautician who is legally entitled to carry out the plasma treatment described. We did not have a basis to suggest that Ms Hindley had 'botched' treatments, as implied by the article.
"The general references to 'cosmetic cowboys', 'rogue beauticians' and 'illegal procedures' do not apply to Ms Hindley and we are happy to make that clear.
"We also published a photograph of a former client of Ms Hindley, which said that they had received plasma skin lightening treatment. This was an error. In fact, Ms Hindley does not administer any treatments which lighten the skin."
The newspaper defended its use of a hidden camera within Hindley's home by an undercover journalist due to the "great public interest in exposing dangers", and the small amount of information obtained through subterfuge that was published.
IPSO agreed and did not find a breach of Clause 10 (clandestine devices and subterfuge).
It also cleared the newspaper of a breach of Clause 2 (privacy), as the undercover reporter only went in areas of Hindley's home that were accessible to clients, and the footage had captured her professional life, not personal, as her home was her place of work.
Read the full IPSO ruling here.
Mail on Sunday pays damages to beautician wrongly named in 'cosmetic cowboy' article
British Journalism Awards 2019 finalists revealed: 'Bravery is the quality that shines through'
External review of IPSO finds press regulator is independent, effective and largely compliant with Leveson
IPSO third-party complaints on climate change 'empower bullies and curb press freedom'
IPSO rulings
1 thought on "Beautician wins complaint against Mail on Sunday over 'cosmetic cowboy' claims"
Ohhh, It's really terrible to be this cosmetologist. This person got really bad image in this publication


text:
THE TIMES DIARY
Stage coach to Downton
Patrick Kidd
Friday January 14 2022, 12.00pm, The Times
The actress Elizabeth McGovern made an early impact on Hollywood with an Oscar nomination for her role in Milos Forman's Ragtime. "This was what, 19, 20?" a reporter asked her during an interview for this week's The Stage. "Just to be clear," McGovern replied, half-sternly. "It was at the age of 19, 20, not the year 1920." McGovern then focused her career on the stage, which benefited her when she later appeared in Downton Abbey.
"I don't think I could have held my own in that calibre of cast if I hadn't spent a lot of time doing theatre," she says. McGovern found the stage experience rewarding though says that at first directors made her do things she found "unnatural". This is


As undoubtedly one of my very favourite bands, I'm always pleased to hear new Band of Horses touring or album release news. So, today was a good Tuesday! Because I heard both.
As it turns out, the Sup Pop alt-rockers announced their upcoming release Mirage Rock this morning, which will hit the shelves on September 17th along with a short UK tour to boot. Mirage Rock is the follow-up to 2010's Infinite Arms, the band's hesitantly received third album that featured a handful of attractive rock numbers, as well as another handful of forgettables. Trust me, this has never been easy to admit - seeing as my obsession with their twang-filled Americana alt-rock stands in the way - but the album simply wasn't extraordinary. Save for a few toe-tapping singles like "Laredo" and "On My Way Back Home", I've had to rely on their genius first two albums (the triumphant-sounding Everything All The Time and Cease to Begin) for the majestic Southern-rock anthems I've spent years swooning to.
Another Band of Horses disappointment? Sadly, theirs was the only concert I've ever missed in my life. I had tickets to it, something came up, I ran late...and missed their set entirely. Heartbreaking! Fingers crossed that never happens again and that the newest album doesn't leave me continuing to hit repeat on their debut and sophomore releases.
Based on this track, as well as the fact that the album is Glyn Johns produced (studio guru behind Bob Dylan, the Beatles, Eric Clapton, The Who, etc. albums), I predict nothing but acclaim, a rustic-sounding autumn and re-invigorated love for their timeless rock goodness.


Karachi : Standard Chartered under its Diversity & Inclusion platform joined hands with British Deputy High Commission and celebrated International Women's Day.
role models to talk about their leadership and professional development journey to them.
Chartered for an event which supports and engages students who are the CEOs and leaders of the future.