1

I understand that this may be a stupid question to some, but I've come to my wit's end trying to understand this condition: 

 if p ∈ (n, succ) then

I keep running across this in some pseudo code that I've been reading for the past 16 hours. I understand that '∈' typicaly symbolizes a set, such as 'p∈b' would make p an element of b, but how would I interpret 'p∈ (n, succ)'?

Full example

procedure n.Stabilize
    p = succ.GetPredecessor
    if p ∈ (n, succ) then
        succ = p
    end if
    succ.Notify n
end procedure

procedure n.Notify p
    if p ∈ (pred, n] then
        pred = p
    end if
end procedure

Note that the square bracket in 'if p ∈ (pred, n] then' is intended.

user100413
  • 11
  • 2
    Please add more context. For first glance, it seems it simply wants to say 'if $p\in\Bbb N$ then'. – Berci Oct 12 '13 at 10:49
  • It's from pseudo code of a distributed hash table, where each node needs to know both it's predecessor (p) and successor (succ). 'n' is the node in question. The function is trying to find if 'p' is the predecessor of 'n'. I'm on my phone right now, but ill post the full block of pseudo code if needed. – user100413 Oct 12 '13 at 10:59
  • @user100413 Please add the full block to the bottom of the question. Given your context, I suspect it should say if$p \in {\text{n},\text{succ}}$ then, i.e. with curly braces. – Lord_Farin Oct 12 '13 at 11:10
  • @Lord_Farin - code added – user100413 Oct 12 '13 at 11:41
  • Looks like we have some interval from pred to succ, then we adjust the endpoints when we execute these two procedures. Moving succ down to p or moving pred up to p, but keeping n inside the interval [pred,succ) ... ??? – GEdgar Oct 12 '13 at 12:19

1 Answers1

1

I'm not entirely sure that this answer is correct, but it seems reasonable and makes (some) intuitive sense.

Let us assume that we have some comparison method $\prec$ with respect to which we want to find successors and predecessors. For example, we could say that $p \prec n$ if $p$ "precedes" $n$.

So the predecessor of $n$ would be a $p$ such that $p \prec n$, and if for any $q$ we have $q \prec n$, then either $q \prec p$ or $q = p$ (more conveniently, $q \preceq p$). Similarly for successor (just flip all the $\prec$ to $\succ$).

Then I suspect that we are dealing with the so-called interval notation. This comprises the following definitions:

$\begin{align} &&&&[p,n] &:= \{q: p \preceq q \preceq n\} & [p,n)&:= \{q: p \preceq q \prec n\}\\ &&&&(p,n] &:= \{q: p \prec q \preceq n\} & (p,n)&:= \{q: p \prec q \prec n\} \end{align}$

With this definition, n.Stabilize is seen to check whether the predecessor of succ is n; if it is rather some p, then we need to update the successor of n to be p.

n.Notify p checks if p should be the predecessor of n; probably the interval (pred,n] (including n) is used because of the root node being its own predecessor.

I hope this continues to make some sense in the broader context in which your question arose.

Lord_Farin
  • 17,743