Three useless and sometimes dangerous data structures

(Part one of three or none)

Data structures are very important in Computer Science as well in many people professional carriers. So it might be strange to think of some data structures that are completely useless and will never be deployed anywhere at any time. But, the very exercise in itself, it’s a good way to look not only at the other side of the coin but also to the other-other side.

The first data structure has to deal with the uncertainty principle of Heisenberg and the very fact that measure can influence the phenomenon we’re inquiring and it can give us just one part of the picture while we’re not sure about the other.

The Heisenberg Tower.
This tower is a simple pile of items and we can push any object in it. But if we want to know the position (index) of any item, having the value we can’t, also knowing the index doesn’t help us getting the value. We’re going to represent any object internally with a POCO object:

public class Floor
{
   public Object Item  {get; set;}
   public int Index {get; set;} 
}

A simple pile of objects

The meaning is simple, you can store any object in the tower but we’re going to record its index with the item itself. In fact, the Add method allows us to create an ArrayList of Floor elements.

Internal structure

  private ArrayList _list = new ArrayList();
  private int _index = 0;
  public void Add(Object val)
  {
   _list.Add(new Floor() {Item = val, Index = _index});
   _index++;
  }

Before anyone complains no, it’s not provided any locking mechanism in order to prevent concurrency access to the internals of the class nor it has been thought to be thread safe!

Now we do have two simple methods that allow us to inquire whether an item is in the tower or some index exists. Both methods don’t deal simultaneously with position and value. Here is the HasValue method.

public bool HasValue(Object val)
  {
   return (from Floor f in _list
    where Compare(f.Item, val) == true
    select true).DefaultIfEmpty(false).FirstOrDefault();
  }

HasValue(v) method

HasIndex(i) Method

Compare is a method that allows you to compare any object to another, either through identity or equivalence.

Now let’s see what happens when we measure our structure, meaning that we try to remove an item. The item is simply removed from the tower but at the same time, the index is recalculated.

public bool Remove(Object val)
 {
  var result = false;
  var found = (
   from Floor f in _list
   where Compare(f.Item, val)select f).FirstOrDefault();
  if (found != null)
  {
   _list.Remove(found);
   Reset();
   result = true;
  }
  return result;
 }

Remove(v) method

So let’s see our method GetValue. It simply removes the item in order to get its index, then is added on top or bottom of the list and searched in the inner list by comparison. Of course, since the object compared is made of two elements, the item and its position, the search will produce always a null.

public Object GetValue(int index)
 {
  Object val = null;
  Floor found = (from Floor f in _list
   where f.Index == index
   select f).FirstOrDefault();
  if (Remove(found.Item))
  {
   _add(found.Index, found.Item);
   val = (from Floor f in _list
    where Compare(f.Item, found)select f.Item).DefaultIfEmpty(null).FirstOrDefault();
  }
  return val;
 }

GetValue(i) Method

The _add method deals with the quirks of being a one item list or the last element.

So, for the index is easy to get:

public int ? GetIndex(Object val)
 {
  int ? index = -1;
  Floor found = (from Floor f in _list
   where Compare(f.Item, val)select f).FirstOrDefault();
  if (found == null)
   return null;
  if (Remove(found.Item))
  {
   _add(found.Index, found.Item);
   index = (from Floor f in _list
    where Compare(f, found)select f.Index).DefaultIfEmpty(-1).FirstOrDefault();
   return (index == -1 ? null : index);
  }
  return null;
 }

The code is here, but a better functional approach has to come : https://github.com/FSharpItalia/Three_impossible_data_structures