Class: AutoC::TreeMap

Inherits:

Collection

• Object
• Code
• Type
• Collection
• AutoC::TreeMap

Includes:

Maps

Defined in:

lib/autoc/collection/tree_map.rb

Overview

TreeMap< K ⇒ E > is a tree-based ordered random access container holding unique keys with each key having an element bound to it.

TreeMap is backed by TreeSet container.

The collection’s C++ counterpart is std::map<> template class.

Generated C interface

Collection management

void typeCopy(Type * dst, Type * src)	Create a new map dst filled with the contents of src. A copy operation is performed on all keys and values in src. NOTE: Previous contents of dst is overwritten.
void typeCtor(Type * self)	Create a new empty map self. NOTE: Previous contents of self is overwritten.
void typeDtor(Type * self)	Destroy map self. Stored keys and values are destroyed as well by calling the respective destructors.
int typeEqual(Type * lt, Type * rt)	Return non-zero value if maps lt and rt are considered equal by contents and zero value otherwise.
size_t typeIdentify(Type * self)	Return hash code for map self.

Basic operations

int typeContainsKey(Type * self, K key)	Return non-zero value if map self contains an entry with a key considered equal to the key key and zero value otherwise.
int typeEmpty(Type * self)	Return non-zero value if map self contains no entries and zero value otherwise.
E typeGet(Type * self, K key)	Return a copy of the element in self bound to a key which is considered equal to the key key. WARNING: self must contain such key otherwise the behavior is undefined. See typeContainsKey().
E typePeekLowestElement(Type * self)	Return a copy of an element bound to the lowest key in self. WARNING: self must not be empty otherwise the behavior is undefined. See typeEmpty().
K typePeekLowestKey(Type * self)	Return a copy of the lowest key in self. WARNING: self must not be empty otherwise the behavior is undefined. See typeEmpty().
E typePeekHighestElement(Type * self)	Return a copy of an element bound to the highest key in self. WARNING: self must not be empty otherwise the behavior is undefined. See typeEmpty().
K typePeekHighestKey(Type * self)	Return a copy of the highest key in self. WARNING: self must not be empty otherwise the behavior is undefined. See typeEmpty().
void typePurge(Type * self)	Remove and destroy all keys and elements stored in self.
int typePut(Type * self, K key, E value)	Put a copy of the element value bound to a copy of the key key into self only if there is no such key in self which is considered equal to key. Return non-zero value on successful put and zero value otherwise.
int typeReplace(Type * self, K key, E value)	If self contains a key which is considered equal to the key key, remove and destroy that key along with an element bound to it and put a new pair built of the copies of key and value, otherwise no nothing. Return non-zero value if the replacement was actually performed and zero value otherwise.
int typeRemove(Type * self, K key)	Remove and destroy a key which is considered equal to the key key. Destroy an element bound to that key. Return non-zero value on successful key/element pair removal and zero value otherwise.
size_t typeSize(Type * self)	Return number of key/element pairs stored in self.

Iteration

void itCtor(IteratorType * it, Type * self)	Create a new ascending iterator it on map self. See itCtorEx(). NOTE: Previous contents of it is overwritten.
void itCtorEx(IteratorType * it, Type * self, int ascending)	Create a new iterator it on map self. Non-zero value of ascending specifies an ascending (lowest to highest key traversal) iterator, zero value specifies a descending (highest to lowest key traversal) iterator. NOTE: Previous contents of it is overwritten.
int itMove(IteratorType * it)	Advance iterator position of it and return non-zero value if new position is valid and zero value otherwise.
K itGetKey(IteratorType * it)	Return a copy of the key from a key/value pair pointed to by the iterator it. WARNING: current position must be valid otherwise the behavior is undefined. See itMove().
E itGetElement(IteratorType * it)	Return a copy of the element from a key/element pair pointed to by the iterator it. WARNING: current position must be valid otherwise the behavior is undefined. See itMove().
E itGet(IteratorType * it)	Alias for itGetElement().

Instance Attribute Summary

• #key ⇒ Object readonly

  Returns the value of attribute key.

Attributes inherited from Collection

#element, #it_ref

Attributes inherited from Type

#type, #type_ref

Instance Method Summary

• #==(other) ⇒ Object (also: #eql?)
• #comparable? ⇒ Boolean
• #copyable? ⇒ Boolean
• #entities ⇒ Object
• #hash ⇒ Object
• #hashable? ⇒ Boolean
• #initialize(type, key_type, value_type, visibility = :public) ⇒ TreeMap constructor

  A new instance of TreeMap.

• #write_impls(stream, define) ⇒ Object
• #write_intf_decls(stream, declare, define) ⇒ Object
• #write_intf_types(stream) ⇒ Object

Methods inherited from Collection

#constructible?, #destructible?, #initializable?

Methods inherited from Type

#abort, #assert, #calloc, coerce, #constructible?, #destructible?, #extern, #free, #initializable?, #inline, #malloc, #method_missing, #orderable?, #prefix, #private?, #public?, #sortable?, #static, #static?, #write_decls, #write_defs, #write_intf

Methods inherited from Code

#attach, #priority, #source_size, #write_decls, #write_defs, #write_intf

Constructor Details

#initialize(type, key_type, value_type, visibility = :public) ⇒ TreeMap

Returns a new instance of TreeMap.

# File 'lib/autoc/collection/tree_map.rb', line 181

def initialize(type, key_type, value_type, visibility = :public)
  super(type, value_type, visibility)
  @key = Type.coerce(key_type)
  @entry = UserDefinedType.new(:type => entry, :identify => entryIdentify, :equal => entryEqual, :less => entryLess, :copy => entryCopy, :dtor => entryDtor)
  @set = TreeSet.new(set, @entry, :static)
  element_requirement(value)
  key_requirement(key)
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class AutoC::Type

Instance Attribute Details

#key ⇒ Object (readonly)

Returns the value of attribute key.

# File 'lib/autoc/collection/tree_map.rb', line 169

def key
  @key
end

Instance Method Details

#==(other) ⇒ Object Also known as: eql?

# File 'lib/autoc/collection/tree_map.rb', line 175

def ==(other) super && key == other.key end

#comparable? ⇒ Boolean

Returns:

• (Boolean)

# File 'lib/autoc/collection/tree_map.rb', line 192

def comparable?; super && key.comparable? end

#copyable? ⇒ Boolean

Returns:

• (Boolean)

# File 'lib/autoc/collection/tree_map.rb', line 190

def copyable?; super && key.copyable? end

#entities ⇒ Object

# File 'lib/autoc/collection/tree_map.rb', line 179

def entities; super << key end

#hash ⇒ Object

# File 'lib/autoc/collection/tree_map.rb', line 173

def hash; super ^ key.hash end

#hashable? ⇒ Boolean

Returns:

• (Boolean)

# File 'lib/autoc/collection/tree_map.rb', line 194

def hashable?; super && key.hashable? end

#write_impls(stream, define) ⇒ Object

# File 'lib/autoc/collection/tree_map.rb', line 231

def write_impls(stream, define)
  super
  stream << %$
    #define #{validValue} 1
    #define #{validKey} 2
    #define #{ownedValue} 4
    #define #{ownedKey} 8
    static #{@entry.type} #{entryKeyOnlyRef}(#{key.type_ref} key) {
      #{@entry.type} entry;
      entry.key = *key;
      entry.flags = #{validKey};
      return entry;
    }
    static #{@entry.type} #{entryKeyValueRef}(#{key.type_ref} key, #{value.type_ref} value) {
      #{@entry.type} entry;
      entry.key = *key;
      entry.value = *value;
      entry.flags = (#{validKey} | #{validValue});
      return entry;
    }
    #define #{entryEqual}(lt, rt) #{entryEqualRef}(&lt, &rt)
    static int #{entryEqualRef}(#{@entry.type}* lt, #{@entry.type}* rt) {
      return #{key.equal("lt->key", "rt->key")};
    }
    #define #{entryLess}(lt, rt) #{entryLessRef}(&lt, &rt)
    static int #{entryLessRef}(#{@entry.type}* lt, #{@entry.type}* rt) {
      return #{key.less("lt->key", "rt->key")};
    }
    #define #{entryIdentify}(obj) #{entryIdentifyRef}(&obj)
    static size_t #{entryIdentifyRef}(#{@entry.type}* entry) {
      return #{key.identify("entry->key")};
    }
    #define #{entryCopy}(dst, src) #{entryCopyRef}(&dst, &src)
    static void #{entryCopyRef}(#{@entry.type_ref} dst, #{@entry.type_ref} src) {
      #{assert}(src->flags & #{validKey});
      dst->flags = (#{validKey} | #{ownedKey});
      #{key.copy("dst->key", "src->key")};
      if(src->flags & #{validValue}) {
        dst->flags |= (#{validValue} | #{ownedValue});
        #{value.copy("dst->value", "src->value")};
      }
    }
    #define #{entryDtor}(obj) #{entryDtorRef}(&obj)
    static void #{entryDtorRef}(#{@entry.type}* entry) {
      #{assert}(entry->flags & #{validKey});
      if(entry->flags & #{ownedKey}) #{key.dtor("entry->key")};
      if(entry->flags & #{validValue} && entry->flags & #{ownedValue}) #{value.dtor("entry->value")};
    }
    static #{@entry.type_ref} #{itGetEntryRef}(#{it_ref});
    static int #{containsAllOf}(#{type_ref} self, #{type_ref} other) {
      #{it} it;
      #{itCtor}(&it, self);
      while(#{itMove}(&it)) {
        int found = 0;
        #{@entry.type}* e = #{itGetEntryRef}(&it);
        if(#{containsKey}(other, e->key)) {
          #{value.type} other_value = #{get}(other, e->key);
          found = #{value.equal("e->value", "other_value")};
          #{value.dtor("other_value")};
        }
        if(!found) return 0;
      }
      return 1;
    }
  $
  @set.write_intf_decls(stream, static, inline)
  @set.write_impls(stream, static)
  stream << %$
    #{define} #{ctor.definition} {
      #{assert}(self);
      #{@set.ctor}(&self->entries);
    }
    #{define} #{dtor.definition} {
      #{assert}(self);
      #{@set.dtor}(&self->entries);
    }
    static int #{putEntryRef}(#{type_ref} self, #{@entry.type_ref} entry) {
      int absent;
      #{assert}(self);
      #{assert}(entry);
      absent = !#{containsKey}(self, entry->key);
      if(absent) #{@set.put}(&self->entries, *entry);
      return absent;
    }
    #{define} #{copy.definition} {
      #{it} it;
      #{assert}(src);
      #{assert}(dst);
      #{ctor}(dst);
      #{itCtor}(&it, src);
      while(#{itMove}(&it)) {
        #{@entry.type}* e = #{itGetEntryRef}(&it);
        #{putEntryRef}(dst, e);
      }
    }
    #{define} #{equal.definition} {
      #{assert}(lt);
      #{assert}(rt);
      return #{size}(lt) == #{size}(rt) && #{containsAllOf}(lt, rt) && #{containsAllOf}(rt, lt);
    }
    #{define} #{identify.definition} {
      #{assert}(self);
      return #{@set.identify}(&self->entries); /* TODO : make use of the values' hashes */
    }
    #{define} void #{purge}(#{type_ref} self) {
      #{assert}(self);
      #{@set.purge}(&self->entries);
    }
    #{define} size_t #{size}(#{type_ref} self) {
      #{assert}(self);
      return #{@set.size}(&self->entries);
    }
    #{define} int #{containsKey}(#{type_ref} self, #{key.type} key) {
      int result;
      #{@entry.type} entry;
      #{assert}(self);
      result = #{@set.contains}(&self->entries, entry = #{entryKeyOnlyRef}(&key));
      #{@entry.dtor("entry")};
      return result;
    }
    #{define} #{value.type} #{get}(#{type_ref} self, #{key.type} key) {
      #{value.type} result;
      #{@entry.type} entry, existing_entry;
      #{assert}(self);
      #{assert}(#{containsKey}(self, key));
      existing_entry = #{@set.get}(&self->entries, entry = #{entryKeyOnlyRef}(&key));
      #{value.copy("result", "existing_entry.value")};
      #{@entry.dtor("existing_entry")};
      #{@entry.dtor("entry")};
      return result;
    }
    #{define} #{key.type} #{peekLowestKey}(#{type_ref} self) {
      #{key.type} result;
      #{@set.node}* node;
      #{assert}(self);
      #{assert}(!#{empty}(self));
      node = #{@set.lowestNode}(&self->entries);
      #{assert}(node);
      #{key.copy("result", "node->element.key")};
      return result;
    }
    #{define} #{value.type} #{peekLowestElement}(#{type_ref} self) {
      #{value.type} result;
      #{@set.node}* node;
      #{assert}(self);
      #{assert}(!#{empty}(self));
      node = #{@set.lowestNode}(&self->entries);
      #{assert}(node);
      #{element.copy("result", "node->element.value")};
      return result;
    }
    #{define} #{key.type} #{peekHighestKey}(#{type_ref} self) {
      #{key.type} result;
      #{@set.node}* node;
      #{assert}(self);
      #{assert}(!#{empty}(self));
      node = #{@set.highestNode}(&self->entries);
      #{assert}(node);
      #{key.copy("result", "node->element.key")};
      return result;
    }
    #{define} #{value.type} #{peekHighestElement}(#{type_ref} self) {
      #{value.type} result;
      #{@set.node}* node;
      #{assert}(self);
      #{assert}(!#{empty}(self));
      node = #{@set.highestNode}(&self->entries);
      #{assert}(node);
      #{element.copy("result", "node->element.value")};
      return result;
    }
    #{define} int #{put}(#{type_ref} self, #{key.type} key, #{value.type} value) {
      int result;
      #{@entry.type} entry;
      #{assert}(self);
      entry = #{entryKeyValueRef}(&key, &value);
      result = #{putEntryRef}(self, &entry);
      #{@entry.dtor("entry")};
      return result;
    }
    #{define} int #{replace}(#{type_ref} self, #{key.type} key, #{value.type} value) {
      int result;
      #{@entry.type} entry;
      #{assert}(self);
      entry = #{entryKeyValueRef}(&key, &value);
      result = #{@set.replace}(&self->entries, entry);
      #{@entry.dtor("entry")};
      return result;
    }
    #{define} int #{remove}(#{type_ref} self, #{key.type} key) {
      int result;
      #{@entry.type} entry;
      #{assert}(self);
      result = #{@set.remove}(&self->entries, entry = #{entryKeyOnlyRef}(&key));
      #{@entry.dtor("entry")};
      return result;
    }
    #{define} void #{itCtorEx}(#{it_ref} self, #{type_ref} map, int ascending) {
      #{assert}(self);
      #{assert}(map);
      #{@set.itCtorEx}(&self->it, &map->entries, ascending);
    }
    #{define} int #{itMove}(#{it_ref} self) {
      #{assert}(self);
      return #{@set.itMove}(&self->it);
    }
    #{define} #{key.type} #{itGetKey}(#{it_ref} self) {
      #{@entry.type_ref} e;
      #{key.type} key;
      #{assert}(self);
      e = #{itGetEntryRef}(self);
      #{key.copy("key", "e->key")};
      return key;
    }
    #{define} #{value.type} #{itGetElement}(#{it_ref} self) {
      #{@entry.type_ref} e;
      #{value.type} value;
      #{assert}(self);
      e = #{itGetEntryRef}(self);
      #{assert}(e->flags & #{validValue});
      #{value.copy("value", "e->value")};
      return value;
    }
    static #{@entry.type_ref} #{itGetEntryRef}(#{it_ref} self) {
      #{assert}(self);
      return #{@set.itGetRef}(&self->it);
    }
  $
end

#write_intf_decls(stream, declare, define) ⇒ Object

# File 'lib/autoc/collection/tree_map.rb', line 219

def write_intf_decls(stream, declare, define)
  super
  stream << %$
    #{declare} #{key.type} #{peekLowestKey}(#{type_ref});
    #{declare} #{value.type} #{peekLowestElement}(#{type_ref});
    #{declare} #{key.type} #{peekHighestKey}(#{type_ref});
    #{declare} #{value.type} #{peekHighestElement}(#{type_ref});
    #define #{itCtor}(self, type) #{itCtorEx}(self, type, 1)
    #{declare} void #{itCtorEx}(#{it_ref}, #{type_ref}, int);
  $
end

#write_intf_types(stream) ⇒ Object

# File 'lib/autoc/collection/tree_map.rb', line 196

def write_intf_types(stream)
  super
  stream << %$
    typedef struct #{@entry.type} #{@entry.type};
    struct #{@entry.type} {
      #{key.type} key;
      #{value.type} value;
      unsigned flags;
    };
  $
  @set.write_intf_types(stream)
  stream << %$
    typedef struct #{type} #{type};
    typedef struct #{it} #{it};
    struct #{type} {
      #{@set.type} entries;
    };
    struct #{it} {
      #{@set.it} it;
    };
  $
end