Heapsort in Arc

(def parent (i)
    (trunc (/ i 2)))

(def left (i)
    (* 2 i))

(def right (i)
    (+ 1 (* 2 i)))

(def elm (h i)
    (let ind (- i 1)
        h.ind))

(def setval (h i val)
    (= (h (- i 1)) val)
    h)

(def hswap (h i j)
    (= temp (elm h i))
    (setval h i (elm h j))
    (setval h j temp))

(def t-lgi (h idx (o curr))
    (if (empty idx)
        curr
        (t-lgi h (cdr idx) (if (no curr)
            (car idx)
            (> (elm h (car idx)) (elm h curr))
            (car idx)
            curr))))

(def largesti (h idx (o hsize (len h)))
    (t-lgi h (keep [>= hsize _] idx)))

(def max-heapify (h i (o hsize (len h)))
    (let largest
        (largesti h (list (left i) (right i) i) hsize)
        (when (~is i largest)
            (hswap h i largest)
            (max-heapify h largest hsize)))
      h)

(def build-max-heap (h (o hsize (len h)))
    (each x (rev:range 1 (trunc (/ hsize 2)))
        (max-heapify h x hsize))
    h)

(def heapsort (h)
    (hswap h 1 (len h))
     (each x (rev:range 2 (- (len h) 1))
        (max-heapify h 1 x)
        (hswap h 1 x))
      h)

;test
;(max-heapify '(16 4 10 14 7 9 3 2 8 1) 2)
;(heapsort '(16 14 10 8 7 9 3 2 4 1))

C# Expressions

One of the cooler features of c# 3.0 are expression trees. A quick intro can be found here .

Now the fact that you can compile a function at runtime means that you can build a dynamic language on top of Linq Expressions.

Here’s a simple dynamic “XML Language” written using Expression Trees.

Basically, the idea here is to have a one-to-one mapping between your XML expression and the Linq EXpressions themselves.

For example,
 

<Expression FunctionName="Constant" Type="System.String" Value="someval" />

would create an Linq Expression of type

 

Expression.Constant("someval",Type.GetType(string));

 

Here’s a related test for the mapping:

 

[TestMethod]
public void GetConstantTest()
{
XMLExpressionProvider expr = new XMLExpressionProvider();
XElement elem = expr.BuildConstant(typeof(int).ToString(), "1");
Assert.AreEqual("1", expr.GetConstant(elem));
}

 

and related implementations:

 

public XElement BuildConstant(string type, string value)
{
XElement elem = new XElement("Expression");
elem.Add(new XAttribute("FunctionName", "Constant"));
elem.Add(new XAttribute("Type", type));
elem.Add(new XAttribute("Value", value));

return elem;
}

public object GetConstant(XElement elem)
{
return elem.Attribute("Value").Value;
}


Binary operations can also be mapped similarly.

Here we’re creating a new Add Expression with the constants 1 and 2. This actually creates a xml representation for the Add Operation.

 

[TestMethod]
public void BuildExpressionTest()
{
XMLExpressionProvider expr = new XMLExpressionProvider();
XElement xelm = expr.BuildExpression("Add", new[] {
expr.BuildConstant(typeof(int).ToString(),"1"),
expr.BuildConstant(typeof(int).ToString(),"2")});
Assert.AreEqual(xelm.ToString(SaveOptions.DisableFormatting),
"<Expression FunctionName=\"Add\"><Expression FunctionName=\"Constant\" Type=\"System.Int32\" Value=\"1\" /><Expression FunctionName=\"Constant\" Type=\"System.Int32\" Value=\"2\" /></Expression>");
}


Basically the XML Represenation would look like

 

<Expression FunctionName="Add">
<Expression FunctionName="Constant" Type="System.Int32" Value="1" />
<Expression FunctionName="Constant" Type="System.Int32" Value="2" />
</Expression>


In the test below, we’re actually creating a XML Representation for a GreaterThan expression and executing it with different parameters.

 

[TestMethod]
public void ExpressionTest()
{
XMLExpressionProvider expr = new XMLExpressionProvider();
ParameterExpression p = Expression.Parameter(typeof(int), "x");
XElement elem = expr.BuildExpression("GreaterThan", new[] { expr.BuildConstant(typeof(int).ToString(), "5"), expr.BuildParameter(0) });
Expression expression= expr.ExpressionFromXElement(elem, new [] {p});
Expression<Func<int, bool>> e = Expression.Lambda<Func<int, bool>>(expression,new []{p});
Console.WriteLine(e.ToString());
Assert.IsTrue(e.Compile().Invoke(4));
Assert.IsFalse(e.Compile().Invoke(7));
}


The heart of the implementation lies in the method ExpressionFromXElement which is implemented as

 

public Expression ExpressionFromXElement(XElement elem, ParameterExpression [] p)
{

if (IsExpression(elem))
{

switch (GetFunctionName(elem))
{
case "Or":
return Expression.Or(ExpressionFromXElement(GetArguments(elem)[0], p), ExpressionFromXElement(GetArguments(elem)[1],p));
case "And":
return Expression.And(ExpressionFromXElement(GetArguments(elem)[0], p), ExpressionFromXElement(GetArguments(elem)[1], p));
case "LessThan":
return Expression.LessThan(ExpressionFromXElement(GetArguments(elem)[0], p), ExpressionFromXElement(GetArguments(elem)[1], p));
case "GreaterThan":
return Expression.GreaterThan(ExpressionFromXElement(GetArguments(elem)[0], p), ExpressionFromXElement(GetArguments(elem)[1], p));
case "Equal":
return Expression.Equal(ExpressionFromXElement(GetArguments(elem)[0], p), ExpressionFromXElement(GetArguments(elem)[1], p));
case "Condition":
return Expression.Condition(ExpressionFromXElement(GetArguments(elem)[0], p), ExpressionFromXElement(GetArguments(elem)[1], p), ExpressionFromXElement(GetArguments(elem)[2], p));
case "Parameter":
return p[Convert.ToInt32(elem.Attribute("Index").Value)];
case "Constant":
return Expression.Constant(((object)GetConstant(elem)),Type.GetType(elem.Attribute("Type").Value));
case "Member":
return Expression.PropertyOrField(ExpressionFromXElement(GetArguments(elem)[0], p), elem.Attribute("FieldName").Value);
case "IsEmptyOrNull":
return Expression.Or(
Expression.Equal(ExpressionFromXElement(GetArguments(elem)[0], p), Expression.Constant(String.Empty)),
Expression.Equal(ExpressionFromXElement(GetArguments(elem)[0], p), Expression.Constant(null)));
default: throw new Exception();
}
}
return null;
}

 

You can also do member accesses:

 

[TestMethod]
public void MemberAccessTest()
{
XMLExpressionProvider expr = new XMLExpressionProvider();
ParameterExpression p = Expression.Parameter(typeof(string), "str");
XElement elem = expr.BuildMemberExpr("Length", new []{expr.BuildParameter(0)});
Expression expression = expr.ExpressionFromXElement(elem, new[] { p });
var e = Expression.Lambda<Func<string, int>>(expression, new[] { p });
Console.WriteLine(e.ToString());
Assert.AreEqual(6, e.Compile().Invoke("string"));
Assert.AreEqual(3, e.Compile().Invoke("str"));
}

[TestMethod]
public void BuildMemberTest()
{
XMLExpressionProvider expr = new XMLExpressionProvider();
Assert.AreEqual("<Expression FunctionName=\"Member\" FieldName=\"MaxValue\"><Expression FunctionName=\"Parameter\" Index=\"0\" /></Expression>", expr.BuildMemberExpr("MaxValue", new []{expr.BuildParameter(0)} ).ToString(SaveOptions.DisableFormatting));
}


The examples given here should give you an idea of how it works and the possiblities that exist.

Another Primitive Obsession Solution

There are a few suggested ways to handle primitive obsession. Personally, I would prefer:


public class Validated
{
private string _value;
private Regex _regex = null;

public Validated(string pattern)
{
_regex = new Regex(pattern);
}

public bool IsValid(string value)
{
if (_regex.IsMatch(value))
return true;
return false;
}

public string Value
{
get { return _value; }
set
{
if (IsValid(value))
_value = value;
else throw new FormatException("Invalid format.");
}
}
}


And use it as:


Validated zip = new Validated(@"/^\d{5}([\-]\d{4})?$/");
Validated email = new Validated(@"^[\w-\.]+@([\w-]+\.)+[\w-]{2,4}$");
zip.Value = "74445";
email.Value = "example@yahoo.com";


Now if you think that this is not flexible enough to accommodate all cases, try this,


public class Validated
{
private string _value;
private Func<string, bool> IsValid;


public Validated(Func<string, bool> isValid)
{
this.IsValid = isValid;
}


public string Value
{
get { return _value; }
set
{
if (IsValid.Invoke(value))
_value = value;
else throw new FormatException("Invalid format.");
}
}
}


And use it as:

Validated zip = new Validated((z) => new Regex(@"/^\d{5}([\-]\d{4})?$/").IsMatch(z));
Validated email = new Validated((e) => new Regex(@"^[\w-\.]+@([\w-]+\.)+[\w-]{2,4}$").IsMatch(e));
zip.Value = "74445";
email.Value = "example@yahoo.com";